引言
五子棋是一种经典的连珠博弈游戏，双方轮流在棋盘上落子，先形成连续五子者获胜。与象棋、围棋不同，五子棋的搜索空间相对较小，但存在大量直接决胜的战术组合。威胁空间搜索（Threat Space Search, TSS）是专门为此类游戏设计的一种选择性搜索算法，它只考虑能够产生威胁（如活四、冲四）的着法，从而将搜索深度聚焦于决胜路径上。本文将用Java实现TSS的核心逻辑，并重点介绍VCF（Victory by Continuous Four，连续冲四胜）路径的识别算法。
核心算法原理
1. 五子棋基本威胁类型
在五子棋中，以下棋型具有直接威胁：
– 活四：四子连珠且两端开放，对手无法防守，下一步必胜。
– 冲四：四子连珠但仅一端开放，对手必须在开放端落子才能防守。
– 活三：三子连珠且两端开放，下一步可形成冲四或活四。
– 跳活三：中间隔一空格的三子连珠，同样具有威胁。
2. 威胁空间搜索（TSS）
传统Minimax搜索需要对每一层枚举所有空位，效率低下。TSS的核心思想是：只搜索能够产生或应对威胁的着法。
- 攻击方的候选着法：所有能形成威胁（活三、冲四等）的位置。
- 防守方的候选着法：所有能阻止对方威胁的位置。
通过层层威胁的生成与应对，搜索树深度大幅减少。
3. VCF必胜路径识别
VCF是指通过连续制造冲四，迫使对手疲于防守，最终形成活四获胜。VCF路径的搜索过程：
1. 当前玩家找到一个冲四威胁。
2. 对手必须在防守点落子。
3. 当前玩家再制造新的冲四威胁。
4. 重复直到形成活四或双冲四（对手无法同时防守）。
Java实现
import java.util.*;
/**
* 五子棋威胁空间搜索(TSS)与VCF必胜路径识别
*/
public class GomokuTSS {
public static final int EMPTY = 0;
public static final int BLACK = 1;
public static final int WHITE = 2;
public static final int BOARD_SIZE = 15;
// 四个方向: 横、竖、左斜、右斜
private static final int[][] DIRS = {{0,1}, {1,0}, {1,1}, {1,-1}};
private int[][] board;
public GomokuTSS() {
this.board = new int[BOARD_SIZE][BOARD_SIZE];
}
/**
* 评估某一行/列/斜线上的棋型
* 返回该线路上指定玩家的所有威胁点
*/
public List<Threat> findThreats(int player) {
List<Threat> threats = new ArrayList<>();
for (int r = 0; r < BOARD_SIZE; r++) {
for (int c = 0; c < BOARD_SIZE; c++) {
if (board[r][c] != EMPTY) continue;
// 尝试在此落子，评估产生的威胁
board[r][c] = player;
Threat threat = evaluateThreatAt(r, c, player);
board[r][c] = EMPTY;
if (threat != null && threat.type != ThreatType.NONE) {
threat.row = r;
threat.col = c;
threats.add(threat);
}
}
}
return threats;
}
/**
* 在(r,c)落子后，评估该位置对各方向产生的威胁
*/
private Threat evaluateThreatAt(int r, int c, int player) {
Threat best = new Threat(r, c, ThreatType.NONE);
for (int[] dir : DIRS) {
// 收集该方向上以(r,c)为中心的连续棋型
LinePattern pattern = analyzeLine(r, c, dir[0], dir[1], player);
if (pattern.count >= 5) {
return new Threat(r, c, ThreatType.FIVE); // 直接五连
}
if (pattern.openEnds == 2 && pattern.count == 4) {
best = maxThreat(best, new Threat(r, c, ThreatType.OPEN_FOUR));
} else if (pattern.openEnds >= 1 && pattern.count == 4) {
best = maxThreat(best, new Threat(r, c, ThreatType.FOUR));
} else if (pattern.openEnds == 2 && pattern.count == 3) {
best = maxThreat(best, new Threat(r, c, ThreatType.OPEN_THREE));
} else if (pattern.openEnds >= 1 && pattern.count == 3 && pattern.hasGap) {
best = maxThreat(best, new Threat(r, c, ThreatType.BROKEN_THREE));
}
}
return best;
}
/**
* 分析某方向上以(r,c)为中心的棋型
*/
private LinePattern analyzeLine(int r, int c, int dr, int dc, int player) {
// 向正方向统计
int countPos = 0, gapPos = -1;
for (int i = 1; i < 5; i++) {
int nr = r + dr * i, nc = c + dc * i;
if (!inBounds(nr, nc)) break;
if (board[nr][nc] == player) {
countPos++;
} else if (board[nr][nc] == EMPTY && gapPos == -1) {
gapPos = i; // 记录第一个间隙位置
} else {
break;
}
}
// 向反方向统计
int countNeg = 0, gapNeg = -1;
for (int i = 1; i < 5; i++) {
int nr = r - dr * i, nc = c - dc * i;
if (!inBounds(nr, nc)) break;
if (board[nr][nc] == player) {
countNeg++;
} else if (board[nr][nc] == EMPTY && gapNeg == -1) {
gapNeg = i;
} else {
break;
}
}
int totalCount = 1 + countPos + countNeg; // 包含当前子
// 判断两端是否开放
int openEnds = 0;
int endPosR = r + dr * (countPos + 1 + (gapPos == countPos + 1 ? 1 : 0));
int endPosC = c + dc * (countPos + 1 + (gapPos == countPos + 1 ? 1 : 0));
if (inBounds(endPosR, endPosC) && board[endPosR][endPosC] == EMPTY) openEnds++;
int endNegR = r - dr * (countNeg + 1 + (gapNeg == countNeg + 1 ? 1 : 0));
int endNegC = c - dc * (countNeg + 1 + (gapNeg == countNeg + 1 ? 1 : 0));
if (inBounds(endNegR, endNegC) && board[endNegR][endNegC] == EMPTY) openEnds++;
boolean hasGap = (gapPos != -1 && gapPos <= countPos + 1) ||
(gapNeg != -1 && gapNeg <= countNeg + 1);
return new LinePattern(totalCount, openEnds, hasGap);
}
private boolean inBounds(int r, int c) {
return r >= 0 && r < BOARD_SIZE && c >= 0 && c < BOARD_SIZE;
}
private Threat maxThreat(Threat a, Threat b) {
return a.type.priority >= b.type.priority ? a : b;
}
/**
* VCF搜索：寻找连续冲四必胜路径
* @return 如果存在VCF路径，返回第一步着法
*/
public int[] findVCF(int player, int depth) {
List<Threat> myThreats = findThreats(player);
for (Threat threat : myThreats) {
if (threat.type == ThreatType.FIVE) {
return new int[]{threat.row, threat.col}; // 直接获胜
}
if (threat.type == ThreatType.OPEN_FOUR) {
return new int[]{threat.row, threat.col}; // 活四必胜
}
}
// 搜索冲四序列
for (Threat threat : myThreats) {
if (threat.type == ThreatType.FOUR) {
int[] result = vcfSearch(threat.row, threat.col, player, depth, true);
if (result != null) return result;
}
}
return null;
}
/**
* 递归VCF搜索
* @param isMyTurn 当前是否为攻击方回合
*/
private int[] vcfSearch(int r, int c, int player, int depth, boolean isMyTurn) {
if (depth <= 0) return null;
int opponent = 3 - player;
if (isMyTurn) {
// 我方落子于(r,c)
board[r][c] = player;
// 检查是否获胜
if (isWin(r, c, player)) {
board[r][c] = EMPTY;
return new int[]{r, c};
}
// 寻找我方的下一个威胁
List<Threat> threats = findThreats(player);
board[r][c] = EMPTY;
// 筛选冲四及以上威胁
List<Threat> fours = new ArrayList<>();
for (Threat t : threats) {
if (t.type == ThreatType.FIVE || t.type == ThreatType.OPEN_FOUR) {
return new int[]{r, c}; // 存在必胜点
}
if (t.type == ThreatType.FOUR) {
fours.add(t);
}
}
// 双冲四也必胜
if (fours.size() >= 2) {
return new int[]{r, c};
}
// 递归搜索每个冲四
for (Threat t : fours) {
int[] result = vcfSearch(t.row, t.col, player, depth - 1, false);
if (result != null) return new int[]{r, c};
}
return null;
} else {
// 对手回合：必须在防守点落子
board[r][c] = player;
List<int[]> defenses = findDefenses(r, c, player);
board[r][c] = EMPTY;
if (defenses.isEmpty()) {
return new int[]{r, c}; // 无防守点，已胜
}
// 对手有多个防守点时，需要所有分支都必胜才成立
// 简化处理：只考虑单防守点情况（大多数VCF路径如此）
if (defenses.size() > 1) return null;
int[] def = defenses.get(0);
board[def[0]][def[1]] = opponent;
// 检查对手是否反杀
List<Threat> oppThreats = findThreats(opponent);
boolean opponentWins = false;
for (Threat t : oppThreats) {
if (t.type == ThreatType.FIVE || t.type == ThreatType.OPEN_FOUR) {
opponentWins = true;
break;
}
}
if (opponentWins) {
board[def[0]][def[1]] = EMPTY;
return null;
}
// 继续搜索我方下一威胁
List<Threat> myNext = findThreats(player);
board[def[0]][def[1]] = EMPTY;
List<Threat> nextFours = new ArrayList<>();
for (Threat t : myNext) {
if (t.type == ThreatType.FIVE || t.type == ThreatType.OPEN_FOUR) {
return new int[]{r, c};
}
if (t.type == ThreatType.FOUR) nextFours.add(t);
}
if (nextFours.size() >= 2) return new int[]{r, c};
for (Threat t : nextFours) {
int[] result = vcfSearch(t.row, t.col, player, depth - 1, false);
if (result != null) return new int[]{r, c};
}
return null;
}
}
/**
* 找到对手必须防守的位置（针对(r,c)落子产生的冲四）
*/
private List<int[]> findDefenses(int r, int c, int player) {
List<int[]> defenses = new ArrayList<>();
// 简化实现：找到所有因该落子而形成的冲四的开放端
board[r][c] = player;
for (int[] dir : DIRS) {
LinePattern pattern = analyzeLine(r, c, dir[0], dir[1], player);
if (pattern.count == 4 && pattern.openEnds == 1) {
// 找到冲四的开放端
int dr = dir[0], dc = dir[1];
// 检查正方向的末端
int endR = r + dr * 4, endC = c + dc * 4;
while (inBounds(endR, endC) && board[endR][endC] == player) {
endR += dr; endC += dc;
}
if (inBounds(endR, endC) && board[endR][endC] == EMPTY) {
defenses.add(new int[]{endR, endC});
}
// 检查反方向的末端
int endR2 = r - dr, endC2 = c - dc;
while (inBounds(endR2, endC2) && board[endR2][endC2] == player) {
endR2 -= dr; endC2 -= dc;
}
if (inBounds(endR2, endC2) && board[endR2][endC2] == EMPTY) {
defenses.add(new int[]{endR2, endC2});
}
}
}
board[r][c] = EMPTY;
return defenses;
}
/**
* 检查(r,c)落子后是否形成五连
*/
private boolean isWin(int r, int c, int player) {
for (int[] dir : DIRS) {
int count = 1;
for (int sign = -1; sign <= 1; sign += 2) {
for (int i = 1; i < 5; i++) {
int nr = r + dir[0] * i * sign;
int nc = c + dir[1] * i * sign;
if (inBounds(nr, nc) && board[nr][nc] == player) {
count++;
} else break;
}
}
if (count >= 5) return true;
}
return false;
}
public void placeStone(int r, int c, int player) {
board[r][c] = player;
}
public void printBoard() {
System.out.print(" ");
for (int c = 0; c < BOARD_SIZE; c++) System.out.printf("%2d", c);
System.out.println();
for (int r = 0; r < BOARD_SIZE; r++) {
System.out.printf("%2d ", r);
for (int c = 0; c < BOARD_SIZE; c++) {
if (board[r][c] == EMPTY) System.out.print(" .");
else if (board[r][c] == BLACK) System.out.print(" X");
else System.out.print(" O");
}
System.out.println();
}
}
// 威胁类型枚举
enum ThreatType {
NONE(0), OPEN_THREE(1), BROKEN_THREE(2), FOUR(3), OPEN_FOUR(4), FIVE(5);
final int priority;
ThreatType(int p) { this.priority = p; }
}
static class Threat {
int row, col;
ThreatType type;
Threat(int r, int c, ThreatType t) { row = r; col = c; type = t; }
}
static class LinePattern {
int count; // 连续子数
int openEnds; // 开放端数
boolean hasGap; // 是否有间隙
LinePattern(int c, int o, boolean g) { count = c; openEnds = o; hasGap = g; }
}
public static void main(String[] args) {
GomokuTSS game = new GomokuTSS();
// 构造一个VCF测试局面：黑棋可连续冲四获胜
// 水平方向: (7,5)(7,6)(7,7) 三子，在(7,8)落子形成冲四
game.placeStone(7, 5, BLACK);
game.placeStone(7, 6, BLACK);
game.placeStone(7, 7, BLACK);
game.placeStone(6, 6, WHITE); // 白棋干扰子
System.out.println("初始局面:");
game.printBoard();
// 查找黑棋威胁
List<Threat> threats = game.findThreats(BLACK);
System.out.println("\n黑棋威胁数: " + threats.size());
for (Threat t : threats) {
if (t.type.priority >= ThreatType.FOUR.priority) {
System.out.printf(" 威胁: (%d,%d) -> %s%n", t.row, t.col, t.type);
}
}
// VCF搜索
int[] vcfMove = game.findVCF(BLACK, 6);
if (vcfMove != null) {
System.out.printf("\n发现VCF必胜首步: (%d, %d)%n", vcfMove[0], vcfMove[1]);
} else {
System.out.println("\n未找到VCF必胜路径");
}
}
}
复杂度分析
- 威胁识别：每次扫描全棋盘所有空位，时间复杂度 $O(N^2 \times 4)$，其中 $N=15$ 为棋盘大小，4为方向数。
- TSS搜索：每层仅考虑威胁着法而非全部空位。若平均每步有 $T$ 个威胁着法，深度为 $d$，则复杂度为 $O(T^d)$。实际中 $T$ 通常远小于总空位数。
- VCF搜索：由于只沿冲四路径搜索，深度通常不超过10即可覆盖绝大多数实战必胜局面。
- 空间复杂度：$O(N^2)$ 存储棋盘，搜索栈深度 $O(d)$。
总结
威胁空间搜索通过聚焦威胁着法，将五子棋的搜索树从广度优先转化为深度优先，极大提升了战术发现的效率。VCF路径识别则是TSS在连珠游戏中的典型应用——通过连续制造冲四，逼迫对手进入”单防”的被动局面。本文实现的Java版本涵盖了威胁识别、冲四生成、防守点计算和递归VCF搜索的完整流程，可作为五子棋AI战术模块的基础组件。
