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

前回に引き続き、数字当てゲームの考察をしていきます。基本ルールは以下の通りです。
ちなみに、また結論先送りなので悪しからず(笑）

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

前回は、数字の種類が０～３の４種類、正解の桁が２桁までを検証し、最善を尽くせば少なくとも３手までに正解を導けることが証明できました。
また、２手目に正解の可能性がない手を選ぶことは悪手（遠回りになる）であるという仮説も生まれました。もう少し詳しく言えば、例えば１手目に選んだ２数の中に１つだけ正解の数字がある（１ペアまたは１ヒット）と評価されたのに、２手目でそれを並びかえただけの手や、初手で選ばなかった２数字を選ぶことを指します。これを「悪手仮説」と定義しましょう(笑）
そこで今回はもう一歩進め、０～４の５種類、正解の桁２桁を検証してみます。
これは初手２０通りなので何とか考え切れるだろう（笑）と言う安直な見込みと、最終的に求めたい１０種類４桁の丁度半分であることから、ゲーム性を探るのに一番良いと判断したためです。
ちなみに４種類２桁は初手１２通りでしたが、４種類３桁に発展させると初手２４通りと倍になってしまいます。桁を増やすのは難易度を倍増させると言えるでしょう。１０種類４桁は何と初手５０４０通り。先が思いやられますね・・・
（＜例１＞から＜例３＞を参照することがありますから、前回も合わせてご覧ください。）

＜例４＞
５種類（０１２３４）、正解２桁、「０１」の場合（評価ごとの場合分けで検証）
◎１手目の組み合わせ・・・２０通り
２ペア・・・・０１（１手で終了）
２ヒット・・・１０（２手で終了）
なし・・・・・２３、２４、３２、３４、４２、４３・・・（１）で検証
１ペア・・・・０２、０３、０４、２１、３１、４１・・・（２）で検証
１ヒット・・・１２、１３、１４、２０、３０、４０・・・（３）で検証
（１）なしの場合・・・初手２３とし、評価なしを踏まえての２手目は６通り。さらに評価で場合分けすると、
２ペア・・・・０１（２手で終了）
２ヒット・・・１０（３手で終了）
１ペア・・・・０４、４１（４手で終了）
１ヒット・・・１４、４０（４手で終了）
※前回＜例２＞で行った３種類、２桁の考察がそのまま当てはまる。
※初手２４、３２、３４、４２、４３についても＜例２＞と同様になるため、（１）の結論は上限４手である。
（２）１ペアの場合・・・初手０２とし、評価１ペアを踏まえての２手目は１９通りあるが、さらに「悪手仮説」を踏まえ、２手目に０か２はどこかに必ず使うことにすると、以下の１２通りに絞られる。
２ペア・・・・０１（２手で終了）
２ヒット・・・１０（３手で終了）
なし・・・・・２３、２４、３２、４２（４手で終了）※＜例２＞より
１ペア・・・・０３、０４、２１（以下の検証により４手以内で終了）
　０３の場合、０の場所が正しいと仮定すると０１か０４の２通りに絞れるので、４手。２の場所が正しいと仮定すると０は使わないことになり、２手目の３の場所と矛盾。よって４手。
　０４の場合、０３と同様に考えて４手。
　２１の場合、０の場所が正しいと仮定すると０１が確定し、３手。２の場所が正しいと仮定すると２手目の１の場所と矛盾。よって３手。
１ヒット・・・１２、３０、４０（以下の検証により４手以内で終了）
　１２の場合、０の場所が正しいと仮定すると０１が確定し、３手。２の場所が正しいと仮定すると２手目の２の場所と矛盾。よって３手。
　３０の場合、０の場所が正しいと仮定すると０１か０４の２通りに絞れるので、４手。２の場所が正しいと仮定すると０は使わないことになり、２手目の３の場所と矛盾。よって４手。
　４０の場合、３０同様に考えて４手。
※初手０３、０４、２１、３１、４１の場合も同様の考えを辿ることで、（２）の結論は上限４手であると言える。
（３）１ヒットの場合・・・初手１２とし、評価１ヒットを踏まえての２手目は１９通りあるが、さらに「悪手仮説」を踏まえ、２手目に１か２はどこかに必ず使うことにすると、以下の１２通りに絞られる。
２ペア・・・・０１（２手で終了）
２ヒット・・・１０（３手で終了）
なし・・・・・２３、２４、３２、４２（４手で終了）※＜例２＞より
１ペア・・・・０２、３１、４１（以下の検証により４手以内で終了）
　０２の場合、０の場所が正しいと仮定すると０１が確定し、３手。２の場所が正しいと仮定すると２手目の２の場所と矛盾。よって３手。
　３１の場合、３の場所が正しいとすると１は使わないことになり、１手目の２の場所と矛盾。１の場所が正しいとすると、０１か４１の２通りに絞れるので、４手。
　４１の場合、３１と同様に考えて４手。
１ヒット・・・２０、１３、１４（以下の検証により４手以内で終了）
　２０の場合、１の場所が正しいと仮定すると０１が確定する。２の場所が正しいと仮定すると２手目の０の場所と矛盾。よって３手。
　１３の場合、１の場所が正しいと仮定すると０１か０４の２通りに絞れるので、４手。２の場所が正しいと仮定すると１は使わないことになり、２手目の３の場所と矛盾。３の場所が正しいと仮定しても同様に矛盾。よって４手。
　１４の場合、１３と同様に考えて４手。
※初手１３、１４、２０、３０、４０の場合も同様の考えを辿ることで、（３）の結論は上限４手であると言える。
以上から、５種類２桁の場合の最短手数は４手である。

ここまでやると、何となく法則性が見えてきました。
検証中、同じような考えの文章を使い回していることからも察しが着くと思いますが、「悪手仮説」を用いると飛びぬけて困る結果は飛び出さず、実にすらすらと解法に向かうことができるのです。考える組み合わせを減らせたと言う利点も大きいですね。
あと、やはり運が良い場合は短くなりますが、運が悪い場合でも飛びぬけて手数がかかることはなく、大体同じ手数に集約することも分かってきました。まさに上限なのかもしれません。
つまり、運が最悪で「常に悪い評価」のみ考えていけば、他の「ちょっと良さそうな評価」は上限に集約するかそれ以内に収まり、最早考えるまでもないということです。これは検証の手間を大幅に減少させることができる発見です。
この場合の「運が悪い評価」は、「最も出やすい評価」と同義であると推測できます。
５種類２桁で言えば、初手なしが６通り、１ヒットが６通り、１ペアが６通りで、いずれも上限は４手でした。
４種類２桁の時は、＜例３＞の通り１ヒットが４通り、１ペアが４通りで、いずれも上限は３手でした。
このまま一般化するのはまだちょっと乱暴な気もしますが・・・
最終目標の１０種類４桁の場合、「最も出やすい評価」は１ヒットの１４４０通りになるようです。
まだまだ気が遠くなりますが（笑）初手の総数が５０４０通りだったことを思えば３分の１以下に減らせてますよね。

では次に、「悪手仮説」は本当に悪手だったのかも検証してみます。
例えば初手０２で１ペア、２手目でその２数を使わず１３で１ヒットという評価を得た場合を考えてみます。
４種類２桁の場合、３手目に０１か３２の判断がつかず４手となってしまうのは明らかに悪手でした。
しかし今回（５種類２桁）の場合、２手目で「４は使用しない」という裏の結果を得ることができるので、０１か３２に絞れたことは手が遅くなっていません。
例えば初手１２で１ヒット、２手目３０で１ヒットでも、同様に上限４手になります。
初手１２で１ヒット、２手目３４でなしだった場合も、０が確定できるので０１か２０に絞れ、４手です。
ただし、１手目に１ペアや１ヒットした２数字をいずれも使わないというのは、２手目で正解する可能性を確実に自ら潰しているので、悪くはならないにしても良くもならないことは間違いないでしょう。＜例４＞の考察のように「悪手仮説」を使用して手を選んだ場合、２手や３手で正解することも稀ですが可能でしたからね。期待値と言う意味ではやはり悪手だと言えると思います。今は上限を考えていますが、そもそも早く正解することがこのゲームの最大の目的なので、期待値は見逃せません。
もちろん、初手１２で１ヒットに対し、２手目で逆にしただけの２１では何も実りもなく大悪手です。「１手目に１数字の存在しか分からなかったのに、その数字を並び替える組み合わせ」だけは完全に除外して構わないでしょう。
これを１０種類４桁に応用すると、例えば１２３４で１ヒットだった場合、４３２１なんて手は大悪手で、５６７８は悪いとはいえないけど僅かに存在する２手目正解の可能性を逃していると判断できるので最善手ではなく、少なくとも例えば１の使用を仮定し５６７１などと攻めて行く姿勢が正解に近づく（期待値が高い）と考えられます。「でも１が正解かどうか判断できないのでは？」と思われるかもしれませんが、それは今後の評価の検証次第で何とでもなると言うのが自分の考えです。と言うか、自分がこのゲームをやる場合はいつもそういう攻め方をしますからね（笑）それでアベレージは７、８手ぐらいですから、飛びぬけて悪くならない「悪手仮説」を使えば、経験上１０手以内で行ける気もしてきました。

最終的には上限と種類や桁数に何らかの法則性を見出せると良いのですけど・・・今回の結果を踏まえると、種類が１増えると手数が１増えるというのはありそうですが、まだ何とも言えません。次はいよいよ桁を増やしてみるか・・・