九子棋（Nine Men’s Morris）是一款源远流长的传统策略棋类游戏，棋盘由三个嵌套的正方形和连接它们的线段组成，共 24 个交叉点。游戏分为三个阶段：放子、走子和飞子，率先将对方棋子减少到仅剩 2 枚者获胜。九子棋的状态空间约为 10^10，完整的博弈树搜索不可行，需要结合阶段策略转换与启发式评估函数来指导 AI 决策。
一、游戏规则与棋盘表示
1.1 棋盘结构
九子棋棋盘可抽象为一个包含 24 个节点的图，每个节点编号为 0～23。节点之间的邻接关系构成棋盘上的合法移动路径。三层的节点分布如下：
– 外层：0, 1, 2, 3, 4, 5, 6, 7
– 中层：8, 9, 10, 11, 12, 13, 14, 15
– 内层：16, 17, 18, 19, 20, 21, 22, 23
每个节点与相邻节点之间有连线，同一层的节点按顺时针排列，层与层之间也有垂直连线。
1.2 游戏阶段
- 放子阶段：双方轮流将手中的 9 枚棋子放到空位上。若放子后形成三连（Mill），可提掉对方一枚非三连的棋子。
- 走子阶段：所有棋子放完后，双方轮流将一枚棋子沿连线移动到相邻空位。形成三连同样可提子。
- 飞子阶段：当一方棋子仅剩 3 枚时，其棋子可以飞到任意空位（不再受相邻限制）。
1.3 胜负判定
- 一方棋子数 ≤ 2：判负
- 一方无合法移动：判负
二、核心算法设计
2.1 三连（Mill）检测
三连指棋盘某条直线上同一方的 3 枚棋子。棋盘共有 16 条三连线，需要实时检测每次落子或移动后是否形成新的三连。
2.2 阶段感知评估函数
不同阶段的评估侧重点不同：
– 放子阶段：重视中心控制、三连威胁数、棋盘开放性
– 走子阶段：重视机动性（合法移动数）、三连威胁、棋子安全度
– 飞子阶段：重视三连威胁与棋子存活
综合评估函数：
score = w1 * (己方棋子数 - 对方棋子数)
+ w2 * (己方三连数 - 对方三连数)
+ w3 * (己方机动性 - 对方机动性)
+ w4 * (己方双连威胁 - 对方双连威胁)
2.3 带阶段剪枝的 Minimax
根据当前阶段动态调整搜索深度：放子阶段深度较浅（4 层），走子阶段中等（5-6 层），飞子阶段由于分支因子小可加深（7-8 层）。
三、Java 实现
import java.util.*;
/**
* 九子棋（Nine Men's Morris）AI 实现
* 核心算法：阶段感知 Minimax + 启发式评估
*/
public class NineMensMorris {
// 棋盘节点数
private static final int NUM_POSITIONS = 24;
// 每位玩家棋子数
private static final int PIECES_PER_PLAYER = 9;
// 棋盘：0=空, 1=玩家, -1=AI
private int[] board;
// 双方剩余未放置棋子
private int playerPiecesToPlace;
private int aiPiecesToPlace;
// 双方场上棋子数
private int playerPiecesOnBoard;
private int aiPiecesOnBoard;
// 当前回合玩家
private int currentPlayer;
// 邻接表：每个位置的相邻位置
private static final int[][] ADJACENT = {
{1, 9}, {0, 2, 4}, {1, 14}, // 0,1,2
{4, 10}, {1, 3, 5, 7}, {4, 13}, // 3,4,5
{7, 11}, {4, 6, 8}, {7, 12}, // 6,7,8
{0, 10, 21}, {3, 9, 11, 18}, {6, 10, 15}, // 9,10,11
{8, 13, 17}, {5, 12, 14, 20}, {2, 13, 23}, // 12,13,14
{11, 16}, {15, 17, 19}, {12, 16}, // 15,16,17
{10, 19}, {16, 18, 20, 22}, {13, 19}, // 18,19,20
{9, 22}, {19, 21, 23}, {14, 22} // 21,22,23
};
// 所有三连线（Mill）
private static final int[][] MILLS = {
{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, // 外层横线
{9, 10, 11}, {12, 13, 14}, {15, 16, 17}, // 中层横线
{18, 19, 20}, {21, 22, 23}, // 内层横线
{0, 9, 21}, {3, 10, 18}, {6, 11, 15}, // 左竖线
{1, 4, 7}, {16, 19, 22}, // 中竖线
{8, 12, 17}, {5, 13, 20}, {2, 14, 23} // 右竖线
};
public NineMensMorris() {
this.board = new int[NUM_POSITIONS];
this.playerPiecesToPlace = PIECES_PER_PLAYER;
this.aiPiecesToPlace = PIECES_PER_PLAYER;
this.playerPiecesOnBoard = 0;
this.aiPiecesOnBoard = 0;
this.currentPlayer = 1; // 玩家先手
}
/**
* 检查某位置是否属于三连线的一部分
*/
public boolean isPartOfMill(int pos, int player) {
for (int[] mill : MILLS) {
if (mill[0] == pos || mill[1] == pos || mill[2] == pos) {
if (board[mill[0]] == player && board[mill[1]] == player
&& board[mill[2]] == player) {
return true;
}
}
}
return false;
}
/**
* 检查某方是否形成新的三连（需要传入刚落子的位置）
*/
public boolean formsMill(int pos, int player) {
for (int[] mill : MILLS) {
boolean containsPos = false;
for (int p : mill) {
if (p == pos) containsPos = true;
}
if (containsPos) {
int count = 0;
for (int p : mill) {
if (board[p] == player) count++;
}
if (count == 3) return true;
}
}
return false;
}
/**
* 获取可以被提掉的对方棋子位置（非三连中的棋子）
*/
public List<Integer> getRemovablePieces(int opponent) {
List<Integer> removable = new ArrayList<>();
for (int i = 0; i < NUM_POSITIONS; i++) {
if (board[i] == opponent && !isPartOfMill(i, opponent)) {
removable.add(i);
}
}
// 如果对方所有棋子都在三连中，则可以提任意棋子
if (removable.isEmpty()) {
for (int i = 0; i < NUM_POSITIONS; i++) {
if (board[i] == opponent) {
removable.add(i);
}
}
}
return removable;
}
/**
* 判断当前处于哪个游戏阶段
* 0=放子, 1=走子, 2=飞子
*/
public int getPhase(int player) {
int piecesToPlace = (player == 1) ? playerPiecesToPlace : aiPiecesToPlace;
int piecesOnBoard = (player == 1) ? playerPiecesOnBoard : aiPiecesOnBoard;
if (piecesToPlace > 0) return 0;
if (piecesOnBoard > 3) return 1;
return 2;
}
/**
* 获取某方所有合法移动
*/
public List<Move> getLegalMoves(int player) {
List<Move> moves = new ArrayList<>();
int phase = getPhase(player);
if (phase == 0) {
// 放子阶段：放到任意空位
for (int i = 0; i < NUM_POSITIONS; i++) {
if (board[i] == 0) {
moves.add(new Move(-1, i, -1)); // from=-1 表示放子
}
}
} else if (phase == 1) {
// 走子阶段：沿邻接线移动
for (int from = 0; from < NUM_POSITIONS; from++) {
if (board[from] == player) {
for (int to : ADJACENT[from]) {
if (board[to] == 0) {
moves.add(new Move(from, to, -1));
}
}
}
}
} else {
// 飞子阶段：飞到任意空位
for (int from = 0; from < NUM_POSITIONS; from++) {
if (board[from] == player) {
for (int to = 0; to < NUM_POSITIONS; to++) {
if (board[to] == 0) {
moves.add(new Move(from, to, -1));
}
}
}
}
}
return moves;
}
/**
* 局面评估函数（阶段感知）
*/
public int evaluate() {
// 胜负判定
if (playerPiecesOnBoard + playerPiecesToPlace <= 2) return -10000;
if (aiPiecesOnBoard + aiPiecesToPlace <= 2) return 10000;
int score = 0;
// 1. 棋子数量差（权重最高）
score += 100 * (playerPiecesOnBoard - aiPiecesOnBoard);
// 2. 三连（Mill）数量差
int playerMills = countMills(1);
int aiMills = countMills(-1);
score += 50 * (playerMills - aiMills);
// 3. 双连威胁（两个己方棋子加一空位）
int playerThreats = countTwoPieceThreats(1);
int aiThreats = countTwoPieceThreats(-1);
score += 30 * (playerThreats - aiThreats);
// 4. 机动性（合法移动数）- 仅在走子/飞子阶段有意义
if (playerPiecesToPlace == 0 && aiPiecesToPlace == 0) {
int playerMobility = getLegalMoves(1).size();
int aiMobility = getLegalMoves(-1).size();
score += 10 * (playerMobility - aiMobility);
}
return score;
}
private int countMills(int player) {
int count = 0;
for (int[] mill : MILLS) {
if (board[mill[0]] == player && board[mill[1]] == player
&& board[mill[2]] == player) {
count++;
}
}
return count;
}
private int countTwoPieceThreats(int player) {
int count = 0;
for (int[] mill : MILLS) {
int playerCount = 0;
int emptyCount = 0;
for (int pos : mill) {
if (board[pos] == player) playerCount++;
else if (board[pos] == 0) emptyCount++;
}
if (playerCount == 2 && emptyCount == 1) count++;
}
return count;
}
/**
* 执行移动并返回是否形成三连
*/
public boolean executeMove(Move move, int player) {
if (move.from == -1) {
// 放子
board[move.to] = player;
if (player == 1) {
playerPiecesToPlace--;
playerPiecesOnBoard++;
} else {
aiPiecesToPlace--;
aiPiecesOnBoard++;
}
} else {
// 走子或飞子
board[move.from] = 0;
board[move.to] = player;
}
return formsMill(move.to, player);
}
/**
* 撤销移动
*/
public void undoMove(Move move, int player, boolean wasMill, int removedPos) {
if (removedPos != -1) {
board[removedPos] = -player;
if (-player == 1) {
playerPiecesOnBoard++;
} else {
aiPiecesOnBoard++;
}
}
if (move.from == -1) {
board[move.to] = 0;
if (player == 1) {
playerPiecesToPlace++;
playerPiecesOnBoard--;
} else {
aiPiecesToPlace++;
aiPiecesOnBoard--;
}
} else {
board[move.to] = 0;
board[move.from] = player;
}
}
/**
* Minimax 搜索（支持三连提子）
*/
public int minimax(int depth, int alpha, int beta, boolean isMaximizing) {
int score = evaluate();
if (Math.abs(score) >= 10000 || depth == 0) {
return score;
}
int player = isMaximizing ? 1 : -1;
List<Move> moves = getLegalMoves(player);
if (moves.isEmpty()) {
return isMaximizing ? -10000 : 10000;
}
if (isMaximizing) {
int maxEval = Integer.MIN_VALUE;
for (Move move : moves) {
boolean formedMill = executeMove(move, player);
if (formedMill) {
// 形成三连，需要提子
List<Integer> removable = getRemovablePieces(-player);
for (int rem : removable) {
board[rem] = 0;
if (-player == 1) playerPiecesOnBoard--;
else aiPiecesOnBoard--;
int eval = minimax(depth - 1, alpha, beta, false);
board[rem] = -player;
if (-player == 1) playerPiecesOnBoard++;
else aiPiecesOnBoard++;
maxEval = Math.max(maxEval, eval);
alpha = Math.max(alpha, eval);
if (beta <= alpha) break;
}
} else {
int eval = minimax(depth - 1, alpha, beta, false);
maxEval = Math.max(maxEval, eval);
alpha = Math.max(alpha, eval);
}
undoMove(move, player, formedMill, -1);
if (beta <= alpha) break;
}
return maxEval;
} else {
int minEval = Integer.MAX_VALUE;
for (Move move : moves) {
boolean formedMill = executeMove(move, player);
if (formedMill) {
List<Integer> removable = getRemovablePieces(-player);
for (int rem : removable) {
board[rem] = 0;
if (-player == 1) playerPiecesOnBoard--;
else aiPiecesOnBoard--;
int eval = minimax(depth - 1, alpha, beta, true);
board[rem] = -player;
if (-player == 1) playerPiecesOnBoard++;
else aiPiecesOnBoard++;
minEval = Math.min(minEval, eval);
beta = Math.min(beta, eval);
if (beta <= alpha) break;
}
} else {
int eval = minimax(depth - 1, alpha, beta, true);
minEval = Math.min(minEval, eval);
beta = Math.min(beta, eval);
}
undoMove(move, player, formedMill, -1);
if (beta <= alpha) break;
}
return minEval;
}
}
/**
* AI 寻找最佳移动
*/
public Move findBestMove(int searchDepth) {
int bestScore = Integer.MAX_VALUE;
Move bestMove = null;
List<Move> moves = getLegalMoves(-1);
for (Move move : moves) {
boolean formedMill = executeMove(move, -1);
int score;
if (formedMill) {
List<Integer> removable = getRemovablePieces(1);
int worstScore = Integer.MAX_VALUE;
for (int rem : removable) {
board[rem] = 0;
playerPiecesOnBoard--;
int eval = minimax(searchDepth - 1, Integer.MIN_VALUE, Integer.MAX_VALUE, true);
worstScore = Math.min(worstScore, eval);
board[rem] = 1;
playerPiecesOnBoard++;
}
score = worstScore;
} else {
score = minimax(searchDepth - 1, Integer.MIN_VALUE, Integer.MAX_VALUE, true);
}
undoMove(move, -1, formedMill, -1);
if (score < bestScore) {
bestScore = score;
bestMove = move;
}
}
return bestMove;
}
/**
* 打印棋盘状态
*/
public void printBoard() {
String[] p = new String[NUM_POSITIONS];
for (int i = 0; i < NUM_POSITIONS; i++) {
p[i] = board[i] == 1 ? "X" : board[i] == -1 ? "O" : String.valueOf(i % 10);
}
System.out.println(p[0] + "--------" + p[1] + "--------" + p[2]);
System.out.println("| | |");
System.out.println("| " + p[8] + "-----" + p[9] + "-----" + p[10] + " |");
System.out.println("| | | | |");
System.out.println("| | " + p[16] + "--" + p[17] + "--" + p[18] + " | |");
System.out.println(p[7] + "--" + p[15] + "-" + p[23] + " " + p[19] + "-" + p[11] + "--" + p[3]);
System.out.println("| | " + p[22] + "--" + p[21] + "--" + p[20] + " | |");
System.out.println("| | | | |");
System.out.println("| " + p[14] + "-----" + p[13] + "-----" + p[12] + " |");
System.out.println("| | |");
System.out.println(p[6] + "--------" + p[5] + "--------" + p[4]);
System.out.println("Player pieces: onBoard=" + playerPiecesOnBoard + ", toPlace=" + playerPiecesToPlace);
System.out.println("AI pieces: onBoard=" + aiPiecesOnBoard + ", toPlace=" + aiPiecesToPlace);
}
/**
* 移动类
*/
static class Move {
int from, to, remove;
Move(int from, int to, int remove) {
this.from = from;
this.to = to;
this.remove = remove;
}
@Override
public String toString() {
if (from == -1) return "Place at " + to;
return "Move " + from + " -> " + to;
}
}
public static void main(String[] args) {
NineMensMorris game = new NineMensMorris();
game.printBoard();
// 演示：AI 走一步
Move aiMove = game.findBestMove(3);
System.out.println("\nAI best move: " + aiMove);
boolean mill = game.executeMove(aiMove, -1);
if (mill) {
List<Integer> rem = game.getRemovablePieces(1);
if (!rem.isEmpty()) {
game.board[rem.get(0)] = 0;
game.playerPiecesOnBoard--;
System.out.println("AI removes piece at " + rem.get(0));
}
}
game.printBoard();
}
}
四、算法复杂度分析
| 阶段 | 分支因子 | 建议搜索深度 | 说明 |
|---|---|---|---|
| 放子 | 20～24 | 3-4 | 空位多，分支大 |
| 走子 | 3～10 | 5-6 | 棋子受限，分支中等 |
| 飞子 | 20～22 | 6-8 | 仅3枚棋子，飞任意位置 |
在放子阶段早期，Alpha-Beta 剪枝效果有限；进入走子阶段后，由于合法移动显著减少，剪枝效率大幅提升，搜索深度可等效提升 1～2 层。
五、总结
九子棋的魅力在于其分阶段的游戏机制，使得单一策略无法通吃全局。本文通过阶段感知的评估函数动态调整 AI 的决策侧重点，结合 Minimax 与 Alpha-Beta 剪枝实现了能够在各个阶段做出合理决策的 AI 对手。读者可以从中学习到图结构棋盘表示、阶段状态机设计以及复杂博弈场景下的启发式评估方法。
