引言
四子连珠（Connect Four）是一款经典的双人博弈游戏，玩家轮流在7列6行的竖立棋盘中投放棋子，率先在横、竖或斜向连成四子者获胜。本文将用Java实现带AI的四子连珠，核心算法为Minimax博弈树搜索配合Alpha-Beta剪枝优化，并设计多维度评估函数辅助决策。
游戏规则与状态表示
棋盘采用7列×6行结构，使用二维整数数组表示：0为空，1为玩家1，2为玩家2。棋子受重力影响，只能落在每列最底部的空位。
核心算法设计
1. 评估函数设计
AI需要在没有搜索到终局时评估当前局面的优劣。评估函数从四个方向（横、竖、主对角线、副对角线）扫描棋盘，对每种连续棋型打分：
- 四连：±10000分（必胜/必败）
- 活三（两边开放）：±1000分
- 眠三（一边开放）：±100分
- 活二：±50分
- 眠二：±10分
2. Minimax搜索
Minimax算法假设对手也会做出最优选择，通过递归搜索博弈树，在MAX层选择得分最大值，在MIN层选择得分最小值。
3. Alpha-Beta剪枝
在Minimax基础上，维护两个阈值：alpha（MAX层当前最优值）和beta（MIN层当前最优值）。当alpha ≥ beta时，剩余分支无需再搜索，直接剪枝。配合中间列优先的走子顺序，剪枝效率可提升数倍。
Java完整实现
import java.util.*;
/**
* 四子连珠AI核心类
* 实现Minimax搜索 + Alpha-Beta剪枝 + 启发式评估
*/
public class ConnectFourAI {
// 棋盘尺寸
public static final int ROWS = 6;
public static final int COLS = 7;
// 玩家标识
public static final int EMPTY = 0;
public static final int PLAYER = 1;
public static final int AI = 2;
// 搜索深度
private int maxDepth;
// 评估权重
private static final int FOUR = 10000;
private static final int OPEN_THREE = 1000;
private static final int CLOSED_THREE = 100;
private static final int OPEN_TWO = 50;
private static final int CLOSED_TWO = 10;
public ConnectFourAI(int depth) {
this.maxDepth = depth;
}
/**
* 获取AI的最佳落子列
*/
public int getBestMove(int[][] board) {
int bestCol = -1;
int bestScore = Integer.MIN_VALUE;
// 中间列优先，提升剪枝效率
int[] order = {3, 2, 4, 1, 5, 0, 6};
for (int col : order) {
int row = getNextOpenRow(board, col);
if (row == -1) continue;
board[row][col] = AI;
int score = minimax(board, maxDepth - 1, false,
Integer.MIN_VALUE, Integer.MAX_VALUE);
board[row][col] = EMPTY;
if (score > bestScore) {
bestScore = score;
bestCol = col;
}
}
return bestCol;
}
/**
* Minimax算法 + Alpha-Beta剪枝
* @param isMaximizing true表示AI回合(MAX层)，false表示玩家回合(MIN层)
*/
private int minimax(int[][] board, int depth,
boolean isMaximizing, int alpha, int beta) {
// 终局判断
if (checkWin(board, AI)) return FOUR;
if (checkWin(board, PLAYER)) return -FOUR;
if (isBoardFull(board) || depth == 0) {
return evaluateBoard(board);
}
int[] order = {3, 2, 4, 1, 5, 0, 6};
if (isMaximizing) {
int maxEval = Integer.MIN_VALUE;
for (int col : order) {
int row = getNextOpenRow(board, col);
if (row == -1) continue;
board[row][col] = AI;
int eval = minimax(board, depth - 1, false, alpha, beta);
board[row][col] = EMPTY;
maxEval = Math.max(maxEval, eval);
alpha = Math.max(alpha, eval);
if (beta <= alpha) break; // Beta剪枝
}
return maxEval;
} else {
int minEval = Integer.MAX_VALUE;
for (int col : order) {
int row = getNextOpenRow(board, col);
if (row == -1) continue;
board[row][col] = PLAYER;
int eval = minimax(board, depth - 1, true, alpha, beta);
board[row][col] = EMPTY;
minEval = Math.min(minEval, eval);
beta = Math.min(beta, eval);
if (beta <= alpha) break; // Alpha剪枝
}
return minEval;
}
}
/**
* 获取指定列的下一个空行（从底部开始）
*/
private int getNextOpenRow(int[][] board, int col) {
for (int row = ROWS - 1; row >= 0; row--) {
if (board[row][col] == EMPTY) return row;
}
return -1;
}
/**
* 检查指定玩家是否获胜
*/
private boolean checkWin(int[][] board, int piece) {
// 水平方向
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c <= COLS - 4; c++) {
if (board[r][c] == piece && board[r][c+1] == piece
&& board[r][c+2] == piece && board[r][c+3] == piece)
return true;
}
}
// 垂直方向
for (int r = 0; r <= ROWS - 4; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] == piece && board[r+1][c] == piece
&& board[r+2][c] == piece && board[r+3][c] == piece)
return true;
}
}
// 主对角线
for (int r = 0; r <= ROWS - 4; r++) {
for (int c = 0; c <= COLS - 4; c++) {
if (board[r][c] == piece && board[r+1][c+1] == piece
&& board[r+2][c+2] == piece && board[r+3][c+3] == piece)
return true;
}
}
// 副对角线
for (int r = 3; r < ROWS; r++) {
for (int c = 0; c <= COLS - 4; c++) {
if (board[r][c] == piece && board[r-1][c+1] == piece
&& board[r-2][c+2] == piece && board[r-3][c+3] == piece)
return true;
}
}
return false;
}
/**
* 棋盘评估函数：从四个方向扫描棋型
*/
private int evaluateBoard(int[][] board) {
int score = 0;
// 水平评估
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c <= COLS - 4; c++) {
score += evaluateWindow(board, r, c, 0, 1);
}
}
// 垂直评估
for (int r = 0; r <= ROWS - 4; r++) {
for (int c = 0; c < COLS; c++) {
score += evaluateWindow(board, r, c, 1, 0);
}
}
// 主对角线评估
for (int r = 0; r <= ROWS - 4; r++) {
for (int c = 0; c <= COLS - 4; c++) {
score += evaluateWindow(board, r, c, 1, 1);
}
}
// 副对角线评估
for (int r = 3; r < ROWS; r++) {
for (int c = 0; c <= COLS - 4; c++) {
score += evaluateWindow(board, r, c, -1, 1);
}
}
// 中间列偏好
for (int r = 0; r < ROWS; r++) {
if (board[r][3] == AI) score += 6;
else if (board[r][3] == PLAYER) score -= 6;
}
return score;
}
/**
* 评估一个四格窗口的得分
* @param dr 行方向增量
* @param dc 列方向增量
*/
private int evaluateWindow(int[][] board, int r, int c, int dr, int dc) {
int aiCount = 0, playerCount = 0, emptyCount = 0;
for (int i = 0; i < 4; i++) {
int cell = board[r + i * dr][c + i * dc];
if (cell == AI) aiCount++;
else if (cell == PLAYER) playerCount++;
else emptyCount++;
}
// 同时包含双方棋子，无威胁
if (aiCount > 0 && playerCount > 0) return 0;
// AI棋型评分
if (aiCount > 0) {
if (aiCount == 4) return FOUR;
if (aiCount == 3 && emptyCount == 1) return OPEN_THREE;
if (aiCount == 3 && emptyCount == 0) return CLOSED_THREE;
if (aiCount == 2 && emptyCount == 2) return OPEN_TWO;
if (aiCount == 2 && emptyCount == 1) return CLOSED_TWO;
}
// 玩家棋型评分（取负）
if (playerCount > 0) {
if (playerCount == 4) return -FOUR;
if (playerCount == 3 && emptyCount == 1) return -OPEN_THREE;
if (playerCount == 3 && emptyCount == 0) return -CLOSED_THREE;
if (playerCount == 2 && emptyCount == 2) return -OPEN_TWO;
if (playerCount == 2 && emptyCount == 1) return -CLOSED_TWO;
}
return 0;
}
private boolean isBoardFull(int[][] board) {
for (int c = 0; c < COLS; c++) {
if (board[0][c] == EMPTY) return false;
}
return true;
}
// 主程序：人机对战演示
public static void main(String[] args) {
ConnectFourAI ai = new ConnectFourAI(5); // 搜索深度5
int[][] board = new int[ROWS][COLS];
Scanner sc = new Scanner(System.in);
boolean playerTurn = true;
while (true) {
printBoard(board);
if (ai.checkWin(board, AI)) {
System.out.println("AI获胜！");
break;
}
if (ai.checkWin(board, PLAYER)) {
System.out.println("玩家获胜！");
break;
}
if (ai.isBoardFull(board)) {
System.out.println("平局！");
break;
}
if (playerTurn) {
System.out.print("请输入落子列(0-6): ");
int col = sc.nextInt();
int row = ai.getNextOpenRow(board, col);
if (row == -1) {
System.out.println("该列已满，请重新输入！");
continue;
}
board[row][col] = PLAYER;
} else {
System.out.println("AI思考中...");
int col = ai.getBestMove(board);
int row = ai.getNextOpenRow(board, col);
board[row][col] = AI;
System.out.println("AI落子于列: " + col);
}
playerTurn = !playerTurn;
}
sc.close();
}
private int getNextOpenRow(int[][] board, int col) {
for (int row = ROWS - 1; row >= 0; row--) {
if (board[row][col] == EMPTY) return row;
}
return -1;
}
private static void printBoard(int[][] board) {
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
char ch = board[r][c] == EMPTY ? '.' :
(board[r][c] == PLAYER ? 'X' : 'O');
System.out.print(ch + " ");
}
System.out.println();
}
System.out.println("0 1 2 3 4 5 6");
}
}
复杂度分析
- 时间复杂度：最坏情况下Minimax搜索复杂度为O(b^d)，其中b≈7为分支因子，d为搜索深度。Alpha-Beta剪枝配合中间列优先排序后，实际复杂度可降至O(b^(d/2))。
- 空间复杂度：O(d)递归栈空间。
扩展优化方向
- 迭代加深：逐步增加搜索深度，在限时内找到最优解
- 置换表：用Zobrist哈希缓存已评估局面，避免重复计算
- 开局库：预存常见开局走法，减少前期搜索时间
- 威胁空间搜索：优先搜索能形成威胁的走法，提升搜索效率
总结
四子连珠AI展示了经典博弈树搜索的应用。Minimax算法保证了对最优对手的必胜/必不败策略，Alpha-Beta剪枝在不改变结果的前提下大幅减少搜索量，而精心设计的评估函数则让AI在有限深度下表现出类人甚至超人的棋力。
