筆者は面倒くさいゲームが苦手であります。人から依頼されて「ヒット&ブロー」について、頭が回らないうえに気の染まない考察を行いますので、間違いにはご容赦いただきたい。
4つのポジションに割当てられた色を交互に推測するゲームです。6色から異なる4色をあらかじめランダムに割当された状態から開始します。4つ色と位置を先に当てれば勝ちです。
ゲームの仔細は他のサイトを参照されたい。
その依頼とは、勝つまでの最小ステップを問うものです。
ここでは「ヒット」の数xと「ブロー」の数yに着目することにします。
ヒットとは場所と色が同時正解であり、ブローとは場所が異なるが4つの場所のいずれかにその色が存在するわけです。
これをxHyBと略称します。まず、xとyの組み合わせを列挙します。
3H1Bは原理的にありえません。4Hはいきなり正解ということです。よって、3H0B以下を個別に検討していきます。また、0H0Bも0H1Bも起こりえないです。
11個のxHyBがあり得るので、それぞれのケースの起きうる組合せ数が手数の上限を与えます。合理的手数の上限というべきでしょう。
アプローチはxHyBにおける配置の数(組合せ数)をカウントする、です。最小ステップを求めるのではなく、xHyBにおける最大の配置数を見積もるのです。
これを上から順番に組合せ数をカウントします。
6色を青、赤、緑、黄、桃、白とし、 B, R, G, Y, P, Wと略記します。
正解を{B, R, G, Y}としても一般性を失いません。ただし、最初の手を下記に限定します。つまり、異なる4色を提示するのが最初の手とします。その結果、xHyBが判定された場合に限定する戦略での考察です。
備考:おそらく異なる4色を選択する手が一番情報量が多いはずですが、その証明はできていませんが最初の手についてすべての組み合わせを出し、その後、同じように場合分け組み合わせ数をカウントすることを繰り返せばいいのでしょうけれど。
1)3H0B
最初の異なる4色を提示して、判定が3H0Bになるのは、たとえば{〇, R, G, Y}の〇がPかWになるケースだけです。2通りあるわけです。一方、{B, R, G, Y}のどれか一つを〇にする選び方は4通り。
2×4=8通り
すなわち、4色以外の2色を順繰りに当てはめてゆけば、8手以内に全正解に行きつけるということです。
2)2H2B
{B, R, G, Y}のうち2色が正解なわけです。それが起きうるケースは4C2から6通りです。2BとなるのはPかWがセレクトされていることになります。2つの正解のポジションでPとWが置かれるケースは2ケースです。
よって、6×2=12通り
3)2H1B
先ほど同様、{B, R, G, Y}のうち2色が正解なわけです。それが起きうるケースは4C2から6通りです。
例えば、{B, R, XX, ZZ}と2Hしているならば、{B,R,Y,〇}もしくは{B,R,〇,G}の二パターンがあり、〇にはそれぞれPかWが入るだけです。
よって、6×2×2=24通り
4)2H0B
先ほど同様、{B, R, G, Y}のうち2色が正解なわけです。それが起きうるケースは4C2から6通りです。例えば、{B, R, XX, ZZ}と2Hしているならば、0BなのでG,Yが紛れ込んでいるわけです。{B, R, P, W}か{B, R, W,P}の2通りです。
よって、6×2=12通り
5)0H3B
三色は含有されている。仔細は略して、8×8=64通り
6)0H4B
ちょっと中抜きして、0H4Bを考えます。これは4色がすべて出揃っている状態です。B, R, G, Yという4色の組み合わせは正しいが{B, R, G, Y}の場所がすべて違うケースの数となる。{R,B,Y,G}のようなケースを数えるわけです。
Whitworthの定理の出番となる。
4!(1-1/1!+1/2!-1/3!+1/4!)=9通り
未完成であるが、以上の組合せ数を上記のテーブルに書き込む。
ここからゲームの戦略を考えてみる。xを増やす、次いでyを増やすのが基本方針であろう。
初回の結果は2H1Bだったとしよう。その時点で可能な色の配置は24通りである。この集合をAと呼ぼう。
次に、初回の入力と配置が重ならない入力を行う。そして、結果が2H0Bだったとしよう。ここで可能な色の配置は12通りであり、Bと集合を呼ぶとする。
その共通集合A∩Bには正解が含まれている可能性が高い。これを繰り返し、xを3まで上昇させる。
なお、初回にすべて異なる色を割り当てることを推奨する。なぜなら、得られる情報が最大であるからだ。
最適性戦略かどうかは不明だというのが実情であります。