必勝法があるゲームを、あえて最強AIで出す

無限ぽこぽこは、ボタンを交互に押し合って最後の1個を押した人が負けというゲームです。見た目はかわいいのですが、中身はミゼール・ニムと呼ばれる、完全に解けている数学的なゲームです。

完全に解けている、というのは文字どおりの意味です。正しく打てば必ず勝てる手順が存在し、それは計算で求められます。運の要素はゼロです。

こういうゲームでAIをどう作るか。ここには設計上の分岐がありました。

手加減させるべきか

最初に考えたのは、難易度設定を用意することでした。「弱い・普通・強い」の3段階を作り、弱いモードではときどきわざと間違える。よくある作りです。

しかしこれには問題があります。プレイヤーが、自分が上手くなったのか相手がミスしただけなのか、区別できないのです。

必勝法のあるゲームで、相手がランダムに間違えるとします。すると勝敗は「相手が間違えたかどうか」で決まります。こちらが正しく打てたかどうかは、ほとんど結果に反映されません。学習のフィードバックとして機能しないわけです。

壁として置くことにした

そこで方針を変えました。COMは常に最善手を打つ。手加減は一切しない。

こうすると何が起きるか。負けたら必ず自分のミスになります。COMは絶対に間違えないので、こちらが1手でも外せば、そこで負けが確定します。

一見すると厳しすぎるようですが、実はこのほうが学習しやすいのです。負けた瞬間に「どこで間違えたのか」だけを考えればいい。相手のミスという雑音がないぶん、原因がはっきりします。

そして必勝法さえ理解すれば、二度と負けません。これは気持ちのいい体験です。

COMの思考：勝敗表を積み上げる

COMの実装は、公式を書き込むのではなく動的計画法で解いています。

考え方はこうです。「残りn個のとき、手番の人は勝てるか」を、n=0から順に積み上げていきます。

ある残り数から打てる全ての手を試す
 → ひとつでも「相手が負ける状態」に持ち込める手があれば、この残り数は勝ち
 → どう打っても「相手が勝つ状態」にしかならなければ、負け

コードにするとこうなります。

for (let r = minPick; r <= total; r++) {
  canWin[r] = false;
  const pickMax = Math.min(maxPick, r);
  for (let p = minPick; p <= pickMax; p++) {
    const after = r - p;
    if (after === 0) continue;      // 全部取る = 最後を取る = 負け
    if (!canWin[after]) {            // 相手を負けポジションに置ける
      canWin[r] = true;
      break;
    }
  }
}

この表さえあれば、COMは常に「相手が負ける残り数」を作る手を選ぶだけで済みます。

公式を書かなかった理由

このゲームの必勝法は、実は綺麗な形で書けます。1〜3個取れる場合なら、「残りを4で割って1余る数」で相手に渡せば勝ちです。

ではなぜ公式を書かなかったか。取れる個数の範囲がステージによって変わるからです。

ステージ	取れる数
1〜2	1〜2個
3〜6	1〜3個
7〜10	2〜4個
11以降	2〜5個

「1個から取れる」場合の公式は単純ですが、「2個以上取らなければならない」場合は話が変わります。1個だけ取って調整する、ということができなくなるからです。

実際、動的計画法で解いた結果を並べるとこうなります。

取れる数	手番が負ける残り数
1〜2個	1, 4, 7, 10, 13…（3で割って1余る）
1〜3個	1, 5, 9, 13, 17…（4で割って1余る）
2〜4個	1, 2, 7, 8, 13, 14…（6で割って1か2余る）
2〜5個	1, 2, 8, 9, 15, 16…（7で割って1か2余る）

「2個以上」になると、負けの数が2つずつペアで現れます。パターンが変わるのです。

公式を4つ書き分けることもできましたが、そうすると取れる個数の設定を変えるたびに公式を導き直す必要があります。動的計画法なら条件を渡すだけで正しい答えが出るので、パラメータをいじるのが怖くなくなりました。

汎用的な解法を1つ持っておくほうが、特殊解を並べるより安全です。

ミゼール（最後を取ったら負け）の落とし穴

普通のニムは「最後を取った人が勝ち」です。このゲームはその逆で、終盤の扱いが正反対になります。

実装で最も気をつけたのは、「全部取ってしまう手」を候補から必ず除外することでした。上のコードの if (after === 0) continue; がそれです。

残り3個で3個取れる場面を考えてください。普通のニムならこれが勝ち手です。しかしミゼールでは、取った瞬間に自分が最後を取ったことになり負けます。この1行を忘れると、AIの挙動が正反対になります。

もうひとつ、残りが最低取得数より少なくなったときの処理も必要でした。「2個以上取らなければならないのに残り1個」という状況では、その人は強制的に最後の1個を取ることになり、負けが確定します。この判定を入れておかないと、ゲームが進行不能になります。

手加減しない代わりに、選ばせる

COMを最強にすると、ひとつ深刻な問題が生じます。開始時の個数によっては、先攻の時点で負けが確定しているのです。

たとえばステージ8は32個スタート、2〜4個取れます。32は「6で割って2余る」ので、これは負けの数です。先攻を選んだ時点で、どう打っても勝てません。

そこで、先攻か後攻かをプレイヤーに選ばせることにしました。

これで公平性が保たれます。開始数が負けの数なら後攻を選べばいい。そうでなければ先攻を選べばいい。正しい手番を選び、正しく打てば、必ず勝てます。

ステージ	開始数	選ぶべき手番
1〜7	6〜28	先攻
8	32	後攻
9〜10	36・40	先攻
11	44	後攻
12〜14	48〜56	先攻

結果として、このゲームで本当に問われているのは最初の選択になりました。盤面を見て、取れる個数を確認して、自分がどちらを選ぶべきか判断する。ここが最大の考えどころです。

手加減するAIを作る代わりに、プレイヤーに正しく選ぶ権利を渡したというのが、この設計のいちばんの要点だと思っています。

盤面の形は完全な飾り

最後にひとつ、正直な話を。

このゲームには不定形のかわいい盤面がありますが、どのボタンを押すかは勝敗にまったく影響しません。隣接している必要すらなく、意味を持つのは「何個押したか」だけです。純粋なニムなので、当然といえば当然です。

では形は無意味かというと、そうでもありません。同じ32個でも、形が違えば別のステージに見えます。中身が数学的に同じでも、見た目が変われば人は違うものとして受け取る。

ステージ1〜4はきれいな長方形にしてルールの理解に集中してもらい、5以降は中央の2×2から広げた不定形の島にしています。意味のない変化にも意味があるというのが、作ってみて分かったことでした。

必勝法の詳しい手順は無限ぽこぽこのページに全部書いてあります。知ってしまうと勝ててしまうので、自力で解きたい方は先に遊んでみてください。