每日算法 — 使用java实现五子棋：威胁空间搜索与VCF必胜路径检测

可莉爸爸 AI算法

引言

五子棋（Gomoku）规则简单但策略深邃。与Minimax搜索不同，高水平五子棋AI通常采用威胁空间搜索（Threat Space Search, TSS），通过识别和推演棋局中的”威胁”（如活三、冲四）来寻找必胜路径。本文使用Java实现TSS核心算法，并集成VCF（Victory by Continuous Four，连续冲四必胜）路径检测，让AI在攻击型棋局中展现出人类高手般的敏锐直觉。

算法核心思想

威胁的定义与分类

在五子棋中，威胁是指一方落子后形成的、对方必须在下一步回应的棋型：

威胁类型 威胁等级 说明
双四（Double Four） 必胜 两个独立冲四，对方无法同时防守
四三（Four-Three） 高威胁 一个冲四+一个活三，对方挡四则活三变四
双三（Double Three） 中威胁 两个活三，若对方不挡则下一步变四三
冲四（Straight Four） 直接威胁 已有四子连珠，对方必须阻挡
活三（Open Three） 潜在威胁 可发展为冲四的三子连珠

威胁空间搜索策略

TSS不是搜索所有空位，而是仅搜索与现有威胁相关的落点：

  1. 生成己方威胁：找出当前局面下所有可形成的威胁落点
  2. 推演威胁序列：假设对手只能防守最直接威胁，递归搜索多步威胁组合
  3. VCF检测：专门搜索通过连续冲四迫使对手防守最终获胜的路径

Java实现

棋盘与威胁检测

import java.util.*;

public class GomokuTSS {
    static final int SIZE = 15;
    static final int EMPTY = 0;
    static final int BLACK = 1;
    static final int WHITE = 2;

    // 方向向量：横、竖、左斜、右斜
    static final int[][] DIRS = {{0,1}, {1,0}, {1,1}, {1,-1}};

    int[][] board = new int[SIZE][SIZE];
    int currentPlayer = BLACK;

    // 棋型评分表（用于非TSS场景的启发式评估）
    static final Map<String, Integer> PATTERNS = new HashMap<>();
    static {
        PATTERNS.put("11111", 100000);   // 连五
        PATTERNS.put("011110", 10000);   // 活四
        PATTERNS.put("01111", 1000);     // 冲四
        PATTERNS.put("11110", 1000);
        PATTERNS.put("01110", 1000);     // 活三
        PATTERNS.put("011100", 500);
        PATTERNS.put("001110", 500);
        PATTERNS.put("0110", 100);       // 活二
        PATTERNS.put("01100", 100);
        PATTERNS.put("00110", 100);
    }

    boolean inBounds(int r, int c) {
        return r >= 0 && r < SIZE && c >= 0 && c < SIZE;
    }

棋型提取与识别

    /**
     * 提取某方向上的棋型字符串
     * @param player 要提取的棋子颜色
     * @param isAttack true表示提取攻击方（当前玩家）棋型
     */
    String extractPattern(int r, int c, int dirIdx, int player) {
        int dr = DIRS[dirIdx][0], dc = DIRS[dirIdx][1];
        StringBuilder sb = new StringBuilder();
        // 向负方向延伸4格
        for (int i = -4; i <= 4; i++) {
            int nr = r + dr * i, nc = c + dc * i;
            if (!inBounds(nr, nc)) sb.append('2'); // 边界视为对手
            else if (board[nr][nc] == EMPTY) sb.append('0');
            else if (board[nr][nc] == player) sb.append('1');
            else sb.append('2');
        }
        return sb.toString();
    }

    /**
     * 检测某个落点是否为威胁点（形成活三、冲四等）
     */
    boolean isThreatMove(int r, int c, int player) {
        if (board[r][c] != EMPTY) return false;
        board[r][c] = player;
        boolean threat = false;
        for (int d = 0; d < 4 && !threat; d++) {
            String pat = extractPattern(r, c, d, player);
            // 检查是否形成活三、冲四或活四
            if (pat.contains("01110") || pat.contains("01111") || 
                pat.contains("11110") || pat.contains("011110")) {
                threat = true;
            }
        }
        board[r][c] = EMPTY;
        return threat;
    }

    /**
     * 获取所有威胁点：落子后形成威胁的位置，以及对方已有威胁需要防守的位置
     */
    List<int[]> getThreatMoves(int player) {
        Set<String> moves = new LinkedHashSet<>();
        int opponent = 3 - player;

        // 1. 己方进攻威胁点
        for (int r = 0; r < SIZE; r++) {
            for (int c = 0; c < SIZE; c++) {
                if (board[r][c] == EMPTY && isThreatMove(r, c, player)) {
                    moves.add(r + "," + c);
                }
            }
        }

        // 2. 对方威胁点（必须防守）
        for (int r = 0; r < SIZE; r++) {
            for (int c = 0; c < SIZE; c++) {
                if (board[r][c] == EMPTY && isThreatMove(r, c, opponent)) {
                    moves.add(r + "," + c);
                }
            }
        }

        // 3. 若威胁点太少，补充周围有棋子的位置
        if (moves.size() < 5) {
            for (int r = 0; r < SIZE; r++) {
                for (int c = 0; c < SIZE; c++) {
                    if (board[r][c] != EMPTY) {
                        for (int dr = -2; dr <= 2; dr++) {
                            for (int dc = -2; dc <= 2; dc++) {
                                int nr = r + dr, nc = c + dc;
                                if (inBounds(nr, nc) && board[nr][nc] == EMPTY) {
                                    moves.add(nr + "," + nc);
                                }
                            }
                        }
                    }
                }
            }
        }

        List<int[]> result = new ArrayList<>();
        for (String m : moves) {
            String[] parts = m.split(",");
            result.add(new int[]{Integer.parseInt(parts[0]), Integer.parseInt(parts[1])});
        }
        return result;
    }

VCF必胜路径检测

    /**
     * VCF检测：寻找通过连续冲四迫使对手防守最终获胜的路径
     * @return 若存在必胜路径，返回第一步落子位置；否则null
     */
    int[] findVCF(int player, int depth, int maxDepth) {
        if (depth > maxDepth) return null;

        List<int[]> threats = getMyThreatMoves(player);
        int opponent = 3 - player;

        for (int[] move : threats) {
            int r = move[0], c = move[1];
            if (board[r][c] != EMPTY) continue;

            board[r][c] = player;

            // 检查是否直接获胜（形成五连）
            if (isWin(r, c, player)) {
                board[r][c] = EMPTY;
                return move;
            }

            // 获取此威胁下对手的防守点
            List<int[]> defenses = getDefenseMoves(r, c, player, opponent);
            boolean allWin = !defenses.isEmpty();

            for (int[] def : defenses) {
                if (board[def[0]][def[1]] != EMPTY) continue;
                board[def[0]][def[1]] = opponent;

                // 递归搜索下一步VCF
                int[] next = findVCF(player, depth + 1, maxDepth);
                board[def[0]][def[1]] = EMPTY;

                if (next == null) {
                    allWin = false;
                    break;
                }
            }

            board[r][c] = EMPTY;
            if (allWin || defenses.isEmpty()) {
                return move;
            }
        }
        return null;
    }

    /**
     * 获取当前玩家的纯进攻威胁点（不包括防守）
     */
    List<int[]> getMyThreatMoves(int player) {
        List<int[]> result = new ArrayList<>();
        for (int r = 0; r < SIZE; r++) {
            for (int c = 0; c < SIZE; c++) {
                if (board[r][c] == EMPTY && isThreatMove(r, c, player)) {
                    result.add(new int[]{r, c});
                }
            }
        }
        // 按威胁等级排序：冲四 > 活三
        result.sort((a, b) -> {
            int sa = threatScore(a[0], a[1], player);
            int sb = threatScore(b[0], b[1], player);
            return sb - sa;
        });
        return result;
    }

    /**
     * 评估某落点的威胁分数
     */
    int threatScore(int r, int c, int player) {
        if (board[r][c] != EMPTY) return 0;
        board[r][c] = player;
        int score = 0;
        for (int d = 0; d < 4; d++) {
            String pat = extractPattern(r, c, d, player);
            if (pat.contains("011110")) score += 10000;
            else if (pat.contains("01111") || pat.contains("11110")) score += 1000;
            else if (pat.contains("01110")) score += 500;
        }
        board[r][c] = EMPTY;
        return score;
    }

    /**
     * 获取对手对某威胁的防守点
     */
    List<int[]> getDefenseMoves(int threatR, int threatC, int threatPlayer, int defender) {
        Set<String> defs = new HashSet<>();
        // 防守点通常是威胁连线上的空位
        for (int d = 0; d < 4; d++) {
            int dr = DIRS[d][0], dc = DIRS[d][1];
            for (int i = -4; i <= 4; i++) {
                int nr = threatR + dr * i, nc = threatC + dc * i;
                if (inBounds(nr, nc) && board[nr][nc] == EMPTY) {
                    defs.add(nr + "," + nc);
                }
            }
        }
        List<int[]> result = new ArrayList<>();
        for (String s : defs) {
            String[] p = s.split(",");
            result.add(new int[]{Integer.parseInt(p[0]), Integer.parseInt(p[1])});
        }
        return result;
    }

    /**
     * 检查某落子是否形成五连获胜
     */
    boolean isWin(int r, int c, int player) {
        for (int d = 0; d < 4; d++) {
            int dr = DIRS[d][0], dc = DIRS[d][1];
            int count = 1;
            // 正向
            for (int i = 1; i < 5; i++) {
                int nr = r + dr * i, nc = c + dc * i;
                if (inBounds(nr, nc) && board[nr][nc] == player) count++;
                else break;
            }
            // 反向
            for (int i = 1; i < 5; i++) {
                int nr = r - dr * i, nc = c - dc * i;
                if (inBounds(nr, nc) && board[nr][nc] == player) count++;
                else break;
            }
            if (count >= 5) return true;
        }
        return false;
    }

TSS主搜索与决策

    /**
     * 主决策函数：优先VCF，其次启发式评估
     */
    int[] makeMove() {
        // 1. 先检查自己是否有VCF必胜路径
        int[] vcf = findVCF(currentPlayer, 0, 8);
        if (vcf != null) {
            System.out.println("发现VCF必胜路径!");
            return vcf;
        }

        // 2. 检查对方是否有VCF，若有则必须阻挡
        int[] oppVCF = findVCF(3 - currentPlayer, 0, 6);
        if (oppVCF != null) {
            System.out.println("阻挡对方VCF!");
            return oppVCF;
        }

        // 3. 威胁空间搜索：寻找一步内形成四三的落点
        List<int[]> threats = getThreatMoves(currentPlayer);
        int[] bestMove = null;
        int bestScore = Integer.MIN_VALUE;

        for (int[] m : threats) {
            int r = m[0], c = m[1];
            if (board[r][c] != EMPTY) continue;
            board[r][c] = currentPlayer;
            int score = evaluateBoard(currentPlayer);
            board[r][c] = EMPTY;
            if (score > bestScore) {
                bestScore = score;
                bestMove = m;
            }
        }

        return bestMove != null ? bestMove : new int[]{SIZE/2, SIZE/2};
    }

    /**
     * 启发式局面评估
     */
    int evaluateBoard(int player) {
        int score = 0;
        int opponent = 3 - player;
        for (int r = 0; r < SIZE; r++) {
            for (int c = 0; c < SIZE; c++) {
                if (board[r][c] == EMPTY) continue;
                for (int d = 0; d < 4; d++) {
                    String pat = extractPattern(r, c, d, board[r][c]);
                    for (Map.Entry<String, Integer> e : PATTERNS.entrySet()) {
                        if (pat.contains(e.getKey())) {
                            int val = e.getValue();
                            if (board[r][c] == player) score += val;
                            else score -= val;
                        }
                    }
                }
            }
        }
        return score;
    }

运行演示

    void playGame() {
        System.out.println("=== 五子棋 TSS AI 演示 ===");
        // 预设一个有利于黑棋进攻的局面
        board[7][7] = BLACK;
        board[7][8] = WHITE;
        board[8][8] = BLACK;
        board[6][6] = WHITE;
        board[9][9] = BLACK;
        board[8][7] = WHITE;

        printBoard();

        currentPlayer = BLACK;
        int[] move = makeMove();
        System.out.printf("黑棋落子: (%d, %d)%n", move[0], move[1]);
        board[move[0]][move[1]] = BLACK;
        printBoard();
    }

    void printBoard() {
        for (int r = 0; r < SIZE; r++) {
            for (int c = 0; c < 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();
        }
    }

    public static void main(String[] args) {
        GomokuTSS game = new GomokuTSS();
        game.playGame();
    }

复杂度分析

阶段 时间复杂度 说明
威胁点生成 $O(SIZE^2)$ 遍历棋盘检测威胁
VCF搜索 $O(b^d)$ $b$为平均分支因子（通常<10），$d$为搜索深度
启发式评估 $O(SIZE^2 \times 4)$ 四方向棋型匹配
实际对局 毫秒级 15×15棋盘，威胁点稀疏

总结

威胁空间搜索将五子棋的搜索空间从 $O(225)$ 压缩到 $O(10\sim30)$ 个关键威胁点，配合VCF必胜路径检测，AI能在复杂局面中快速发现杀招。本文实现的Java版本包含完整的棋型识别、威胁生成与递归验证逻辑，读者可在此基础上扩展VC2（两步必胜）检测、禁手规则（针对有禁手五子棋）以及神经网络辅助评估，打造更强的对弈引擎。

Tagged with: