数字当てゲームの考察 その３

第１回、第２回に引き続き、数字当てゲームの考察をしていきます。
ちなみに、今回も完結編ではありませんよ(笑）ヘタレですいません。

①親が０～９の中から４桁の数字を予め決める。（同じ数字はなし、千の位０もあり）
②子がその数字を予想して当てる。
③親は１手ごとに数字があればヒット、数字と桁（場所）があっていればペアという評価を与える。
課題：４ペアにできるまでの最短手数（評価を踏まえ、最善を尽くした手数の上限）を考える。

前回は最終目標の半分である、数字の種類が０～４の５種類、正解の桁が２桁を検証し、最善を尽くせば少なくとも４手までに正解を導けることが証明できました。また、「初手の結果を踏まえ、２手目で正解可能性のない手は除外する」（悪手仮説）も俄然真実味が増してきました。
さらに、まだ検証の余地がありそうですが、以下の２つの仮説も浮上してきました。
・「全ての評価別の場合分けにおいて上限はある手数に収束する」（上限収束仮説）
・「最も起こりやすい評価の中に最も手数がかかる場合が潜む」（木を隠すなら森仮説）（笑）
ざっくり言えば、「飛びぬけて手数がかかることはないから、同じくらい悪い評価のを適当に見繕って調べていけば上限に辿り着く」という感じです。と言うか、そうでないとこれ以上はとてもやっていけそうにありません（笑）
今回は、新しい仮説を使いつつ、一気に９種類３桁を検証してみたいと思います。
これは昔遊んでいた数字当てゲームの入門編とも言えるルールで、小学２年生の１学期の学習を終えた時点でいつでも遊ぶことができます。（「百の位」等）
一般的に０を使わずに１～９の数字で行うので、今回もそれで考えたいと思います。
もちろん、１手目の組み合わせはいきなり５０４通りと今までの２０倍以上になりますから、全ての検証はできませんしする気もありません。
あくまでも自分の仮説に沿って上限を探ることが目的ですが、もしかしたら辿っていない手に妙手が潜んでいるなど、根本的に間違っている場合もあるかもしれません。それはご了承ください。

＜例５＞
９種類（１２３４５６７８９）正解３桁、「１２３」の場合（評価ごとの場合分けで検証）
◎１手目の組み合わせ・・・５０４通り　１＋２＋３＋１８＋３６＋４８＋９０＋１２０＋１８０＝５０４
３ペア・・・・・１２３（１通り）
３ヒット・・・・２３１、３１２（２通り）
１ペア２ヒット・１３２、３２１、２１３（３通り）
２ペア・・・・・１２４、１２５、１２６、１２７、１２８、１２９、１４３、１５３、１６３、１７３、１８３、１９３、
　　　　４２３、５２３、６２３、７２３、８２３、９２３（１８通り）
１ペア１ヒット・１３４、１３５、１３６、１３７、１３８、１３９、１４２、１５２、１６２、１７２、１８２、１９２、
　　　　３２４、３２５、３２６、３２７、３２８、３２９、４２１、５２１、６２１、７２１、８２１、９２１、
　　　　２４３、２５３、２６３、２７３、２８３、２９３、４１３、５１３、６１３、７１３、８１３、９１３（３６通り）
２ヒット・・・・２１４、２１５、２１６、２１７、２１８、２１９、２３４、２３５、２３６、２３７、２３８、２３９、
　　　　２４１、２５１、２６１、２７１、２８１、２９１、４３２、５３２、６３２、７３２、８３２、９３２、
　　　　４３１、５３１、６３１、７３１、８３１、９３１、３１４、３１５、３１６、３１７、３１８、３１９、
　　　　３４２、３５２、３６２、３７２、３８２、３９２、４１２、５１２、６１２、７１２、８１２、９１２（４８通り）
１ペア・・・・・１４５、１４６、１４７、１４８、１４９、１５４、１５６、１５７、１５８、１５９、１６４、１６５、
　　　　１６７、１６８、１６９、１７４、１７５、１７６、１７８、１７９、１８４、１８５、１８６、１８７、
　　　　１８９、１９４、１９５、１９６、１９７、１９８、４２５、４２６、４２７、４２８、４２９、５２４、
　　　　５２６、５２７、５２８、５２９、６２４、６２５、６２７、６２８、６２９、７２４、７２５、７２６、
　　　　７２８、７２９、８２４、８２５、８２６、８２７、８２９、９２４、９２５、９２６、９２７、９２８、
　　　　４５３、４６３、４７３、４８３、４９３、５４３、５６３、５７３、５８３、５９３、６４３、６５３、
　　　　６７３、６８３、６９３、７４３、７５３、７６３、７８３、７９３、８４３、８５３、８６３、８７３、
　　　　８９３、９４３、９５３、９６３、９７３、９８３（９０通り）
なし・・・・・・４５６、４５７、４５８、４５９、４６５、４６７、４６８、４６９、４７５、４７６、４７８、４７９、
　　　　４８５、４８６、４８７、４８９、４９５、４９６、４９７、４９８、５４６、５４７、５４８、５４９、
　　　　５６４、５６７、５６８、５６９、５７４、５７６、５７８、５７９、５８４、５８６、５８７、５８９、
　　　　５９４、５９６、５９７、５９８、６４５、６４７、６４８、６４９、６５４、６５７、６５８、６５９、
　　　　６７４、６７５、６７８、６７９、６８４、６８５、６８７、６８９、６９４、６９５、６９７、６９８、
　　　　７４５、７４６、７４８、７４９、７５４、７５６、７５８、７５９、７６４、７６５、７６８、７６９、
　　　　７８４、７８５、７８６、７８９、７９４、７９５、７９６、７９８、８４５、８４６、８４７、８４９、
　　　　８５４、８５６、８５７、８５９、８６４、８６５、８６７、８６９、８７４、８７５、８７６、８７９、
　　　　８９４、８９５、８９６、８９７、９４５、９４６、９４７、９４８、９５４、９５６、９５７、９５８、
　　　　９６４、９６５、９６７、９６８、９７４、９７５、９７６、９７８、９８４、９８５、９８６、９８７（１２０通り）
１ヒット・・・・４１５、４１６、４１７、４１８、４１９、５１４、５１６、５１７、５１８、５１９、６１４、６１５、
　　　　６１７、６１８、６１９、７１４、７１５、７１６、７１８、７１９、８１４、８１５、８１６、８１７、
　　　　８１９、９１４、９１５、９１６、９１７、９１８、４５１、４６１、４７１、４８１、４９１、５４１、
　　　　５６１、５７１、５８１、５９１、６４１、６５１、６７１、６８１、６９１、７４１、７５１、７６１、
　　　　７８１、７９１、８４１、８５１、８６１、８７１、８９１、９４１、９５１、９６１、９７１、９８１、
　　　　２４５、２４６、２４７、２４８、２４９、２５４、２５６、２５７、２５８、２５９、２６４、２６５、
　　　　２６７、２６８、２６９、２７４、２７５、２７６、２７８、２７９、２８４、２８５、２８６、２８７、
　　　　２８９、２９４、２９５、２９６、２９７、２９８、４５２、４６２、４７２、４８２、４９２、５４２、
　　　　５６２、５７２、５８２、５９２、６４２、６５２、６７２、６８２、６９２、７４２、７５２、７６２、
　　　　７８２、７９２、８４２、８５２、８６２、８７２、８９２、９４２、９５２、９６２、９７２、９８２、
　　　　３４５、３４６、３４７、３４８、３４９、３５４、３５６、３５７、３５８、３５９、３６４、３６５、
　　　　３６７、３６８、３６９、３７４、３７５、３７６、３７８、３７９、３８４、３８５、３８６、３８７、
　　　　３８９、３９４、３９５、３９６、３９７、３９８、４３５、４３６、４３７、４３８、４３９、５３４、
　　　　５３６、５３７、５３８、５３９、６３４、６３５、６３７、６３８、６３９、７３４、７３５、７３６、
　　　　７３８、７３９、８３４、８３５、８３６、８３７、８３９、９３４、９３５、９３６、９３７、９３８（１８０通り）

さて、５０４通り全て書き出しただけで３０００文字オーバーですが、書いた意味はあったのでしょうか(汗）実はこれ、規則性に従ってコピペしているだけでそんなに考えてないのですよね・・・組み合わせの可能性は９パターンあり、今まではその全てを検証していましたけど、今回は早速「木を隠すなら森仮説」を信じ、「１手目で最も起こりやすくて不運な１ヒットだった「４１５」の先に、必ず全体の上限が存在する」と仮定して続きを考えたいと思います。さらに、２手目は例えば「６７１」のように、１か４か５を場所を変えて一つ使う「悪手仮説」を活用すると、一気に１８０通りに絞られます。当然正解する可能性も含まれていますし、２手目としては悪い手ではないでしょう。
「え？一手目４１５なら、普通に全部使ってない６７８とかの方が良いのでは？つーかいつも私はそうしてるし？」と思われた方は、もう一度第１回、第２回の「悪手仮説」を読んできて下さい。簡単に言い返すと、「１手目１ヒットなのに、絶対３ペアにならない２手目を選ぶのは遠回りじゃないの？」ということです。あくまでも仮説なので、自分も断言はできませんが、今回は自説で突っ走ってみるのが目的ですので(笑）

◎初手「４１５」評価１ヒットを踏まえた２手目の候補
※１、４、５のいずれかの数字一つを、初手とは場所を変えて用いる場合・・・１８０通り
３ペア・・・・・１２３（１通り）
３ヒット・・・・２３１（１通り）
１ペア２ヒット・１３２、３２１（２通り）
２ペア・・・・・１２６、１２７、１２８、１２９、１６３、１７３、１８３、１９３、５２３、（９通り）
１ペア１ヒット・１３６、１３７、１３８、１３９、１６２、１７２、１８２、１９２、２４３、２５３、３２４、６２１、
　　　　７２１、８２１、９２１、（１５通り）
２ヒット・・・・２６１、２７１、２８１、２９１、３６１、３７１、３８１、３９１、６３１、７３１、８３１、９３１、
　　　　３４２、２３４、５３２、３５２（１６通り）
１ペア・・・・・１６７、１６８、１６９、１７６、１７８、１７９、１８６、１８７、１８９、１９６、１９７、１９８、
　　　　６２４、７２４、８２４、９２４、５２６、５２７、５２８、５２９、６４３、７４３、８４３、９４３、
　　　　５６３、５７３、５８３、５９３、６５３、７５３、８５３、９５３（３２通り）
なし・・・・・・６４７、６４８、６４９、７４６、７４８、７４９、８４６、８４７、８４９、９４６、９４７、９４８、
　　　　６７４、６８４、６９４、７６４、７８４、７９４、８６４、８７４、８９４、９６４、９７４、９８４、
　　　　５６７、５６８、５６９、５７６、５７８、５７９、５８６、５８７、５８９、５９６、５９７、５９８、
　　　　６５７、６５８、６５９、７５６、７５８、７５９、８５６、８５７、８５９、９５６、９５７、９５８（４８通り）
１ヒット・・・・６７１、６８１、６９１、７６１、７８１、７９１、８６１、８７１、８９１、９６１、９７１、９８１、
　　　　２４６、２４７、２４８、２４９、３４６、３４７、３４８、３４９、６４２、７４２、８４２、９４２、
　　　　２６４、２７４、２８４、２９４、３６４、３７４、３８４、３９４、６３４、７３４、８３４、９３４、
　　　　５３６、５３７、５３８、５３９、５６２、５７２、５８２、５９２、２５６、２５７、２５８、２５９、
　　　　３５６、３５７、３５８、３５９、６５２、７５２、８５２、９５２（５６通り）

最も多く、そして最も厳しいだろう評価は「２手目も１ヒット」という結果になりました。確かに２回とも１ヒットだと、体感でもかなり厳しいと言えます。まず、１手目に使った数字を一つ再使用したわけですが、その数が合ってたのか違ってたのかの判断がつきません。まだ次に多かった評価「なし」の方が、すっきり早く解決できそうですね。しかし、「木を隠すなら森仮説」なので、我慢して「１ヒット」「１ヒット」の続きを考えていきましょう。
ここで正解から逆算すると、２手目１ヒットの５６通りを次の２つに場合分けできることが分かります。
①１手目から再利用した１数字が実は当たっていたがまだ場所が違い、２手目に選んだ２数字は外れの場合・・・１２通り
②１手目に選んだ数字は間違っていて、２手目に選んだ２数字のうち１つが当たり、場所が違っている場合・・・４４通り
①は、例えば「６７１」の場合です。１が正しいと仮定して再使用したので、もしこれなら既に４５と６７を使用しないと仮定でき、３手目の候補は１○○となり、あとの２数は残る２３８９の中から２つの数字を選ぶことになります。ん？どこかで見たような・・・？
そう、実はコレ、４種類２桁ですからもう＜例３＞で証明済みなのです。確か３手でしたね。ここまで２手かかっているので、上限は５手ということになります。しかし、問題は②の場合もあるということでしょう。例えば「２４６」ですが、確率的にも４分の３以上はこちらのパターンです。常に最悪を想定する今回の趣旨では、３手目で②をどう攻略するかが鍵となりそうです。
とりあえず考えられるのは、やはり①だと仮定して３手目の候補を絞ることでしょうか。どう言うことかというと、１手目に再使用した数字をさらに３手目でも回して使ってみるということです。ここまで１ヒット１ヒットときたので、もし①だったとして、再使用したその数を本当に使うのならば、次は必ず１ペア以上になりますよね。もし②だと泥沼にはまりそうですが、やはり４分の１でも正解の可能性がある以上、攻めて行くべきでしょう。

①１手目「４１５」評価１ヒット、２手目「６７１」評価１ヒットを踏まえた３手目の候補
※１が正解だと仮定し、百の位は１に固定。残りの数字は出ていない２３８９から選ぶ。・・・１２通り
３ペア・・・・・１２３（３手で終了）
１ペア２ヒット・１３２（４手で終了）
２ペア・・・・・１２８、１２９、１８３、１９３（５手で終了）
１ペア１ヒット・１３８、１８２、１９２、（５手で終了）
１ペア・・・・・１３９、１８９、１９８（５手で終了）
以上より、上限は５手であると言える。※＜例３＞を参照。

②１手目「４１５」評価１ヒット、２手目「２４６」評価１ヒットを踏まえた３手目の候補
※４が正解だと仮定し、一の位は４に固定。残りの数字は出ていない３７８９から選ぶ。・・・１２通り
なし・・・・・・７８４、７９４、８７４、８９４、９７４、９８４
１ヒット・・・・３７４、３８４、３９４、７３４、８３４、９３４

ここで衝撃の事実が発覚しました。①だと仮定して１手目、２手目に使った数字を再々使用した結果、仮に②だった場合は１ペア以上にならないので、３手目ではっきり①か②かが判別できたのです。もし３手目の評価が１ペア以上ならば①だったと確実に言えることになり、自動的に残り手数も見えてくるオマケつき。もう検証の必要もありません。
そして、３手目の評価が「なし」か「１ヒット」だった場合、少なくとも②であることははっきりするわけです。結果的に３手目が正解可能性のない悪手になってしまったのは気になりますが、あとは②の場合の続きを考えるだけです。
組み合わせ数に差がないので、「なし」の方で検証してみましょう。
まあ、「上限収束仮説」に頼れば、一方を検証すれば十分に上限の片鱗が見えてくるはずです。
で、評価「なし」の場合は、３手目で３つの数字を使わないことがやっと確定します。「７８４」だとしましょう。ここで分かるのは、１と５のどちらかを使うことと、２と６のどちらかを使うこと、そして３と９のどちらかを使うことです。４手目は、１手目、２手目の場所の制約を踏まえると、次の２２通りになります。８パターンに分かれ、やはり１ヒットが一番運のない手に見えますが、そろそろ差もなくなってきたので、一応全てを場合分けで考えてみます。

◎１手目「４１５」評価１ヒット、２手目「２４６」評価１ヒット、３手目「７８４」評価なしを踏まえた４手目の候補
※１か５、２か６、３か９からそれぞれ選ぶ。ただし５と６は一の位、１は十の位、２は百の位に入らない場合→２２通り
３ペア・・・・・１２３（４手で終了）
１ペア２ヒット・１３２、３２１・・・（１）で検証
なし・・・・・・５６９、６５９・・・（２）で検証
１ペア１ヒット・１９２、９２１・・・（３）で検証
２ペア・・・・・１２９、１６３、５２３・・・（４）で検証
２ヒット・・・・３５２、５３２、３６１、６３１・・・（５）で検証
１ペア・・・・・１６９、５２９、６５３、５６３・・・（６）で検証
１ヒット・・・・９６１、６９１、５９２、９５２・・・（７）で検証
（１）「１３２」評価１ペア２ヒットは、３や２の場所が正しいと仮定すると矛盾が生じるので１の場所が確定となり、次の５手で終了。
（２）「５６９」評価なしは、必然的に数字が確定し、１２３、１３２、３２１のいずれかとなる。５手目１２３なら終了。５手目１３２ならば次の６手目で終了。３２１も同様に６手。
（３）「１９２」評価１ペア１ヒットは、１の場所が正しいと仮定すると１２３か１６９、９の場所が正しいと仮定するとと６９１、２の場所が正しいと仮定すると９５２をそれぞれ検証しなければならない。５手目１２３なら終了。５手目１６９とし、評価１ペアを踏まえれば１の場所が確定するので１２３が導け、６手。５手目６９１とし、評価１ヒットを踏まえると９は使わないことが分かり、４手目から１の場所も確定するので１２３が導け６手。５手目９５２とし、評価１ヒットを踏まえると２の場所が確定し１２３が導け６手である。従って（３）の上限は６手。
（４）「１２９」評価２ペアは、１と２が正しいと仮定すると５手目１２３で終了となるが、１と９が正しいと仮定すると１６９、２と９が正しいと仮定すると５２９をそれぞれ検証しなければならない。５手目１６９とし、評価１ペアを踏まえると２の場所が確定するが、まだ１２３と５２９の検証が必要となり、７手かかる。５手目５２９としても、同様に７手かかる。従って（４）の上限は７手。
（５）「３５２」評価２ヒットは、１と３が正しいと仮定すると１２３、３と５が正しいと仮定すると５６３、２と５が正しいと仮定すると５２９をそれぞれ検証しなければならない。５手目１２３なら終了。５手目５６３とし、評価１ペアなら２の場所が確定するが、まだ１２３と５２９のの検証が必要となり、７手かかる。５手目５２９としても、同様に７手かかる。従って（５）の上限は７手。
（６）「１６９」評価１ペアは、１が正しいと仮定すると１２３か１３２、６が正しいと仮定すると５６３、９が正しいと仮定すると５２９をそれぞれ検証しなければならない。５手目１２３なら終了。５手目１３２とし、評価１ペア２ヒットなら（１）より６手。５手目５６３とし、評価１ペアを踏まえると６が正しいことはありえなくなるが、まだ１２３と５２９の検証が必要となり、７手かかる。５手目５２９としても、同様に７手かかる。従って（６）の上限は７手。
（７）「９６１」評価１ヒットは、１が正しいと仮定すると１２３か１３２、６が正しいと仮定すると６５３、９が正しいと仮定すると５２９と５９２をそれぞれ検証しなければならない。５手目１２３なら終了。５手目１３２とし、評価１ペア２ヒットなら（１）より６手。５手目６５３とし、評価１ペアを踏まえると５や６が正しいことはありえなくなり、１２３が確定し６手。５手目５２９とし、評価１ペアを踏まえると５と９が正しいことはありえなくなり、１２３が確定し６手。５手目５９２とし、評価１ヒットを踏まえると、９が正しいことはありえないが、２が正しいと仮定すると１２３、６が正しいと仮定すると６５３の２択となるので、７手。従って（７）の上限は７手。
以上より、「なし」の場合の上限は７手であると言える。

同数だった２ヒット、１ペア、１ヒットが、計ったようにピッタリ上限７手で収束しました。２ペアも７手だったのは意外でしたが、試しに他の数字でも検証してみたところ、６～７手でピッタリと終えることができるようです。「上限収束仮説」様々ですな。３手目の博打がどう影響したかは分かりませんが、４分の１の確率で５手以内で終われますし、４分の３の場合でも７手ならそれほど遅れた印象もないでしょう。つーか５年前に感じていたそのままですしね。もちろん、「悪手仮説」を用いたアルゴリズムの結果が７手だったと言うだけで、もしかしたらもっと良い手段があっていつでも６手で終われる可能性も排除できていませんが・・・「２手目あえて遠回り仮説」も検証の必要があるのかな？
ここで、確かめの意味も込めて「３手目１ヒットの場合」も軽く扱ってみたいと思います。
例えば１手目「４１５」評価１ヒット、２手目「２４６」評価１ヒット、３手目「３７４」評価１ヒットは、再々使用していた４を使わないことだけでなく、今まで一度も使っていない８９も使用しないことがもう確定できるので、３手目「なし」よりも条件が良くなりそうです。即ち、４手目は１か５、２か６、３か７の組み合わせを、場所の制約も踏まえて選んだ１６通りに絞られ、一応場合分けすると評価「１ペア」のグループが最も多くなりますが、やはりその結果を踏まえた検証候補が「なし」の場合と同様３～４つに絞られるので、いずれも７手までで十分答えられ、上限は７手だと結論付けても問題ないことを確認しました。

総括してみると、「９種類３桁の数字当てゲームはいかなる場合でも上限７手で終えることができる」ことになり、これが８手以上かかった場合は、明らかに遠回りをしたなどの悪手を打っていると断言できるわけです。「１ヒット→１ヒット→なし→１ヒット→１ヒット→１ペア」という、６手目まではっきり言って考え得る最悪の絶望的な運を辿ったとしても（笑）最初から筋道を立てて考えていれば必ず７手目に「３ペア」にできるということですね。

さて、最後はいよいよ完結編、１０種類４桁です。今回だけで１万文字弱ですし、さらに１０倍の組み合わせがあるわけですが、冬休み中に果たして更新できるのか！？（笑）


＜後述＞
１０種類４桁の検証原稿は書いていますがどうも簡単に行かなさそうな気配があるので、このシリーズの次回更新は未定です。