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

５年前にやったネタですが、今年再び教室で流行らせたので（笑）マジメに考察してみようと思います。
先に断っておきますが、この更新では答えは出ていませんし、今後出る保証もありません(笑）

ちなみにルールは以下の通りです。
①親が０～９の中から４桁の数字を予め決める。（同じ数字はなし、千の位０もあり）
②子がその数字を予想して当てる。
③親は、数字があっていればヒット、数字と場所があっていればペアと言う。
④１０回目までに４ペアにできれば子の勝ち。

最初は１５回ぐらいかかっていた子ども達も、慣れてきたのか結構早く当てられるようになってきました。１０種類の中から順列組み合わせて４桁ですから、これ無作為にやると最悪５０４０手もかかるのですよね（笑）しかし、１回１回ヒントを吟味にしていくことで、体感で１０手ぐらいなら５分５分の勝率になるようです。運が良いと５０４０分の１の確率で１手で４ペア揃い終了となるわけですが、もし運が最悪の場合でも、ちゃんと考えて最善を尽くしたら理論上何手までで終了できるか、その上限はおそらく存在するはずです。この場合の上限とは、期待値ではなく「最も答えにくい評価を与えられ続けた場合に最善を尽くした最短手」なので、ひょっとしたら１０手よりも相当かかってしまうのかもしれません。

例えば正解が０１２３の時、子が１２３０と言ったとします。
これは４ヒットとなり、１手目としては最上位級のラッキーな現象です。
しかし、場所の手がかりが「今の場所ではない」という情報しかないので、場所を確定させるのにはどうしてもあと３つの場所を１つずつ試す必要があり、初手も合わせて上限は４手と言うことになります。期待値で言うと平均３手で当たりますが、いくら理詰めでやっても運が悪いと４手かかる場合は、やはり上限は４手だと言わざるを得ません。ちなみに１手目４ヒットが起きる確率は千に一つ程度ですから、そんなラッキーが起きても４手はかかってしまうわけです。このゲームを４手で終了できた場合は「よく考えたね」と褒めるより宝くじを買いに行くことをお勧めするでしょう（笑）ましてや初手が「１ヒット」だとしたら、その後かなり苦戦を強いられることは経験上誰もが思うところですね。もしかしたら最悪で１５手くらいかかってしまうのかもしれません。５０４０通りの数を１５回も選ぶ作業の検証なんて、コンピューターでも使わない限り無理ですね(笑）まあ、上限が４手だと確認できたので、もし１手目に４ヒットが出たのに５手もかかるのは「あなたは最善を尽くしていない」と断言できるわけですけど。
そこで、何か良い方法はないか、この冬休みに少しずつ最短手数を考えてみることにしました。
まずはゲーム性を整理してみることにします。

＜ゲーム性の理解＞
・選ばれる数の種類・・・１０通り（０１２３４５６７８９）
・正解の数の桁・・・４桁
・同じ数字は使わない。千の位が０もアリ。
・１手目の順列組み合わせ・・・１０Ｐ４（パーミテーション１０の４）＝５０４０通り
・１手ごとに選んだ４桁の数に対して、数字と場所が合えば１ペア、場所は違うが数字が使用されていれば１ヒットとし、「１ペア１ヒット」などの評価が与えられる。（言い方は一様でなく、地域によってイート、バイトなどと表現することもあるが評価の意味は同じ）
・最終的に、最短で４ペアを目指すゲームである。
・この場合の最短とは「運が最悪を辿った場合、最善を尽くした手数の上限」である。
・無作為に行くと５０４０手かかるが、これは上限ではない。
・与えられた評価を参考にし、次の手に最善を尽くすことが重要であると考える。
・例えば１手目で４ヒットなら、２手目以降に他の数字を試す必要はなく、上限は４手である。ただしこれはかなりラッキーで、早い部類だと考えられる。
・０を使わない９種類、３桁の場合でも初手５０４通りもあり、検証が難しい。
・半分の５種類、２桁なら初手２０通りなのでいけるかも？
・とりあえず、もっと極端に減らして法則をつかむことを優先する。

＜例１＞
２種類（０１）、正解２桁、「０１」の場合（ゲーム性が存在する最もシンプルな条件での検証）
◎１手目の組み合わせは、０１か１０の２通りしかない。
（１）運が良く１手目０１ならば２ペアとなり、１手で終了。
（２）運が悪く１手目１０ならば２ヒットとなり、次の２手目で０１が導ける。
即ち、組み合わせが２通りの場合の上限は２手である。

＜例２＞
３種類（０１２）、正解２桁、「０１」の場合（総当りで検証）
◎１手目の組み合わせは、０１　１０　０２　２１　１２　２０　の６通り　
（１）１手目０１ならば２ペアとなり、１手で終了。
（２）１手目１０ならば２ヒットとなり、２は使用しないことが分かり、次の２手目で０１が導ける。
（３）１手目０２ならば１ペアとなり、残った１の使用が確定する。
　また０か２のどちらかの場所は確定しているので、２手目は０１か１２の２通りとなる。
　即ち、３手かかる。※＜例１＞より
（４）１手目２１ならば１ペアとなり、残った０の使用が確定する。
　また２か１のどちらかの場所は確定しているので、２手目は０１か２０の２通りとなる。
　即ち、３手かかる。
（５）１手目１２ならば１ヒットとなり、その瞬間０の使用が確定する。
　また１か２のどちらかが逆なので、２手目は０１か２０の２通り。
　即ち、３手かかる。
（６）１手目２０ならば１ヒットとなり、その瞬間１の使用が確定する。
　また２か０のどちらかが逆なので、２手目は０１か１０の２通り。
　即ち、３手かかる。
　よって、上限は３手である。

１手目はどうしても無作為に行くしかありませんが、その結果を踏まえて２手目からは任意に数字を選ぶことで、どんな場合でも少なくとも３手で終われる事が分かりました。
しかも、１手目の結果が同じ評価の場合、２手目は数字が違うだけでその考え方は全く一緒であることも分かりました。
これは、数をＡ、Ｂ、Ｃとし、正解の１桁目をＭ、２桁目をＮとした場合、例えばＭ＝Ａ（１ペア評価）ならばＭ≠Ｂ、Ｃなので、ＢもＣも差がないためだと考えられます。
そこで、次はもう１種類だけ増やし、評価ごとに場合分けして考えることにします。

＜例３＞
４種類（０１２３）、正解２桁、「０１」の場合（評価ごとの場合分けで検証）
◎１手目の組み合わせ・・・１２通り
０１　２ペア（１手で終了）
１０　２ヒット・・・（１）で検証
２３　　なし・・・（２）で検証
３２　　なし
０２　１ペア・・・（３）で検証　
０３　１ペア
２１　１ペア
３１　１ペア
１２　１ヒット・・・（４）で検証
１３　１ヒット
２０　１ヒット
３０　１ヒット
（１）２ヒットの場合
　並び方が違うだけなので、２手目で２ペアが確定する。即ち２手。
（２）なしの場合
　その瞬間残った２数字の使用が確定するが場所が不明なので、２手目は０１か１０の２通りとなり、３手。
（３）１ペアの場合・・・１手目は「０２」とし、評価１ペアを踏まえての２手目は次の１１通り
０１　２ペア（２手で終了）
１０　２ヒット・・・正解の逆並びだと分かるので、次の３手目で０１が導ける。
０３　１ペア・・・０の場所が確定する。何故なら、１手目の１ペアが２の方だった場合０は使わないことになり、０３も１ペアの結果に矛盾する。同時に２と３は使わないことが分かるので、次の３手目で０１が導ける。
２１　１ペア・・・同様に考えて１の場所が確定し、３手
３１　１ペア・・・同じ１ペアでも、今度は０２、１３のそれぞれどちらの場所を使用するか分からないので、４手。
２３　　なし・・・０と１の使用が確定する。同時に０の場所も確定するので、次の３手目で０１が導ける。
３２　　なし・・・同様に考えて３手
１２　１ヒット・・・０の場所が確定する。また１の使用も確定するので、次の３手目で０１が導ける。
１３　１ヒット・・・０の場所が確定する。しかし１と３のどちらを使用するか分からないので、４手。
２０　１ヒット・・・結局０か２のどちらが使われているか分からないので、３手目は他の数字で試すしかない。例えば２１なら４手、３１なら５手となり、明らかに手が遅くなる。
３０　１ヒット・・・０の場所が正しいと仮定すると２、３は使わないことになるので０１しかない。２の場所が正しいと仮定すると０は使わないことになり、２と３が１桁目に来てしまい矛盾。よって３手。

・・・ここまでやって、そろそろ心が折れてきました（笑）
１手目で１ペアだった数字はあと３つありますが、それぞれに対して２手目の１１通りをぶつけていくのは大変すぎます。そもそも、１手目０２の時点で１ペアが確定しているのに、それを無視して２手目に２０を選ぶ手は明らかに最善から遠ざかっていますよね。また、１手目に使わなかった２数（１３、３１）を２手目に選ぶ場合は４手かかり、これも全体で見ると１手マイナスとなっています。これらは囲碁・将棋で言う悪手ということになりますね。
　以上から、２手目は無作為でなく、最善の手を任意で選ぶ必要があることが分かります。
　まとめると、１手目に１場所が確定した場合は、そのどちらかの数を２手目に組み込むことで、最短３手で分かると言えるでしょう。遭えて遠回りする必要はないのですから。
というわけで、残りの０３、２１、３１の場合も、同様に考えれば全て３手以内であると考えられ、「１手目１ペアだった場合の上限は３手」だといえるでしょう。

（４）１ヒットの場合・・・１手目を「１２」とし、評価１ヒットを踏まえての２手目は次の１１通り
しかし、（３）の結果を踏まえ、いくつかの候補は手数が確定できる。
０１　２ペア（２手で終了）
１０　２ヒット（３手）
２３　　なし（３手）
３２　　なし（３手）
０２　１ペア（３手）
３１　１ペア（３手）
そして、次の３つの候補は手を遅らせることが確定なので、選ばないことで対処する。
０３　１ペア（４手）・・・初手で選ばなかった２数字は使用しない
３０　１ヒット（４手）・・・初手で選ばなかった２数字は使用しない
２１　１ペア（６手）・・・初手を並び替えただけの２数字は使用しない
そこで、残った２つについて検証する。
１３　１ヒット・・・初手１の数字を正しいと仮定すると、１の場所が決まり３と２は使わないことになるので０１しかない。初手２の数字を正しいと仮定すると、１は使わないことになり、２と３が２桁目に来てしまい矛盾。２手目３の数字を正しいと仮定すると、同様に矛盾。よって３手。
２０　１ヒット・・・２は使用しないことが分かるので、０１が確定する。よって３手。
以上から、最短３手であると言える。

１３、２０、３０の場合も、同様に考えれば３手であると言えるでしょう。
まとめると、１手目の結果を踏まえて明らかに手が遅くなる組み合わせを避けることで、この条件下での上限は３手であると言えます。手が遅くなる組み合わせとは以下の２つ。
・２手目に初手を並び替えただけの手
・２手目に初手で選ばなかった２数字を使った手
これら２つの悪手に共通する要素は、いずれも「２手目に正解の可能性が０の手」であると言えます。
ちなみに、この「悪手の法則」を無視し、例えば以下のような最悪を辿ると６手となってしまいます。
２０（１ヒット）→０２（１ペア）→１３（１ヒット）→３１（１ペア）→３２（なし）→０１（２ペア）
それでも無作為に選ぶ場合の最悪の１２手よりは早いですけど、こんな答え方をしていた子どもがいたら、流石に遠回りだろうと言わざるを得ません。まあ、数の種類や桁が増えると悪手だとはまだ断定できないので、一応現段階では「悪手の仮説」としておきますが、やはりゲームですから２手目も「当てに行く」姿勢が大切なのは直感的にも正しいのではないかと思います。
また、＜例２＞から数字の種類を１つ増やしたので上限は４手に増えるのかと思っていましたが、いつでも３手以内で答えられると分かったのは予想外でした。上限は種類に比例しているわけではなさそうです。残念・・・

次はもう少し種類増やすか、そろそろ桁を増やすか・・・どちらも大変そうだ(笑）