三维井字棋（3D Tic-Tac-Toe）是经典井字棋的三维扩展，玩家在一个 3×3×3 的立方体空间内轮流落子，率先在任意直线（水平、垂直、纵深或对角线）上连成三子者获胜。相比二维版本，三维棋盘提供了 49 条可能的获胜直线，状态空间复杂度大幅提升，使得简单的穷举难以应对，必须借助博弈树搜索与剪枝算法。
一、游戏规则与状态表示
三维井字棋使用 3×3×3 的立体棋盘，坐标用 (x, y, z) 表示，其中 x, y, z ∈ {0, 1, 2}。获胜条件为在以下任意方向的直线上占据三个连续位置：
– 轴向直线：沿 X、Y、Z 三个坐标轴方向，共 27 条
– 平面对角线：每个 3×3 平面内的对角线，共 18 条
– 体对角线：贯穿立方体的空间对角线，共 4 条
棋盘状态用一个三维整型数组 board[3][3][3] 表示，0 为空，1 为玩家（Max），-1 为 AI（Min）。
二、核心算法：Minimax 与 Alpha-Beta 剪枝
Minimax 算法通过递归模拟双方的最优走法来评估当前局面的价值。在三维井字棋中，由于分支因子约为 20～25，纯 Minimax 在深度较大时效率低下，因此引入 Alpha-Beta 剪枝来剔除不可能影响最终决策的子树。
2.1 局面评估函数
评估函数是 AI 决策质量的关键。我们对每条获胜直线进行评分：
– 若一条直线上有 3 个己方棋子：+10000
– 若一条直线上有 2 个己方棋子且 1 个空位：+100
– 若一条直线上有 1 个己方棋子且 2 个空位：+10
– 若一条直线上有 2 个对方棋子且 1 个空位：-500（必须阻挡）
2.2 Alpha-Beta 剪枝
在递归搜索过程中维护两个值：
– alpha：Max 玩家（玩家）能保证的最小得分下界
– beta：Min 玩家（AI）能保证的最大得分上界
当 alpha >= beta 时，当前分支可以被剪枝，无需继续搜索。
三、Java 实现
import java.util.ArrayList;
import java.util.List;
/**
* 三维井字棋 - 3D Tic-Tac-Toe
* 核心算法：Minimax + Alpha-Beta 剪枝
*/
public class TicTacToe3D {
// 棋盘大小
private static final int SIZE = 3;
// 玩家棋子（Max）
private static final int PLAYER = 1;
// AI 棋子（Min）
private static final int AI = -1;
// 空位
private static final int EMPTY = 0;
// 所有可能的获胜直线（坐标三元组列表）
private static final int[][][] LINES = generateLines();
private int[][][] board;
public TicTacToe3D() {
this.board = new int[SIZE][SIZE][SIZE];
}
/**
* 生成所有49条获胜直线
* 包括：轴向(27) + 平面对角线(18) + 体对角线(4)
*/
private static int[][][] generateLines() {
List<int[][]> lines = new ArrayList<>();
// 1. 轴向直线（沿x, y, z轴）
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
// 沿x轴
lines.add(new int[][]{{0,i,j}, {1,i,j}, {2,i,j}});
// 沿y轴
lines.add(new int[][]{{i,0,j}, {i,1,j}, {i,2,j}});
// 沿z轴
lines.add(new int[][]{{i,j,0}, {i,j,1}, {i,j,2}});
}
}
// 2. 平面对角线（xy, xz, yz平面）
for (int k = 0; k < SIZE; k++) {
// xy平面对角线
lines.add(new int[][]{{0,0,k}, {1,1,k}, {2,2,k}});
lines.add(new int[][]{{0,2,k}, {1,1,k}, {2,0,k}});
// xz平面对角线
lines.add(new int[][]{{0,k,0}, {1,k,1}, {2,k,2}});
lines.add(new int[][]{{0,k,2}, {1,k,1}, {2,k,0}});
// yz平面对角线
lines.add(new int[][]{{k,0,0}, {k,1,1}, {k,2,2}});
lines.add(new int[][]{{k,0,2}, {k,1,1}, {k,2,0}});
}
// 3. 体对角线（贯穿整个立方体）
lines.add(new int[][]{{0,0,0}, {1,1,1}, {2,2,2}});
lines.add(new int[][]{{0,0,2}, {1,1,1}, {2,2,0}});
lines.add(new int[][]{{0,2,0}, {1,1,1}, {2,0,2}});
lines.add(new int[][]{{0,2,2}, {1,1,1}, {2,0,0}});
return lines.toArray(new int[lines.size()][][]);
}
/**
* 检查指定玩家是否获胜
*/
public boolean checkWin(int player) {
for (int[][] line : LINES) {
int count = 0;
for (int[] pos : line) {
if (board[pos[0]][pos[1]][pos[2]] == player) {
count++;
}
}
if (count == SIZE) {
return true;
}
}
return false;
}
/**
* 检查棋盘是否已满
*/
public boolean isFull() {
for (int x = 0; x < SIZE; x++) {
for (int y = 0; y < SIZE; y++) {
for (int z = 0; z < SIZE; z++) {
if (board[x][y][z] == EMPTY) {
return false;
}
}
}
}
return true;
}
/**
* 获取所有空位坐标
*/
public List<int[]> getEmptyCells() {
List<int[]> empties = new ArrayList<>();
for (int x = 0; x < SIZE; x++) {
for (int y = 0; y < SIZE; y++) {
for (int z = 0; z < SIZE; z++) {
if (board[x][y][z] == EMPTY) {
empties.add(new int[]{x, y, z});
}
}
}
}
return empties;
}
/**
* 局面评估函数：对当前棋盘状态打分
* 正值有利于玩家，负值有利于AI
*/
public int evaluate() {
if (checkWin(PLAYER)) return 10000;
if (checkWin(AI)) return -10000;
int score = 0;
for (int[][] line : LINES) {
int playerCount = 0;
int aiCount = 0;
int emptyCount = 0;
for (int[] pos : line) {
int cell = board[pos[0]][pos[1]][pos[2]];
if (cell == PLAYER) playerCount++;
else if (cell == AI) aiCount++;
else emptyCount++;
}
// 评分逻辑
if (playerCount > 0 && aiCount > 0) continue; // 双方都有子，无法成线
if (playerCount == 2 && emptyCount == 1) score += 100;
else if (playerCount == 1 && emptyCount == 2) score += 10;
else if (aiCount == 2 && emptyCount == 1) score -= 500; // 必须阻挡
else if (aiCount == 1 && emptyCount == 2) score -= 10;
}
return score;
}
/**
* Minimax + Alpha-Beta 剪枝
* @param depth 当前搜索深度
* @param alpha Max玩家的下界
* @param beta Min玩家的上界
* @param isMaximizing 当前是否为Max玩家回合
* @return 当前局面的评估值
*/
public int minimax(int depth, int alpha, int beta, boolean isMaximizing) {
int score = evaluate();
// 终止条件：某方获胜、棋盘已满或达到最大深度
if (Math.abs(score) == 10000 || isFull() || depth == 0) {
return score;
}
List<int[]> empties = getEmptyCells();
if (isMaximizing) {
int maxEval = Integer.MIN_VALUE;
for (int[] pos : empties) {
board[pos[0]][pos[1]][pos[2]] = PLAYER;
int eval = minimax(depth - 1, alpha, beta, false);
board[pos[0]][pos[1]][pos[2]] = 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[] pos : empties) {
board[pos[0]][pos[1]][pos[2]] = AI;
int eval = minimax(depth - 1, alpha, beta, true);
board[pos[0]][pos[1]][pos[2]] = EMPTY;
minEval = Math.min(minEval, eval);
beta = Math.min(beta, eval);
if (beta <= alpha) break; // Alpha剪枝
}
return minEval;
}
}
/**
* AI 寻找最佳落子位置
* @param searchDepth 搜索深度（建议 4-6）
* @return 最佳落子坐标 [x, y, z]
*/
public int[] findBestMove(int searchDepth) {
int bestScore = Integer.MAX_VALUE;
int[] bestMove = null;
List<int[]> empties = getEmptyCells();
for (int[] pos : empties) {
board[pos[0]][pos[1]][pos[2]] = AI;
int score = minimax(searchDepth - 1, Integer.MIN_VALUE, Integer.MAX_VALUE, true);
board[pos[0]][pos[1]][pos[2]] = EMPTY;
if (score < bestScore) {
bestScore = score;
bestMove = pos.clone();
}
}
return bestMove;
}
/**
* 在指定位置落子
*/
public boolean makeMove(int x, int y, int z, int player) {
if (x < 0 || x >= SIZE || y < 0 || y >= SIZE || z < 0 || z >= SIZE) {
return false;
}
if (board[x][y][z] != EMPTY) {
return false;
}
board[x][y][z] = player;
return true;
}
/**
* 打印当前棋盘状态（按Z层展开）
*/
public void printBoard() {
for (int z = 0; z < SIZE; z++) {
System.out.println("Layer z=" + z + ":");
for (int y = 0; y < SIZE; y++) {
for (int x = 0; x < SIZE; x++) {
char c = board[x][y][z] == PLAYER ? 'X' :
board[x][y][z] == AI ? 'O' : '.';
System.out.print(c + " ");
}
System.out.println();
}
System.out.println();
}
}
/**
* 主程序：简单对局演示
*/
public static void main(String[] args) {
TicTacToe3D game = new TicTacToe3D();
// 玩家先手落子于中心
game.makeMove(1, 1, 1, PLAYER);
System.out.println("Player moves to (1,1,1)");
game.printBoard();
// AI 寻找最佳应对
int[] aiMove = game.findBestMove(4);
game.makeMove(aiMove[0], aiMove[1], aiMove[2], AI);
System.out.println("AI moves to (" + aiMove[0] + "," + aiMove[1] + "," + aiMove[2] + ")");
game.printBoard();
// 检查胜负
if (game.checkWin(AI)) {
System.out.println("AI wins!");
} else if (game.checkWin(PLAYER)) {
System.out.println("Player wins!");
} else {
System.out.println("Game continues...");
}
}
}
四、算法复杂度分析
三维井字棋的状态空间上限为 3^27 ≈ 7.6×10^12，但由于游戏通常在十几步内结束，实际搜索空间远小于此。
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(b^d) | b 为分支因子（约 20），d 为搜索深度 |
| Alpha-Beta 剪枝后 | O(b^(d/2)) | 理想排序下，搜索深度等效翻倍 |
| 空间复杂度 | O(d) | 递归栈深度，等于当前搜索深度 |
在深度为 4～6 的设置下，AI 能在毫秒级完成决策，同时保持较高的对局水平。
五、总结
三维井字棋将经典游戏升维，使得简单的规则枚举不再适用。通过 Minimax 算法模拟双方最优策略，并借助 Alpha-Beta 剪枝将搜索效率提升数个数量级，AI 能够在复杂的立体空间中找到精妙的三子连线。读者通过本文可以掌握三维状态表示、博弈树搜索以及启发式评估函数的设计方法，这些技术同样适用于五子棋、象棋等更复杂的博弈场景。
