GambitBoard ができるまで — チェス AI を自前で書く

GambitBoard は、一人でも遊べるチェスです。ルール判定は chess.js に任せ、対局する AI は自前で書きました。アルファベータ探索・取る手の並べ替え・静止探索・駒の位置評価・反復深化 ── 教科書的な要素を素直に積んだエンジンです。

#🎯 ルールは借りて、思考は自分で書く

チェスを実装するとき、面倒なのは AI ではなくルールです。アンパサン、キャスリング、プロモーション、ステイルメイト、三回同形反復、50 手ルール。全部書くと AI に手が回りません。

なので ルール判定は chess.js に委譲し、自分は「どの手を指すか」だけを書くことにしました。合法手の生成も詰みの判定も向こう任せです。

この切り分けは正解でした。面白いのは思考のほうで、ルールは正しく動けば誰が書いても同じです。

#⚖️ 評価関数 ── 駒の価値 + 位置の価値

局面の良し悪しを数値にするのが評価関数です。基本は駒の点数(ポーン 1、ナイト・ビショップ 3、ルーク 5、クイーン 9)ですが、それだけだと駒を取り合うだけの AIになります。

そこで Piece-Square Table (PST) を足しました。「同じ駒でも、盤上のどこにいるかで価値が違う」という表です。

• ナイトは中央が強く、隅は弱い
• ポーンは前に進むほど価値が上がる
• キングは序盤は隅に隠れているほうが安全

この表があるだけで、AI が中央を取りに来たり、ポーンを前に出したりするようになります。駒得しか見ない AI と、形を作る AI の差がここです。

黒番の評価は、盤を上下反転させて白用の表を引いています。表を 2 つ持たずに済み、非対称なバグも防げます。

#🌲 Negamax + アルファベータ

探索は negamax です。ミニマックスの変形で、**「相手にとっての評価は自分の評価の符号反転」**という性質を使って、最大化と最小化を 1 つの関数にまとめます。

const score = -negamax(chess, depth - 1, -beta, -alpha, ply + 1, ctx)

再帰呼び出しで α と β を入れ替えて符号を反転するのが negamax の型です。これだけで手番ごとの場合分けが消えます。

アルファベータ枝刈りは「もうこの手は選ばれないと分かった時点で、その先を調べない」最適化です。効きは手の順番に強く依存します。良い手を先に調べるほど、後の枝が早く切れる。

#🎯 MVV-LVA ── 取る手を先に調べる

そこで手を並べ替えます。使ったのは MVV-LVA(Most Valuable Victim - Least Valuable Aggressor)。

// 取られる駒の価値が高く、 取る駒の価値が低い手から調べる

「ポーンでクイーンを取る」が最優先、「クイーンでポーンを取る」は後回し。得が大きい手ほど枝刈りが効きやすいので、そこから調べます。

並べ替えを入れる前と後で、同じ深さの探索時間が体感で数倍変わりました。アルファベータは順番がすべてです。

#🔍 静止探索 ── 取り合いの途中で止めない

探索の深さで打ち切ると、致命的な誤判定が起きます。取り合いの途中で評価してしまう問題です。

「クイーンでポーンを取った」局面で深さが尽きると、AI は「ポーン 1 点得した」と判断します。次の手でクイーンを取り返されるのに。これを 水平線効果 と呼びます。

対策が 静止探索(quiescence search) です。深さが 0 になっても、取る手だけは続けて調べる。

function quiesce(chess, alpha, beta, ctx): number {
  const standPat = evaluate(chess)
  if (standPat >= beta) return beta
  if (standPat > alpha) alpha = standPat
  // 取る手だけを生成して 再帰

  const score = -quiesce(chess, -beta, -alpha, ctx)
  ...
}

standPat(何もしないときの評価)を下限に置くのがポイントで、「取り合いに参加しない」という選択肢も残します。これがないと、不利な取り合いを強制されたことになってしまいます。

静止探索を入れた瞬間に AI が強くなるのが、作っていて一番はっきり分かった変化でした。

#⏱️ 反復深化 ── 時間で打ち切る

深さを固定すると、局面によって思考時間がばらつきます。序盤は速いのに終盤で固まる、といったことが起きる。

そこで深さ 1 から順に探索し、時間切れになったら直前の結果を使う反復深化にしました。

if (ctx.timedOut) return alpha

一見すると無駄に見えます(深さ 1〜4 を捨てて 5 を使う)。でも探索木は指数的に増えるので、浅い探索のコストは全体のごく一部です。しかも浅い探索で得た「良さそうな手」を次の深さで先に調べれば、枝刈りが効いて結局速くなります。

強さ 3 段階は、この思考時間の上限を変えているだけです。

#😓 苦労したところ

UI が固まる。 探索は同期処理なので、思考中はブラウザが止まります。深さを浅くするか、Web Worker に逃がすかの二択でした。今は思考時間の上限を短めに取り、「AI 思考中」の演出を出して待たせています。Worker 化は積み残しです。

強さの調整。 弱いと退屈、強いと勝てない。3 段階を用意して、一番弱い設定では評価にわずかなノイズを混ぜています。完璧に最善を指す弱い AI より、たまに緩む AI のほうが対局として楽しいと判断しました。

演出。 駒が瞬間移動すると何が起きたか分かりません。移動アニメーション、王手の点滅、駒を取ったときのエフェクト、詰みの演出を入れました。思考の結果を見せるだけでなく、指し手が読めるようにする部分です。

#🔭 今後の拡張

• Web Worker へ探索を逃がして UI を止めない
• トランスポジションテーブル(同じ局面の再計算を省く)
• オープニングブック(定跡)
• 棋譜の PGN 書き出し

#💡 このサービスから言えること

借りるところと書くところを最初に分けると、面白い部分に時間を使えます。 ルールを自作していたら、静止探索まで到達しなかったはずです。

そして探索系は、教科書の要素を素直に積むだけで確実に強くなります。アルファベータ、手の並べ替え、静止探索、反復深化 ── どれも 1960〜70 年代に確立した手法で、それぞれ数十行。工夫を発明する前に、既にある道具を全部使うほうが早いと感じました。