master mind by c++; part 1 基盤プログラム

これから c++ プロジェクト実装の勉強がてら, master mind というゲームを解くプログラムを作成する様子を数回に分けてまとめたいと思います.
目標はなるべく標準で, かつモダンな実装です.

これからの全体的な流れ
master mind ( マスターマインド ) とは
用語
問題設定
全体の流れ
データコンテナの選定
全体像
policy
trial
コード全体
まとめ
他の記事

これからの全体的な流れ

今回のプロジェクトは下記の流れで行います.

解決したい問題の把握 --> 本稿
全体の処理フローの作成 --> 本稿
使用言語の決定 --> 今回はc++決めうち
データ型(データコンテナ)の決定 --> 本稿
まず最小限の動くコードの作成 --> 本稿
ビルドツールの整備(makefile, cmake)
単体テストの整備(問題なく実行されるか)
計測コードの整備(実行時間、探索回数の測定など)
機能の高度化と、単体テストの追加

作業順序の整合性に気をつけて作成しています. 例えば, ある機能を高速化/高度化するならば, その効果を確かめながら実装を行う必要があります( 本当に速くなったのか? 効率的になったのか? ). そのためには「計測」が重要であるため, 「計測」部分のコードの作成を「機能の高度化」の前に行います. また, 開発するにあたりコンパイル頻度もそれなりにあるのでビルドツールを整備することも重要です. そのために最小限動くコードを作成しておき, それを使いながらビルドツールを整えます.

master mind ( マスターマインド ) とは

今回は master mind というゲームを解くプログラムを作成します.

Wiki:
Online Game: Play Mastermind Online

隠されたピンの配列を当てるゲームです. プレイヤーはピンの配列を試し, それに応じたヒントをもらって隠されたピンの配列の候補を減らしていきます.
ヒントは

hit ヒット = 色と配置が合っているピンの数
blow ブロー = 色は合っているけど配置が違うピンの数

の2つが与えられます. ゲーム進行の図.

f:id:inarizuuuushi:20210619151455p:plain:w200

用語

記事やプログラムで用いる用語の整理

code コード ... ピンの配列
secret 秘密コード ... 隠されたピンの配列
guess 推測コード ... 試すピンの配列
trial 試行 ... ピン配列を試して, (hit, blow)の情報をもらうこと

問題設定

目標: なるべく少ない回数で秘密コードを当てる
入力: 問題設定(ピンの色、ピンの数、色の重複の有無), 試行ごとの(hit, blow)結果

全体の流れ

秘密コードの候補となるコード集合Sの取得
推論コードの候補集合Gの取得
policy: Gから一つ, 推論コードgを選択
trial: 推論コードgによる, コード集合Sの(hit, blow)を取得 ( ユーザーからの入力 )
秘密コード候補Sの更新
もしSの要素数が1になったらその要素が秘密コードであるため, それを出力して終了. そうでなければ2に戻る

初めに秘密コードの一覧を取得する必要があるのか(一覧を書き出さずに計算を進める方法もありそう)など, より改良はできそうですが最小限の動くコードを作れれば十分なため, 上記の流れをプログラムしてみます.

データコンテナの選定

これから, c++ のコードを書いていきます.
まずはデータコンテナに何を使用するかを検討しましょう.

コード (ピンの配列)

ピンの色は整数(int), その配列なのでarray か vector, ピンの個数は実行時のコマンドライン引数によって可変にしたいため, vectorを選択.

(hit, blow)

hit, blowは整数(int), そのペア(タプル)なのでpair<int, int>.

コード一覧

上記コード(vector)の集合を扱えれば良い. とりあえず, dequeでいいでしょ.

まとめ

クラスを作るほどでもないので, typedefで作成.

typedef std::vector<int>      Code;
typedef std::pair<int, int>   HitBlow;
typedef std::deque<Code>      CodeList;

追記今風はusingで作成.

using Code     = std::vector<int>;
using HitBlow  = std::pair<int, int>;
using CodeList = std::deque<Code>;

全体像

秘密コード集合Sの要素数が1になるまで, policy と trialを繰り返します.
推測コード集合GをSとします.

int main()
{
   // とりあえず(2色, 2ピン)
   CodeList S{ Code{0,0}, Code{0,1}, Code{1,0}, Code{1,1} };

   // main
   while( S.size() > 1 )
   {
      Code guess = policy(S, S); // G <- S
      trial(S, guess);           // update S
   }

   // post process
   Code guess = S[0];
   std::cout << "guess is [ " << guess[0] << " " << guess[1] << " ]" << std::endl;

   return 0;
}

policy

とりあえず, 推論コードの候補集合からランダムに選択することにする.

/**
* @fn Code policy(CodeList S, CodeList G)
* @brief 推論コード候補集合Gから1つを選択する
* @param[in] S 秘密コードの候補集合
* @param[in] G 推論コードの候補集合
* @return 推論コード
*/
Code policy(
      CodeList &S,
      CodeList &G
      )
{
   // random sampling from G
   std::mt19937 engine(0);
   std::uniform_int_distribution<> sampler(0, G.size()-1);
   Code guess = G[sampler(engine)];
   return guess;
}

trial

推測コードの結果はユーザーからの入力として,
その結果に当てはまるコードのみ抽出する.

/**
* @fn Code trial(CodeList &S, Code &guess)
* @brief 推論コード候補集合Gから1つを選択する
* @param[in, out] S 秘密コードの候補集合
* @param[in] 推論コード
*/
void trial(
      CodeList &S,
      Code &guess
      )
{
   // 入力待ち
   int hit, blow;
   std::cout << "guess is [ " << guess[0] << " " << guess[1] << " ]" << std::endl;
   std::cout << " input hit blow (e.g. 2 2): ";
   std::cin >> hit >> blow;
   HitBlow InputHitBlow(hit, blow);

   // 選別
   CodeList newS;
   for ( Code code : S )
   {
      if( countHitBlow(code, guess) == InputHitBlow )
      {
         newS.push_back(code);
      }
   }
   S = newS;
}

/**
* @fn HitBlow countHitBlow(Code &code, Code &guess)
* @brief コード2つから, hit, blowを計算する
* @param[in] code コード
* @param[in] guess コード
* @return (hit, blow)
*/
HitBlow countHitBlow(
      Code &code,
      Code &guess
      )
{
    std::vector<int> x(2, 0);
    std::vector<int> y(2, 0);
    int hit = 0, blow = 0;
    for( int i = 0; i < 2; i++ )
    {
       if( code[i] == guess[i] )
       {
          hit++;
       }
       else
       {
          x[code[i]]++;
          y[guess[i]]++;
       }
    }
    for( int i = 0; i < 2; i++ )
    {
       blow += std::min(x[i], y[i]);
    }
    return HitBlow(hit, blow);
}

コード全体

main.cpp で保存して g++ main.cpp -std=c++11 でコンパイルできます.

main.cpp · GitHub

ひとまず, ここまで.

まとめ

2色2ピンの場合のmaster mind解法プログラムを実装しました

他の記事

次の記事
一覧 mastermind カテゴリーの記事一覧 - サブロウ丸

Sabrou-mal サブロウ丸

主にプログラミングと数学