引言
五子棋（Gomoku）是一种两人对弈的纯策略型棋类游戏。在标准规则下，先形成五子连珠的一方获胜。除了基础的Alpha-Beta剪枝与估值函数之外，威胁空间搜索（Threat Space Search, TSS）是一种专门针对五子棋的高效搜索算法，它通过识别棋盘上的”威胁点”来大幅剪枝，尤其擅长寻找必胜路径。本文将用Java实现基于威胁空间搜索的五子棋AI，重点讲解VCF（Victory by Continuous Four，连续冲四胜）必胜路径的检测算法。
威胁空间搜索核心思想
威胁空间搜索不同于传统的Minimax全宽度搜索，它只关注能够产生致命威胁的着法。在五子棋中，威胁分为不同等级：
- 活四：四个棋子连成一线且两端开放，对手无法防守，直接获胜。
- 冲四：四个棋子连成一线且只有一端开放，需要对手立即防守。
- 活三：三个棋子连成一线且两端开放，下一步可以形成活四或冲四。
- 跳活三：中间有空格的活三，同样具有极大威胁。
威胁空间搜索的核心策略是：只生成能够产生威胁的着法，并递归检测对手是否能够化解这些威胁。如果存在一系列威胁使得对手始终处于被动防守状态，最终形成无法防守的活四，则找到了必胜路径。
VCF必胜路径检测
VCF是指通过连续制造冲四（Four）来迫使对手防守，最终形成活四获胜的策略。VCF检测算法的基本流程如下：
- 识别当前棋盘上所有能够形成冲四的点（即”四”点）。
- 对于每一个冲四点，模拟落子后检查是否已经形成五连（直接获胜）。
- 如果没有直接获胜，检查对手是否必须防守（即对手的冲四/活三情况）。
- 在对手防守后，递归检查是否还能继续制造新的冲四。
- 如果在某条分支上能够连续制造冲四直至获胜，则找到了VCF必胜路径。
Java实现
棋盘表示与基础工具类
import java.util.*;
/**
* 五子棋棋盘表示与威胁检测
*/
public class GomokuBoard {
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[][] DIRECTIONS = {
{0, 1}, {1, 0}, {1, 1}, {1, -1}
};
private int[][] board;
public GomokuBoard() {
this.board = new int[BOARD_SIZE][BOARD_SIZE];
}
public GomokuBoard(int[][] board) {
this.board = new int[BOARD_SIZE][BOARD_SIZE];
for (int i = 0; i < BOARD_SIZE; i++) {
System.arraycopy(board[i], 0, this.board[i], 0, BOARD_SIZE);
}
}
public int get(int row, int col) {
return board[row][col];
}
public void set(int row, int col, int player) {
board[row][col] = player;
}
public boolean isValid(int row, int col) {
return row >= 0 && row < BOARD_SIZE && col >= 0 && col < BOARD_SIZE;
}
public boolean isEmpty(int row, int col) {
return isValid(row, col) && board[row][col] == EMPTY;
}
/**
* 检查某位置落子后是否形成五连
*/
public boolean checkWin(int row, int col, int player) {
for (int[] dir : DIRECTIONS) {
int count = 1;
// 正向搜索
for (int step = 1; step < 5; step++) {
int r = row + dir[0] * step;
int c = col + dir[1] * step;
if (isValid(r, c) && board[r][c] == player) {
count++;
} else {
break;
}
}
// 反向搜索
for (int step = 1; step < 5; step++) {
int r = row - dir[0] * step;
int c = col - dir[1] * step;
if (isValid(r, c) && board[r][c] == player) {
count++;
} else {
break;
}
}
if (count >= 5) return true;
}
return false;
}
/**
* 获取指定方向上的棋子序列，用于威胁识别
* 返回 [连续棋子数, 左端空格数, 右端空格数, 是否被阻挡]
*/
public LineInfo getLineInfo(int row, int col, int[] dir, int player) {
// 从(row, col)出发，沿dir方向获取连续信息
int count = 0;
int leftSpace = 0;
int rightSpace = 0;
boolean leftBlocked = false;
boolean rightBlocked = false;
// 先检查(row, col)本身
if (isValid(row, col) && board[row][col] == player) {
count++;
}
// 正向
for (int step = 1; step < 6; step++) {
int r = row + dir[0] * step;
int c = col + dir[1] * step;
if (!isValid(r, c)) {
rightBlocked = true;
break;
}
if (board[r][c] == player) {
if (rightSpace == 0) count++;
} else if (board[r][c] == EMPTY) {
rightSpace++;
if (rightSpace > 1) break; // 最多统计一个空格
} else {
rightBlocked = true;
break;
}
}
// 反向
for (int step = 1; step < 6; step++) {
int r = row - dir[0] * step;
int c = col - dir[1] * step;
if (!isValid(r, c)) {
leftBlocked = true;
break;
}
if (board[r][c] == player) {
if (leftSpace == 0) count++;
} else if (board[r][c] == EMPTY) {
leftSpace++;
if (leftSpace > 1) break;
} else {
leftBlocked = true;
break;
}
}
return new LineInfo(count, leftSpace, rightSpace, leftBlocked, rightBlocked);
}
/**
* 获取棋盘上所有空位
*/
public List<int[]> getEmptyCells() {
List<int[]> cells = new ArrayList<>();
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == EMPTY) {
cells.add(new int[]{i, j});
}
}
}
return cells;
}
public GomokuBoard copy() {
return new GomokuBoard(this.board);
}
}
/**
* 线路信息辅助类
*/
class LineInfo {
int count; // 连续棋子数
int leftSpace; // 左端空格数
int rightSpace; // 右端空格数
boolean leftBlocked;
boolean rightBlocked;
LineInfo(int count, int leftSpace, int rightSpace, boolean leftBlocked, boolean rightBlocked) {
this.count = count;
this.leftSpace = leftSpace;
this.rightSpace = rightSpace;
this.leftBlocked = leftBlocked;
this.rightBlocked = rightBlocked;
}
/**
* 判断是否为活四（四子连珠，两端开放）
*/
boolean isOpenFour() {
return count == 4 && leftSpace >= 1 && rightSpace >= 1 && !leftBlocked && !rightBlocked;
}
/**
* 判断是否为冲四（四子连珠，仅一端开放）
*/
boolean isFour() {
return count == 4 && ((leftSpace >= 1 && rightBlocked) || (rightSpace >= 1 && leftBlocked)
|| (leftSpace >= 1 && !leftBlocked && rightSpace == 0 && !rightBlocked)
|| (rightSpace >= 1 && !rightBlocked && leftSpace == 0 && !leftBlocked));
}
/**
* 判断是否为活三（三子连珠，两端各至少一个空格）
*/
boolean isOpenThree() {
return count == 3 && leftSpace >= 1 && rightSpace >= 1 && !leftBlocked && !rightBlocked;
}
/**
* 判断是否为跳活三（中间有空格的活三）
*/
boolean isSplitThree() {
return count == 3 && (leftSpace + rightSpace >= 2) && !leftBlocked && !rightBlocked;
}
}
威胁识别与VCF搜索
/**
* 威胁空间搜索与VCF必胜检测
*/
public class ThreatSpaceSearch {
private static final int MAX_DEPTH = 20; // VCF搜索最大深度
/**
* 威胁类型枚举
*/
enum ThreatType {
WIN, // 直接获胜（五连）
FOUR, // 冲四（必须防守）
OPEN_FOUR, // 活四（无法防守）
OPEN_THREE // 活三（潜在威胁）
}
/**
* 威胁节点
*/
static class Threat {
int row, col;
ThreatType type;
List<int[]> defenses; // 对手的防守点
Threat(int row, int col, ThreatType type, List<int[]> defenses) {
this.row = row;
this.col = col;
this.type = type;
this.defenses = defenses;
}
}
/**
* 查找当前棋盘上指定玩家的所有威胁
*/
public static List<Threat> findThreats(GomokuBoard board, int player) {
List<Threat> threats = new ArrayList<>();
int opponent = (player == GomokuBoard.BLACK) ? GomokuBoard.WHITE : GomokuBoard.BLACK;
for (int i = 0; i < GomokuBoard.BOARD_SIZE; i++) {
for (int j = 0; j < GomokuBoard.BOARD_SIZE; j++) {
if (board.get(i, j) != GomokuBoard.EMPTY) continue;
// 模拟落子
board.set(i, j, player);
// 检查是否直接获胜
if (board.checkWin(i, j, player)) {
List<int[]> defenses = new ArrayList<>();
threats.add(new Threat(i, j, ThreatType.WIN, defenses));
board.set(i, j, GomokuBoard.EMPTY);
continue;
}
// 检查四个方向上的威胁
List<int[]> allDefenses = new ArrayList<>();
boolean isOpenFour = false;
boolean isFour = false;
boolean isOpenThree = false;
for (int[] dir : new int[][]{{0,1}, {1,0}, {1,1}, {1,-1}}) {
LineInfo info = board.getLineInfo(i, j, dir, player);
if (info.isOpenFour()) {
isOpenFour = true;
} else if (info.isFour()) {
isFour = true;
// 冲四的防守点是活四的另一端
if (info.leftSpace >= 1 && !info.leftBlocked) {
// 需要找到具体的防守坐标
int dr = i, dc = j;
for (int step = 1; step <= 5; step++) {
int nr = i - dir[0] * step;
int nc = j - dir[1] * step;
if (board.isEmpty(nr, nc)) {
allDefenses.add(new int[]{nr, nc});
break;
}
}
}
if (info.rightSpace >= 1 && !info.rightBlocked) {
for (int step = 1; step <= 5; step++) {
int nr = i + dir[0] * step;
int nc = j + dir[1] * step;
if (board.isEmpty(nr, nc)) {
allDefenses.add(new int[]{nr, nc});
break;
}
}
}
} else if (info.isOpenThree() || info.isSplitThree()) {
isOpenThree = true;
}
}
board.set(i, j, GomokuBoard.EMPTY);
// 分类威胁
if (isOpenFour) {
threats.add(new Threat(i, j, ThreatType.OPEN_FOUR, new ArrayList<>()));
} else if (isFour) {
// 去重防守点
List<int[]> uniqueDefenses = new ArrayList<>();
for (int[] d : allDefenses) {
boolean exists = false;
for (int[] u : uniqueDefenses) {
if (u[0] == d[0] && u[1] == d[1]) {
exists = true;
break;
}
}
if (!exists) uniqueDefenses.add(d);
}
threats.add(new Threat(i, j, ThreatType.FOUR, uniqueDefenses));
} else if (isOpenThree) {
threats.add(new Threat(i, j, ThreatType.OPEN_THREE, new ArrayList<>()));
}
}
}
return threats;
}
/**
* VCF搜索：寻找连续冲四必胜路径
* @return 如果找到必胜路径，返回获胜的落子序列；否则返回null
*/
public static List<int[]> searchVCF(GomokuBoard board, int player, int depth) {
if (depth > MAX_DEPTH) return null;
List<Threat> threats = findThreats(board, player);
// 优先处理直接获胜
for (Threat t : threats) {
if (t.type == ThreatType.WIN) {
List<int[]> result = new ArrayList<>();
result.add(new int[]{t.row, t.col});
return result;
}
}
// 处理活四（无法防守，直接获胜）
for (Threat t : threats) {
if (t.type == ThreatType.OPEN_FOUR) {
List<int[]> result = new ArrayList<>();
result.add(new int[]{t.row, t.col});
return result;
}
}
// 尝试冲四序列
for (Threat t : threats) {
if (t.type != ThreatType.FOUR) continue;
// 模拟落子（制造冲四）
board.set(t.row, t.col, player);
if (t.defenses.isEmpty()) {
// 没有防守点，直接获胜
List<int[]> result = new ArrayList<>();
result.add(new int[]{t.row, t.col});
board.set(t.row, t.col, GomokuBoard.EMPTY);
return result;
}
// 对手必须防守每一个防守点
boolean allWin = true;
List<int[]> bestSequence = null;
for (int[] defense : t.defenses) {
if (!board.isEmpty(defense[0], defense[1])) {
allWin = false;
break;
}
// 对手防守
int opponent = (player == GomokuBoard.BLACK) ? GomokuBoard.WHITE : GomokuBoard.BLACK;
board.set(defense[0], defense[1], opponent);
// 递归搜索
List<int[]> subSequence = searchVCF(board, player, depth + 1);
board.set(defense[0], defense[1], GomokuBoard.EMPTY);
if (subSequence == null) {
allWin = false;
break;
}
if (bestSequence == null || subSequence.size() > bestSequence.size()) {
bestSequence = subSequence;
}
}
board.set(t.row, t.col, GomokuBoard.EMPTY);
if (allWin && bestSequence != null) {
List<int[]> result = new ArrayList<>();
result.add(new int[]{t.row, t.col});
result.addAll(bestSequence);
return result;
}
}
return null;
}
/**
* 综合威胁搜索：结合VCF与估值选择最佳着法
*/
public static int[] findBestMove(GomokuBoard board, int player) {
// 首先尝试VCF
List<int[]> vcfSequence = searchVCF(board, player, 0);
if (vcfSequence != null && !vcfSequence.isEmpty()) {
System.out.println("找到VCF必胜路径！");
return vcfSequence.get(0);
}
// 如果没有VCF，尝试阻止对手的VCF
int opponent = (player == GomokuBoard.BLACK) ? GomokuBoard.WHITE : GomokuBoard.BLACK;
List<int[]> opponentVCF = searchVCF(board, opponent, 0);
if (opponentVCF != null && !opponentVCF.isEmpty()) {
// 对手有VCF，尝试阻止
System.out.println("检测到对手VCF威胁，进行防守！");
// 返回一个能够阻止对手VCF的着法
return findBlockingMove(board, player, opponentVCF);
}
// 否则使用启发式评估选择最佳着法
return heuristicSearch(board, player);
}
/**
* 寻找阻止对手VCF的防守着法
*/
private static int[] findBlockingMove(GomokuBoard board, int player, List<int[]> opponentVCF) {
// 简单策略：占据对手VCF路径上的关键点
if (opponentVCF != null && !opponentVCF.isEmpty()) {
int[] firstThreat = opponentVCF.get(0);
return firstThreat;
}
return heuristicSearch(board, player);
}
/**
* 启发式搜索：基于威胁数量的简单评估
*/
private static int[] heuristicSearch(GomokuBoard board, int player) {
int bestScore = Integer.MIN_VALUE;
int[] bestMove = null;
// 只考虑已有棋子附近的空位（减少搜索空间）
Set<String> candidates = new HashSet<>();
for (int i = 0; i < GomokuBoard.BOARD_SIZE; i++) {
for (int j = 0; j < GomokuBoard.BOARD_SIZE; j++) {
if (board.get(i, j) != GomokuBoard.EMPTY) {
for (int di = -2; di <= 2; di++) {
for (int dj = -2; dj <= 2; dj++) {
int ni = i + di, nj = j + dj;
if (board.isEmpty(ni, nj)) {
candidates.add(ni + "," + nj);
}
}
}
}
}
}
// 如果没有候选点（开局），选择中心
if (candidates.isEmpty()) {
return new int[]{GomokuBoard.BOARD_SIZE / 2, GomokuBoard.BOARD_SIZE / 2};
}
for (String key : candidates) {
String[] parts = key.split(",");
int r = Integer.parseInt(parts[0]);
int c = Integer.parseInt(parts[1]);
int score = evaluatePoint(board, r, c, player);
if (score > bestScore) {
bestScore = score;
bestMove = new int[]{r, c};
}
}
return bestMove;
}
/**
* 评估某位置的分数
*/
private static int evaluatePoint(GomokuBoard board, int row, int col, int player) {
int score = 0;
board.set(row, col, player);
List<Threat> myThreats = findThreats(board, player);
for (Threat t : myThreats) {
if (t.row == row && t.col == col) {
switch (t.type) {
case WIN: score += 100000; break;
case OPEN_FOUR: score += 10000; break;
case FOUR: score += 1000; break;
case OPEN_THREE: score += 100; break;
}
}
}
board.set(row, col, GomokuBoard.EMPTY);
// 同时考虑防守价值
int opponent = (player == GomokuBoard.BLACK) ? GomokuBoard.WHITE : GomokuBoard.BLACK;
board.set(row, col, opponent);
List<Threat> oppThreats = findThreats(board, opponent);
for (Threat t : oppThreats) {
if (t.row == row && t.col == col) {
switch (t.type) {
case WIN: score += 50000; break;
case OPEN_FOUR: score += 5000; break;
case FOUR: score += 500; break;
case OPEN_THREE: score += 50; break;
}
}
}
board.set(row, col, GomokuBoard.EMPTY);
return score;
}
}
主程序与测试
/**
* 五子棋威胁空间搜索主程序
*/
public class GomokuTSS {
public static void main(String[] args) {
GomokuBoard board = new GomokuBoard();
// 设置一个测试局面：黑棋有机会通过VCF获胜
// 创建一个冲四局面
board.set(7, 7, GomokuBoard.BLACK);
board.set(7, 8, GomokuBoard.BLACK);
board.set(7, 9, GomokuBoard.BLACK);
board.set(7, 10, GomokuBoard.BLACK); // 横向四子
board.set(8, 7, GomokuBoard.WHITE);
board.set(6, 7, GomokuBoard.WHITE);
System.out.println("=== 五子棋威胁空间搜索演示 ===");
printBoard(board);
// 测试威胁识别
System.out.println("\n黑棋的威胁分析：");
List<ThreatSpaceSearch.Threat> threats = ThreatSpaceSearch.findThreats(board, GomokuBoard.BLACK);
for (ThreatSpaceSearch.Threat t : threats) {
if (t.type == ThreatSpaceSearch.ThreatType.WIN ||
t.type == ThreatSpaceSearch.ThreatType.OPEN_FOUR ||
t.type == ThreatSpaceSearch.ThreatType.FOUR) {
System.out.printf(" 威胁: (%d, %d) - %s%n", t.row, t.col, t.type);
}
}
// 测试VCF搜索
System.out.println("\nVCF搜索：");
List<int[]> vcf = ThreatSpaceSearch.searchVCF(board, GomokuBoard.BLACK, 0);
if (vcf != null) {
System.out.println("找到必胜路径！落子序列：");
for (int[] move : vcf) {
System.out.printf(" (%d, %d)%n", move[0], move[1]);
}
} else {
System.out.println("当前局面无VCF必胜路径");
}
// 测试AI选择最佳着法
int[] bestMove = ThreatSpaceSearch.findBestMove(board, GomokuBoard.BLACK);
System.out.printf("\nAI推荐着法: (%d, %d)%n", bestMove[0], bestMove[1]);
}
private static void printBoard(GomokuBoard board) {
System.out.print(" ");
for (int j = 0; j < GomokuBoard.BOARD_SIZE; j++) {
System.out.printf("%2d ", j);
}
System.out.println();
for (int i = 0; i < GomokuBoard.BOARD_SIZE; i++) {
System.out.printf("%2d ", i);
for (int j = 0; j < GomokuBoard.BOARD_SIZE; j++) {
char c = '.';
if (board.get(i, j) == GomokuBoard.BLACK) c = 'X';
else if (board.get(i, j) == GomokuBoard.WHITE) c = 'O';
System.out.printf(" %c ", c);
}
System.out.println();
}
}
}
算法复杂度分析
威胁空间搜索的时间复杂度远低于传统Minimax搜索。在15×15的棋盘上：
- 全宽度Minimax：每步约225个候选着法，深度为4时搜索空间约为 $225^4 \approx 2.5 \times 10^9$。
- 威胁空间搜索：每步通常只生成5-20个威胁着法，深度为10时搜索空间约为 $10^{10}$ 但在实际中大量分支会被对手的防守所剪枝。
VCF搜索在实际中通常能在毫秒级完成，因为它只关注致命威胁而非所有可能的着法。
总结
威胁空间搜索是五子棋AI中一种非常高效的 specialized 搜索算法。本文实现了：
- 棋盘表示与基础工具：支持15×15棋盘、四方向检测、线路信息提取。
- 威胁识别系统：自动识别活四、冲四、活三等威胁类型。
- VCF必胜路径检测：通过递归搜索连续冲四序列，检测是否存在必胜路径。
- 综合决策引擎：优先VCF攻击，其次防守对手VCF，最后使用启发式评估。
读者通过本文可以深入理解威胁空间搜索的核心思想，并将其应用到其他棋类游戏的AI开发中。
