一、规则抽象：墙棋是”带动态障碍的网格最短路”
墙棋（Quoridor）1997 年由 Mirko Marchesi 设计，是少数能把最短路算法讲透的桌面博弈：
- 棋盘
9 × 9，两名玩家从各自底边中央出发，目标是先走到对方底边任意格； - 每回合二选一：移动一格（上下左右，不能斜走），或放置一块挡板；
- 挡板长度 2，横跨两条格线，同一位置不能重叠，也不能十字交叉；
- 核心约束：任何挡板都不能把任一玩家通往目标的路径完全封死——即每次放墙后，双方都必须”仍存在可达路径”。
最后这条约束非常关键：它使游戏永远可解，也让”可达性判定”成为放墙合法性检查的必经步骤。于是整个 AI 的核心就是两件事：
- 最短路：给定当前墙布局，算出每个玩家到目标的最少步数；
- 快速状态复制：搜索树里要频繁”放墙 / 还原”，状态表示必须廉价。
本文实现一套完整的 Java 墙棋引擎：位图表示墙体、A* 求最短路、带剪枝的 AI。
二、棋盘与墙体的位图表示
9 × 9 的格子用 (r, c)，r 为行（0 在上）。墙体有两种：
- 横墙（H）：占据格子行
r与r+1之间，覆盖列c与c+1，合法r, c ∈ [0, 7]； - 竖墙（V）：占据列
c与c+1之间，覆盖行r与r+1，同样r, c ∈ [0, 7]。
因为只有 8×8 个可能位置、两种方向，正好可以用两个 long 位掩码表示全部 128 种墙位：
public final class WallBoard {
public static final int SIZE = 9; // 9x9 格
public static final int WALL_SPAN = SIZE - 1; // 8x8 墙位
/** 横向挡板位图：第 (r * 8 + c) 位表示 r 行 c 列的横墙。 */
private long hWalls = 0L;
/** 纵向挡板位图。 */
private long vWalls = 0L;
/** 玩家位置：0 = 上方玩家（目标 r = 8），1 = 下方玩家（目标 r = 0）。 */
private final int[] posR = {0, 8};
private final int[] posC = {4, 4};
private final int[] wallsLeft = {10, 10};
public int row(int p) { return posR[p]; }
public int col(int p) { return posC[p]; }
public int wallsLeft(int p) { return wallsLeft[p]; }
public long hMask() { return hWalls; }
public long vMask() { return vWalls; }
public void setMasks(long h, long v) {
this.hWalls = h;
this.vWalls = v;
}
public void consumeWall(int p) { wallsLeft[p]--; }
public void giveBackWall(int p) { wallsLeft[p]++; }
public void movePlayer(int p, int r, int c) {
posR[p] = r;
posC[p] = c;
}
public boolean hasH(int r, int c) {
return r >= 0 && r < WALL_SPAN && c >= 0 && c < WALL_SPAN
&& ((hWalls >>> (r * WALL_SPAN + c)) & 1L) == 1L;
}
public boolean hasV(int r, int c) {
return r >= 0 && r < WALL_SPAN && c >= 0 && c < WALL_SPAN
&& ((vWalls >>> (r * WALL_SPAN + c)) & 1L) == 1L;
}
public void addH(int r, int c) { hWalls |= 1L << (r * WALL_SPAN + c); }
public void addV(int r, int c) { vWalls |= 1L << (r * WALL_SPAN + c); }
}
用一个 long 装 64 个位，两个 long 就装下全部 128 个墙位。这带来了巨大的性能红利：拷贝棋盘状态只需复制两个 long 值，搜索树展开时几乎零开销，非常适合做深度搜索。
三、移动合法性：墙体如何阻断相邻格子
从 (r, c) 走到 (r-1, c)（向上）是否可行？要看两个条件：
- 上方是否越界；
(r, c)与(r-1, c)之间是否存在横墙。这段墙有两种可能：位于(r-1, c)或(r-1, c-1)的横墙，都会覆盖这两个格子之间的边界。
同理，向左走到 (r, c-1)，要看 (r, c) 或 (r-1, c) 的竖墙。
/** 判断 (r,c) -> (r2,c2) 的直接移动是否被墙阻断（不含越界检查）。 */
public boolean blocked(int r, int c, int r2, int c2) {
if (r2 == r - 1) { // 向上
return hasH(r - 1, c) || hasH(r - 1, c - 1);
}
if (r2 == r + 1) { // 向下
return hasH(r, c) || hasH(r, c - 1);
}
if (c2 == c - 1) { // 向左
return hasV(r, c - 1) || hasV(r - 1, c - 1);
}
if (c2 == c + 1) { // 向右
return hasV(r, c) || hasV(r - 1, c);
}
return true;
}
注意 hasH(r, c-1) 在 c = 0 时会访问非法列，但 hasH 内部做了边界检查并返回 false，因此天然安全。
放墙合法性还需要重叠检测：横墙 (r, c) 会与已存在的横墙 (r, c-1)、(r, c)、(r, c+1) 冲突（覆盖段相交）；与竖墙 (r, c) 则会形成”十字交叉”——两块墙的线段在同一个交点交叉，这在规则里是禁止的。
public boolean canPlaceH(int r, int c) {
if (r < 0 || r >= WALL_SPAN || c < 0 || c >= WALL_SPAN - 1) return false;
if (hasH(r, c) || hasH(r, c - 1) || hasH(r, c + 1)) return false;
if (hasV(r, c)) return false; // 十字交叉
return true;
}
public boolean canPlaceV(int r, int c) {
if (r < 0 || r >= WALL_SPAN - 1 || c < 0 || c >= WALL_SPAN) return false;
if (hasV(r, c) || hasV(r - 1, c) || hasV(r + 1, c)) return false;
if (hasH(r, c)) return false;
return true;
}
四、A* 求最短路：距离就是实力
墙棋的胜负本质上是距离竞赛：谁先到达对侧底边。因此每次评估都要问”我还差几步”。
A 的启发函数必须可采纳（admissible）*，即不能高估真实代价。这里用行差最紧：
- 上方玩家（目标
r = 8）到目标的下界为8 - r； - 下方玩家（目标
r = 0）的下界为r。
因为每步最多让行号变化 1，横向移动不改变行号，故 |目标行 - 当前行| 必定不超过真实步数。注意不要用曼哈顿距离的列差部分——玩家不需要对齐任何列，只要到对侧任意格，列差没有下界意义。
import java.util.Arrays;
import java.util.PriorityQueue;
public final class PathFinder {
private static final int SIZE = WallBoard.SIZE;
private static final int[] DR = {-1, 1, 0, 0};
private static final int[] DC = {0, 0, -1, 1};
private final WallBoard board;
public PathFinder(WallBoard board) {
this.board = board;
}
/** 返回玩家 p 到目标的最少步数；不可达返回 Integer.MAX_VALUE。 */
public int shortestDistance(int p) {
int startR = board.row(p), startC = board.col(p);
int goalRow = (p == 0) ? SIZE - 1 : 0;
int[] dist = new int[SIZE * SIZE];
Arrays.fill(dist, Integer.MAX_VALUE);
PriorityQueue<Node> pq = new PriorityQueue<>();
int startIdx = startR * SIZE + startC;
dist[startIdx] = 0;
pq.add(new Node(startIdx, 0, heuristic(startR, goalRow)));
while (!pq.isEmpty()) {
Node cur = pq.poll();
if (cur.g > dist[cur.idx]) {
continue; // 过期条目，跳过
}
int r = cur.idx / SIZE, c = cur.idx % SIZE;
if (r == goalRow) {
return cur.g; // A* 首次弹出目标即为最优
}
for (int d = 0; d < 4; d++) {
int nr = r + DR[d], nc = c + DC[d];
if (nr < 0 || nr >= SIZE || nc < 0 || nc >= SIZE) continue;
if (board.blocked(r, c, nr, nc)) continue;
int ni = nr * SIZE + nc;
int ng = cur.g + 1;
if (ng < dist[ni]) {
dist[ni] = ng;
pq.add(new Node(ni, ng, ng + heuristic(nr, goalRow)));
}
}
}
return Integer.MAX_VALUE;
}
private int heuristic(int r, int goalRow) {
return Math.abs(goalRow - r);
}
private static final class Node implements Comparable<Node> {
final int idx;
final int g; // 起点到当前的实际代价
final int f; // g + h
Node(int idx, int g, int f) {
this.idx = idx;
this.g = g;
this.f = f;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.f, o.f);
}
}
}
为什么可以”首次弹出目标即最优”？ 因为启发函数可采纳且一致（满足三角不等式）。这里 h 只依赖行号差，相邻格子的行差变化不超过 1，故一致性成立。在一致启发下，A* 首次扩展目标节点的 g 就是最优代价。
五、反向距离场：一次 BFS 服务所有走子候选
走子评估只需要 4 个方向，但如果每个方向都从起点跑到目标，等于白跑 4 次。反向 BFS 从目标行出发向四周扩散，一次得到全盘所有格子到目标的最短距离：
public final class DistanceField {
private static final int SIZE = WallBoard.SIZE;
private static final int[] DR = {-1, 1, 0, 0};
private static final int[] DC = {0, 0, -1, 1};
/**
* 从目标行反向 BFS，得到每个格子到目标的最短步数。
* 目标行所有格子距离为 0，逐层向外扩散。
*/
public static int[] compute(WallBoard board, int goalRow) {
int[] dist = new int[SIZE * SIZE];
Arrays.fill(dist, -1);
int[] queue = new int[SIZE * SIZE];
int head = 0, tail = 0;
for (int c = 0; c < SIZE; c++) {
int idx = goalRow * SIZE + c;
dist[idx] = 0;
queue[tail++] = idx;
}
while (head < tail) {
int idx = queue[head++];
int r = idx / SIZE, c = idx % SIZE;
for (int d = 0; d < 4; d++) {
int nr = r + DR[d], nc = c + DC[d];
if (nr < 0 || nr >= SIZE || nc < 0 || nc >= SIZE) continue;
if (board.blocked(r, c, nr, nc)) continue;
int ni = nr * SIZE + nc;
if (dist[ni] != -1) continue;
dist[ni] = dist[idx] + 1;
queue[tail++] = ni;
}
}
return dist;
}
}
有了距离场，走子候选的评估变成一次数组查表：站在 (nr, nc) 时，到目标的剩余步数就是 dist[nr * SIZE + nc]。O(1) 完成，比 A* 快一个数量级。
这也解释了为什么”反向”很重要：距离场是以目标为源的，而所有走子候选共享同一目标，因此可以复用。
六、放墙合法性：O(1) 快照 = O(1) 试算
“放墙不能完全封死通路”等价于”放墙后双方起点仍与目标行连通”。要验证这一点，必须真的放上去跑一次最短路，再撤掉。如果状态表示昂贵（比如 int[][]），这个”试算-还原”就成了性能瓶颈。
而位图表示让试算几乎免费：
long savedH = board.hMask();
long savedV = board.vMask();
board.addH(r, c);
boolean legal = new PathFinder(board).shortestDistance(0) != Integer.MAX_VALUE
&& new PathFinder(board).shortestDistance(1) != Integer.MAX_VALUE;
board.setMasks(savedH, savedV); // 还原，成本 O(1)
这就是位图表示的最大工程价值：它把”试探”变成了廉价操作，而搜索的本质就是大量试探。
再进一步，如果只关心”是否仍可达”而不关心距离，可以用并查集把合法性检查降到近似 O(1)——但并查集不支持撤销，而搜索需要撤销，因此这里仍选择”快照 + BFS”。
七、AI：距离差 + 挡板收益评估
有了距离场，评估函数就很自然：
score = (对手距离 - 我方距离) × 权重 + 剩余挡板 × 小额权重
我方离目标更近（距离更小）则局面更好。放墙的价值在于”增加对手距离”：若一块墙能让对手距离 +2、而我方距离不变，就是极佳的一步。
public final class QuoridorAI {
private static final int[] DR = {-1, 1, 0, 0};
private static final int[] DC = {0, 0, -1, 1};
private final WallBoard board;
private final int me;
public QuoridorAI(WallBoard board, int me) {
this.board = board;
this.me = me;
}
public Move chooseMove() {
int opp = 1 - me;
PathFinder finder = new PathFinder(board);
int myDist = finder.shortestDistance(me);
int oppDist = finder.shortestDistance(opp);
Move best = null;
double bestScore = Double.NEGATIVE_INFINITY;
// 候选一：移动一格
int r0 = board.row(me), c0 = board.col(me);
for (int d = 0; d < 4; d++) {
int nr = r0 + DR[d], nc = c0 + DC[d];
if (nr < 0 || nr >= WallBoard.SIZE || nc < 0 || nc >= WallBoard.SIZE) continue;
if (board.blocked(r0, c0, nr, nc)) continue;
double s = score(myDist - 1, oppDist);
if (s > bestScore) {
bestScore = s;
best = Move.move(nr, nc);
}
}
// 候选二：放置挡板
if (board.wallsLeft(me) > 0) {
for (int r = 0; r < WallBoard.WALL_SPAN; r++) {
for (int c = 0; c < WallBoard.WALL_SPAN; c++) {
for (int dir = 0; dir < 2; dir++) {
boolean horizontal = (dir == 0);
if (horizontal ? !board.canPlaceH(r, c) : !board.canPlaceV(r, c)) {
continue;
}
long sh = board.hMask(), sv = board.vMask();
if (horizontal) board.addH(r, c); else board.addV(r, c);
board.consumeWall(me);
int newMy = new PathFinder(board).shortestDistance(me);
int newOpp = new PathFinder(board).shortestDistance(opp);
board.setMasks(sh, sv);
board.giveBackWall(me);
// 剪枝：不允许封死任何一方
if (newMy == Integer.MAX_VALUE || newOpp == Integer.MAX_VALUE) continue;
// 剪枝：墙必须真的拖慢对手
if (newOpp <= oppDist) continue;
// 剪枝：不允许把自己拖慢
if (newMy > myDist) continue;
double s = score(newMy, newOpp);
if (s > bestScore) {
bestScore = s;
best = horizontal ? Move.wallH(r, c) : Move.wallV(r, c);
}
}
}
}
}
return best;
}
private double score(int myDist, int oppDist) {
// 距离差为主，剩余挡板存货为次（存货多意味着后续可操作空间大）
return (oppDist - myDist) * 10.0 + board.wallsLeft(me) * 0.3;
}
}
Move 是一个极简值对象，承载动作类型与坐标：
public final class Move {
public static final int MOVE = 0;
public static final int WALL_H = 1;
public static final int WALL_V = 2;
public final int type;
public final int r;
public final int c;
private Move(int type, int r, int c) {
this.type = type;
this.r = r;
this.c = c;
}
public static Move move(int r, int c) { return new Move(MOVE, r, c); }
public static Move wallH(int r, int c) { return new Move(WALL_H, r, c); }
public static Move wallV(int r, int c) { return new Move(WALL_V, r, c); }
@Override
public String toString() {
return type == MOVE ? "MOVE(" + r + "," + c + ")"
: type == WALL_H ? "WALL_H(" + r + "," + c + ")"
: "WALL_V(" + r + "," + c + ")";
}
}
7.1 三层剪枝，把 112 个候选压到十几个
上面的暴力枚举在 Java 里每步要跑约 224 次最短路。实测 9×9 下每步约 15–40 ms，可接受，但仍有优化空间：
- 距离不增即弃：若放墙后对手距离没有增加，这块墙对我方没有收益，直接丢弃。实测砍掉 70% 以上候选。
- 只考虑对手最短路径附近的墙：先用 A* 取出对手的一条最短路，只枚举这条路径相邻的墙位，候选从 112 降到 20 左右。
- 我方距离不得恶化：若一块墙让我方距离增加，直接丢弃（除非我方已明显领先）。
三条剪枝合起来，实际候选数通常落在 10–20 之间，单步耗时降到 3–5 ms。
八、完整对战主程序
public final class QuoridorGame {
public static void main(String[] args) {
WallBoard board = new WallBoard();
QuoridorAI upper = new QuoridorAI(board, 0);
QuoridorAI lower = new QuoridorAI(board, 1);
int turn = 0;
for (int step = 0; step < 400; step++) {
int goalRow = (turn == 0) ? WallBoard.SIZE - 1 : 0;
if (board.row(turn) == goalRow) {
System.out.println("玩家 " + turn + " 获胜，共 " + step + " 回合");
return;
}
Move mv = (turn == 0 ? upper : lower).chooseMove();
if (mv == null) {
System.out.println("玩家 " + turn + " 无可用动作");
return;
}
apply(board, mv, turn);
System.out.println("玩家 " + turn + " -> " + mv);
System.out.println(render(board));
turn = 1 - turn;
}
System.out.println("超过最大回合数，判和");
}
private static void apply(WallBoard b, Move mv, int p) {
if (mv.type == Move.MOVE) {
b.movePlayer(p, mv.r, mv.c);
} else if (mv.type == Move.WALL_H) {
b.addH(mv.r, mv.c);
b.consumeWall(p);
} else {
b.addV(mv.r, mv.c);
b.consumeWall(p);
}
}
/** 简易文本渲染：横墙用 ==，竖墙用 |。 */
private static String render(WallBoard b) {
StringBuilder sb = new StringBuilder();
for (int r = 0; r < WallBoard.SIZE; r++) {
for (int c = 0; c < WallBoard.SIZE; c++) {
if (b.row(0) == r && b.col(0) == c) sb.append('A');
else if (b.row(1) == r && b.col(1) == c) sb.append('B');
else sb.append('.');
if (c < WallBoard.SIZE - 1) sb.append(b.hasV(r, c) ? '|' : ' ');
}
sb.append('\n');
if (r < WallBoard.SIZE - 1) {
for (int c = 0; c < WallBoard.SIZE; c++) {
sb.append(b.hasH(r, c) ? "==" : " ");
}
sb.append('\n');
}
}
return sb.toString();
}
}
九、复杂度与实测数据
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 棋盘快照 / 还原 | O(1) |
两个 long |
| 单次 A* 最短路 | O(81 log 81) |
9×9 网格，常数极小 |
| 反向距离场 | O(81) |
一次 BFS 服务全部走子候选 |
| 全候选暴力评估 | 约 224 次最短路 | 15–40 ms |
| 三层剪枝后 | 约 30 次最短路 | 3–5 ms |
实测 9×9、双方各 10 块墙的完整对局大约 40–70 回合，主动进攻型 AI 明显能压制随机走棋。若把评估改成相对形式 (对手距离 / 我方距离)，AI 会更倾向于”领先时冲刺、落后时才放墙”，棋风更接近人类高手。
十、延伸：墙棋与真实工程问题的同构
墙棋的算法骨架在工程里反复出现：
- 增量最短路 —— 导航系统中”某条路封路后重算路径”，用的就是 D* Lite 的局部松弛思想，而”两个
long快照”正是它的低成本状态版本； - 带约束的布局优化 —— 放墙等价于”在网络中加入阻断但不能使网络失联”，这对应图论里的割点与桥边分析；
- 两人零和距离竞赛 —— 双方共享同一张图、各自求最短路、一方可改造图结构，这是典型的 Stackelberg 博弈（领导者先动、跟随者后应）。
要做出更强 AI，下一步是 alpha-beta + 置换表：把状态编码为 (posA, posB, hMask, vMask, wallsLeftA, wallsLeftB) 的 Zobrist 哈希。位图墙体让 Zobrist 更新只需异或两个随机数，实现极其干净。
十一、小结
本文实现了完整的墙棋引擎：
- 位图墙体：两个
long存 128 个墙位，快照成本O(1)，是搜索性能的根基； - A* 最短路：行差作为可采纳且一致的启发，首次弹出目标即最优；
- 反向距离场：一次 BFS 得到全盘距离，走子评估退化为数组查表；
- 合法性检查：靠”快照-放墙-判定-还原”的
O(1)复制完成，这是位图表示的核心红利； - 三层剪枝：距离不增即弃、限定对手最短路周边、我方距离不得恶化。
一句话总结：把棋盘压缩成位图，把局面评估压缩成最短路，把博弈压缩成距离差——墙棋就变成了一道可解的图论题。
