ゲームプレイと探索 ― ミニマックスとα-β枝刈りから、コンピュータ・チェスとチェッカーの実装まで

Posted at 2026-07-29

ゲームプレイと探索 ― ミニマックスとα-β枝刈りから、コンピュータ・チェスとチェッカーの実装まで

2人で交互に指す完全情報ゲームを、ステート空間問題の一種として定式化し、ミニマックスアルゴリズムがゲームツリーの上でどう働くかを確認します。組み合わせ論的爆発によって完全なゲームツリーの探索が不可能になる点を押さえたうえで、静的評価による切り捨て探索、α-β枝刈り、静止探索、繰り返し深化、置き換えテーブル、必殺手のヒューリスティックスといった、ゲームのプログラマが実際に使っているトリックを順に見ていきます。サンプルプログラムとしてチェッカーをSwiftで実装し、各手法が探索ノード数をどれだけ減らすかを実測します。最後に、この分野の最先端であるコンピュータ・チェスと、将棋・囲碁への応用に触れます。

はじめに
1. 技のゲームとステート空間の対応関係
2. ゲームツリー
3. 棒取りゲーム ― 完全なゲームツリーを解く
4. ミニマックスアルゴリズム
5. ネガマックス ― 2つの視点を1つにまとめる
6. 組み合わせ論的爆発
7. 静的評価による切り捨て探索
8. 静的評価関数
9. α-β枝刈り
10. α-βの効率と手の順序づけ
11. サンプルプログラム ― チェッカー
12. ミニマックスとα-βの実測
13. 静止探索と水平線効果
14. 繰り返し深化
15. 置き換え問題と置き換えテーブル
16. 必殺手のヒューリスティックスと履歴ヒューリスティック
17. 序盤定石集と終盤データベース
18. コンピュータ・チェス
19. 将棋
20. 囲碁
まとめ
注釈
参考資料

はじめに

前回の記事では、単独の主体が目標に向かってステート空間を進む探索を扱いました。地図の上で経路を探すとき、演算子を適用するのは自分だけです。誰も邪魔をしません。

ゲームでは事情が変わります。演算子を適用するのは自分と相手が交互であり、しかも相手は自分の目標を妨害することを目標としている。この一点が加わるだけで、探索の枠組みは大きく組み替えられます。「目標に至る経路」を1本見つけても意味がありません。相手がどう応じてきても対処できる方針を持つ必要があるからです。

この記事では、2人でプレイする、離散的で、完全情報の、確定的なゲームだけを扱います。チェス、将棋、囲碁、チェッカー、オセロがこれにあたります。ポーカーや麻雀（隠された情報がある）、バックギャモン（サイコロという偶然の要素がある）は対象外です。この制限のおかげで、ゲームツリーという単一の構造ですべてを表現できます。

扱う道具立ては、1950年前後に提案されたミニマックスと静的評価という2つの考え方と、そのうえに積み上げられた高速化の工夫です。後者はいずれも、組み合わせ論的爆発というただ1つの敵と戦うために編み出されたものです。

1. 技のゲームとステート空間の対応関係

ゲームは大きく2種類に分けられます。

技のゲーム（game of skill）：結果が完全にプレイヤーの選択で決まる。偶然の要素がない
運のゲーム（game of chance）：サイコロやカードの配り方など、偶然が結果に影響する

この記事で扱うのは技のゲームで、さらに次の条件を課します。

条件	意味
2人	プレイヤーはちょうど2人
交互	手番が交互に回ってくる
離散	手の選択肢が有限個で数え上げられる
完全情報	両者が同じ情報を見ている。隠された手札などがない
確定的	手を選べば結果の局面が一意に決まる
ゼロサム	一方の利得は他方の損失。引き分けを含む3値（勝ち・引き分け・負け）でよい

これらの条件を満たすゲームは、前回定義したステート空間問題とほぼそのまま対応します。

ステート空間問題	技のゲーム
ステート	局面（position）。盤面の配置と、どちらの手番かの組
初期ステート	初期局面
演算子	合法手（legal move）
後続ステート	その手を指した後の局面
目標判定	終局判定（詰み、駒がなくなる、手がなくなる、など）
コスト関数	ここでは使わない。代わりに終局の利得（utility）を使う

対応しない部分がひとつだけあります。解の形です。

ステート空間問題の解は経路、つまり演算子の列である
ゲームの解は戦略（strategy）、つまり「相手がどう指してきたら自分はこう指す」という対応の全体である

なぜなら、経路のうち自分が選べるのは1手おきだけだからです。残り半分は相手が決めます。したがって「初手はこれ、次はこれ」という一本道の計画は立てられません。相手のあらゆる応手に対する備えが要ります。

この違いは形式的には、演算子を適用する主体が交互に入れ替わり、しかも一方が目標判定を最大化しようとし、他方が最小化しようとする、と言い換えられます。ゲームの探索アルゴリズムがすべて「最大化と最小化の交替」という形をしているのは、この構造から直接出てきます。

なお、この条件を満たし、必ず有限の手数で終わるゲームには、確定した理論値（先手必勝、後手必勝、引き分けのいずれか）が存在することが知られています。Ernst Zermelo が1913年に示した結果です（注1）。チェスの理論値が何であるかは今も分かっていませんが、「分からない」だけで「決まっていない」わけではありません。

2. ゲームツリー

**ゲームツリー（game tree）**は、局面をノード、合法手を辺として、初期局面から到達しうるすべての局面を展開した木です。

                    根（自分の手番）        ← MAXノード
                 /        |        \
              手a        手b        手c
             /            |            \
        （相手の手番）  （相手の手番）  （相手の手番）   ← MINノード
        /    \          /    \          /    \
      ...    ...      ...    ...      ...    ...

MAXノード：自分の手番の局面。自分に有利な値を最大化する手を選ぶ
MINノード：相手の手番の局面。相手は自分に有利な値を最小化する手を選ぶ
葉（leaf）：終局した局面。勝ち・負け・引き分けの利得が確定する

ここで「値」は常に一方のプレイヤーから見た値として定義します。慣例的にMAX側（探索している側）から見た値を使い、勝ちを +1、引き分けを 0、負けを -1 とします。

重要なのは、ゲームツリーが探索ツリーであってステート空間そのものではないという点です。同じ局面が異なる手順で現れれば、木の別の場所に別ノードとして重複して現れます。この重複が後で述べる置き換え問題につながります。

3. 棒取りゲーム ― 完全なゲームツリーを解く

まず、ゲームツリー全体を最後まで探索できるくらい小さなゲームで仕組みを確かめます。**棒取りゲーム（Last One Loses）**を使います。

棒が n 本並んでいる
2人が交互に、1本・2本・3本のいずれかを取る
最後の1本を取った側が負け

ステートは「残りの本数」と「手番」だけです。

enum Turn {
    case max, min
    var opponent: Turn { self == .max ? .min : .max }
}

struct Sticks {
    var remaining: Int
    var turn: Turn
}

func moves(_ s: Sticks) -> [Int] {
    guard s.remaining > 0 else { return [] }
    return Array(1...min(3, s.remaining))
}

func apply(_ take: Int, to s: Sticks) -> Sticks {
    Sticks(remaining: s.remaining - take, turn: s.turn.opponent)
}

func isTerminal(_ s: Sticks) -> Bool { s.remaining == 0 }

// 最後の1本を取った側が負け → 終局時に手番が回ってきた側が勝ち
func utility(_ s: Sticks) -> Int { s.turn == .max ? 1 : -1 }

utility の符号に注意してください。棒が0本になった局面で手番が回ってきたということは、直前に相手が最後の1本を取ったということです。したがって、その局面で手番を持っている側が勝者です。

このゲームには手で解ける必勝法があります。残り本数が 4k + 1 のときに手番が回ってきた側が負けます。相手に常に「4の倍数プラス1」を渡し続ければよいからです。プログラムがこの構造を自力で見つけられるかどうかが、以下の確認になります。

4. ミニマックスアルゴリズム

ミニマックス（MINIMAX）アルゴリズムは、ゲームツリーを再帰的にたどり、各ノードの値を次のように定めます。

葉ノードの値は、その終局の利得
MAXノードの値は、子ノードの値の最大値
MINノードの値は、子ノードの値の最小値

つまり「相手の有利さを最小化し、自分の有利さを最大化する」手を選ぶ、という原理を素直に書き下したものです。前提として、相手も最善を尽くすと仮定します。この仮定は悲観的ですが、安全側の仮定です。相手が最善を尽くさなければ、結果は仮定より良くなることはあっても悪くなることはありません。

var visited = 0

func minimax(_ s: Sticks) -> Int {
    visited += 1
    if isTerminal(s) { return utility(s) }
    if s.turn == .max {
        var best = Int.min
        for m in moves(s) { best = max(best, minimax(apply(m, to: s))) }
        return best
    } else {
        var best = Int.max
        for m in moves(s) { best = min(best, minimax(apply(m, to: s))) }
        return best
    }
}

func bestMove(_ s: Sticks) -> (take: Int, value: Int) {
    visited += 1                      // ルートノード
    var best = (take: 0, value: s.turn == .max ? Int.min : Int.max)
    for m in moves(s) {
        let v = minimax(apply(m, to: s))
        if s.turn == .max ? (v > best.value) : (v < best.value) { best = (m, v) }
    }
    return best
}

棒の本数を変えて実行した結果です。

棒 1 本: 値 -1  最善手 1 本  探索ノード 2
棒 2 本: 値 +1  最善手 1 本  探索ノード 4
棒 3 本: 値 +1  最善手 2 本  探索ノード 8
棒 4 本: 値 +1  最善手 3 本  探索ノード 15
棒 5 本: 値 -1  最善手 1 本  探索ノード 28
棒 6 本: 値 +1  最善手 1 本  探索ノード 52
棒 7 本: 値 +1  最善手 2 本  探索ノード 96
棒 8 本: 値 +1  最善手 3 本  探索ノード 177
棒 9 本: 値 -1  最善手 1 本  探索ノード 326
棒 10 本: 値 +1  最善手 1 本  探索ノード 600
棒 11 本: 値 +1  最善手 2 本  探索ノード 1104
棒 12 本: 値 +1  最善手 3 本  探索ノード 2031

値が -1（手番側の負け）になるのは 1本・5本・9本のときで、予想どおり 4k + 1 の形をしています。勝てる局面では、常に残りを 4k + 1 にする本数を取っています。ミニマックスは必勝法を教えられたわけではなく、ゲームツリーを最後まで見た結果としてそれを再発見しています。

同時に、右端のノード数に注目してください。棒が3本増えるごとにノード数がおよそ6倍になっています。この程度の玩具のゲームですら、指数的に増えているのです。

5. ネガマックス ― 2つの視点を1つにまとめる

上のコードには max を取る枝と min を取る枝が別々に書かれています。ゼロサムであることを使うと、これを1つにまとめられます。

あるノードの、手番側から見た値は、子ノードの、子の手番側から見た値の符号を反転したものの最大値に等しい。

minimax(s, MAX) = -minimax(s, MIN)

という関係が成り立つからです。この書き方を**ネガマックス（negamax）**と呼びます（注2）。

func negamax(_ s: Sticks) -> Int {
    if isTerminal(s) { return 1 }     // 終局は常に手番側の勝ち（手番側から見た値）
    var best = Int.min
    for m in moves(s) {
        best = max(best, -negamax(apply(m, to: s)))
    }
    return best
}

分岐が消えて、max と符号反転だけになりました。ネガマックス形式を使うときの約束は1つだけです。評価値は常に「その局面で手番を持っている側から見た値」でなければならない。第3節の utility はMAX側から見た値を返す関数だったので、ここではそのまま使えません。このゲームの終局は「手番が回ってきた側の勝ち」と決まっているので、手番側から見た終局の値は常に +1 です。うっかり utility(s) を返すと、負け局面まで勝ちと判定する、原因の分かりにくいバグになります。以降のコードはすべてこの形式で書きます。

6. 組み合わせ論的爆発

棒取りゲームは最後まで探索できました。実際のゲームではそうはいきません。

ゲームツリーのノード数はおよそ b^d です。b は分岐係数（平均合法手数）、d はゲームの深さ（終局までの平均手数、片側1手を1と数える）です。主なゲームの見積もりは次のとおりです（注3）。

ゲーム	分岐係数 `b`	深さ `d`	局面数の見積もり	ゲームツリーの大きさ
三目並べ	4	9	10³	10⁵
チェッカー	約3	70	10²⁰	10³¹
オセロ	10	58	10²⁸	10⁵⁸
チェス	35	80	10⁴⁶	10¹²³
将棋	80	115	10⁷¹	10²²⁶
囲碁（19路）	250	150	10¹⁷⁰	10³⁶⁰

チェスについて Claude Shannon が1950年の論文で見積もった 10¹²⁰ という数は、**シャノン数（Shannon number）**と呼ばれます（注4）。表の 10¹²³ はその後の再見積もりで、桁の話としては同じことです。観測可能な宇宙の原子数がおよそ 10⁸⁰ と言われますから、比較の対象になりません。

この、選択肢が指数的に増えていく現象を**組み合わせ論的爆発（combinatorial explosion）**と呼びます。これがゲームプログラミングにおける唯一にして最大の敵であり、以降で扱う手法はすべて、これに対する対策です。対策は2つの方向に分かれます。

探索を浅く打ち切る：完全なゲームツリーの代わりに、途中で止めて推定値を使う（第7〜8節）
無駄な枝を見ない：結論に影響しない部分木を探索から省く（第9節以降）

7. 静的評価による切り捨て探索

最後まで探索できないなら、決められた深さで止めるしかありません。しかし止めた先は終局ではないので、勝ち負けが確定していません。そこで、その局面がどれくらい有利かを推定する関数を用意します。これを**静的評価関数（static evaluation function）**と呼びます。「静的」というのは、先読みをせずに盤面だけを見て判断するという意味です。

ミニマックスの終了条件を「終局に達したら」から「終局に達したか、決めた深さまで来たら」に変えたものを切り捨て探索（truncated search）、あるいは深さ制限探索と呼びます。

func negamax(_ b: Board, depth: Int) -> Double {
    let ms = legalMoves(b)
    if ms.isEmpty { return -winScore }          // 手がない = 手番側が負け
    if depth == 0 { return evaluate(b, for: b.toMove) }
    var best = -Double.infinity
    for m in ms {
        best = max(best, -negamax(apply(m, to: b), depth: depth - 1))
    }
    return best
}

終局判定を深さ判定より先に書いている点が重要です。深さ制限に達していても終局しているなら、推定値ではなく確定した勝敗を返さなければなりません。

この変更で、探索は「正しい答えを出す手続き」から「限られた計算量で良さそうな手を選ぶ手続き」に変わります。得られる値はもはやゲームの理論値ではなく、深さ d までの先読みと評価関数の組み合わせによる推定値です。

そして次の重要な性質が成り立ちます。同じ評価関数を使うなら、深く探索するほど強くなる。評価関数の誤差は、深く探索するほど実際の終局に近い局面で測られるため、小さくなるからです。この性質があるおかげで、「探索を速くする」ことがそのまま「強くする」ことになります。ゲームプログラミングが徹底的に速度を追求してきた理由がここにあります。

8. 静的評価関数

静的評価関数の設計は、探索の速さと並ぶもう一方の柱です。典型的には、盤面から読み取れる特徴量の線形結合として作られます。

評価値 = w₁ × 特徴量₁ + w₂ × 特徴量₂ + … + wₙ × 特徴量ₙ

チェスやチェッカーでは、次のような特徴量が使われます。

特徴量	説明
駒得（material）	駒の価値の合計の差。ほとんどの局面で最も影響が大きい
可動性（mobility）	合法手の数の差。動ける駒が多いほうが有利
中央支配	盤の中央付近を占めているかどうか
キングの安全性	チェスなら王の周囲の守り、チェッカーならキングへの昇格しやすさ
ポーン構造	チェス固有。孤立ポーン、二重ポーン、パスポーンなど

Shannon が1950年に示したチェスの評価関数は、駒得に可動性とポーン構造の項を加えた線形式でした。Arthur Samuel のチェッカープログラム（1959年）は、こうした特徴量の重みを対局の経験から自動調整することを試みており、機械学習の初期の代表例として知られています（注5）。

この記事のサンプルプログラムでは、次の単純な評価関数を使います。

0.7 × (味方のキング − 敵のキング) + 0.3 × (味方の駒 − 敵の駒)

キングの差に重み 0.7、駒数の差に重み 0.3 を与えたものです。チェッカーのキングは前後どちらにも動けるので通常の駒より価値が高く、その差をこの重みが表しています。

評価関数について押さえておくべき点が2つあります。

第一に、絶対値には意味がなく、順序にだけ意味があります。 評価値が 0.3 であることに物理的な意味はありません。別の局面の評価値と比較して大小が正しく並んでいれば、それで十分です。したがって重み全体を定数倍しても、探索の結果は変わりません。

第二に、精度と計算コストがトレードオフになります。 評価関数を精緻にすれば1局面あたりの判断は良くなりますが、その分だけ1秒あたりに評価できる局面数が減り、探索が浅くなります。第7節で述べたとおり深さは強さに直結するので、これは実際に悩ましい取引です。歴史的には、比較的単純な評価関数で深く探索する方針（Shannon の言う Type A）が、複雑な評価関数で選択的に探索する方針（Type B）に対して優位を占めてきました。

9. α-β枝刈り

切り捨て探索によって深さは有限になりましたが、b^d という形はそのままです。ここで効いてくるのが**α-β枝刈り（alpha-beta pruning）**です。

α-β枝刈りは、ミニマックスと完全に同じ値を返しながら、結論に影響しない部分木の探索を省く手法です。近似ではありません。答えは1ビットも変わらず、ただ速くなります。

基本のアイデア

MAXノードで、すでに値 6 を確保できる手を見つけているとします。次の手を調べていて、その先のMINノードで値 4 が見つかったとします。MINノードは子の最小値を取るので、このMINノードの値は必ず 4 以下です。ということは、この手を選んでも 6 を下回るだけです。このMINノードの残りの子を調べる必要はありません。

この判断に使う2つの値が α と β です。

記号	意味	別の言い方
α	MAX側がすでに確保できると分かっている値の下限	悲観的評価（少なくともこれだけは取れる）
β	MIN側がすでに強制できると分かっている値の上限	楽観的評価（せいぜいこれくらいしか取れない）

探索は常に区間 [α, β] を持って進み、この区間の外に出た枝は捨てられます。

α切り捨て（alpha cutoff）：MINノードで、値が α 以下になった。MAX側はこの枝を選ばないので、残りの兄弟を捨てる
β切り捨て（beta cutoff）：MAXノードで、値が β 以上になった。MIN側はこの枝に入らせないので、残りの兄弟を捨てる

ネガマックス形式では、この2つは1つの条件にまとまります。

func alphaBeta(_ b: Board, depth: Int, alpha: Double, beta: Double) -> Double {
    let ms = legalMoves(b)
    if ms.isEmpty { return -winScore }
    if depth == 0 { return evaluate(b, for: b.toMove) }
    var alpha = alpha
    var best = -Double.infinity
    for m in ms {
        // 子から見た区間は、符号を反転して上下も入れ替わる
        let v = -alphaBeta(apply(m, to: b), depth: depth - 1, alpha: -beta, beta: -alpha)
        best = max(best, v)
        alpha = max(alpha, v)
        if alpha >= beta { break }              // 切り捨て
    }
    return best
}

再帰呼び出しで alpha: -beta, beta: -alpha と渡している部分が要点です。値の符号を反転すると、区間の上下が入れ替わります。

動きを追う

値を固定した小さなゲームツリーで、実際に何が捨てられるかを見てみます。深さ4（MAX → MIN → MAX → 葉）、各ノードの子は2〜3個です。

indirect enum Node {
    case leaf(Int)
    case branch([Node])
}

let tree: Node = .branch([
    .branch([                                        // MIN
        .branch([.leaf(3), .leaf(12), .leaf(8)]),    // MAX
        .branch([.leaf(2), .leaf(4), .leaf(6)]),
    ]),
    .branch([
        .branch([.leaf(4), .leaf(2), .leaf(3)]),
        .branch([.leaf(11), .leaf(13), .leaf(6)]),
    ]),
    .branch([
        .branch([.leaf(7), .leaf(15), .leaf(1)]),
        .branch([.leaf(9), .leaf(20), .leaf(5)]),
    ]),
])

葉を評価した順序と、切り捨てが起きた場所を記録しながら実行した結果です。

ミニマックス値: 15（評価した葉 18 個）
α-βの値: 15（評価した葉 14 個）

  葉 111 = 3  [α=-∞, β=+∞]
  葉 112 = 12  [α=3, β=+∞]
  葉 113 = 8  [α=12, β=+∞]
  葉 121 = 2  [α=-∞, β=12]
  葉 122 = 4  [α=2, β=12]
  葉 123 = 6  [α=4, β=12]
  葉 211 = 4  [α=6, β=+∞]
  葉 212 = 2  [α=6, β=+∞]
  葉 213 = 3  [α=6, β=+∞]
  → α切り捨て at 2 (β=4 ≤ α=6)、残り 1 枝を捨てる
  葉 311 = 7  [α=6, β=+∞]
  葉 312 = 15  [α=7, β=+∞]
  葉 313 = 1  [α=15, β=+∞]
  葉 321 = 9  [α=6, β=15]
  葉 322 = 20  [α=9, β=15]
  → β切り捨て at 32 (α=20 ≥ β=15)、残り 1 枝を捨てる

値はどちらも15で一致し、評価した葉は18個から14個に減りました。 2か所で切り捨てが起きています。

2番目のMIN子（ノード2）で、最初の子が 4 と判明した。根ではすでに α = 6 を確保済みなので、このMIN子は 4 以下にしかならない。残りの部分木（3枚の葉）をまるごと捨てた
3番目の枝の中のMAXノード（ノード32）で、20 が見つかった。親のMINノードはすでに β = 15 を持っているので、この枝には入らせない。残りの葉を捨てた

捨てた部分木の中に、実は 13 という大きな値が含まれていました（ノード22の子）。それでも答えが変わらないのは、その値に到達する前にMIN側が別の手を選ぶからです。α-βが安全なのは、値を推測しているのではなく、「この部分木の値がどうであろうと結論は変わらない」ことを論理的に確かめているためです。

10. α-βの効率と手の順序づけ

α-β枝刈りがどれだけ得をするかは、手を調べる順序に決定的に依存します。

最良の場合：各ノードで最善手を最初に調べる。このとき探索するノード数は b^(d/2) 程度に落ちる
最悪の場合：各ノードで最善手を最後に調べる。切り捨てが1度も起きず、素のミニマックスと同じ b^d になる

最良の場合の b^(d/2) という結果は Donald Knuth と Ronald Moore による解析で示されたもので、実質的な分岐係数が b から √b に下がることを意味します（注6）。これは劇的です。同じ時間で2倍の深さまで読めるということだからです。

もっとも、最善手が最初に分かっているなら探索する必要がありません。実際には近似的に良い順序を作ることになります。よく使われる手がかりは次のとおりです。

手がかり	内容
駒を取る手を先に	大きな変化を起こす手は、大きな値の変化をもたらしやすい
前回の探索での最善手	繰り返し深化と組み合わせる（第14節）
置き換えテーブルの記録	同じ局面を以前に調べたときの最善手（第15節）
必殺手・履歴	他の場所で切り捨てを起こした手（第16節）

順序づけについて、この記事のチェッカーで測ってみて分かったことが1つあります。でたらめに順序を入れ替えても、性能はほとんど変わりません。 効くのは「良い手を先に見る」という情報を持った順序づけだけです。実測は第16節で示します。

11. サンプルプログラム ― チェッカー

ここまでの手法を実際に測るために、チェッカー（イングリッシュ・ドラフツ）をSwiftで実装します。ルールは次のとおりです。

8×8の盤の濃いマスだけを使う（32マス）。双方12駒ずつで開始する
通常の駒は斜め前方に1マス進む。キングは斜め前後どちらにも進める
相手の駒を跳び越して取る。跳び越しが可能なときは必ず跳ばなければならない（強制取り）
連続して跳び越せる場合は、跳べるだけ跳ぶ
最奥列に到達した駒はキングに昇格する。ただし跳び越しの途中で昇格したらその手番は終わる
動かせる手がなくなった側の負け

11.1 チェッカー盤

盤面は64マスの配列として持ちます。Board を Hashable にしておくのは、後で置き換えテーブルの鍵に使うためです。

enum Player: Int, Hashable {
    case black = 0, white = 1
    var opponent: Player { self == .black ? .white : .black }
}

struct Piece: Hashable {
    var owner: Player
    var isKing: Bool
}

struct Board: Hashable {
    var cells: [Piece?]          // 64マス。row * 8 + col
    var toMove: Player

    static func initial() -> Board {
        var cells = [Piece?](repeating: nil, count: 64)
        for row in 0..<3 {
            for col in 0..<8 where (row + col) % 2 == 1 {
                cells[row * 8 + col] = Piece(owner: .black, isKing: false)
            }
        }
        for row in 5..<8 {
            for col in 0..<8 where (row + col) % 2 == 1 {
                cells[row * 8 + col] = Piece(owner: .white, isKing: false)
            }
        }
        return Board(cells: cells, toMove: .black)
    }
}

初期局面を表示すると次のようになります。小文字が通常の駒、大文字がキング、. が空いている濃いマスです。黒（b）が上から下へ、白（w）が下から上へ進みます。

  a b c d e f g h
8   b   b   b   b 
7 b   b   b   b   
6   b   b   b   b 
5 .   .   .   .   
4   .   .   .   . 
3 w   w   w   w   
2   w   w   w   w 
1 w   w   w   w

11.2 手の生成

手は経路（通過するマスの列）と取った駒の位置で表します。連続跳び越しがあるため、単一の移動先では表現できません。

struct Move: Hashable {
    var path: [Int]              // 出発マスから到着マスまで
    var captured: [Int]
    var from: Int { path.first! }
    var to: Int { path.last! }
    var isCapture: Bool { !captured.isEmpty }
}

let kingRow: [Player: Int] = [.black: 7, .white: 0]

func directions(_ p: Piece) -> [(Int, Int)] {
    let forward = p.owner == .black ? 1 : -1
    if p.isKing { return [(1, 1), (1, -1), (-1, 1), (-1, -1)] }
    return [(forward, 1), (forward, -1)]
}

func onBoard(_ r: Int, _ c: Int) -> Bool { r >= 0 && r < 8 && c >= 0 && c < 8 }

跳び越しは再帰で生成します。跳んだ先からさらに跳べる場合は、その続きだけを結果に含めます（途中で止まることは許されないため）。

func jumpMoves(from square: Int, piece: Piece, cells: [Piece?],
               path: [Int], captured: [Int]) -> [Move] {
    let r = square / 8, c = square % 8
    var results: [Move] = []
    for (dr, dc) in directions(piece) {
        let mr = r + dr, mc = c + dc          // 跳び越す相手の駒
        let lr = r + 2 * dr, lc = c + 2 * dc  // 着地マス
        guard onBoard(lr, lc) else { continue }
        let mid = mr * 8 + mc, landing = lr * 8 + lc
        guard let victim = cells[mid], victim.owner != piece.owner,
              !captured.contains(mid), cells[landing] == nil else { continue }
        // 連続跳び越しを調べるため、盤面を仮に更新する
        var next = cells
        next[square] = nil
        next[landing] = piece
        next[mid] = nil
        let promoted = !piece.isKing && lr == kingRow[piece.owner]!
        let more = promoted ? []             // キング昇格でその手番は終わる
            : jumpMoves(from: landing, piece: piece, cells: next,
                        path: path + [landing], captured: captured + [mid])
        if more.isEmpty {
            results.append(Move(path: path + [landing], captured: captured + [mid]))
        } else {
            results += more
        }
    }
    return results
}

func legalMoves(_ b: Board) -> [Move] {
    var jumps: [Move] = [], steps: [Move] = []
    for square in 0..<64 {
        guard let piece = b.cells[square], piece.owner == b.toMove else { continue }
        jumps += jumpMoves(from: square, piece: piece, cells: b.cells,
                           path: [square], captured: [])
        let r = square / 8, c = square % 8
        for (dr, dc) in directions(piece) where onBoard(r + dr, c + dc) {
            let dest = (r + dr) * 8 + (c + dc)
            if b.cells[dest] == nil {
                steps.append(Move(path: [square, dest], captured: []))
            }
        }
    }
    return jumps.isEmpty ? steps : jumps   // 跳び越しがあれば強制
}

func apply(_ m: Move, to b: Board) -> Board {
    var next = b
    var piece = b.cells[m.from]!
    next.cells[m.from] = nil
    for square in m.captured { next.cells[square] = nil }
    if !piece.isKing && m.to / 8 == kingRow[piece.owner]! { piece.isKing = true }
    next.cells[m.to] = piece
    next.toMove = b.toMove.opponent
    return next
}

最終行の jumps.isEmpty ? steps : jumps が強制取りのルールです。この1行のせいで、チェッカーではあるノードの合法手は「全部が跳び越し」か「全部が静かな手」のどちらかになります。この性質は後で静止探索と手の順序づけの両方に効いてきます。

11.3 手の生成の検証

探索の測定をする前に、手の生成が正しいことを確かめます。ゲームプログラミングでは、初期局面から深さ d までの葉の数を数える perft という検証がよく使われます。イングリッシュ・ドラフツの値は公表されているので、それと突き合わせます。

func perft(_ b: Board, _ depth: Int) -> Int {
    if depth == 0 { return 1 }
    let ms = legalMoves(b)
    if depth == 1 { return ms.count }
    var total = 0
    for m in ms { total += perft(apply(m, to: b), depth - 1) }
    return total
}

perft(1) = 7  期待値 7  OK
perft(2) = 49  期待値 49  OK
perft(3) = 302  期待値 302  OK
perft(4) = 1469  期待値 1469  OK
perft(5) = 7361  期待値 7361  OK
perft(6) = 36768  期待値 36768  OK
perft(7) = 179740  期待値 179740  OK
perft(8) = 845931  期待値 845931  OK
perft(9) = 3963680  期待値 3963680  OK

深さ9まで完全に一致しました。強制取り、連続跳び越し、昇格でその手番が終わる規則まで含めて、手の生成は正しいと確認できます。以降の測定値は、この土台の上で得られたものです。

11.4 静的評価関数

第8節で述べた式をそのまま実装します。ネガマックス形式で使うため、引数で渡された側から見た値を返します。

func evaluate(_ b: Board, for player: Player) -> Double {
    var myKings = 0, oppKings = 0, myPieces = 0, oppPieces = 0
    for cell in b.cells {
        guard let p = cell else { continue }
        if p.owner == player {
            myPieces += 1; if p.isKing { myKings += 1 }
        } else {
            oppPieces += 1; if p.isKing { oppKings += 1 }
        }
    }
    return 0.7 * Double(myKings - oppKings) + 0.3 * Double(myPieces - oppPieces)
}

let winScore = 1000.0

初期局面では両者が対称なので評価値は 0.0 になります。駒を1つ多く持っている局面では 0.3、キングを1つ多く持っていればさらに 0.7 が加わります。

12. ミニマックスとα-βの実測

測定には、自己対局で16手進めた次の中盤局面を使います。手番は黒、合法手は8手、駒数は黒10・白9です。

  a b c d e f g h
8   .   .   b   b 
7 b   b   b   b   
6   b   .   b   b 
5 .   w   .   .   
4   .   w   b   . 
3 .   w   .   .   
2   .   w   .   w 
1 w   w   w   w

この局面を、素のネガマックス、α-β枝刈り、そしてα-βに後の節の改良（手の順序づけ・置き換えテーブル・繰り返し深化）をすべて加えた改良版の3通りで探索し、訪れたノード数を数えました。実効分岐係数は、ノード数の d 乗根、つまり「1手あたり実質いくつの枝を見たか」です。

深さ	ネガマックス	α-β	改良版α-β	実効分岐係数（ネガマックス → α-β → 改良版）
4	1,051	418	277	5.69 → 4.52 → 4.08
5	4,554	1,045	685	5.39 → 4.02 → 3.69
6	20,913	2,978	1,106	5.25 → 3.79 → 3.22
7	91,798	6,914	2,342	5.12 → 3.54 → 3.03
8	432,873	20,926	4,212	5.06 → 3.47 → 2.84
9	1,979,702	52,578	10,035	5.01 → 3.35 → 2.78

3通りとも同じ値（0.3）と同じ最善手（e7-d6）を返しています。 高速化は結論を変えていません。

深さ9では、α-βだけでノード数が約38分の1になり、改良版では約197分の1になりました。効果が深さとともに大きくなっている点が重要です。指数の底が下がっているので、深く読むほど差が開きます。

実効分岐係数で見ると、素のネガマックスの 5.01 に対してα-βは 3.35 です。第10節で述べた理想値は √5.01 ≈ 2.24 なので、そこまでは届いていません。手の順序が理想的ではないためです。改良版では 2.78 まで下がり、理想に近づきます。

13. 静止探索と水平線効果

固定の深さで探索を打ち切ることには、深刻な副作用があります。

水平線効果

深さ制限のちょうど境目で、駒を取る手を指したところで探索が止まったとします。評価関数は「駒を1つ多く持っている」と判断し、その手を高く評価します。しかし次の1手で取り返されるとしたら、その評価は誤りです。探索の地平線（horizon）の向こう側にある事実が見えていないのです。

これを**水平線効果（horizon effect）**と呼びます。Hans Berliner が1973年に命名しました（注7）。

第11節のチェッカーで、実際にこの現象が起きる局面を探しました。黒の手番で、跳び越しが強制されている局面です。

  a b c d e f g h
8   b   b   b   b 
7 .   b   b   b   
6   b   b   b   b 
5 .   .   w   .   
4   .   .   .   . 
3 b   .   w   w   
2   w   w   w   w 
1 w   w   w   w

深さを変えて、根の評価値がどう動くかを見ます。

深さ	α-βの値	静止探索つきの値
1	0.6	0.0
2	0.3	0.0
3	0.6	0.0
4	0.0	0.0
5	0.0	0.0
6	0.0	0.0

左の列が教科書どおりの振動を見せています。奇数の深さで 0.6、偶数の深さで 0.3 や 0.0。 奇数深さでは自分が取ったところで探索が止まるので有利に見え、偶数深さでは取り返されるところまで見えるので評価が下がります。深さ4以降でようやく安定します。つまり深さ3の探索は、この局面を「駒得できる」と誤って判断していたわけです。

静止探索

対策は、深さ制限に達しても、局面が「静か」でなければ探索を続けることです。これを**静止探索（quiescence search）**と呼びます。静かな局面とは、大きな変化を起こす手（主に駒を取る手）が残っていない局面のことです。

func quiescence(_ b: Board, alpha: Double, beta: Double) -> Double {
    let ms = legalMoves(b)
    if ms.isEmpty { return -winScore }
    // 跳び越しが1つでもあれば全部が跳び越し（強制）。なければ静かな局面。
    if !ms[0].isCapture { return evaluate(b, for: b.toMove) }
    // 跳び越しは強制なので「指さずに評価値で止まる」選択肢はない
    var alpha = alpha
    var best = -Double.infinity
    for m in ms {
        let v = -quiescence(apply(m, to: b), alpha: -beta, beta: -alpha)
        best = max(best, v)
        alpha = max(alpha, v)
        if alpha >= beta { break }
    }
    return best
}

func alphaBetaQ(_ b: Board, depth: Int, alpha: Double, beta: Double) -> Double {
    if depth == 0 { return quiescence(b, alpha: alpha, beta: beta) }
    let ms = legalMoves(b)
    if ms.isEmpty { return -winScore }
    var alpha = alpha
    var best = -Double.infinity
    for m in ms {
        let v = -alphaBetaQ(apply(m, to: b), depth: depth - 1, alpha: -beta, beta: -alpha)
        best = max(best, v)
        alpha = max(alpha, v)
        if alpha >= beta { break }
    }
    return best
}

上の表の右の列がその結果です。深さ1から一貫して 0.0 を返しています。 深さ4以上のα-βと同じ結論に、深さ1で到達しているわけです。取り合いの決着がつくまで読み切ってから評価しているので、駒の取り合いの途中で判断を下すことがありません。

コストは小さく済みます。この局面の深さ6で、ノード数は300から440に増えただけでした。跳び越しは駒を減らす一方なので、静止探索は必ず有限で止まります。

なお、上のコードはチェッカーに固有の単純化をしています。強制取りのルールにより、跳び越しがあれば他の手は存在しません。チェスのように駒を取る手と取らない手が混在するゲームでは、「取る手だけを選んで探索し、取らずに止まる選択肢（stand pat）も候補に含める」という形にする必要があります。

水平線効果は静止探索で完全になくなるわけではありません。取り合い以外の要因（たとえば数手先に確実に失う駒）は残ります。プログラムが、避けられない損失を地平線の向こうへ押しやるためだけに無意味な手を指す、という現象は古くから知られています。

14. 繰り返し深化

深さを固定して探索すると、2つの問題が生じます。1つは、実戦では持ち時間があり、どこまで読めるかを事前に決められないこと。もう1つは、第10節で見たとおり良い手の順序が事前に分からないことです。

**繰り返し深化（iterative deepening, 反復深化とも呼ばれます）**は、この両方を同時に解決します。深さ1で探索し、次に深さ2、次に深さ3と、順に深くしていくだけです。前回の記事で単独主体の探索に使ったのと同じ考え方です。

func iterativeDeepening(_ b: Board, maxDepth: Int) -> (move: Move?, value: Double) {
    var best: Move? = nil
    var value = 0.0
    for d in 1...maxDepth {
        var alpha = -Double.infinity
        var localBest: Move? = nil
        // 前回の探索での最善手を最初に調べる
        for m in order(legalMoves(b), ply: 0, ttBest: best) {
            let v = -search(apply(m, to: b), depth: d - 1, ply: 1,
                            alpha: -.infinity, beta: -alpha)
            if v > alpha { alpha = v; localBest = m }
        }
        best = localBest
        value = alpha
    }
    return (best, value)
}

一見すると無駄が多そうに思えます。深さ1から d-1 までの探索をやり直しているからです。しかしノード数が深さに対して指数的に増えるため、最後の1回が全体のほとんどを占めます。分岐係数を b とすると、繰り返し分の追加コストはおよそ b / (b - 1) 倍です。b = 3 なら5割増し、b = 35 なら3パーセント増しにすぎません。

そして、その追加コストを補って余りある見返りがあります。前回の探索で最善だった手を、次の探索で最初に調べられるのです。第10節のとおり、良い順序づけはα-βの効率を大きく左右します。実際には、繰り返し深化は無駄どころか正味で得になることがほとんどです。

利点をまとめます。

持ち時間が尽きた時点で打ち切っても、直前の深さの完全な結果が手元にある
前回の結果を手の順序づけに使え、α-βの切り捨てが増える
探索が深まるにつれて値がどう動くかが観察でき、局面が不安定かどうかの手がかりになる

繰り返し深化は Chess 4.5（David Slate と Lawrence Atkin、1977年）で本格的に採用され、以後この分野の標準になりました（注8）。

15. 置き換え問題と置き換えテーブル

第2節で触れたとおり、ゲームツリーは同じ局面を何度も別ノードとして展開します。手順が違っても同じ局面に到達することを**置き換え（transposition）**と呼びます。チェスなら「1.d4 Nf6 2.c4」と「1.c4 Nf6 2.d4」は違う手順ですが、同じ局面です。

同じ局面を何度も探索し直すのは明らかな無駄です。そこで、探索した局面の結果を辞書に記録しておき、再び現れたら使い回します。これが**置き換えテーブル（transposition table）**です。Richard Greenblatt の Mac Hack VI（1967年）で導入されました（注9）。

素朴に「局面 → 評価値」を記録するだけでは足りません。α-β枝刈りのせいで、記録される値が正確な値とは限らないからです。切り捨てが起きたノードでは、値が上限または下限としてしか分かっていません。そのため、値と一緒にその値が何を意味するのかを記録する必要があります。

種別	意味	使い方
`exact`	ミニマックス値そのもの	そのまま返せる
`lower`	真の値はこれ以上（β切り捨てが起きた）	`α` を引き上げるのに使える
`upper`	真の値はこれ以下（値が `α` を超えなかった）	`β` を引き下げるのに使える

enum Bound { case exact, lower, upper }
struct TTEntry { var depth: Int; var value: Double; var bound: Bound; var best: Move? }

var tt: [Board: TTEntry] = [:]

記録した深さも保存します。浅い探索の結果を、深い探索の答えとして使ってはいけないからです。使えるのは記録時の深さが今回の要求以上のときだけです。

探索の冒頭で辞書を引き、末尾で書き込みます。

if let e = tt[b] {
    ttBest = e.best                        // 深さが足りなくても順序づけには使える
    if e.depth >= depth {
        switch e.bound {
        case .exact: return e.value
        case .lower: alpha = max(alpha, e.value)
        case .upper: beta = min(beta, e.value)
        }
        if alpha >= beta { return e.value }
    }
}

// …探索本体…

let bound: Bound = best <= origAlpha ? .upper : (best >= beta ? .lower : .exact)
tt[b] = TTEntry(depth: depth, value: best, bound: bound, best: bestMove)

ttBest の扱いに注目してください。記録された深さが足りず値としては使えない場合でも、そこに書かれた最善手は順序づけのヒントとして使えます。 実際のところ、置き換えテーブルの効果の多くはこちらから来ます。

チェッカーでの実測です。

深さ	ノード数	値として使えたヒット	登録された局面数
6	1,106	19	312
7	2,342	47	549
8	4,212	144	1,128

値をそのまま使い回せた回数は多くありません。チェッカーはキング以外の駒が前にしか進めないため、局面が後戻りしにくく、置き換えが起きにくいのです。それでも第16節の表が示すとおり、置き換えテーブルはノード数を確実に減らしています。主たる貢献は値の再利用ではなく、手の順序づけの改善です。

実際のエンジンでは、Board をそのまま辞書の鍵にする代わりに、Zobrist ハッシュという手法で局面を64ビットの整数に畳み込みます。各（マス, 駒種）の組にあらかじめ乱数を割り当てておき、盤上にある駒の乱数を排他的論理和で合成する方法です。駒を1つ動かしたときの更新が数回の排他的論理和で済む点が優れています。Albert Zobrist が1970年に提案しました（注10）。

16. 必殺手のヒューリスティックスと履歴ヒューリスティック

順序づけの手がかりをもう2つ紹介します。どちらも「過去にうまくいった手は、これからもうまくいく」という経験則に基づきます。

必殺手のヒューリスティックス

**必殺手のヒューリスティックス（killer move heuristic, KMH）**は、同じ深さの別のノードで切り捨てを起こした手を覚えておき、次のノードで優先的に調べる手法です。

根拠はこうです。ゲームツリーの同じ深さにあるノードは、たいてい似た局面です。相手が何を指したとしても、こちらの強力な一手（相手の重要な駒を取る手など）は依然として強力であることが多い。ある枝でその手が切り捨てを起こしたなら、隣の枝でも起こす見込みが高いわけです。

通常は深さごとに2手だけ保持します。

var killers: [[Move]] = Array(repeating: [], count: 64)   // 深さごとに2手

// β切り捨てが起きたとき（駒を取る手は元々優先されるので除く）
if !m.isCapture {
    killers[ply].insert(m, at: 0)
    if killers[ply].count > 2 { killers[ply].removeLast() }
}

履歴ヒューリスティック

**履歴ヒューリスティック（history heuristic, HH）**は、これを深さによらず全体に一般化したものです。「どのマスからどのマスへ」という移動そのものに点数をつけ、切り捨てを起こすたびに加点します。Jonathan Schaeffer が1989年に整理しました（注11）。

var history: [Int: Int] = [:]       // from * 64 + to → 実績点

// β切り捨てが起きたとき
history[m.from * 64 + m.to, default: 0] += depth * depth

加点を depth * depth にしているのは、深いところ（＝根に近い、探索の広い部分）で起きた切り捨てのほうが価値が高いからです。葉の近くでの切り捨ては1つの部分木しか節約しませんが、根の近くでの切り捨ては巨大な部分木を丸ごと省きます。

順序づけの実装

これらを優先度に変換して並べ替えます。

func order(_ ms: [Move], ply: Int, ttBest: Move?) -> [Move] {
    ms.sorted { a, b in score(a, ply, ttBest) > score(b, ply, ttBest) }
}

private func score(_ m: Move, _ ply: Int, _ ttBest: Move?) -> Int {
    if m == ttBest { return 1_000_000 }                    // 置き換えテーブルの最善手
    if m.isCapture { return 100_000 + m.captured.count }   // 多く取る手ほど先に
    if killers[ply].contains(m) { return 90_000 }          // 必殺手
    return history[m.from * 64 + m.to] ?? 0                // 履歴の実績点
}

各手法の寄与を測る

第12節の中盤局面で、手法を1つずつ積み上げて測りました。

深さ	α-βのみ	+必殺手・履歴	+置き換えテーブル	+繰り返し深化
6	2,978	865	804	1,106
7	6,914	2,859	2,252	2,342
8	20,926	5,433	3,134	4,212
9	52,578	15,197	8,484	10,035

深さ9で見ると、必殺手と履歴ヒューリスティックだけでノード数が 3分の1以下 になり、置き換えテーブルを加えるとさらに減って 6分の1 になっています。順序づけがα-βの効率をいかに左右するかがよく分かります。

最後の列（繰り返し深化つき）が1つ手前の列より多い点は、そのとおり報告しておきます。この設定では、繰り返し分の再探索コストが順序づけの改善分をわずかに上回りました。チェッカーは分岐係数が小さいため、繰り返しのオーバーヘッド b / (b - 1) が相対的に大きくなるからです。それでも実戦で繰り返し深化を使う理由は第14節のとおりで、持ち時間が尽きた時点で常に使える答えが手元にあるという性質にあります。ノード数だけで判断すべきものではありません。

順序づけには「情報」が要る

第10節で予告した測定です。順序づけの方法を変えて、α-βのノード数を比べました。

深さ	自然順	逆順	1手先の評価値順	ランダム順（10回平均）
6	2,978	3,189	2,874	2,838
7	6,914	7,655	6,691	6,506
8	20,926	20,174	20,363	18,304

ほとんど差がありません。 逆順にしてもランダムにしても1割程度しか変わらず、深さ8ではランダムのほうがわずかに良いくらいです。

一方で、必殺手と履歴ヒューリスティックを入れた表では、同じ深さ8でノード数が20,926から5,433へと4分の1近くまで減りました。この対比が示していることは明快です。手を並べ替えること自体に意味はありません。意味があるのは、良い手を先に持ってくる「情報」を持ち込むことです。 探索を減らすのは知識である、という記号主義AIに一貫した主題が、ここでも同じ形で現れます。

そのほかの拡張

実際のエンジンでは、さらに次のような手法が使われます。

手法	内容
アスピレーション・ウィンドウ	前回の値の近くに狭い `[α, β]` を張って探索し、外れたらやり直す
NegaScout / PVS	最初の手以外は「これは最善手ではない」と仮定して幅ゼロの窓で調べ、外れた場合だけ再探索する（注12）
無駄手（null move）による枝刈り	「1手パスしても相手に勝てる」なら、この枝は良すぎるとみなして切る
選択的延長	王手など重要な変化では深さを1手分延ばす
前向き枝刈り	見込みの薄い手を、値を確かめる前に切り捨てる。α-βと違い安全ではない

このうち前向き枝刈りだけは性質が異なります。α-βや置き換えテーブルは答えを変えませんが、前向き枝刈りは正しい手を捨ててしまう可能性があります。速度と正しさを交換する取引であり、Shannon の言う Type B の思想にあたります。

17. 序盤定石集と終盤データベース

探索を減らすもっとも直接的な方法は、答えを覚えておくことです。ゲームの序盤と終盤には、これが特に有効です。

序盤定石集

**序盤定石集（opening book）**は、序盤の局面と、そこで指すべき手の対応表です。チェスや将棋の序盤は何世紀にもわたって人間が研究してきた蓄積があり、探索で0から考え直すよりも、その蓄積を引くほうが速くて確実です。

序盤定石集が特に効くのは、序盤が探索にとって最も苦手な局面だからです。駒がすべて盤上にあるので分岐係数が最大で、しかも良し悪しが表れるのは何十手も先です。評価関数と数手の先読みでは、序盤の微妙な優劣を捉えられません。定石集を引いている間、プログラムは実質的に無限の深さで探索していることになります。

終盤データベース

終盤では逆の性質が現れます。駒が減って局面数が扱える範囲に収まるので、すべての局面を後ろ向きに解いて表にしておくことができます。これを終盤データベース（endgame database）、チェスでは**エンドゲーム・テーブルベース（endgame tablebase）**と呼びます。

作り方は探索ではなく後ろ向き帰納です。まず勝敗が確定している局面に印をつけ、そこから1手戻れる局面、2手戻れる局面…と逆向きに広げていきます。完成した表を引けば、その局面の理論値（勝ち・引き分け・負け）と最善手が即座に分かります。

チェッカーの終盤データベースは特別な位置を占めています。Jonathan Schaeffer らのプログラム Chinook は、駒が10個以下のすべての局面（約39兆局面）を解いた表を持っていました。これが1994年の世界チャンピオン獲得を支え、最終的に2007年、チェッカーは引き分けであることが証明されました（注13）。序盤からの前向き探索と終盤データベースからの後ろ向き解析を突き合わせる方法で、探索した局面はおよそ 10¹⁴ に及びます。第6節の表にあるとおり、チェッカーの全局面数は 10²⁰ ですから、そのおよそ100万分の1を調べただけで結論が出たことになります。α-β枝刈りと終盤データベースの威力です。

18. コンピュータ・チェス

コンピュータ・チェスは、ゲームプレイと問題解決の研究において最も長く、最も集中的に取り組まれてきた対象です。この記事で扱ってきた手法のほとんどが、チェスのために発明されたか、チェスで実用性を証明されました。

出発点

1950年に Claude Shannon が発表した論文が、事実上すべての出発点です（注4）。この論文はすでに次の要素をすべて含んでいました。

局面を数値化する静的評価関数（駒得＋可動性＋ポーン構造の線形結合）
ミニマックスによる先読み
固定深さで打ち切る方式（Type A）と、有望な手だけを選んで深く読む方式（Type B）の対比
駒の取り合いの途中で評価してはいけないという指摘（静止探索の原型）
ゲームツリーの大きさが 10¹²⁰ 程度であるという見積もり

Alan Turing もほぼ同時期に Turochamp を設計しています。当時これを動かせる計算機がなかったため、Turing は自分で紙の上で手順を実行して対局しました（注14）。

α-β枝刈りは、1950年代後半に複数の研究者が独立に見つけています。John McCarthy が名前を与え、Newell・Shaw・Simon のチェスプログラム（1958年）や Arthur Samuel のチェッカープログラムが同種の考え方を使っていました。厳密な解析は1975年の Knuth と Moore による論文まで待つことになります（注6）。

Type A の勝利

Shannon は Type B（人間のように有望な手を選んで深く読む）のほうが有望だと考えていました。実際の歴史はそうなりませんでした。

計算機が速くなるにつれ、単純な評価関数で全幅を深く読む Type A が優位に立ちました。選択的に読むには「どの手が有望か」を判断する必要があり、その判断自体が間違えるからです。間違えて捨てた手が最善手だった場合、取り返しがつきません。一方、全幅探索は遅くても間違えません。

この方向を象徴するのが Deep Blue です。1997年、当時の世界チャンピオン Garry Kasparov に6局のマッチで勝利しました（注15）。専用ハードウェアで毎秒2億局面を評価し、通常12手前後、変化によっては40手以上を読んでいました。中身は本記事で扱った手法の集大成です。α-β、繰り返し深化、置き換えテーブル、静止探索、序盤定石集、終盤データベース。新しい原理はほとんどありません。あったのは、既知の手法の徹底的な最適化と、専用ハードウェアによる圧倒的な速度でした。

Deep Blue の勝利がAIにとって何を意味したかについては、当時から議論があります。「知能」と呼べるものは実装されておらず、しているのは高速な探索と単純な評価だけだからです。一方で、チェスの強さが探索の量でここまで説明できてしまうという事実自体が、この分野の重要な発見でもありました。

その後

2000年代以降、市販の計算機で動くプログラムが人間の最高峰を明確に上回りました。Stockfish に代表される現代のエンジンは、本記事の手法に加えて、探索の枝を大胆に削る手法（late move reductions など）と、対局データから調整された評価関数を組み合わせています。

2017年の AlphaZero は別の方向を示しました。ルール以外の知識を与えず、自己対局だけで評価関数と方策を学習し、探索にはα-βではなくモンテカルロ木探索（第20節）を使うものです（注16）。この流れを受けて、現在の主要なエンジンはα-β探索と、ニューラルネットワークによる評価関数（NNUE など）を組み合わせた形に落ち着いています。探索の枠組みは古典的なままで、評価関数だけが学習されたものに置き換わったと見ることができます。

19. 将棋

将棋はチェスと同じ枠組み（2人・離散・完全情報・確定的）に収まりますが、探索の観点では明確に難しくなっています。理由は持ち駒です。

取った駒を自分の駒として盤上に打てるため、次の2つが起きます。

分岐係数が大きい：チェスの約35に対し、将棋は約80。打つ手の選択肢が加わるためです
駒が減らない：チェスは駒が減って終盤に向かうにつれ単純になりますが、将棋は盤上の駒が減っても持ち駒として戻ってきます。終盤データベースを作りにくく、静止探索の終了も自明ではありません

ゲームツリーの大きさは 10²²⁶ 程度と見積もられており、チェスの 10¹²³ を大きく上回ります（注3）。

探索の適用

それでも、基本の枠組みはそのまま通用します。α-β枝刈り、繰り返し深化、置き換えテーブル、必殺手・履歴ヒューリスティックは将棋のプログラムでも標準的に使われています。将棋固有の工夫としては、詰将棋の専用ルーチンがあります。終盤で詰みを読む部分は、通常の評価関数つき探索ではなく、AND/ORグラフに対する専用の探索（df-pn など）で解くほうがはるかに効率的だからです。1997年には脊尾昌宏のプログラムが、当時最長とされた詰将棋「ミクロコスモス」（1525手詰）を解いています（注17）。

評価関数の学習

将棋のプログラミングにおける転換点は、保木邦仁の Bonanza（2005年）でした。それまで将棋の評価関数は、開発者が人間の棋力に基づいて手作業で調整するものでした。Bonanza は2つの点でこれを覆しました。

全幅探索：将棋では手が多すぎるため選択的探索が必須と考えられていたのに対し、チェス流の全幅α-β探索を採用した
評価関数の機械学習：プロ棋士の棋譜を教師データとして、「棋譜の指し手が探索で最善と評価されるように」重みを自動調整した（Bonanza メソッド、後に 3駒関係 による大規模な特徴量へ発展）

これは第8節で述べた「評価関数の重みをどう決めるか」という問題への直接的な答えであり、Samuel がチェッカーで試みたことの現代版でもあります。以後、将棋プログラムの評価関数は学習で作るのが標準になりました。

2010年代には、コンピュータ将棋とプロ棋士の公開対局が継続的に行われ、2017年には当時の名人が Ponanza に敗れています。現在は将棋でも、探索はα-βの系譜、評価関数はニューラルネットワークという組み合わせが主流です。

20. 囲碁

囲碁は、本記事の枠組みがそのままでは通用しなかったゲームです。理由は2つあり、どちらも本質的です。

なぜ難しいのか

第一に、分岐係数が桁違いに大きい。 19路盤には361の交点があり、序盤の合法手は250前後です。チェスの35と比べると、同じ深さを読むのに必要なノード数が比較にならないほど増えます。合法な局面数は 2.08 × 10¹⁷⁰ と正確に数え上げられています（注18）。

第二に、そして決定的に、静的評価関数が作れない。 これが本当の壁でした。チェスやチェッカーなら「駒を数える」という強力で単純な手がかりがあります。囲碁にはそれがありません。盤上の石の数は優劣とほとんど関係がなく、地の大きさは石の配置が確定するまで決まらず、石の生死は数十手先の攻め合いの結果として初めて定まります。ある石が生きているか死んでいるかを判定すること自体が、それ自体で探索を要する難しい問題なのです。

第7節で述べた「深く探索するほど強くなる」という関係は、評価関数がそれなりに正しいという前提の上に成り立っています。囲碁ではその前提が崩れており、そのためα-βを深く回しても強くなりませんでした。1990年代から2000年代半ばまで、囲碁プログラムはアマチュア初級者の域を出ませんでした。

モンテカルロ木探索

突破口は2006年前後に開かれました。静的評価関数を作るのをやめ、代わりにランダムな対局を終局まで打ち進めて勝率を測るという発想です。局面の良し悪しを盤面の特徴から判断する代わりに、そこから何度もでたらめに終局まで打ってみて、勝った割合で近似します。

これを木探索と組み合わせたものがモンテカルロ木探索（Monte Carlo tree search, MCTS）です。Rémi Coulom が2006年に定式化し、Levente Kocsis と Csaba Szepesvári がUCT（多腕バンディット問題の UCB1 を木に適用したもの）によって、有望な枝を深く調べることと未知の枝を試すことのバランスを理論的に扱えるようにしました（注19）。

MCTS はミニマックスと性質が大きく異なります。

	ミニマックス＋α-β	モンテカルロ木探索
木の形	一様な深さまで全幅	有望な枝だけ非対称に深く伸びる
葉の評価	静的評価関数	ランダム対局の勝率
値の意味	評価関数による推定値	勝率の推定値
途中で止めた場合	深さが揃っていないと使えない	いつ止めても、その時点の統計が使える
必要な領域知識	評価関数の設計が必須	原理的には勝敗判定だけでよい

評価関数の設計が不要という点が、囲碁にとって決定的でした。MCTS を採用した Crazy Stone や MoGo は、それまでのプログラムを大きく上回り、9路盤ではプロに迫る水準に達しました。

AlphaGo

それでも19路盤でトップ棋士に及ぶには、もう一段が必要でした。2016年の AlphaGo は、MCTS に2つのニューラルネットワークを組み合わせました（注20）。

方策ネットワーク（policy network）：この局面で有望な手はどれかを出力する。MCTS が調べる枝を絞り込むのに使う
価値ネットワーク（value network）：この局面の勝率はどれくらいかを出力する。ランダム対局の代わり、あるいはその補完として使う

AlphaGo は2016年に李世乭（イ・セドル）九段に4勝1敗で勝利しました。翌年の AlphaGo Zero は人間の棋譜を一切使わず自己対局のみで学習し、さらに AlphaZero は同じ枠組みを囲碁・チェス・将棋に適用して、いずれでも当時最強のプログラムを上回りました（注16）。

ここで注目したいのは、AlphaGo が探索を捨てていないことです。使っているのはあくまで木探索であり、ニューラルネットワークが担っているのは第8節で扱った静的評価関数と、第10節・第16節で扱った手の順序づけ、つまり探索を絞り込むための知識の部分です。本記事で見てきた構造そのものは維持されています。

囲碁の物語が示しているのは、探索の枠組みは正しかったが、それを支える知識を人間が書き下せる領域とそうでない領域があるということです。チェスやチェッカーでは「駒を数える」という知識を人間が書けました。囲碁ではそれが書けず、学習で獲得するほかありませんでした。

まとめ

2人でプレイする離散的で完全情報のゲームは、ステート空間問題とほぼそのまま対応します。違いは、演算子を適用する主体が交互に入れ替わり、一方が値を最大化し他方が最小化しようとする点、そして解が経路ではなく戦略になる点だけです。ミニマックスアルゴリズムは、この構造を素直に再帰で書き下したものでした。

しかし完全なゲームツリーの探索は、玩具のようなゲームを除いて組み合わせ論的爆発によって不可能です。実用的なプログラムは、次の2つの妥協から出発します。

決めた深さで打ち切り、静的評価関数で局面を推定する（切り捨て探索）
結論に影響しない部分木を、論理的に安全な形で省く（α-β枝刈り）

そのうえに積み上げられた工夫は、大きく2種類に分かれます。

答えを変えずに速くするもの――α-β枝刈り、置き換えテーブル、手の順序づけ（必殺手・履歴ヒューリスティック）、繰り返し深化。これらは探索するノード数を減らすだけで、返す値は変わりません。

答えの質を上げるもの――静止探索（水平線効果の緩和）、序盤定石集、終盤データベース、選択的延長。これらは探索に知識を持ち込み、限られた深さでより正しい判断をさせます。

チェッカーでの実測では、素のネガマックスに対してα-βだけで深さ9のノード数が38分の1になり、手の順序づけ・置き換えテーブル・繰り返し深化まで加えると197分の1になりました。しかも返す最善手は最初から最後まで同じです。そして、順序づけの実験が示したとおり、ノード数を減らしたのは並べ替えという操作ではなく、良い手を先に見るという情報でした。

コンピュータ・チェスの歴史は、この枠組みを速度によってどこまで押し切れるかの実験であり、Deep Blue はその到達点でした。将棋は分岐係数と持ち駒によって同じ枠組みをより厳しい条件に置き、評価関数を学習で作る方向を先に開きました。囲碁は静的評価関数が書けないという理由で枠組みそのものを一度拒み、モンテカルロ木探索と学習された評価関数によって、探索の枠組みの中へ改めて取り込まれました。

前回の記事の結びと同じことが、ここでも言えます。探索を減らすのは知識である。 ゲームプログラミングの歴史は、その知識を人間が書き下すところから、対局の経験から学習させるところへ移っていった歴史でもあります。

注釈

Ernst Zermelo, "Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels"（1913年）。2人・有限・完全情報・確定的なゲームには確定した理論値が存在することを、集合論を用いて示した。ゼロサム2人ゲームにおけるミニマックス定理は John von Neumann（1928年）による。
ネガマックス形式は Donald E. Knuth・Ronald W. Moore の解析（注6）で整理された表記。ゼロサム性 min(a, b) = -max(-a, -b) を用いてMAXノードとMINノードの処理を1つにまとめる。
分岐係数・深さ・ゲームツリーの大きさの見積もりは、Louis Victor Allis, "Searching for Solutions in Games and Artificial Intelligence"（博士論文、1994年）の整理に基づく、広く引用されている概数。桁の目安として扱うべき値で、局面の定義や数え方によって変動する。
Claude E. Shannon, "Programming a Computer for Playing Chess"（Philosophical Magazine, 1950年）。静的評価関数、ミニマックス、Type A / Type B の区別、駒の取り合いの途中で評価してはならないという指摘、そしてゲームツリーの大きさの見積もり（シャノン数）を含む、この分野の出発点となった論文。
Arthur L. Samuel, "Some Studies in Machine Learning Using the Game of Checkers"（IBM Journal of Research and Development, 1959年）および続編（1967年）。評価関数の重みを対局から自動調整する手法（丸暗記学習、後に signature table）を示し、機械学習という語を広めた研究として知られる。
Donald E. Knuth・Ronald W. Moore, "An Analysis of Alpha-Beta Pruning"（Artificial Intelligence, 1975年）。最適な手の順序のもとでα-β探索が調べるノード数がおよそ b^(d/2) になることを示した。α-βの考え方自体は1950年代後半に John McCarthy、Allen Newell・John Shaw・Herbert Simon、Arthur Samuel らによって独立に見出されている。
Hans J. Berliner, "Some Necessary Conditions for a Master Chess Program"（IJCAI, 1973年）。固定深さで探索を打ち切ることに起因する評価の誤りを水平線効果として指摘した。
David J. Slate・Lawrence R. Atkin, "CHESS 4.5 — The Northwestern University Chess Program"（Chess Skill in Man and Machine, 1977年）。繰り返し深化を時間制御と手の順序づけの両方に活用する方式を確立した。
Richard D. Greenblatt・Donald E. Eastlake・Stephen D. Crocker, "The Greenblatt Chess Program"（AFIPS, 1967年）。Mac Hack VI として知られ、置き換えテーブルを導入した初期の例。人間との公式戦で勝利した最初のチェスプログラムでもある。
Albert L. Zobrist, "A New Hashing Method with Application for Game Playing"（1970年、技術報告）。各（マス, 駒種）の組に乱数を割り当て、排他的論理和で局面を64ビットに畳み込む手法。差分更新が排他的論理和だけで済む点が探索と相性がよい。
Jonathan Schaeffer, "The History Heuristic and Alpha-Beta Search Enhancements in Practice"（IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989年）。履歴ヒューリスティックを定式化し、各種の探索改良手法を実験的に比較した。必殺手のヒューリスティックスはそれ以前から広く使われていた。
Judea Pearl の Scout アルゴリズム（1980年）を実用化したものが Alexander Reinefeld の NegaScout（1983年）で、principal variation search（PVS）としても知られる。同種の考え方を反復的に適用するものに Aske Plaat らの MTD(f)（1996年）がある。
Jonathan Schaeffer ほか, "Checkers Is Solved"（Science, 2007年）。チェッカーが双方最善で引き分けであることを証明した。前向きのα-β探索と、駒10個以下の終盤データベース（約39兆局面）を突き合わせる方法による。Chinook は1994年に世界チャンピオンの称号を得ている。
Alan Turing の Turochamp（1948年に着想、1953年に手順として公表）。当時これを実行できる計算機がなく、Turing は紙の上で手続きを実行して対局した。
1997年5月の Deep Blue 対 Garry Kasparov の6局マッチ。Deep Blue が2勝1敗3引き分けで勝利した。技術的な報告は Feng-hsiung Hsu, "Behind Deep Blue"（2002年）および Murray Campbell ほか, "Deep Blue"（Artificial Intelligence, 2002年）にある。
David Silver ほか, "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play"（Science, 2018年）。AlphaZero がルール以外の知識を与えられずに自己対局のみで学習し、囲碁・チェス・将棋のいずれでも当時最強のプログラムを上回ったことを報告した。
詰将棋の探索は、通常の評価関数つきα-β探索ではなく、AND/ORグラフに対する証明数探索（df-pn など）で扱われる。1997年に脊尾昌宏のプログラムが「ミクロコスモス」（1525手詰）を解いた。df-pn は長井歩・今井浩（2002年）による。
John Tromp が2016年に、19路盤の合法な局面数を 2.081681994 × 10¹⁷⁰ と正確に数え上げた。
Rémi Coulom, "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search"（Computers and Games, 2006年）がモンテカルロ木探索を定式化し、Levente Kocsis・Csaba Szepesvári, "Bandit based Monte-Carlo Planning"（ECML, 2006年）が UCB1 を木探索に適用した UCT を示した。
David Silver ほか, "Mastering the game of Go with deep neural networks and tree search"（Nature, 2016年）。方策ネットワークと価値ネットワークをモンテカルロ木探索に組み合わせた AlphaGo を報告した。人間の棋譜を使わない AlphaGo Zero は同誌2017年の論文による。
本記事のチェッカー実装は、イングリッシュ・ドラフツ（8×8、強制取り、通常の駒は前方のみ）の規則に従う。手の生成は初期局面からの perft を深さ9まで公表値と照合して検証した。掲載したノード数・評価値・実効分岐係数はすべて実測値である。

参考資料

元記事（Bitz Notebook）: ゲームプレイと探索 ― ミニマックスとα-β枝刈りから、コンピュータ・チェスとチェッカーの実装まで

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

ゲームプレイと探索 ― ミニマックスとα-β枝刈りから、コンピュータ・チェスとチェッカーの実装まで

ゲームプレイと探索 ― ミニマックスとα-β枝刈りから、コンピュータ・チェスとチェッカーの実装まで

目次

はじめに

1. 技のゲームとステート空間の対応関係

2. ゲームツリー

3. 棒取りゲーム ― 完全なゲームツリーを解く

4. ミニマックスアルゴリズム

5. ネガマックス ― 2つの視点を1つにまとめる

6. 組み合わせ論的爆発

7. 静的評価による切り捨て探索

8. 静的評価関数

9. α-β枝刈り

基本のアイデア

動きを追う

10. α-βの効率と手の順序づけ

11. サンプルプログラム ― チェッカー

11.1 チェッカー盤

11.2 手の生成

11.3 手の生成の検証

11.4 静的評価関数

12. ミニマックスとα-βの実測

13. 静止探索と水平線効果

水平線効果

静止探索

14. 繰り返し深化

15. 置き換え問題と置き換えテーブル

16. 必殺手のヒューリスティックスと履歴ヒューリスティック

必殺手のヒューリスティックス

履歴ヒューリスティック

順序づけの実装

各手法の寄与を測る

順序づけには「情報」が要る

そのほかの拡張

17. 序盤定石集と終盤データベース

序盤定石集

終盤データベース

18. コンピュータ・チェス

出発点

Type A の勝利

その後

19. 将棋

探索の適用

評価関数の学習

20. 囲碁

なぜ難しいのか

モンテカルロ木探索

AlphaGo

まとめ

注釈

参考資料