「CPUの相手」を作り込む:ランダムから先読みまで

1. 3 段階の違いを先に整理する

3 つの段階で変わるのは「手を選ぶとき、何を見るか」だけです。

• 1 ランダム、見るもの：置ける手の一覧だけ、手の選び方：一覧から無作為に選ぶ、向いている役割：入門。ルールの確認相手
• 2 一手先、見るもの：自分の一手の直後の盤面、手の選び方：直後の評価が最もよい手、向いている役割：中級。目先の得は逃さない相手
• 3 先読み、見るもの：相手の返しも含む数手先、手の選び方：相手が最善を返す前提で最良の手、向いている役割：上級。罠にかかりにくい相手

段階 2 と 3 の差は、相手の返しを考えるかどうかです。段階 2 は、目先で得でも次に取り返される手を平気で選びます。段階 3 は、相手の返しを織り込みます。この「相手は自分に不利な手を選ぶ」という前提で最良の手を探す方法を、ミニマックス法と呼びます。

アソバースの公式作品では、「潮目のオセロ」と「灯りのチェス」が 3 段階の相手を用意しています。段階の中身は公開情報からは分かりません。作品を開いて段階ごとに打ち比べ、どこで差を感じるか確かめてみてください。この記事のコードを書く前に一度触っておくと、各段階に何を期待するかが見えてきます。

2. 手順 0:ルールを 3 つの関数に切り分ける

CPU を書く前に、ゲームのルールを CPU から呼べる形に整えます。必要なのは次の 3 つです。

• 今の盤面で打てる手の一覧を返す関数
• 盤面に手を適用して、次の盤面を返す関数（元の盤面は壊さない）
• 終局かどうかを返す関数

この切り分けができていれば、CPU は盤面の中身を知らなくて済みます。例題には「15 個の石の山から 1〜3 個ずつ取り合い、最後の石を取った側が勝ち」というゲームを使います。ルールが短く、先読みの効果が分かりやすいからです。

以降のコードは、上から順に 1 つのファイルへ貼れば単独で動きます。Node.js でもブラウザのコンソールでも実行できます。

const game = {
  moves: (s) => [1, 2, 3].filter((n) => n <= s.left),
  apply: (s, m) => ({ left: s.left - m, turn: 1 - s.turn }),
  over: (s) => s.left === 0,
};
function evaluate(s, me) {
  if (!game.over(s)) return 0;
  return 1 - s.turn === me ? 1 : -1;
}

turn は 0 か 1 で、手番の側を表します。evaluate は「自分から見た盤面の点数」を返す関数です。終局で勝ちなら 1、負けなら -1、決着がついていなければ 0 とします。最後の石を取った側は、その手で手番が相手に移っているので、1 - s.turn が勝者です。

自分のゲームに移すときは、この evaluate を書き換えます。オセロなら石の数の差、チェスなら駒の価値の合計などが出発点になります。

3. 手順 1〜3:手を選ぶ関数を 3 段階で書く

3 段階を、一つの関数 pickMove にまとめます。まず先読み用の search を用意します。

1. search(s, depth, me) を書きます。終局か、読む深さが 0 になったら evaluate を返します。
2. それ以外は、打てる手を一つずつ適用して search を再帰で呼び、点数の一覧を作ります。
3. 手番が自分なら最大値を、相手なら最小値を返します。相手は自分に最も不利な手を選ぶ、という前提です。

function search(s, depth, me) {
  if (game.over(s) || depth === 0) return evaluate(s, me);
  const vals = game.moves(s).map((m) => search(game.apply(s, m), depth - 1, me));
  return s.turn === me ? Math.max(...vals) : Math.min(...vals);
}

次に pickMove を書きます。段階 1 は無作為に選ぶだけです。段階 2 と 3 は、各手を適用した後の盤面に search で点数をつけ、最高点の手から選びます。

function pickMove(s, level, depth = 20) {
  const ms = game.moves(s), me = s.turn;
  const rnd = (a) => a[Math.floor(Math.random() * a.length)];
  if (level === 1) return rnd(ms);
  const d = level === 2 ? 1 : depth;
  const scored = ms.map((m) => ({ m, v: search(game.apply(s, m), d - 1, me) }));
  const best = Math.max(...scored.map((x) => x.v));
  return rnd(scored.filter((x) => x.v === best)).m;
}

段階 2 と 3 の違いは、d の値だけです。段階 2 は d = 1 なので、search は一手指した直後の evaluate をそのまま返します。段階 3 は d が大きいので、相手の返しの先まで読みます。

同点の手が複数あるときは、無作為に選びます。最初に見つかった手を固定で選ぶと、同じ局面で毎回同じ手を返す単調な相手になります。

4. 手順 4:段階同士を戦わせて強さを測る

書いた段階が本当に強い順に並んでいるかは、CPU 同士を対戦させて確かめます。

function play(levelA, levelB) {
  let s = { left: 15, turn: 0 };
  while (!game.over(s)) {
    const level = s.turn === 0 ? levelA : levelB;
    s = game.apply(s, pickMove(s, level));
  }
  return 1 - s.turn; // 勝者(0か1)
}
function tally(a, b, n = 200) {
  let aWins = 0;
  for (let i = 0; i < n; i++) {
    if (i % 2 === 0) { if (play(a, b) === 0) aWins++; }
    else if (play(b, a) === 1) aWins++;
  }
  return aWins / n;
}
console.log(tally(2, 1), tally(3, 2), tally(3, 1));

tally(a, b) は、段階 a が段階 b に勝った割合を返します。記録の取り方は次のとおりです。

• 単位:1 つの組み合わせにつき 200 戦（n で変更できます）。
• 先手と後手:交互に入れ替えます。このゲームは先手が有利になる可能性が高く、固定すると段階の差と先手の差が混ざるためです。
• 回数:乱数を使うので、同じ組み合わせを 2〜3 回繰り返し、数字がどれくらいぶれるかも見ておきます。

結果は次の基準で読みます。

• 段階 2 が段階 1 に勝ち越し、段階 3 が段階 2 に勝ち越していれば、段階が強さの順に並んでいます。
• 差がほとんど出ないなら、その段階の evaluate が弱いか、読む深さが足りないかのどちらかです。
• 段階 3 同士の対戦（tally(3, 3)）も試してみてください。両方が最善に近いとき、勝敗が先手・後手のどちらかに偏るなら、ゲーム自体の有利不利が出ています。

このゲームで読み深さを pickMove(s, 3, 5) のように浅くするとどうなるかも、ぜひ試してください。先が見えない手はすべて同じ 0 点になるので、段階 3 の強さが段階 1 に近づくはずです。確かめるのは読者の手元です。

5. 実際のゲームに移すときの落とし穴

例題を自分のゲームに移すとき、つまずきやすい点が 4 つあります。

評価関数が段階 3 の強さを決める

例題は終局まで読み切れるので、評価は勝ち・負けだけで足ります。オセロやチェスは終局まで読めないため、途中の盤面に点をつけます。ここが雑だと、深く読んでも強くなりません。まずは石の差や駒の価値などの単純な式から始めて、段階 2 と 3 の勝率差で改善を確かめます。

読む深さは、待たせてよい時間で決める

深さを 1 増やすと、探索する局面数は手の選択肢の数だけ増えます。ブラウザで動かす以上、プレイヤーを長く待たせるわけにはいきません。「灯りのチェス」は CPU の思考時間を約 450ms に制限しています。自分のゲームでも、最初に待たせてよい時間を決め、その範囲に収まる深さを選ぶのが現実的です。

パスや連続手番を扱えるようにする

ゲームによっては、打てる手がなく手番が飛ぶことがあります。「潮目のオセロ」では、置けない手番は自動でパスになります。moves が空のとき、Math.max() は空の配列に対して -Infinity を返します。search の中で「手がなければ手番だけ交代して続ける」処理を足しておかないと、先読みが止まります。

段階を「強さ」だけで決めない

初心者向けの段階は、弱いだけでなく「負けても納得できる」相手にしたいところです。段階 3 の最高点の手を、たまに 2 番目の手に差し替える方法もあります。ただし、わざとの悪手は不自然に見えます。段階の差は、まず読む深さと評価の細かさで作り、そのうえで調整します。

次の行動

まず上のコードを貼って実行し、tally(2, 1)、tally(3, 2)、tally(3, 1) の数字を確かめてください。次に、同じ 3 関数の切り分けで自分のゲームの moves・apply・over を書き、evaluate を最も単純な式で入れてみます。仕上げに「潮目のオセロ」か「灯りのチェス」で 3 段階を打ち比べ、自分のゲームの段階に何を期待するかを決めておくと、作り込みの方向がはっきりします。