サブロウ丸

Sabrou-mal サブロウ丸

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

master mind by c++; part13 minmax, exp_minmax, entropy policy

c++ mastermind

今回やること

新しい推論コード取得関数の実装

推論コードの決定

ランダムサンプリング

毎回の試行においてどのコードで試すのがよいか?を考えてみます. 現在はコードの候補集合Sからランダムに一つ選ぶ, というのを繰り返すことになっています.

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

もっとも最適化戦略については, 網羅的な全探索が必要であり, ピンの個数や色が多くなると現実的な時間での求解は困難です. そのため, その次の1手だけ考えてもっとも状況が良くなるような手を, 人工的(ヒューリスティック)に考えてみます.

minmax

もう少し良い選択方法を考えてみましょう.
ある推論コードで試行した場合, 出題者からその推論コードに応じた(hit, blow)の組み(ヒント)が返ってきます. その結果秘密コード候補が絞られることになるのですが, その絞られた後のコード候補が最悪の場合でもなるべく少なくなるように選ぶとします.

数式で表現すると,

argmin_(c in G) { max_(h in H) { #C_c(h) } }

ここで

  • 推論コード候補集合をG
  • (hit, blow)の組みの候補をH
  • コードcで試行してh = (hit, blow)が返ってきたときの秘密コード集合をC_c(h)

です. 例えば

  • G = { [0, 0], [0, 1], [1, 0], [1, 1] }
  • c = [0, 1]

の場合

  • C_c(hit=1, blow=0) = { [0, 0], [1, 1] }
  • C_c(hit=2, blow=0) = { [0, 1] }
  • C_c(hit=0, blow=2) = { [1, 0] }

となります.

/**
 * @fn minmax(std::map<Hint, int> &d, int N)
 * @brief score function based on minmax policy
 * @param[in] d distribution of S by test code; d(hint) = number of candidates from S
 * @param[in] N size of S
 * @return the smaller the better score value
 */
double minmax(
      std::map<Hint, int> &d,
      int N
      )
{
   double maxElm = -1;
   for ( auto pair : d )
   {
      if ( pair.second > maxElm ) maxElm = pair.second;
   }
   return maxElm;
}

上記関数は, ある推論コードの候補のスコアを返す関数で, 最終的にはこのスコア値が最も低いコードを推論コードとして使用します. ( すなわち max_(h in H) { #C_c(h) } の部分ですね ) ここでプログラム中の d は事前に計算しておいた, key: h(hint) → value: #C_c(h) を返す map です.

exp_minmax

別の方法を考えてみましょう. 試行によって絞られた後の秘密コード候補の要素数の期待値が最小のコードを選択してみます.

argmin_(c in G) { sum_(h in H) { (#C_c(h) / #C) * #C_c(h) }}
= argmin_(c in G) { (1 / #C ) sum_(h in H) { #C_c(h)^2 } }

ここで, #C = sum_(h in H){ #C_c(h) } です.

/**
 * @fn expMinMax(std::map<Hint, int> &d, int N)
 * @brief score function based on expMinMax policy
 * @param[in] d distribution of S by test code
 * @param[in] N size of S
 * @return the smaller the better score value
 */
double expMinmax(
      std::map<Hint, int> &d,
      int N
      )
{
   double exp = 0;
   for ( auto pair : d )
   {
      exp += pair.second * pair.second;
   }
   return exp / N;
}

entropy

また, 別の基準として情報量(エントロピー)を最大化させるようなコードを選択するのもありそうです.

argmax_(c in G) { - sum_(h in H; #C_c(h) > 0) { (#C_c(h) / #C) log ((#C_c(h) / #C)) }}
= argmin_(c in G) { sum_(h in H; #C_c(h) > 0) { (#C_c(h) / #C) log ((#C_c(h) / #C)) }}
/**
 * @fn entropy(std::map<Hint, int> &d, int N)
 * @brief score function based on entropy policy
 * @param[in] d distribution of S by test code
 * @param[in] N size of S
 * @return the smaller the better score value
 */
double entropy(
      std::map<Hint, int> &d,
      int N
      )
{
   double minus_entropy = 0.0;
   double p;
   for ( auto pair : d )
   {
      if ( pair.second > 0 )
      {
         p = static_cast<double>(pair.second) / N;
         minus_entropy += p * std::log(p);
      }
   }
   return minus_entropy;
}

実装

実装についてはこちらの回答を参考にしました. 

/**
* @fn Code minmaxPolicy(CodePtrList &S, CodePtrList &G, Config &config)
* @brief 推論コード候補集合Gから, objFuncの値が最小のものを選択する
* @param[in] S 秘密コードの候補集合
* @param[in] G 推論コードの候補集合
* @param[in] objFunc 推論コード取得用のスコア関数
* @param[in] config パラメタ
* @return 推論コード
*/
template<class ObjFunc>
auto distPolicy(
      CodePtrList &S,
      CodePtrList &G,
      ObjFunc objFunc,
      Config &config
      )

templateによるスコア関数の指定を行っています. 使用する部分は下記のような感じ.

/**
* @fn Code policy(CodePtrList S, CodePtrList G, Config &config)
* @brief 推論コード候補集合Gから1つを選択する
* @param[in] S 秘密コードの候補集合
* @param[in] G 推論コードの候補集合
* @param[in] config パラメタ
* @return 推論コード
*/
auto policy(
      CodePtrList &S,
      CodePtrList &G,
      Config &config
      )
{
   if ( config.policy == "random" )
   {
      return randomPolicy(S, G);
   }
   else if ( config.policy == "minmax" )
   {
      return distPolicy(S, G, minmax, config);
   }
   else if ( config.policy == "exp_minmax" )
   {
      return distPolicy(S, G, expMinmax, config);
   }
   else if ( config.policy == "entropy" )
   {
      return distPolicy(S, G, entropy, config);
   }
   else
   {
      exit(1);
   }
}

ソースコード全体
master_mind_cpp/policy.h at feature/minmax_policy · nariaki3551/master_mind_cpp · GitHub

推論手数の実験

  • git branch: feature/minmax_policy
  • git commit: cc62026416f8450ac7ca32b4b0df23e4be402a46

全てのコードに対し, それを秘密コードに設定して, 実際に上記の方法によって推論コードを 選択していった場合に秘密コードを割り当てるまで必要だった手数の統計情報によって比較します.

  • max count ... その推論コード取得方法で必要だった最大手数
  • average count ... 全ての秘密コードに対して必要だった手数の平均

colors 4 pins 4

policy max count average count
random 4 2.9648
minmax 4 2.9023
exp_minmax 4 2.8867
entropy 4 2.8633

colors 5 pins 4

policy max count average count
random 6 3.6704
minmax 5 3.4832
exp_minmax 4 3.3168
entropy 4 3.3024

colors 6 pins 4

policy max count average count
random 6 3.9714
minmax 5 3.8642
exp_minmax 5 3.7793
entropy 5 3.8287

colors 4 pins 5

policy max count average count
random 5 3.5010
minmax 5 3.4092
exp_minmax 5 3.2422
entropy 5 3.2500

colors 5 pins 5

policy max count average count
random 6 3.9901
minmax 5 3.7885
exp_minmax 5 3.7331
entropy 5 3.7174

average countを見ると, entropy の結果が良いですね.

まとめ

推論コード取得関数を追加しました. その結果, ランダムに推論コードを決定するものよりも手数が少ないものが作成でき, 特にentropy型の推論関数が平均手数が最も良い結果になりました.

コード

参考

他の記事