Hit&Blow(別名MOO)を早く解くためのアルゴリズムを検討中。とりあえず、何も考えずに矛盾のない候補を絞り込みながら、候補からランダムに取り出しては試すというアルゴリズムの場合、平均で4.8回答で正解に辿りつく
発生確率から期待値に基づいて選択するアルゴリズムを検討しているけど、、あまりこれ以上効率が上がらないような。。
全探査アルゴリズム
（１）候補から一つを選ぶ
（２）選んだ候補をＨ＆Ｂのゲームに提示、Hit/Blow数を得る
（３）3H/0Blowなら正解、終了、そうでないなら（３）へ
（３）得られたHit/Blow数と矛盾しない候補のみ残す
（１）に戻る平均：4.8回答（３桁数字、重複なし、０なし、１万回の試行平均）
ちなみに、、矛盾のない候補からランダムに選ぶのではなく、未使用数字を優先して選ぶようにしても正解に至る平均回答数は、4.8であった。
次にダメ元で、、１回目は１２３を必ず質問、２回目は４５６を必ず質問して矛盾しない候補集合を作り、３回目からは絞られた候補から選択するアルゴリズムを試した。この結果、若干良くなった。小数点の差ですが、再計測した結果は以下
1回目：123、２回目：456を固定的に質問して矛盾しない候補を作成、その後は候補から選ぶ
平均 4.78 (回答数：47762 設問回数：10000)矛盾しない候補集合から選ぶ
mean 4.84 (回答数：48365 設問回数：10000)
一応理系の人間なので、、当てずっぽうでアルゴリズムを考えるのではなくて、ちゃんと系統立てて考えたい。。なんせ７０年代に流行ったゲームだそうなので当時の解析資料もあるはず。。あぁ自分の頭の出来具合が嘆かわしい。。素材はともかく、努力してこなかったせいか。
■追記(130518)
いろんな記事を読んでいて、自分なりに理解したのは、次におきうる回答(3h0b,2h0b,...,0h0b)を想定して、期待値に基づきもっとも候補が減るような手を選択するというアルゴリズムです。自分の日本語（＋数学）能力で到底説明できないので、以下のご参考ＵＲＬを見てください。この期待値最少化を可能にする候補を都度計算して推定とする方法で実装しました。ただ、このアルゴリズムは計算量が非常に多くて、当初都度計算するためGAEでは処理時間の閾値にひっかかって処理中断されてしまいました。そこで、３回の回答分は想定回答としてローカルＰＣで計算して配列にしておき、GAE上では配列（PythonではDictionary）を引くだけにしました。この方法で、３回目の回答まではほぼ瞬間で応答可能になりました。一方、４回目からは真面目に期待値計算するので非常に遅いです。
■ご参考ＵＲＬ
[Strategies for playing MOO, or “Bulls and Cows”] by John Francis
http://www.jfwaf.com/Bulls%20and%20Cows.pdf
（自分の数学能力ではよく分かりませんでした。時間がある時にゆっくり読み直したいですが）
「木曜日が足りない男」様
Hit&Blow 必勝法研究 その１ （使わせてもらったアルゴリズム）
http://www.giovedi.net/etc/hbstudy1.html
■実装URL
Hit and Blow Solver (Hit&Blowを解くプログラム)
http://under-dev.appspot.com/solver
