chakokuのブログ(rev4)

日々のごった煮ブログです

Hit and Blow Solverを試作(GAE上)

かなり昔、Google App Engine(以降、GAE)上で、Hit and Blowの検証用ツール(Verifier)を作ってそのまま放置していたのだけど、Hit and Blow(以降、H&B)検証ツールに関する質問を受けたりコメント欄で意見交換しているうちに、他人が設問したH&Bに対して回答案を作る機能を作ってほしいという要望を受けて(受けたと解釈して)、人に代わって回答を考えてくれる H&B Solverを作ってみた。

アルゴリズムとしては基本的に総当たりで、チカラワザで全探査させていて、次の候補は矛盾のない候補のリストからランダムに1つを抽出しています。でも正しくは戦略的に確率の期待値にもとづいて候補を決める方がより短い応答回数で勝てるようになるそうです。だけど、そこまで作るのはちょっと大変なので、今は(上記記載のように)矛盾のない候補から一つを選んで試してもらうというアルゴリズムにとどまっています。そのうち、改良版を作りたいけど。。モチベーション依存ですね。チカラわざアルゴリズムの場合、3桁数字に対して、おおよそ5回〜6回で回答に辿りつきます。

H&B Solverに興味のある方は以下のURLからお使いいただけます。戦略的に動いていないし、スクラッチで試行錯誤しながら作った汚いソースになっているので、ソース公開は控えます。(ある程度綺麗になったら公開しますけど、、今のレベルではソースを見た人を混乱させて終わりになるだろう。。)
Pythonは漢字はUTFで扱うのが無難なようだけど、UTFでソースを書くのがエディタの都合上ちょっと大変なのでへなちょこ英語だけで書いています。


使い方:
(1)先方のHit&Blowゲームアプリが指定する桁(3桁、4桁)で回答を
作るように、solverのset Ketaのラジオボタンを選択する。(基本は3桁を想定)
(2)もし先方のゲームが、重複を許す、0を許す、等のルールであれば
それに合わせてチェックボックスにチェックを入れる
(3)設定を変更した場合は[reset]ボタンで初期化する(ここはちょっとクサイ仕様)
(4)準備OKなら、[solve]ボタンを押す

(5)まず第一回目の回答案がnthTry:1の guess numberの枠に表示されますので、
この回答案を先方のHit&Blowゲームに入力する
(6)先方のHit&Blowゲームは、hit:N blow:Mと回答してくるので、その数値を
solverのnthTry:1のhitの枠、blowの枠に入力する
(7)入力が終わったら[solve]ボタンを押す

(8)2回目の回答案がnthTry:2のguess numberの枠に表示される。先方のHit&Blow
ゲームに回答案を入力する
(9)先方のHit&Blowゲームが hit/blowを回答するので、得られた数値をsolverの
各枠に入力

以降、回答案が1つになるまで上記、(8)-(9)を繰り返す。
回答候補が1つに絞れたら終了

質問やご意見がありましたらコメント欄に記載ください。under-devという名前の通り開発中です。(エラー処理とかアプリご利用者の誘導とかちゃんとやっていない)

■追記(130518AM)
少し賢いアルゴリズムを実装、以下のURLにデプロイした。実際にGAE上で動かしてみると、3桁のHit&Blowは動くけど、4桁になると探査空間が広すぎるのかサーバ側のタイムアウトに引っかかる。あらかじめ探査したテーブルを持たせるような実装にしないと使い物にならない。。

■追記(130518PM)
少し賢いアルゴリズム(期待値最少アルゴリズム)では計算量が多すぎて、GAEの実行時間の閾値にひっかかりエラー中断となる。そこで、1回目と2回目を問い合わせ文字列を固定(4桁の場合、1234−>9876を必ず使う)にして、3回目からまじめに計算するようにした。いまはなんとかギリギリ閾値に収まっている。でも、この遅さはありえないので、最初の応答3回分ぐらいは、全空間をあらかじめ計算してツリーを作っておき、ツリーを辿るだけで計算不要で応答できるように変えるつもり。

■追記(130518PM)
処理を高速にするため、3手まではテーブルを引くだけで済むようにした。具体的にはローカルPCで空間探査させて、NhMbが来た時は、3456を質問する、というようなQA想定集のテーブルを用意して、3手までは空間探査せずに済ませた。これで、4桁の場合であっても計算に時間がかかりすぎて時間切れになるのを回避した。ただし、、このテーブルの出来具合が効率の良いQAを決めるのだけど、、あまり凝ったアルゴリズムではないので最適なテーブルにはなっていないと思われる。

■追記(200720)
古いプログラムですが、使いたいというコメントをいただいたのでGoogleAppEngine上のサービスを起動してみた。課金ルールに紐づいていないのか、決済設定なしのプロジェクトになっている。。。なぜか。。

■関連URL
Hit and Blow Solver (Hit&Blowを解くプログラム)
http://under-dev.appspot.com/solver
(GAE上でPythonで実装、開発中のレベル)

■ご参考URL(他人様のSolverの記事)

「Thank GOD Daemon, it's BSD」様
Hit and Blow (Mastermind) solver (LabVIEW 版)!! の巻
http://www.bsddiary.net/d/20070202.html

「数当てゲームを解く - 情報処理学会
(この解法はランダムな選択(今の自分と同じレベル))
http://www.ipsj.or.jp/07editj/promenade/4606.pdf

東京大学工学部 田中哲朗」様
数当てゲームMOOの最小質問戦略と最強戦略
http://www.tanaka.ecc.u-tokyo.ac.jp/~ktanaka/papers/gpw96.pdf
(一番数理学的に裏付けのある説明。。多分)

「木曜日が足りない男」様
Hit&Blow 必勝法研究 その1
http://www.giovedi.net/etc/hbstudy1.html