前回作成した753ゲームはコンピュータ側の着手はランダムに選択していただけなので弱すぎました。今回はこれを改善します。
753ゲーム必勝法
実は753ゲームには必勝法が存在します。
これによるとつながっている未選択部分の個数を2進法に変換し、その排他的論理和の合計（以下「排他的論理和の合計」と書く）が0になるように選択すれば勝つことができるようです。もし自分の番になったときに「排他的論理和の合計」が0の場合は勝つことはできません。相手が正しく着手すれば必ず負けることになります。
では自分が着手したあと「排他的論理和の合計」が0になるようにするにはどうすればいいでしょうか？
まず「排他的論理和の合計」の1番左側の1になっている桁を確認します。そしてその桁と同じ桁のビットが立っているグループを探します。そこから選択します。もし該当する箇所が複数ある場合はそのなかのひとつを選びます。
どこから選択するかが決まったら何個を選択するのかを考えます。これはそれ以外のグループのビット毎の排他的論理和の合計を計算します。その数だけ残すように選択をすればよいのです。
例：
最初は7と5と3なので(7 ^ 5 ^ 3)を計算します。計算結果は1です。1番左側の1になっている桁は右から1桁目なので、7と5と3のなかから2進法に変換すると右から1桁目が1であるものを探します。実は7と5と3はいずれも条件に合致しています。そこでここでは7から選択することにします。
では7からいくつ選択すればいいのでしょうか？ 5と3の排他的論理和は6なので6個残るように選択します。つまり選択するのは1個だということです。
プレイヤーがミスしたらコンピュータ側を勝たせる
では前回のコードにそのようなアルゴリズムを組み込んでみましょう。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
function think(){ let groups = getUnselectedCellsGroups(); // 既出（前回の記事を参照） if(groups.length == 0){ // すでにセルはすべて選択されているかもしれない（プレイヤーの勝利） onPlayerWin(); return; } // 「排他的論理和の合計」を計算する let xor = 0; for(let i = 0; i < groups.length; i++) xor ^= groups[i].length; // 「排他的論理和の合計」が0でないなら勝つ手段が存在する // 0の場合はどうすることもできないので乱数を生成して適当に選ぶ let done = false; if(xor != 0) done = toWin(xor, groups); // 必勝法を採用 if(!done) random(groups); // 自力では勝てないので適当に着手する // コンピュータ側の着手ですべてのセルが選択されているかもしれない（コンピュータの勝利） groups = getUnselectedCellsGroups(); if(groups.length == 0){ onPlayerLose(); return; } $result.innerText = 'あなたの番です'; } |
コンピュータ側が勝つ着手をするtoWin関数を示します。上記のアルゴリズムで着手しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
function toWin(xor, groups){ for(let left = 2; left >= 0; left--){ // 1番左側の1になっている桁を確認 if ((xor >> left) & 1) { let xor2 = 0; let done = false; let from = null; // その桁と同じ桁のビットが立っているグループを探すとともに // それ以外のグループのビット毎の排他的論理和の合計を計算する for(let i = 0; i < groups.length; i++){ if(!done && (groups[i].length >> left) & 1){ done = true; from = groups[i]; continue; } else xor2 ^= groups[i].length; } if(from == null) return false; // 想定外の事態 // 選択するセルがわかったので選択する for(let i = 0; i < from.length - xor2; i++) from[i].children[0].remove(); return true; } } return false; // 想定外の事態 } |
random関数はコンピュータ側に勝つ手段がない場合にランダムな着手をさせるためのものです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
function random(groups){ let r = Math.floor(Math.random() * groups.length); let group = groups[r]; let start = Math.floor(Math.random() * group.length); let count = Math.floor(Math.random() * (group.length - start)) + 1; if(groups.length == 1) count = group.length; for(let i = 0; i < count; i++) group[start + i].children[0].remove(); } |
応用編
753だとパターン化するとすぐにどうすればいいかわかってしまうのでランダムに出題されるようなパズル形式にしてもよいと思います。たとえばこんなのはどうでしょうか？
