tuneoの日記: 超久しぶりにあれげメモ:3桁のHit & Blowを俺の代わりに解くプログラム 6
ちょいとAndroidスマホ(というかタブレット)でゲームなんぞに手を出してしまいまして掲題のパズル?を解かないといけないのですが、いかんせん脳みそがすっかり衰えた(現役学生の頃なら余裕だったとも言えないのが悲しい)当方としては「こんなもん解いてられるか!第一、敵キャラはごりっごりにプログラムで推論してるのに、なんで俺が脳みそをすりへらさにゃならんのだ!」(答:そういうゲームだから)と、理不尽千万なことを考えて開発に着手しようと思い立った次第。
まずゲームのルールについて。このゲームは二人で遊ぶ。
1.先攻・後攻を決め、それぞれは0~9までの数字を三つ選んで一回ずつ使って3桁の数を考える。百の位が0になってもよいので「数」というとちょっと語弊があるのだが。
2.先攻側は後攻側に使っていない数字をひとつ提示してハンデを補う。
3.先攻側は後攻側の考えた数を推測して提示する。
4.後攻側は先攻側の考えた数がどれだけ自分の考えた正解に近いか、○hit, ○blowの形でヒントを出す。
hit:数字と桁が一致している。たとえば正解が314で先攻の提示した数が325だったら桁も数字も一致する3で1hit。
blow:先攻の考えた数には正解で使った数字が含まれているが、桁が違う。上記の例で、正解は同じだが先攻の提示した数が159だったら1は含まれているが桁が違うので1blowとなる。
hitとblowは同時に存在することがある。正解が314で提示された数字が415だったら、1が1hit、4が1blowで1hit, 1blowとなる。
3hitならゲーム終了。正解を提示した側の勝ち。
5.提示された数字が3hitでなければ、攻守交替で今度は後攻が先攻の考えた数を当てるために提示し、先攻はヒントを出す。以後どちらかに3hitが出るまで繰り返し。
どういうデータ構造を使うか。しょせん3桁の整数なんだからリストでもで十分なんだけど(h,j,i)とかいうリストをキーにした辞書のほうがいいのかな。うーむ、とりあえずは組んでみるか。
プログラムの流れとしては、どういう理屈でかは後で考えるとして表(or辞書)に各数の「正解っぽさ」(要は確率だな)を格納しておいて、最も高い候補を提示する(同じ確率の候補が存在した場合はランダムか、辞書順で最初か、選び方はいくつか考えられる)。それを俺がゲームのNPCに提示してお伺いを立て、hitとblowを返されたらプログラムに入力する。プログラムはこれまでに提示した候補とそれに対するhit & blowを元に、正解っぽさの表を更新して候補を提示というのを、3hitが出るまで繰り返す。
まずは絞り込みのために「こりゃサルでもわかるだろ」というケースを考える。以後簡単のためhitはh, blowはbと表記。
・3h0b(大当たり)
そのものズバリ100%でおしまい。
・0h3b(数字は三つ合ってるが並び順が違う)
組み合わせを変えて試行すればいい。勝ったも同然?三つの数字からなるそれぞれの候補は16.6%、それ以外は0%。
・0h0b(大ハズレ)
提示した三つの数字からなる六つの数(a,b,cがそれぞれ0~9の数字だとしてabc,acb,bac,bca,cab,cba)は心置きなく解の候補から除外できる。これらが正解である確率は0%。
で、後はblowとhitが入り乱れてる場合は今後の解析と検討を要する、という感じだな。
・0h1b
・0h2b
・1h0b
・1h1b
・1h2b
・2h0b
・2h1b
たぶん中学生の頃 (スコア:1)
それが小規模に流行って、授業中にこっそりやってました。
で、ゾロメを順番に投げてわかるパターンから割と少ない手順であてる方法がなんとなくわかってから負けなくなって。
だんだんやり方を真似されるようになってクラス内では飽和状態になってただ作業するか一発大穴狙うかしか選択肢が無くなり。
結果的に廃れてしまった思い出があったけど。
#今その方法は思い出せないケド・・・ orz
面白そうですね (スコア:1)
abcを除いた、残りの7つから3つを選択して作成した羅列が正解となりますから、可能性は7x6x5=210通り。
先攻初期状態で10x9x8=720通りに比べると、グッと減りますね。
2Hit1Blowについては、2ヶ所が桁、値ともに一致する場合、1Blowする自由度はなさそうです。
例:正解314で、3a4を提示する場合、a=1なら3Hit勝利。それ以外なら、2Hit0Blow。
Re:面白そうですね (スコア:1)
> もっとたくさん排除できると思います。
ご指摘のとおりです。
つーか、自分で解いてるときは分かってるのになんで文とかコードに落とし込むときにロジックが欠落するんだかorz。
触発されてしまった (スコア:1)
はじめに、基本戦略として、
相手に提示する記号列(チャレンジ記号列)は、現在の解候補記号列の集合から選択する。ヒントが得られる毎に、解候補記号列の集合から、ヒントと矛盾する記号列を除外する事で、正解に至る事を目指す。
チャレンジ記号列と正解記号列を照合すると、3桁各々について、{Hit, Blow, Miss} の3種類の状態があり得る。
例えば、チャレンジ記号列 cha を照合した各桁の結果が [Hit, Miss, Blow] だとして、これを満たす解候補記号列 may の条件は、定義通りにベタ書きすれば、
(cha[0] == may[0]) && (cha[1] != may[0] && cha[1] != may[1] && cha[1] != may[2]) && (cha[2] != may[2] && (cha[2] == may[0] || cha[2] == may[1])
である。含意関係を整理し、さらにルール上、異なる桁は等しい記号となり得ないため、
cha[0] == may[0] && cha[1] != may[2] && cha[2] == may[1]
と最適化できる。
このような、3桁の照合結果に対する解候補の妥当性判定処理を、ありうる照合結果全てに対して定義しておけば、あとはそれを随時呼び出すだけである。
これらは、3状態3桁なので高々3^3=27種類、そこからルール上あり得ない [B,H,H] といったパターン3つを除くと、24種類である。これならもう手書きできる。
さて、
相手から与えられるヒントには各桁の状態は含まれておらず、ただHitとBlowがそれぞれ幾つであったかのみが与えられる。
例えば、ヒントが"1Hit, 1Blow"と与えられた場合、想定されうる全ての状態は {[H,B,M], [H,M,B], [B,H,M], [B,M,H], [M,H,B], [M,B,H]} である。ちなみにこれは、状態の組み合わせが最も多くなるヒントである。
現在の解候補記号列の集合から、これら状態のいずれかと矛盾しない記号列のみを選択する事で、解候補を絞り込んでゆける。
材料は出そろった。あとはこれを実装すればよい。
Re:触発されてしまった (スコア:1)
上述の解候補の絞り込み処理を、JavaScriptで実装した。
var Hit = 0;
var Blow = 1;
var Miss = 2;
var pred = [[[], [], []], [[], [], []], [[], [], []]];
pred[Hit][Hit][Hit] = function(cha, may) { return cha[0] == may[0] && cha[1] == may[1] && cha[2] == may[2]; };
pred[Hit][Hit][Blow] = function(cha, may) { return null; };
pred[Hit][Hit][Miss] = function(cha, may) { return cha[0] == may[0] && cha[1] == may[1] && cha[2] != may[2]; };
pred[Hit][Blow][Hit] = function(cha, may) { return null; };
pred[Hit][Blow][Blow] = function(cha, may) { return cha[0] == may[0] && cha[1] == may[2] && cha[2] == may[1]; };
pred[Hit][Blow][Miss] = function(cha, may) { return cha[0] == may[0] && cha[1] == may[2] && cha[2] != may[1]; };
pred[Hit][Miss][Hit] = function(cha, may) { return cha[0] == may[0] && cha[1] != may[1] && cha[2] == may[2]; };
pred[Hit][Miss][Blow] = function(cha, may) { return cha[0] == may[0] && cha[1] != may[2] && cha[2] == may[1]; };
pred[Hit][Miss][Miss] = function(cha, may) { return cha[0] == may[0] && cha[1] != may[1] && cha[1] != may[2] && cha[2] != may[1] && cha[2] != may[2]; };
pred[Blow][Hit][Hit] = function(cha, may) { return null; };
pred[Blow][Hit][Blow] = function(cha, may) { return cha[0] == may[2] && cha[1] == may[1] && cha[2] == may[0]; };
pred[Blow][Hit][Miss] = function(cha, may) { return cha[0] == may[2] && cha[1] == may[1] && cha[2] != may[0]; };
pred[Blow][Blow][Hit] = function(cha, may) { return cha[0] == may[1] && cha[1] == may[0] && cha[2] == may[2]; };
pred[Blow][Blow][Blow] = function(cha, may) { return (cha[0] == may[1] || cha[0] == may[2]) && (cha[1] == may[0] || cha[1] == may[2]) && (cha[2] == may[0] || cha[2] == may[1]); };
pred[Blow][Blow][Miss] = function(cha, may) { return (cha[0] == may[1] || cha[0] == may[2]) && (cha[1] == may[0] || cha[1] == may[2]) && cha[2] != may[0] && cha[2] != may[1] && cha[2] != may[2]; };
pred[Blow][Miss][Hit] = function(cha, may) { return cha[0] == may[1] && cha[1] != may[0] && cha[2] == may[2]; };
pred[Blow][Miss][Blow] = function(cha, may) { return (cha[0] == may[1] || cha[0] == may[2]) && cha[1] != may[0] && cha[1] != may[1] && cha[1] != may[2] && (cha[2] == may[0] || cha[2] == may[1]); };
pred[Blow][Miss][Miss] = function(cha, may) { return (cha[0] == may[1] || cha[0] == may[2]) && cha[1] != may[0] && cha[1] != may[1] && cha[1] != may[2] && cha[2] != may[0] && cha[2] != may[1] && cha[2] != may[2]; };
pred[Miss][Hit][Hit] = function(cha, may) { return cha[0] != may[0] && cha[1] == may[1] && cha[2] == may[2]; };
pred[Miss][Hit][Blow] = function(cha, may) { return cha[0] != may[2] && cha[1] == may[1] && cha[2] == may[0]; };
pred[Miss][Hit][Miss] = function(cha, may) { return cha[0] != may[0] && cha[0] != may[2] && cha[1] == may[1] && cha[2] != may[0] && cha[2] != may[2]; };
pred[Miss][Blow][Hit] = function(cha, may) { return cha[0] != may[1] && cha[1] == may[0] && cha[2] == may[2]; };
pred[Miss][Blow][Blow] = function(cha, may) { return cha[0] != may[0] && cha[0] != may[1] && cha[0] != may[2] && (cha[1] == may[0] || cha[1] == may[2]) && (cha[2] == may[0] || cha[2] == may[1]); };
pred[Miss][Blow][Miss] = function(cha, may) { return cha[0] != may[0] && cha[0] != may[1] && cha[0] != may[2] && (cha[1] == may[0] || cha[1] == may[2]) && cha[2] != may[0] && cha[2] != may[1] && cha[2] != may[2]; };
pred[Miss][Miss][Hit] = function(cha, may) { return cha[0] != may[0] && cha[0] != may[1] && cha[1] != may[0] && cha[1] != may[1] && cha[2] == may[2]; };
pred[Miss]
Re:触発されてしまった (スコア:1)
ぶはっ。
> と < を間違えた。おかげでコメント部分がお目汚しです。すまぬ…