主旨
Hit&Blowとは、未知の3~4桁の数字を、１質問毎に与えられるヒントを元に予想し当てられるまでの質問数の少なさを競うというゲームである。
この記事ではHit&Blowにおいて、桁数と数字の種類数別に必要最小手数を示し、特に3桁×10種(0~9)、3桁×9種(1~9)、4桁×6種(1~6)それぞれのルールの場合の最小期待値手順を調査する。
ルール説明
個人的にわかりやすかったので、こちらのサイトの説明文を参考にさせていただきました。
3桁×10種の場合のHit&Blowのルール
- 出題者は、0から9までの互いに異なる数字を使った 3桁の数を正解として用意し､解答者から隠しておく。
- 解答者は、解を予想し、質問をする｡
- 出題者は、質問と正解の数を比較して、
Hit数(同じ数字が同じ桁に出現する回数)と
Blow数(同じ数字が違う桁に出現する回数)をヒントとして解答者に与える｡ - 解答者はなるべく少ない質問で正解を当てる。
Hit&Blowのルールは以上である。
調査方法
まずはこのゲームの必要最小手数をコンピュータによって解析できるようにするために、どのように最適化していったかについて思考手順を示していこうと思う。
解析プログラムの実行環境にはPython3.8 Google ColabのJupyterNotebookを用いた。
1. 総当たりについて考える
必要最小手数について知りたい時に最も最初に考えられるのが、総当たりによる解析である。全ての手順について列挙してしまえば、何手で相手の考え得る数字全てに辿り着けるのかは明白である。まずは総当たりが可能かについて考えてみる。
例えば0~9×3桁のHit&Blowを考えるとして、一回の質問としてあり得るのは何パターンだろうか。
012, 013, 014, ... , 789のように一つずつ数え上げても良いが、これは場合の数の計算によって求めることができる。一桁目を0~9から選ぶとすると10通り、二桁目は一桁目と被らないようにするため9通り、三桁目は一桁目と二桁目と被らないようにするため8通り、よって10×9×8=720通りと求めることができる。
またこの質問は複数回にわたって行われるため、n回の質問を行うと考えると、場合の数は$720^n$通りとなる。例えば5回の質問をするとして、あり得るパターンの数は$720^5$であり、これは約193兆通りである。
しかし、193兆通りのパターンを全探索するのには途方もない時間がかかる。それはコンピュータ上でも同じであり、一般的なコンピュータが一秒で回せるループは単純な処理でおよそ1億回程度なので、193兆回のループを回しきるのに少なくとも半月以上かかる計算となる。しかもこのやり方だともし必要最小手数が6回以上だった場合は解がでないのでやり直しとなり、次は6回の質問であり得るパターンを総当たりするため約14京回の計算をするために約16124日を費やすこととなる。
ここまでで、単純な全探索によって必要最小手数を求めることは無謀であることがわかった。ここからは解析可能になるまで計算を減らす工夫を考えていく。
2. 再帰的に解析するモデルを考える
全探索には無駄が多い。必要最小手数を求めるのにおいて、例えば012を質問した後にもう一度012を質問するというのが非効率なのは明白なので、探索しなくても構わない。また、相手が最初に選ぶ数は完全にランダムであるなら、一番最初の質問は012だろうと951だろうとその後の必要最小手数は変わらないはずである。このように非効率な手順を排除し計算回数を減らすために、まずは効率化を容易にするための枠組みを整える。
そこで、①相手が選びうる数の集合、②今回の質問、③前回までの質問履歴の3要素を入力すると、その時点からの必要最小手数を出力する以下のようなモデルを考える。
モデル名: find_min_depth
入力: 相手が選びうるパターンの集合、今回の質問、前回までの質問履歴
出力: 必要最小手数
① 相手が選びうるパターンの集合を、今回の質問によるジャッジの結果(2hit0biteなど)によって更に細かい集合(以後は分割後の集合と呼ぶ)にわける。
② もし分割後の集合の中に複数解を持つものが無ければ、3H0Bのみなら1手で終了なので1を出力し、それ以外なら2手で終了なので2を出力する。
③ 前回までの質問履歴と今回の質問から、同値でない次の質問候補の集合を生成する。
④ 分割後の集合と次の質問の集合の組合せ全てについて、find_min_depthを実行する。引数には分割後の集合、次の質問、前回までの質問履歴＋今回の質問を用い、出力された手数を記録する。
⑤ ④で質問ごとの手数を求めたので、分割後の集合それぞれについて手数が最も少ない次の質問を採用し、このときの手数を必要最小手数とする。
⑥ ⑤で求めた分割後の集合それぞれについての必要最小手数の中で、最も多い手数を今回の質問による必要最小手数とし、これに1を足したものを戻り値として返す。
このような再帰モデルfind_min_depthによって、任意の局面からの必要最小手数を計算できる。
単純な例として、1~3×2桁の条件で、find_min_depthによって必要最小手数を求めた場合を考える。
初手で相手が選びうる数の集合は{12, 13, 21, 23, 31, 32}の6通り、最初の質問は12、前回までの質問履歴はなしとしてfind_min_depthに入力する。
① 相手が選びうる数の集合を質問"12"に対するジャッジの結果によって分割すると、{2H0B: 12, 1H0B: 13, 32, 0H2B: 21, 0H1B: 23, 31}のように分けられる。
② 対照でない質問の集合を生成する。過去の質問は"12"だけなので、これと重複しない質問の集合は{13, 21, 23}の3通りである。(3で解説)
③ 2H0Bを除く分割後の集合全てについて更にfind_min_depthを実行する。分割後の集合ごとの出力結果は
{13, 32} → 質問"13"により{2H0B: 13, 0H1B: 32}、{32} → 質問"32"より{2H0B: 32}なので2手で終了
{21} → 質問"21"により{2H0B: 21}なので1手で終了
{23, 31} → 質問"23"により{2H0B: 23, 0H1B: 31}、{31} → 質問"31"より{2H0B: 31}なので2手で終了
④ ③の結果の中で最大の手数は2手であり、一番最初の"12"の質問と合わせて必要最小手数は3手となる。
以上によって、1~3×2桁のHit&Blowは少なくとも3手で求められることがわかった。ここからは、計算量を少なくするための工夫を施す。
3. 質問履歴から対照でない次の質問の集合を生成するには
"012"の次の質問として、013, 014, 015, ... , 789全ての質問を全探索するのは非効率である。例えば"012"の質問から見て"456"と"789"は、4と7、5と8、6と9で数字を入れ替えれば同じ意味を持つため同値といえる。また"120"と"201"も、順番を入れ替えただけなので同値といえる。
このような同値となる質問を排除した結果、"012"の対照でない次の質問の集合は、{013, 021, 023, 034, 103, 120, 134, 345}の8個となった。これらの共通点は、"012"の質問に対してのジャッジの結果が異なるという点である。
よって対照でない次の質問の集合を以下の手順で定める。
① 質問としてあり得る全てのパターンリストを作成する。
② 作成したリストのパターン一つひとつに対して、質問履歴の中の全ての質問をし、ジャッジの結果をまとめたものを記録する。
③ もし過去のジャッジの結果の中で、全く同じものがあればそのパターンは排除する。なければ次の質問候補として残す。
以上の手順により次の質問候補を作成することとする。Pythonのプログラムは以下のようになる。
def produce_patterns(history_set):
pattern_set = set()
already_exists = set()
for pattern in permutations(range(num_size), digit_size):
judge_list = []
for history_pattern in history_set:
judge = judge_hb(history_pattern, pattern)
judge_list.append(judge)
judge_tuple = tuple(judge_list)
if judge_tuple not in already_exists:
pattern_set.add(pattern)
already_exists.add(judge_tuple)
return pattern_set
ここでjudge_hbとは、パターン２つを引数とすることで、ジャッジ結果をtuple型で返す関数である。
これにより、0~9×3桁の5手までの探索は全探索では約193兆通りだったのが、対照な質問を排除することによって3,656,481通りにまで減らすことができる。
4. 枝刈り
枝刈りとは、探索途中でこれ以上探索の必要がないことがわかったら探索を打ち切ることである。
Hit&Blowの探索の場合、例えば途中の時点で7手で相手の数字を当てられるような手順を見つけたなら、必要最小手数を見つける上では6手以下で相手の数字を当てられるような手順が存在しないかどうかだけ確認すれば良い。よってそれ以降探索途中の手順が7手を超えることがわかったなら、その手順はすぐに飛ばして次の手順に移っても問題ない。
これを実装するために、find_min_depthモデルの引数にlimit_depthを加え、手数がlimit_depthを超えたら探索を中断するようにした。
基本的な最適化は以上の要領で行った。
結果
find_min_depthモデルや、それを改良したモデルによって解析した結果を示す。
1. 必要最小手数の解析
find_min_depthモデルによって、数字の種類数と桁数のパラメータをかえて必要最小手数を求めた結果を以下に示す。
digitsが桁数、num_sizeは数字の種類数、min_depthは必要最小手数をそれぞれ表している。桁数と種類数が大きい場合は解析に時間がかかりすぎるため省略している。
この結果から特に、3桁×10種の場合の最短手数は7手、4桁×6種の場合の最短手数は5手となることがわかる。
ついでに解析時間の変化についてもグラフ化した結果を示す。
数字の種類数が増えるごとに解析時間が指数的に増加している様子が読み取れる。
2. 最小期待値手順の解析
find_min_depthを改良し、各盤面において最も手数の期待値が少なくなるような手順である最小期待値手順を探索するfind_earnest_treeモデルを作成した。
3桁×10種のHit&Blowの場合
find_earnest_treeを用いて最小期待値手数を調べたところ、期待値は5.015手となった。よって手数を少なくすることに最善を尽くせば、平均5.015手で相手の数字を当てることができる。
また、具体的な手順について以下のURLの画像に示したので、参照してほしい。
https://github.com/ysgrProgramming/hitblow/blob/main/310earnest_dot.png
画像の見かたについて説明する。
- ◯の中身が質問の内容を表し、矢印が質問に対する結果と遷移先を表す。
- 最も上の◯から質問が始まる。この画像では(0,1,2)が最初の質問となる。
- ◯の中身について、例えば(0,1,2)aと書いていた場合、012と質問することを意味する。付随しているアルファベットはgraphvizでの問題を解決するために仕方なくつけたものであり、意味はない。
- ◯と◎の違いについて、◯はその質問によって相手の数字を当てる(3H0Bとなる)可能性があるのに対して、◎は相手の数字を当てることはなく、その質問は"捨て"であることを表す。
画像を参考に、一手目を"012"とした時の結果と二手目について表にまとめた。
| 結果 | 2H0B | 1H2B | 1H1B | 1H0B | 0H3B | 0H2B | 0H1B | 0H0B |
|---|---|---|---|---|---|---|---|---|
| 二手目 | 034 | 021 | 034 | 034 | 120 | 134 | 134 | 345 |
二手目に有効な質問には034や134が多い。これは数字の種類がまだ確定していない場合は、相手のパターンを当てに行くよりも残りの数字を探しに行く方がが戦略として強いからだと考えられる。
個人的には012の後は二手目345が強いと思っていたが、１手目の数字を一つ使ったほうが得られる情報が多いらしい。
3桁×9種のHit&Blowの場合
find_earnest_treeを用いて最小期待値手数を調べたところ、期待値は4.698手となった。
具体的な手順は以下のURLに示した。画像の見かたについては、3桁×10種で説明した通りである。
https://github.com/ysgrProgramming/hitblow/blob/main/39earnest_dot.png
画像を参考に、一手目を"123"とした時の結果と二手目について表にまとめた。
| 結果 | 2H0B | 1H2B | 1H1B | 1H0B | 0H3B | 0H2B | 0H1B | 0H0B |
|---|---|---|---|---|---|---|---|---|
| 二手目 | 145 | 132 | 145 | 145 | 231 | 245 | 245 | 456 |
4桁×6種のHit&Blowの場合
find_earnest_treeを用いて最小期待値手数を調べたところ、期待値は4.086手となった。
具体的な手順は以下のURLに示した。画像の見かたについては、3桁×10種で説明した通りである。
https://github.com/ysgrProgramming/hitblow/blob/main/46earnest_dot.png
画像を参考に、一手目を"0123"とした時の結果と二手目について表にまとめた。
| 結果 | 3H0B | 2H2B | 2H1B | 2H0B | 1H3B | 1H2B | 1H1B | 0H4B | 0H3B | 0H2B |
|---|---|---|---|---|---|---|---|---|---|---|
| 二手目 | 1245 | 1243 | 1245 | 1356 | 1245 | 1245 | 1356 | 2145 | 2145 | 2156 |
Nintendo Switchのソフトである「世界の遊び大全」に収録されているHit&Blowの重複なしルールについては、この結果を参照することで最善手を指すことができる。
補足
実際のコードはこちら→https://github.com/ysgrProgramming/hitblow/blob/main/hit_brow.ipynb
Pythonについて理解があれば、私が用意した各種ツールを使ってより深い理解が得られると思う。(わかりやすくなるように努力はしました)
今回示した最小期待値手順は、あくまで相手が選ぶパターンがランダムであるということが前提となる。よってここで示した手順を実践で使う際は、事前に0~9それぞれについて入れ替える数字を決めておくことを推奨する。
また、今回示した最小期待値手順は対人戦となった場合の最善手順であるとは限らないことに注意して欲しい。例えば相手があと一手で自分の数字を当てられることがわかっているのに、捨て質問をするのは最善ではない。
また、時間があれば重複ありバージョンの解析やアイテムありの解析なんかもやってみたいと思います。
追記
3桁×10種の場合について、6手以内に当てることができるというものや、平均5手以下で当てることができる(当記事では5.015手)という説があります。これらは当記事の解析結果に反しますが、個人的にはあながち間違いというわけではないと考えています。
なぜなら、人間が設定する数字には偏りがあるからです。例えば012や456など、連続する数字というのは相手の質問がまぐれ当たりする確率が高いため、選ばれる確率が低いといえます。当記事の解析では、こういった数字が選ばれるのも等確率として扱っているのでこのような結果となっていると考えています。
また、3桁×10種の必要最小手数は7手ですが、解析結果の手順を見れば分かる通り、7手かかるパターンは3個程度しかないため、とても確率が低いです。
総合すると、人間相手のときは心理戦もうまく活用した方が強いです。