黑白棋（Reversi / Othello）是一款经典的二人零和博弈棋盘游戏，双方在8×8的棋盘上轮流落子，夹住对方棋子的直线（横、竖、斜）上的所有对方棋子将翻转为己方颜色。本文用Java实现一个带AI的黑白棋游戏，核心讲解Minimax博弈树搜索、Alpha-Beta剪枝优化，以及多维度启发式局面评估函数的设计。
博弈树搜索框架
黑白棋的AI决策采用深度优先的Minimax搜索：
– Max节点：AI试图最大化自己的评估值
– Min节点：对手试图最小化AI的评估值（即最大化自己的得分）
– Alpha-Beta剪枝：维护[alpha, beta]窗口，当某分支的值超出窗口时立即停止搜索该分支
启发式评估函数
黑白棋中棋子数不等于优势（角落被占后大量翻转常见），因此评估函数需综合多个维度：
- 棋子权重表：角落和边缘位置价值远高于中心，角落为最高价值（约+100），边缘次之，中心附近为负分。
- 行动力（Mobility）：可落子位置越多，选择空间越大，通常赋予正权重。
- 稳定子（Stable Discs）：无法被翻转的棋子，尤其是角落及其延伸线上的棋子。
- ** frontier（前沿子）**：与空格相邻的棋子容易被翻转，应尽量减少。
Java 实现
import java.util.*;
public class ReversiAI {
static final int SIZE = 8;
static final int EMPTY = 0, BLACK = 1, WHITE = 2;
static final int[] DX = {-1,-1,-1,0,0,1,1,1};
static final int[] DY = {-1,0,1,-1,1,-1,0,1};
// 位置权重表：角落最高，边缘次之，中心附近为负
static final int[][] POSITION_WEIGHT = {
{100, -20, 10, 5, 5, 10, -20, 100},
{-20, -30, -5, -5, -5, -5, -30, -20},
{ 10, -5, 10, 2, 2, 10, -5, 10},
{ 5, -5, 2, 0, 0, 2, -5, 5},
{ 5, -5, 2, 0, 0, 2, -5, 5},
{ 10, -5, 10, 2, 2, 10, -5, 10},
{-20, -30, -5, -5, -5, -5, -30, -20},
{100, -20, 10, 5, 5, 10, -20, 100}
};
int[][] board = new int[SIZE][SIZE];
int currentPlayer = BLACK;
public ReversiAI() {
// 初始布局
board[3][3] = board[4][4] = WHITE;
board[3][4] = board[4][3] = BLACK;
}
// 判断落子是否合法，返回可翻转的坐标列表
public List<int[]> getFlips(int x, int y, int player) {
List<int[]> flips = new ArrayList<>();
if (x < 0 || x >= SIZE || y < 0 || y >= SIZE || board[x][y] != EMPTY) return flips;
int opponent = 3 - player;
for (int d = 0; d < 8; d++) {
List<int[]> line = new ArrayList<>();
int nx = x + DX[d], ny = y + DY[d];
while (nx >= 0 && nx < SIZE && ny >= 0 && ny < SIZE && board[nx][ny] == opponent) {
line.add(new int[]{nx, ny});
nx += DX[d]; ny += DY[d];
}
if (!line.isEmpty() && nx >= 0 && nx < SIZE && ny >= 0 && ny < SIZE && board[nx][ny] == player) {
flips.addAll(line);
}
}
return flips;
}
public List<int[]> getValidMoves(int player) {
List<int[]> moves = new ArrayList<>();
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
if (!getFlips(i, j, player).isEmpty())
moves.add(new int[]{i, j});
return moves;
}
public void makeMove(int x, int y, int player) {
List<int[]> flips = getFlips(x, y, player);
board[x][y] = player;
for (int[] f : flips) board[f[0]][f[1]] = player;
}
// 多维度启发式评估函数
public int evaluate(int player) {
int score = 0;
int myFrontiers = 0, oppFrontiers = 0;
int myMoves = getValidMoves(player).size();
int oppMoves = getValidMoves(3 - player).size();
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (board[i][j] == player) {
score += POSITION_WEIGHT[i][j];
} else if (board[i][j] == 3 - player) {
score -= POSITION_WEIGHT[i][j];
}
// 前沿子统计
if (board[i][j] != EMPTY) {
boolean isFrontier = false;
for (int d = 0; d < 8 && !isFrontier; d++) {
int ni = i + DX[d], nj = j + DY[d];
if (ni >= 0 && ni < SIZE && nj >= 0 && nj < SIZE && board[ni][nj] == EMPTY)
isFrontier = true;
}
if (isFrontier) {
if (board[i][j] == player) myFrontiers++;
else oppFrontiers++;
}
}
}
}
// 加权组合
score += (myMoves - oppMoves) * 5; // 行动力差异
score -= (myFrontiers - oppFrontiers) * 3; // 前沿子差异（负权重）
return score;
}
// Alpha-Beta剪枝的Minimax搜索
public int[] minimax(int depth, int player, int alpha, int beta, boolean maximizing) {
List<int[]> moves = getValidMoves(player);
// 游戏结束或无合法移动时进行终局评估
if (depth == 0 || moves.isEmpty()) {
int eval = evaluate(BLACK); // 始终从BLACK视角评估
return new int[]{-1, -1, eval};
}
int bestX = moves.get(0)[0], bestY = moves.get(0)[1];
if (maximizing) {
int maxEval = Integer.MIN_VALUE;
for (int[] move : moves) {
int[][] saved = saveBoard();
makeMove(move[0], move[1], player);
int eval = minimax(depth - 1, 3 - player, alpha, beta, false)[2];
restoreBoard(saved);
if (eval > maxEval) {
maxEval = eval;
bestX = move[0]; bestY = move[1];
}
alpha = Math.max(alpha, eval);
if (beta <= alpha) break; // Beta剪枝
}
return new int[]{bestX, bestY, maxEval};
} else {
int minEval = Integer.MAX_VALUE;
for (int[] move : moves) {
int[][] saved = saveBoard();
makeMove(move[0], move[1], player);
int eval = minimax(depth - 1, 3 - player, alpha, beta, true)[2];
restoreBoard(saved);
if (eval < minEval) {
minEval = eval;
bestX = move[0]; bestY = move[1];
}
beta = Math.min(beta, eval);
if (beta <= alpha) break; // Alpha剪枝
}
return new int[]{bestX, bestY, minEval};
}
}
// 排序优化：优先搜索高价值位置（提升剪枝效率）
public int[] minimaxSorted(int depth, int player, int alpha, int beta, boolean maximizing) {
List<int[]> moves = getValidMoves(player);
if (depth == 0 || moves.isEmpty()) {
return new int[]{-1, -1, evaluate(BLACK)};
}
// 按位置权重排序
moves.sort((a, b) -> Integer.compare(POSITION_WEIGHT[b[0]][b[1]], POSITION_WEIGHT[a[0]][a[1]]));
return minimaxHelper(moves, depth, player, alpha, beta, maximizing);
}
private int[] minimaxHelper(List<int[]> moves, int depth, int player, int alpha, int beta, boolean maximizing) {
int bestX = moves.get(0)[0], bestY = moves.get(0)[1];
if (maximizing) {
int maxEval = Integer.MIN_VALUE;
for (int[] move : moves) {
int[][] saved = saveBoard();
makeMove(move[0], move[1], player);
int eval = minimax(depth - 1, 3 - player, alpha, beta, false)[2];
restoreBoard(saved);
if (eval > maxEval) { maxEval = eval; bestX = move[0]; bestY = move[1]; }
alpha = Math.max(alpha, eval);
if (beta <= alpha) break;
}
return new int[]{bestX, bestY, maxEval};
} else {
int minEval = Integer.MAX_VALUE;
for (int[] move : moves) {
int[][] saved = saveBoard();
makeMove(move[0], move[1], player);
int eval = minimax(depth - 1, 3 - player, alpha, beta, true)[2];
restoreBoard(saved);
if (eval < minEval) { minEval = eval; bestX = move[0]; bestY = move[1]; }
beta = Math.min(beta, eval);
if (beta <= alpha) break;
}
return new int[]{bestX, bestY, minEval};
}
}
private int[][] saveBoard() {
int[][] copy = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) copy[i] = board[i].clone();
return copy;
}
private void restoreBoard(int[][] saved) {
for (int i = 0; i < SIZE; i++) board[i] = saved[i].clone();
}
public void printBoard() {
System.out.println(" 0 1 2 3 4 5 6 7");
for (int i = 0; i < SIZE; i++) {
System.out.print(i + " ");
for (int j = 0; j < SIZE; j++) {
char c = board[i][j] == EMPTY ? '.' : (board[i][j] == BLACK ? 'X' : 'O');
System.out.print(c + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
ReversiAI game = new ReversiAI();
game.printBoard();
// AI执黑，深度6搜索
int[] move = game.minimaxSorted(6, BLACK, Integer.MIN_VALUE, Integer.MAX_VALUE, true);
System.out.println("\nAI suggests: (" + move[0] + "," + move[1] + ") eval=" + move[2]);
game.makeMove(move[0], move[1], BLACK);
game.printBoard();
}
}
复杂度分析
- 时间复杂度：Minimax搜索为O(b^d)，b为分支因子（平均约8-10），d为搜索深度。Alpha-Beta剪枝在最优排序下可将复杂度降至O(b^(d/2))。深度6的搜索在实际运行中完全可接受。
- 空间复杂度：O(d×SIZE²)用于递归栈和棋盘状态保存。
评估策略对比
| 评估维度 | 早期权重 | 晚期权重 | 说明 |
|---|---|---|---|
| 位置权重 | 高 | 极高 | 始终核心 |
| 行动力 | 高 | 低 | 开局重要 |
| 前沿子 | 中 | 低 | 避免被翻转 |
| 棋子数 | 忽略 | 极高 | 终局唯一标准 |
实战中通常根据剩余空格数动态调整权重：前30步重视位置和行动力，后34步逐渐转向稳定子和棋子数统计。深度搜索配合优质评估函数，AI可达到人类高手水平。
