先読みはどこで打ち切るか：ミニマックスを3手で体験する

3手先の木を描く

自分が打ち、相手が打ち、また自分が打つ場面を考えてみます。これが3手先読みです。各局面で打てる手は2つとします。

次の図で、「葉」は3手先まで進んだ局面です。「粗い評価」は、それ以上読み進めずに局面の見た目だけで付ける点数です。駒の数や角の取得など、手軽に数えられるものから作る点数を想像してください。

根（自分の手番）
├─ A　粗い評価 6
│   ├─ Aa　粗い評価 5
│   │   ├─ 葉 3
│   │   └─ 葉 5
│   └─ Ab　粗い評価 2
│       ├─ 葉 2
│       └─ 葉 4
└─ B　粗い評価 5
    ├─ Ba　粗い評価 3
    │   ├─ 葉 6
    │   └─ 葉 6
    └─ Bb　粗い評価 4
        ├─ 葉 7
        └─ 葉 1

根から見て、Aを選ぶかBを選ぶかが今の問題です。下から順に点数を戻します。

1. Aa、Ab、Ba、Bbは自分の手番なので、子の葉のうち大きいほうを取ります。Aaは5、Abは4、Baは6、Bbは7です。
2. AとBは相手の手番なので、子のうち小さいほうを取ります。Aは4、Bは6です。
3. 根は自分の手番なので、大きいほうのBを選びます。

Bbの葉7は魅力的に見えますが、Bを選ぶと相手がBaへ進めてBbを避けるので、実際に得られるのは6です。ミニマックスは「相手が自分に不利な手を選ぶ」前提で点数を戻すので、こうした期待外れを織り込めます。

打ち切る深さで、選ぶ手が変わる

同じ木を、読む深さだけ変えて評価してみます。深さ1は自分の手の直後で止めて粗い評価を使い、深さ2は相手の応手まで読んで止めます。

• 1手、評価に使う層：A、Bの粗い評価、Aの点数：6、Bの点数：5、選ぶ手：A
• 2手、評価に使う層：Aa、Ab、Ba、Bbの粗い評価を相手が最小化、Aの点数：2、Bの点数：3、選ぶ手：B
• 3手、評価に使う層：葉を自分が最大化、相手が最小化、Aの点数：4、Bの点数：6、選ぶ手：B

深さ1ではAが良く見えますが、相手の応手を1つ読むとAbの2が見えてAは悪い手に変わります。この木では、浅い読みの結論が深い読みで覆っています。深さを増やしたら結論がどう動くかを見ることが、打ち切り位置を考える出発点になります。

一方で、深さ2と3は同じ結論です。深さを足しても選ぶ手が変わらない局面では、追加の読みは時間を使うだけで、強さに寄与しません。ただし、どの局面でそうなるかは、読み終えてからでないと分かりません。

浅く打ち切ると、もう一つ起こりやすい失敗があります。駒を取った直後の局面で止めると、取り返される手が読みの外に出て、有利に見えてしまいます。読みの末端が交換の途中だと、評価が当てにならなくなります。これはよく知られた現象で、「水平線効果」と呼ばれます。

なぜ無限には読めないのか

この木は小さいので、3手先でも局面は8個で済みます。実際のゲームでは、1局面で打てる手の数（分岐数）が大きく、深さとともに急増します。

一般に、チェスは1局面で30手前後、オセロは10手前後といわれることが多いです。ここでは分岐数30で計算してみます。

• 1手、末端の局面数（30の深さ乗）：30
• 2手、末端の局面数（30の深さ乗）：900
• 3手、末端の局面数（30の深さ乗）：27,000
• 4手、末端の局面数（30の深さ乗）：810,000

1手深くするたびに、読む局面は分岐数倍になります。この増え方では、深さを1つ足す価値と時間のコストが釣り合わなくなる地点が必ず来ます。打ち切りは手抜きではなく、返事を待たせない対戦ゲームでは不可欠な設計判断です。

なお、深さの打ち切りとは別に、「結果を変えない枝は読まない」アルファベータ法という枝刈りがあります。打ち切りは読む範囲そのものを狭めるので結論が変わりえますが、枝刈りは結論を保ったまま読む量を減らします。二つは別の道具として使い分けます。

打ち切りの基準は何にするか

打ち切りの基準には、おもに三つの選択肢があります。

• 深さで決める：常に3手など固定します。実装は簡単ですが、局面によって読む量が大きく変わります。
• 時間で決める：決めた時間までは1手ずつ深さを増やしながら読み、時間が来たら最後に読み終えた深さの結論を使います。
• 局面の静けさで決める：駒の取り合いの途中なら、もう少し読んでから止めます。水平線効果への対策になります。

アソバースの「灯りのチェス」の案内には、CPUの思考時間が約450msに制限されていることが書かれています。設計から読み取れるのは、CPUが際限なく読み続けず、短い待ち時間で返す前提で作られているということです。

一方、その中身が「固定の深さ」なのか「時間までの段階的な深掘り」なのかは、確認済みの案内には含まれていません。3段階の相手の違いが、読みの深さの差なのか、評価の粗さや手の選び方の差なのかも同様です。この部分は作品を開いて確かめることになります。判定エンジンとしてchess.jsが同梱されていることは分かっていますが、それは手の合法性や終局の判定を担う部品であり、CPUの読み方そのものを説明するものではありません。

「潮目のオセロ」にも3段階の相手があり、返る石のプレビューと理由付きヒントがあります。プレビューは、1手先の結果を目で見えるようにする機能です。理由付きヒントがどんな観点で手を勧めているかは案内からは分からないので、実際に表示を見て確かめてください。

自分の手で木を動かし、作品で確かめる

まず、上の木をそのままコードにして動かします。ブラウザのコンソールか、Node.jsで実行できます。

const L = (v) => ({ v });
const N = (v, ...c) => ({ v, c });

// 上の図と同じ木。vは粗い評価、葉はvだけ持つ
const tree = N(0,
  N(6, N(5, L(3), L(5)), N(2, L(2), L(4))), // A
  N(5, N(3, L(6), L(6)), N(4, L(7), L(1)))  // B
);

function minimax(node, depth, isMax) {
  if (depth === 0 || !node.c) return node.v;
  const vals = node.c.map((ch) => minimax(ch, depth - 1, !isMax));
  return isMax ? Math.max(...vals) : Math.min(...vals);
}

function choose(depth) {
  const scores = tree.c.map((ch) => minimax(ch, depth - 1, false));
  const pick = scores[0] >= scores[1] ? "A" : "B";
  return { depth, scores, pick };
}

for (const d of [1, 2, 3]) console.log(choose(d));

出力は、先の表と一致するはずです。違っていたら、図を手でたどり直し、どの層で最大と最小を取り違えたかを探してください。

次に、自分の木で試します。

1. 葉の数字を1つ変えて、3手先の結論が変わる数字を探します。結論が変わる境目を見つけると、「どの数字が選択を左右しているか」が分かります。
2. 粗い評価の数字を変えて、深さ1の結論を意図的にBへ変えてみます。粗い評価が深い読みと食い違うと、浅い読みがどれだけ当てにならないかを実感できます。
3. 枝を3本に増やし、各深さで評価される葉の数を数えてみます。

そのうえで、公式作品でCPUの性格を観察する方法です。数字を作らず、自分の記録だけで判断します。

• 対象：灯りのチェスの3段階の相手を、段階ごとに最低3局ずつ。
• 条件：序盤は毎回同じ進め方にします。
• 観察する点：自分の駒を1つ取らせる代わりに、次の手で相手のより価値の高い駒を取れる交換を仕掛けます。この「2手先で回収できる誘い」に、段階ごとに相手が乗るかどうかを局ごとに記録します。
• 記録の単位：1局につき、誘いに乗ったか、乗らなかったか、誘いに気づく前に別の手を指したかの3区分で記録します。
• 読み方：乗らない相手が多い段階は、2手先を見ている可能性があります。ただし、手に乱れがあるCPUなら、同じ局面でも毎回同じ反応とは限りません。そのため、1局の結果で深さを断定せず、3局以上の傾向で判断します。

どの段階でも誘いに乗る場合、その局面を2手先まで読む力が、少なくとも相手に備わっていない可能性があります。ただし、乗る・乗らないは読みの深さ以外の要因でも変わります。結論は「読みの深さが違いそうだ」と控えめに留めてください。

次の行動

まず上のコードを動かし、葉の数字を1つ変えて、3手先の結論が変わる境目を探してみてください。そのあと灯りのチェスと潮目のオセロの3段階の相手を、記録を取りながら遊び、CPUが「どこで読みを止めていそうか」を自分の観察で推測してみてください。自作のゲームにCPUを入れるときは、深さ固定から始めて、返事が遅くなったら時間で打ち切る方式へ進めるのが現実的です。

参考資料

• Stuart Russell、Peter Norvig『Artificial Intelligence: A Modern Approach』（対戦型探索・ミニマックスとアルファベータ法の解説）
• アソバース公式作品「灯りのチェス」「潮目のオセロ」の作品案内