数当てゲームHit&Blowで負けて悔しくてGoでソルバーを作った
作ったもの
Hit&Blowという「互いの数字を推理し合い先に当てたほうが勝ちとなる2人対戦のゲーム」のソルバーコマンドを作りました。
Hit&Blowはスマホアプリゲームが人気で、2年前にブームが到来しYoutuberはじめしゃちょーもプレイ動画を上げています。
現在もAppStoreの単語ゲーム部門で4位になる人気です。
Hit&Blowのルール
互いのプレイヤーが0~9の数字を重複なしで3つ並べ、出題者と回答者は交代してゲームを進める。
回答者が出した回答に対して、出題者はヒットとブローの数でヒントを与える。
回答と正解を比べて、数と桁位置の両方が同じであることをヒットと呼び、数だけが同じで桁位置が異なることをブローと呼ぶ。
たとえば、正解が085で回答が018なら出題者は1Hit 1Blowというヒントを与え、正解までこれを繰り返す。より少ない回答で正解を言い当てた方を勝ちとする。
経緯
先に紹介したアプリを暇潰しに何回か最高レベルのCPUと対戦してみたところ見事にボコボコにされてしまいました...10戦して3勝5敗2分で負け越しました...
この大敗がとても悔しくコンピュータの力を借りてなんとか圧倒することはできないかと考えました。
特徴
最小限のUIで適切なサポートを得るために以下の特徴を持つコマンドラインツールをGoで実装しました。
- ツールは最短で正解に辿り着くための適切な回答を教えてくれる
- 回答に対して得たヒントは選択肢から直感的に選べる
- 0~9以外の数値群や3桁以外の数列で行う派生ゲームにも対応できる
ソルバーのアルゴリズム
以下の論文を参考にしています(p4のB.Landyさんの1つ目の評価関数)
このゲームでは正解に辿り着くための適切な回答を続けると勝利までの手数を減らすことにつながります。
適切な回答とは「回答に対して正解候補群が生み出すヒント群の個数分布の分散が大きい回答」と言い換えることができると思います。
例えば正解の候補が9個ある状況で以下のケースA,Bを考えます。
- [ケースA] "012"と回答すると0H1Bが4つ, 0H2Bが3つ, 1H1Bが2つ返ってくる
- [ケースB] "987"と回答すると0H1Bが1つ, 0H2Bが1つ, 1H1Bが1つ, 0H1Bが1つ, 0H2Bが1つ, 1H1Bが1つ, 0H1Bが1つ, 0H2Bが1つ, 1H1Bが1つ返ってくる
この時、ケースAではどのヒントが返ってきてももう1,2ターン回答を投げる必要がありそうです。
対してケースBのではどんなヒントが返ってきてもあと一手で正解を言い当てられるのでケースAよりも優れた回答と言えます。
上げた例は極端な例ですが、とどのつまり正解候補群が出すヒントが満遍なく散らばるような回答が良いということです。
この"ヒントが満遍なく散らばる"を正しく表現する「(ヒントの種類, そのヒントを出す正解候補の数)の組を入力に散らばりを出力する関数」があれば良いということになります。
先に挙げたB.Landyさんはそれが
本ソルバーでは全ての回答候補(012~789の720パターン)に対してヒストグラムから導き出せる上記の関数値を計算し、それが最も小さくなるものを次の回答として推薦する仕組みになっています。
お世話になったpackage
選択肢から選べるようにするコマンドラインpackage
正解の候補を絞り込むための部分順列を出力するpackage
(pythonのitertoolsがリスペクトされており非常に親しみやすいです)
使ってみた
本ソルバーを使ってみたところ自力では大敗した最高レベルのCPUに対して6勝2敗2分と勝ち越すことができました!!
あたらめて調べてみると完全解析により最小期待値手数が5.012と算出されいました、今回のソルバーでも同様の期待手数を測定したところ5.022となり、ほとんど最適な方法に近いことがわかります。
Discussion