五目並べ AI：必殺判定と探索の分業

五目並べ の AI は当初、深さ 4 の素の alpha-beta だけでした。結果は散々で、相手の活三を放置し、自分の勝ち手を見逃すこともありました。深さが足りないと、評価関数が「三手後に負ける」を普通の局面として読んでしまうためです。

解決策は深さを増やすことではなく、盤面だけで確定する手を探索から外に出すことでした。

三層、順番は固定

順	判定	動作
1	自分が五連を作れるか	即打つ、探索しない
2	相手が次に五連を作れるか	受ける
3	自分／相手が活四を作れるか	打つ／潰す
4	いずれも無し	alpha-beta に渡す

前の三つが必殺判定層です。共通する性質は「盤面の形だけで決まり、後の展開に依存しない」こと。これを探索に渡すと、確定事実を再検証するためにノードを浪費し、しかも浅い深さでは検証しきれず間違えます。

探索は不確実性のためにある。盤面が既に語っていることを再発見させる場所ではない。

活四を独立に判定する理由

活四（.XXXX.）は両端が空いた四連で、相手は一子では両端を止められません。つまり出た時点で勝ちです。

第三層で単に「四連があるか」を見ると、片端を塞がれた棒四も数えてしまいます。相手に一手で消されるので、打てば手番の無駄遣いです。よって形の文字列で判定します。011110 が活四、011112 と 211110 は棒四です。

四方向それぞれ 9 マスの窓を走査し、0/1/2 の文字列にして照合します。

const PATTERN = {
  FIVE: 1e7,
  OPEN_FOUR: 3e5,
  FOUR: 2.6e4,
  OPEN_THREE: 2e4,
  THREE: 1100,
  OPEN_TWO: 600,
  TWO: 90,
  ONE: 6,
};

この数値は任意ではありません。五連が他全部の合計を上回ること、そして活四が活三二つより大きいこと。後者を破ると、必勝の活四を二つの脅威と交換してしまいます。

探索層の標準部品三点

• 反復深化：深さ 1 から順に探索し、完了した最後の層を保持。時間切れでも途中の層ではなく、直前の完了層の結論が使えます。
• 置換表：Zobrist ハッシュを鍵に、深さ・評価・境界種別（正確／上界／下界）を保存。
• 候補の絞り込み：既存の石の近傍のみ。225 点のうち検討に値するのは通常 20 点未満です。

見落としやすい点が一つ。時間予算は探索の内部で確認します。外側の setTimeout では駄目です。1024 ノードごとに時計を見て中断フラグを立て、層ごとに巻き戻します。そうしないと途中で切れた層の評価が、不完全な木から計算されてしまいます。

難易度とは予算のこと

五段階は一つのエンジンと五組のパラメータです。

難易度	深さ	時間	揺らぎ	候補幅
1 初心者	1	90ms	0.9	8
2 入門	2	200ms	0.5	10
3 中級	4	450ms	0.18	12
4 上級	6	900ms	0.04	14
5 達人	8	1800ms	0	16

「揺らぎ」は上位候補からのランダム選択です。深さを下げるだけでは弱くなりません。必殺判定層が残るので、初心者でも五連の機会は逃しません。

AI に考えを語らせる

調整中に必ず困るのが「なぜこの手を選んだのか」です。探索の記録自体は簡単で、層ごとの深さ・最善手・評価と、根の候補数件を残すだけです。

本当に手間がかかったのは評価値でした。alpha-beta が返すのは殆ど境界値、つまり「X より良くはない」です。それを表示すると候補が全部同じ数字になり、壊れているように見えます。そこでツリーを開いた時だけ、根の候補を全幅探索し直して正確な値を取ります。遅くなりますが、実際に見たい人だけが払うコストです。

利用者に見せる数字は本物でなければならない。境界値で組んだ「過程」は、過程が無いより悪い。

まとめ

現在の強さは「活三を尊重する」程度です。本物のエンジンはもっと多くを持ちます（VCF/VCT 探索、評価の学習）。しかしブラウザゲームでは、深さを 4 から 8 に上げるより必殺判定層の方がはるかに効きました。勝敗は大抵、短い手順で決まるからです。