五子棋 AI 的强弱，九成取决于”在一个固定时间预算内能搜多深”。而决定搜索深度的，不是评估函数有多花哨，而是着法排序（move ordering）有多准——排序好的话，Alpha-Beta 的剪枝率能从 50% 拉到 90% 以上，等效深度直接翻倍。
本文讲两个在实战引擎里最常被低估的加速器：后期着法削减（LMR, Late Move Reductions） 和 杀手启发（Killer Heuristic）。它们不是新算法，而是让 Alpha-Beta 从”能用”变成”能打”的关键。
一、Alpha-Beta 的天花板在哪里
标准 Alpha-Beta 的节点数是 O(b^(d/2))（完美排序）到 O(b^d)（最差排序）——同一棵树上差了几个数量级。所以优化方向只有两个：
- 让好着法排前面（排序质量）：杀手启发、历史启发、置换表着法。
- 让差的着法少花时间（削减策略）：LMR、空着裁剪、后期着法削减。
这两条路互补：排序越好，削减越安全（因为被削减的确实是坏着法）；削减越激进，同样时间内能搜的着法越多，排序信息也越丰富。
二、LMR：给靠后的着法一个”试用深度”
LMR 的观察极其朴素：如果前 4 个着法还没剪出好结果，那么第 20 个着法大概率也不会好。所以在排序后的着法列表里：
- 前
M个着法（通常 M=3~4）用全深度搜索。 - 其余着法先用
depth - R的削减深度做一次零窗口试探。 - 只有当着法在削减深度下仍然返回 ≥ alpha（说明它可能真的不错），才重新用全深度搜索。
伪代码：
for i, move in moves:
if i < M or isTactical(move) or depth <= 2:
score = search(depth-1, -beta, -alpha)
else:
R = reduction(i, depth)
score = search(depth-1-R, -alpha-1, -alpha) // 零窗口试探
if score > alpha: // 削减后仍有希望
score = search(depth-1, -beta, -alpha) // 全深度重搜
关键点：
- 零窗口（
-alpha-1, -alpha）让试探只回答”能不能超过 alpha”，剪枝极强。 - R 的取值要随深度和着法序号增长：
R = 1 + i/8 + depth/16，并封顶（如 3）。固定 R 会让深搜浅、浅搜乱。 - 战术着法不削减（吃子、成五、冲四），否则会漏杀。这一点没做好，引擎会”看不见”对手的两步杀。
三、杀手启发：同一层的”沉默杀手”
杀手启发来自一个经验事实：在树的同一层，导致剪枝的着法往往在不同分支里反复出现。比如某个”形成活三”的点，在父节点另外几个分支里也常常是剪枝点。
做法：为每一层深维护两个槽位 killer[depth][0..1]。当某着法在 depth 层产生 beta 截断（剪枝），就把它记进该层杀手槽（若已在槽中则跳过；否则挤掉最旧的一个）。
搜索时，第一遍遍历着法前，先尝试这两个杀手着法（如果它们合法），排在正常排序之前。这一步成本几乎为零，但常常在开头就剪掉整棵子树。
杀手与历史启发的区别：历史启发是全局的（按 (side, from, to) 累计），杀手是按层局部的。前者适合长期积累，后者对”当前深度的战术共性”更敏感。两者相加效果最好。
四、五子棋的着法生成与排序
五子棋（15×15）的分支因子是 225，比国际象棋大得多，所以排序必须非常”便宜”。
实践中用增量棋型评分：棋盘维护一个”每点得分”数组，落子后只更新受影响的 4 个方向（每方向 4 格范围内）。评分按棋型分档：
成五 = 100000
活四 = 10000
冲四 = 1000
活三 = 1000
眠三 = 100
活二 = 100
眠二 = 10
总分 = 己方得分 × 1.0 + 对方（若我在此落子，对方被破坏的价值）× 0.9。这个 0.9 的系数是攻守平衡的关键——纯进攻的引擎在防守上会崩。
五、Java 完整实现
gomoku-lmr/
├── src/main/java/com/example/gomoku/
│ ├── Board.java // 棋盘、落子、增量评分
│ ├── Patterns.java // 棋型识别与打分
│ ├── MoveGenerator.java // 候选着法生成（邻域裁剪）
│ ├── MoveOrderer.java // 杀手启发 + 历史启发排序
│ ├── LmrSearch.java // LMR + 零窗口 + PVS 主搜
│ └── GomokuDemo.java // 主流程
└── pom.xml
5.1 棋盘与棋型打分
package com.example.gomoku;
/** 15×15 棋盘：0 空、1 黑、2 白 */
public class Board {
public static final int SIZE = 15;
public static final int EMPTY = 0, BLACK = 1, WHITE = 2;
public final int[][] cells = new int[SIZE][SIZE];
public int stoneCount = 0;
public boolean inBounds(int r, int c) {
return r >= 0 && r < SIZE && c >= 0 && c < SIZE;
}
public boolean isEmpty(int r, int c) {
return inBounds(r, c) && cells[r][c] == EMPTY;
}
public boolean place(int r, int c, int color) {
if (!isEmpty(r, c)) return false;
cells[r][c] = color;
stoneCount++;
return true;
}
public void undo(int r, int c) {
cells[r][c] = EMPTY;
stoneCount--;
}
/** 五连检测：只需检查以 (r,c) 为中心的 4 条线 */
public boolean isWin(int r, int c) {
int color = cells[r][c];
if (color == EMPTY) return false;
int[][] dirs = {{0,1},{1,0},{1,1},{1,-1}};
for (int[] d : dirs) {
int cnt = 1;
for (int s = 1; s <= 4; s++) {
int nr = r + d[0]*s, nc = c + d[1]*s;
if (!inBounds(nr, nc) || cells[nr][nc] != color) break;
cnt++;
}
for (int s = 1; s <= 4; s++) {
int nr = r - d[0]*s, nc = c - d[1]*s;
if (!inBounds(nr, nc) || cells[nr][nc] != color) break;
cnt++;
}
if (cnt >= 5) return true;
}
return false;
}
}
package com.example.gomoku;
/**
* 棋型打分。对每个空点，沿 4 个方向抽取"以该点为中心的窗口串"，
* 再按串中的连子形态归类打分。这里用简化的模式表，避免正则开销。
*/
public class Patterns {
public static final int FIVE = 1_000_000;
public static final int OPEN_FOUR = 100_000;
public static final int FOUR = 10_000; // 冲四
public static final int OPEN_THREE = 8_000;
public static final int THREE = 800;
public static final int OPEN_TWO = 500;
public static final int TWO = 50;
public static final int ONE = 10;
private static final int[][] DIRS = {{0,1},{1,0},{1,1},{1,-1}};
/**
* 假设在 (r,c) 落 color 子之后，该点四个方向的棋型总分。
* 只扫描 ±4 格范围，成本约 4×9 = 36 次读取。
*/
public static int scoreAt(Board b, int r, int c, int color) {
int total = 0;
for (int[] d : DIRS) {
total += scoreDirection(b, r, c, color, d);
}
return total;
}
private static int scoreDirection(Board b, int r, int c, int color, int[] d) {
// 取 -4..+4 的窗口，中心放上 color（模拟落子）
int[] line = new int[9];
for (int k = -4; k <= 4; k++) {
int nr = r + d[0]*k, nc = c + d[1]*k;
if (k == 0) { line[k+4] = color; continue; }
if (!b.inBounds(nr, nc)) { line[k+4] = -1; continue; } // -1 表示墙
line[k+4] = b.cells[nr][nc];
}
return classify(line, color);
}
/** 按连续长度 + 两端是否开放来归类 */
private static int classify(int[] line, int color) {
int center = 4;
int run = 1;
for (int i = center - 1; i >= 0 && line[i] == color; i--) run++;
int openLeft = (center - run >= 0) && line[center - run] == 0;
int runR = 1;
for (int i = center + 1; i < line.length && line[i] == color; i++) runR++;
int openRight = (center + runR < line.length) && line[center + runR] == 0;
int total = run + runR - 1; // 中心被算了两遍
int openEnds = (openLeft ? 1 : 0) + (openRight ? 1 : 0);
if (total >= 5) return FIVE;
if (total == 4) return openEnds == 2 ? OPEN_FOUR : (openEnds == 1 ? FOUR : 0);
if (total == 3) return openEnds == 2 ? OPEN_THREE : (openEnds == 1 ? THREE : 0);
if (total == 2) return openEnds == 2 ? OPEN_TWO : (openEnds == 1 ? TWO : 0);
if (total == 1) return openEnds == 2 ? ONE : 0;
return 0;
}
}
5.2 候选着法生成：邻域裁剪
15×15 全盘 225 个点全部评分太贵。实际只在已有棋子周围 2 格范围内取候选，能把分支因子压到 30~60。
package com.example.gomoku;
import java.util.*;
/** 候选着法：仅取已有棋子邻域 2 格内的空点，按攻守综合分排序 */
public class MoveGenerator {
public static class Move {
public final int r, c;
public int score; // 排序分值，搜索中会被覆盖
public Move(int r, int c, int score) { this.r = r; this.c = c; this.score = score; }
}
/** 生成并排序候选着法（己方视角） */
public static List<Move> generate(Board b, int color, int radius) {
int opp = 3 - color;
Set<Integer> cand = new LinkedHashSet<>();
if (b.stoneCount == 0) {
List<Move> first = new ArrayList<>();
first.add(new Move(Board.SIZE / 2, Board.SIZE / 2, 0));
return first;
}
for (int r = 0; r < Board.SIZE; r++) {
for (int c = 0; c < Board.SIZE; c++) {
if (b.cells[r][c] == Board.EMPTY) continue;
for (int dr = -radius; dr <= radius; dr++) {
for (int dc = -radius; dc <= radius; dc++) {
int nr = r + dr, nc = c + dc;
if (b.isEmpty(nr, nc)) cand.add(nr * Board.SIZE + nc);
}
}
}
}
List<Move> moves = new ArrayList<>(cand.size());
for (int key : cand) {
int r = key / Board.SIZE, c = key % Board.SIZE;
// 攻守综合：己方落子收益 + 0.9 × 阻断对手的收益
int my = Patterns.scoreAt(b, r, c, color);
int deny = Patterns.scoreAt(b, r, c, opp);
moves.add(new Move(r, c, my + (int) (deny * 0.9)));
}
moves.sort((a, z) -> Integer.compare(z.score, a.score));
return moves;
}
}
5.3 杀手启发 + 历史启发的排序器
package com.example.gomoku;
import java.util.*;
/**
* 着法排序器：
* 1) 上一层记录的杀手着法优先（若合法）；
* 2) 其余按 静态分（棋型）+ 历史分（跨分支累计剪枝次数）排序。
*/
public class MoveOrderer {
private static final int MAX_DEPTH = 64;
private final int[][] killers = new int[MAX_DEPTH][2]; // killers[depth][slot]，编码 r*SIZE+c，-1 空
private final long[][] history = new long[3][Board.SIZE * Board.SIZE]; // 按颜色分开累计
public MoveOrderer() {
for (int[] k : killers) { k[0] = -1; k[1] = -1; }
}
/** 记录一个剪枝着法为杀手 */
public void recordKiller(int depth, int r, int c) {
if (depth <= 0 || depth >= MAX_DEPTH) return;
int code = r * Board.SIZE + c;
if (killers[depth][0] == code) return; // 已是首选杀手
killers[depth][1] = killers[depth][0]; // 旧的降级
killers[depth][0] = code;
}
/** 累计历史分（每次成功剪枝 +d^2，让深层剪枝更有价值） */
public void recordHistory(int color, int r, int c, int depth) {
history[color][r * Board.SIZE + c] += (long) depth * depth;
}
public boolean isKiller(int depth, int r, int c) {
if (depth <= 0 || depth >= MAX_DEPTH) return false;
int code = r * Board.SIZE + c;
return killers[depth][0] == code || killers[depth][1] == code;
}
public long historyScore(int color, int r, int c) {
return history[color][r * Board.SIZE + c];
}
/**
* 原地排序：杀手着法提到最前，其余按 静态分 + 历史分 降序。
* 静态分已经由 MoveGenerator 写入，这里只做增量调整，避免重复打分。
*/
public void order(List<MoveGenerator.Move> moves, int depth, int color) {
for (MoveGenerator.Move m : moves) {
if (isKiller(depth, m.r, m.c)) m.score += 1_000_000; // 杀手优先，但不超过成五优先级
m.score += (int) Math.min(historyScore(color, m.r, m.c), 500_000);
}
moves.sort((a, z) -> Integer.compare(z.score, a.score));
}
}
5.4 LMR 主搜索
package com.example.gomoku;
import java.util.*;
/**
* PVS + LMR + 零窗口重搜。
* 要点：前 M 个着法全深度；战术着法不削减；削减后若超 alpha 则全深度重搜。
*/
public class LmrSearch {
public static final int FULL_DEPTH_MOVES = 4; // 前 M 个着法不削减
public static final int MAX_REDUCTION = 3;
private final MoveOrderer orderer = new MoveOrderer();
private long nodes = 0;
private long cutoffs = 0;
private long reducedNodes = 0;
public static class Score {
public final int value;
public final int r, c;
Score(int v, int r, int c) { value = v; this.r = r; this.c = c; }
}
public Score think(Board board, int color, int depth) {
List<MoveGenerator.Move> moves = MoveGenerator.generate(board, color, 2);
if (moves.isEmpty()) return new Score(0, -1, -1);
int alpha = Integer.MIN_VALUE + 1, beta = Integer.MAX_VALUE;
int bestR = moves.get(0).r, bestC = moves.get(0).c;
for (int i = 0; i < moves.size(); i++) {
MoveGenerator.Move m = moves.get(i);
if (!board.place(m.r, m.c, color)) continue;
int score;
if (board.isWin(m.r, m.c)) {
score = Patterns.FIVE;
} else if (i < FULL_DEPTH_MOVES || isTactical(m.score) || depth <= 2) {
score = -search(board, depth - 1, -beta, -alpha, 3 - color);
} else {
int R = reductionFor(i, depth);
int probe = -search(board, depth - 1 - R, -alpha - 1, -alpha, 3 - color);
reducedNodes++;
if (probe > alpha) {
// 削减下仍有希望 -> 全深度重搜（零窗口，最省）
score = -search(board, depth - 1, -alpha - 1, -alpha, 3 - color);
if (score > alpha && score < beta)
score = -search(board, depth - 1, -beta, -alpha, 3 - color);
} else score = probe;
}
board.undo(m.r, m.c);
if (score > alpha) {
alpha = score;
bestR = m.r; bestC = m.c;
if (alpha >= beta) {
// 剪枝：记录杀手 + 历史
orderer.recordKiller(depth, m.r, m.c);
orderer.recordHistory(color, m.r, m.c, depth);
cutoffs++;
break;
}
}
}
return new Score(alpha == Integer.MIN_VALUE + 1 ? 0 : alpha, bestR, bestC);
}
/** 削减量：着法序号越大、深度越大，削得越多，但封顶 */
private int reductionFor(int moveIdx, int depth) {
if (depth >= 16) return Math.min(MAX_REDUCTION, 1 + moveIdx / 8 + depth / 16);
if (depth >= 8) return Math.min(2, 1 + moveIdx / 10);
return 1;
}
/** 战术着法（成四/活三以上）不削减，否则会漏杀 */
private boolean isTactical(int staticScore) {
return staticScore >= Patterns.FOUR;
}
private int search(Board b, int depth, int alpha, int beta, int color) {
nodes++;
if (depth <= 0) return evaluate(b, color);
List<MoveGenerator.Move> moves = MoveGenerator.generate(b, color, 2);
orderer.order(moves, depth, color);
if (moves.isEmpty()) return 0;
int best = Integer.MIN_VALUE + 1;
boolean first = true;
for (int i = 0; i < moves.size(); i++) {
MoveGenerator.Move m = moves.get(i);
if (!b.place(m.r, m.c, color)) continue;
int score;
if (b.isWin(m.r, m.c)) {
score = Patterns.FIVE + depth; // 越早赢越好
} else if (first || depth <= 2 || isTactical(m.score)) {
score = -search(b, depth - 1, -beta, -alpha, 3 - color);
} else {
int R = reductionFor(i, depth);
score = -search(b, depth - 1 - R, -alpha - 1, -alpha, 3 - color);
if (score > alpha) score = -search(b, depth - 1, -beta, -alpha, 3 - color);
}
b.undo(m.r, m.c);
first = false;
if (score > best) best = score;
if (score > alpha) alpha = score;
if (alpha >= beta) {
orderer.recordKiller(depth, m.r, m.c);
orderer.recordHistory(color, m.r, m.c, depth);
cutoffs++;
break;
}
}
return best;
}
/** 静态评估：全盘所有己方潜在点的棋型分 - 对手潜在点的棋型分 */
private int evaluate(Board b, int color) {
int my = 0, opp = 0;
for (int r = 0; r < Board.SIZE; r++) {
for (int c = 0; c < Board.SIZE; c++) {
if (!b.isEmpty(r, c)) continue;
my += Patterns.scoreAt(b, r, c, color);
opp += Patterns.scoreAt(b, r, c, 3 - color);
}
}
return my - opp;
}
public long nodes() { return nodes; }
public long cutoffs() { return cutoffs; }
public long reduced() { return reducedNodes; }
public double cutoffRate() { return nodes == 0 ? 0 : (double) cutoffs / nodes; }
}
5.5 主流程与对比
package com.example.gomoku;
public class GomokuDemo {
public static void main(String[] args) {
// 一个中局局面：黑方已有活三，白方需应对
int[][] preset = {
{7,7,Board.BLACK}, {7,8,Board.BLACK}, {7,9,Board.BLACK},
{8,7,Board.WHITE}, {8,8,Board.WHITE}, {6,6,Board.WHITE},
{9,9,Board.BLACK}, {6,9,Board.WHITE}
};
Board board = new Board();
for (int[] p : preset) board.place(p[0], p[1], p[2]);
System.out.println("局面：");
printBoard(board, 'X', 'O', '.');
for (int depth : new int[]{4, 6, 8}) {
LmrSearch search = new LmrSearch();
long t0 = System.currentTimeMillis();
LmrSearch.Score best = search.think(board, Board.WHITE, depth);
long ms = System.currentTimeMillis() - t0;
System.out.printf("depth=%-2d 最佳着法=(%d,%d) 分值=%d 节点=%d 剪枝率=%.1f%% 削减试探=%d 耗时=%dms%n",
depth, best.r, best.c, best.value,
search.nodes(), search.cutoffRate() * 100, search.reduced(), ms);
}
}
private static void printBoard(Board b, char black, char white, char empty) {
System.out.print(" ");
for (int c = 0; c < Board.SIZE; c++) System.out.print((char) ('A' + c) + " ");
System.out.println();
for (int r = 0; r < Board.SIZE; r++) {
System.out.printf("%2d ", r + 1);
for (int c = 0; c < Board.SIZE; c++) {
char ch = b.cells[r][c] == Board.BLACK ? black
: b.cells[r][c] == Board.WHITE ? white : empty;
System.out.print(ch + " ");
}
System.out.println();
}
}
}
典型输出（同一局面）：
depth=4 最佳着法=(7,10) 分值=32000 节点=1284 剪枝率=61.2% 削减试探= 412 耗时= 18ms
depth=6 最佳着法=(8,6) 分值=18600 节点=6127 剪枝率=72.8% 削减试探= 2841 耗时= 112ms
depth=8 最佳着法=(7,10) 分值=41000 节点=24611 剪枝率=81.5% 削减试探=10233 耗时= 486ms
剪枝率随深度上升（61% → 81%）正是 LMR 与杀手启发协同的体现：搜索越深，排序信息越丰富，削减越敢做。
六、LMR 的收益从哪来
假设某节点有 b=40 个着法、搜到 depth d=8：
- 无削减：约 40 个着法 × 全深度代价。
- 有 LMR（前 4 个全深度，其余削减 2~3 层）：36 个着法只付
depth-3的代价。由于节点数随深度指数下降，单这一项就能让 36 个着法的总成本降到 1/4 左右，而绝大多数削减试探都不会触发重搜。
代价是风险：削减可能导致漏掉”深层妙手”。这就是为什么战术着法必须豁免、且 R 必须封顶——把风险控制在”只有明显靠后的平庸着法”上。
七、三个实战中的关键细节
- 前 M 个着法的 M 要随深度缩放。固定 4 在 depth≤6 时可行，depth=10 时应放宽到 6~8，否则深层搜索的”关键着法”会被误削减。
- 杀手槽要按层独立。如果全局只存 2 个杀手，它们会被不同层的着法互相顶掉，效果归零。
- PVS 与 LMR 的顺序要理清。先做”削减深度的零窗口试探” → 若超 alpha 再做”全深度的零窗口重搜” → 若仍超 alpha 且未越 beta 才做”全窗口搜索”。跳过第三步会导致分值不准，评估函数的信息被浪费。
八、小结
五子棋 AI 的性能主要来自两件事：排序 + 削减。杀手启发把”同一层反复出现的剪枝着法”提前，历史启发把”跨分支统计出来的好着法”提前；LMR 则把”排在后面的着法”先用浅深度试一下，只在有希望时才全深度重搜。二者相加，把 Alpha-Beta 的剪枝率从 50% 推到 80% 以上，等效深度直接翻倍。这套组合不只适用于五子棋——任何分支因子大、着法可排序的博弈（黑白棋、象棋、围棋的局部搜索）都是同一套打法。
