この前、何気なくみたテレビが面白かった。
numer0n という、数当てゲームで芸能人が競うという内容。

hit&blowとして知られる古典的なゲームで、僕は子供のころ親父がポケコンにプログラムしたもので遊んでいた。海外ではmaster mindというボードゲームして知られているようだ。
http://en.wikipedia.org/wiki/Mastermind_(board_game)

numer0nは単純なhit&blowではなく、様々なアイテムが追加されるなどルールにアレンジが加えてある。また、対戦者の掛け合いによる推測や妨害がテレビのショーを単純なゲーム以上に面白いものにしている。

下記の解説動画が素晴らしい。

Numer0n（ヌメロン）　第1回 round1　対戦を検証してみた

http://www.youtube.com/watch?v=-ZBLjDd8dvk


一般的な4桁のhit&blowは、下記のサイトでアルゴリズムの検討がされていた。一読の価値あり。
Hit&Blow 必勝法研究
http://www.giovedi.net/etc/hbstudy1.html
http://www.giovedi.net/etc/hbstudy2.html


さてここで、numer0nの3桁の残り可能性を僕も考えてみる。
最初は10*9*8=780個の正解候補がある。
最初のコールで正解候補はどれだけ減るのか？
例えば、最初に987をコールした場合はこうなる。(最初は何をコールしても確率は同じですが)

EAT-BITE	正解候補数	出現率	候補例
0-0	210	29.17	012 013 014 015 016 021 023 024 025 026 031 032 ...
0-1	252	35.00	018 019 028 029 038 039 048 049 058 059 068 069 ...
0-2	63	8.75	078 079 098 178 179 198 278 279 298 378 379 398 ...
0-3	2	0.28	798 879
1-0	126	17.50	017 027 037 047 057 067 081 082 083 084 085 086 ...
1-1	42	5.83	089 097 189 197 289 297 389 397 489 497 589 597 ...
1-2	3	0.42	789 897 978
2-0	21	2.92	087 187 287 387 487 587 687 907 917 927 937 947 ...
3-0	1	0.14	987

平均正解候補数: 180.09

アンガールズの田中が「物事が進まないことのたとえ」として挙げた0-1は、確かに最も絞り込めていない。とはいえ有利とされる0-0とそこまで大きくは違わない気がするが。

上記の必勝法のページでも書かれているように、候補が絞り込めないジャッジほど出る確率が高い。つまり、0-1が最も出やすい。

ということで、0-1の場合をもうちょっと掘り下げて、次のコールを考えてみる。

987で0-1なら候補はx9x,xx9,8xx,xx8,7xx,x7x (xは0から6)となる。素直にそのうちの765をコールした場合は以下のようになる。

EAT-BITE	正解候補数	出現率	候補例
0-0	80	31.75	018 019 028 029 038 039 048 049 091 092 093 094 ...
0-1	75	29.76	058 059 071 072 073 074 096 158 159 170 172 173 ...
0-2	19	7.54	076 176 276 376 476 570 571 572 573 574 596 658 ...
0-3	1	0.40	576
1-0	45	17.86	068 069 095 168 169 195 268 269 295 368 369 395 ...
1-1	18	7.14	075 175 275 375 475 568 569 695 706 716 726 736 ...
1-2	2	0.79	675 756
2-0	11	4.37	705 715 725 735 745 760 761 762 763 764 865
3-0	1	0.40	765

平均正解候補数: 58.98

これに対して、正解候補を無視して未開拓の654をコールする「ローラー」作戦もある。

EAT-BITE	正解候補数	出現率	候補例
0-0	72	28.57	018 019 028 029 038 039 071 072 073 091 092 093 ...
0-1	96	38.10	048 049 068 069 075 076 095 096 148 149 168 169 ...
0-2	18	7.14	468 469 475 476 495 496 548 549 568 569 576 596 ...
1-0	48	19.05	058 059 074 094 158 159 174 194 258 259 274 294 ...
1-1	12	4.76	458 459 574 594 648 649 675 695 756 764 856 864
2-0	6	2.38	658 659 674 694 754 854

平均正解候補数:68.29

これだけを見ると、ローラーよりも単純に正解候補をコールしたほうが良い。
ただ本当に重要なのは「正解にたどり着くまでの期待コール数」であって、直近の候補の絞込みではない。しかし、そのためには全ての可能性を網羅したゲーム木を作る必要があるのだけど、すぐに組み合わせが爆発してしまうし、枝刈りが難しくて単純には行かない。というか、そもそもNP完全問題であることが証明されているから、真っ向勝負では最適解を得るのは難しい。

ということで、このままこのアプローチで突き進むと大変そうなので気分を変えて、回答アルゴリズムを変えつつ10万回試行して正答にかかるまでのコール数の変化という側面を見てみる。

最初は正解候補からランダムにコールして絞り込んでいくアルゴリズム。

コール数	正解数	正解確率	平均正解候補数
1	133	0.13	180.29
2	1823	1.82	40.52
3	9949	9.95	8.87
4	25779	25.78	2.74
5	40344	40.34	1.53
6	15527	15.53	1.31
7	6138	6.14	1.05
8	307	0.31	1.00

平均コール数:4.77

この一番シンプルな方法でも、4コール目までに35%程度で3EAT、5コール目までに80%の確率で3EAT。
ただ、候補が絞られた後に正解を当てる、詰めが苦手のようだ。


次に正解候補から期待正解候補数が最も小さくなるコールの場合。

コール数	正解数	正解確率	平均正解候補数
1	141	0.14	179.92
2	1952	1.95	40.42
3	9873	9.87	8.18
4	28670	28.67	2.32
5	42452	42.45	1.41
6	11890	11.89	1.30
7	5022	5.02	1.00

平均コール数:4.67

4コール目からの正解率の向上が若干見られる。また、8コール目まで行ってしまうヘマも無くなった。
ここから分かることは、3コール目までの序盤ではあまり最適なコールを考える必要が無いということかもしれない。


次に、正解候補に捕われず980種から期待正解候補数が最も小さくなるコール。(ただし、候補が100以上ある場合は、計算時間短縮のため正解候補からランダム選択とする)

コール数	正解数	正解確率	平均正解候補数
1	123	0.12	179.72
2	1914	1.91	40.21
3	9494	9.49	7.81
4	43032	43.03	1.82
5	43888	43.89	1.04
6	1549	1.55	1.00

平均コール数:4.33

かなり数値が良くなった。4コール目までに54%程度で3EAT、5コール目でほぼ100%の確率で3EAT。3コール目の平均正解候補数が改善されていることから、その辺りから正解候補に拘らない方が絞込みに有意な差が出る模様。

これは深さ1の探索をしているだけなので、さらに効率を上げるためには2手先の候補数を評価する必要がある。けど、2手先でも結構大変だよね。ここまでは力ずくのコードで計算したけど、真面目に考えないとだめっぽい。


ということで先送りして、numer0nの特徴であるアイテムについて調べてみる。
特に、調べやすそうな攻撃アイテム。
まずはHIGH&LOW。各桁の5以上か5未満かが分かる。初回で使えばいきなり絞り込めるし、終盤の詰めでも使える可能性もある優れもの。
その絞り込まれるパターンを見てみる。

宣言	正解候補数	出現確率
LLL	60	8.33
LLH	100	13.89
LHL	100	13.89
LHH	100	13.89
HLL	100	13.89
HLH	100	13.89
HHL	100	13.89
HHH	60	8.33

大体100候補に絞り込める。実際に初回にHIGH&LOWを使って、全パターンから期待正解候補数が最も小さくなるコールで10万回試行するとどうなるか。

コール数	正解数	正解確率	平均正解候補数
1	1966	1.97	20.30
2	13716	13.72	4.19
3	60327	60.33	1.34
4	23991	23.99	1.00

平均コール数:3.06
まず3コール目で特定されるし、最悪でも4コール目で終了してしまう。アイテムを使わないときと比べたら、1.3コール分の価値があるといえる。


次にSLASHを調べる。これは各桁の最大数と最小数の差を得る。これも初回での絞り込みに活躍する。

SLASH NUM	正解候補数	出現確率
2	24	3.33
3	54	7.50
4	90	12.50
5	132	18.33
6	180	25.00
7	108	15.00
8	84	11.67
9	48	6.67

HIGH&LOWと違うのは、2や9のときに大きく絞り込めるが、6のとき等はあまり絞り込めない。

これもまた初回にSLASHを使って、全パターンから期待正解候補数が最も小さくなるコールで10万回試行する。

コール数	正解数	正解確率	平均正解候補数
1	1161	1.16	24.74
2	19414	19.41	4.45
3	53798	53.80	1.39
4	25160	25.16	1.02
5	467	0.47	1.00

平均コール数:3.04
HIGH&LOWより最悪ケースは悪くなっているが、大きく絞り込めるパターンがあるので2コール目での3EATが増えて、トータルでは若干良いようだ。ただ、実際は大きく絞り込めるパターンを相手が設定する可能性は低いので、実戦ではもう少し悪い値になると思われる。その代わり、相手は絞りこまれやすい数字を避ける可能性が高い(これはHIGH&LOWにも少しいえることだけど)。


ここまでをまとめると、

• 深さ1の探索でもランダムに正解候補から選ぶより0.4コールは短縮できる
• HIGH&LOWやSLASHは1.3コール程度の短縮に繋がる

次なる課題は、

• 深さ1より大きい探索
• 他のアイテムの調査
• 1手1手のミクロなコールの仕方の検証

がある。気が向いたら続く。