黑白棋（Reversi / Othello）是一款经典的8×8双人策略棋盘游戏，由英国人在19世纪末发明。其规则简洁但策略深远：双方轮流落子，每次必须至少翻转对方一枚棋子，最终棋多者胜。正因为状态空间庞大且决策深度要求高，黑白棋成为检验博弈算法的绝佳实验场。
本文将用Java从零实现一个完整的黑白棋AI，核心讲解Minimax算法构建博弈树、Alpha-Beta剪枝砍掉无效分支，以及多维度估值函数对棋局进行量化评估。最终代码可直接运行，支持与AI进行人机对战。
一、黑白棋核心规则
黑白棋在8×8棋盘上进行，初始状态为中央四格呈”十”字交替排列（两黑两白）。
1.1 落子规则
- 落子位置必须与对方棋子相邻，且在该方向（横、竖、斜）上形成”己方—连续对方—己方”的夹吃结构。
- 落子后，被夹住的所有对方棋子翻转为我方颜色。
- 如果一方无合法落子位置，则轮空，由对方继续落子。
- 双方均无合法落子时，游戏结束，棋盘上棋子多者获胜。
1.2 策略深度
- 完整博弈树的节点数约为10^28，无法穷举。
- 实际对局中，前20步的分支因子约8~12，后40步逐渐减少。
- 因此需要借助搜索算法+估值函数来在有限深度内做出近似最优决策。
二、Minimax算法：在博弈树中寻找最优解
Minimax算法假设对手永远会采取对我方最不利的行动，因此我方在最大化自己收益的同时，也要考虑对手会最小化我方收益。
2.1 核心思想
- MAX节点（我方回合）：选择子节点中的最大得分。
- MIN节点（对方回合）：选择子节点中的最小得分。
- 递归搜索直到达到预设深度，此时用估值函数评估当前局面。
2.2 伪代码
function minimax(board, depth, isMaximizing):
if depth == 0 or gameOver:
return evaluate(board)
if isMaximizing:
maxEval = -infinity
for each move in legalMoves:
eval = minimax(board.after(move), depth-1, false)
maxEval = max(maxEval, eval)
return maxEval
else:
minEval = +infinity
for each move in legalMoves:
eval = minimax(board.after(move), depth-1, true)
minEval = min(minEval, eval)
return minEval
2.3 复杂度问题
- 若平均分支因子为b，搜索深度为d，则时间复杂度为O(b^d)。
- 以b=10、d=6为例，需要搜索约10^6个节点，在Java中尚可接受；但d=8时达到10^8，明显过慢。
- Alpha-Beta剪枝是解决这一问题的关键优化。
三、Alpha-Beta剪枝：砍掉不必探索的分支
Alpha-Beta剪枝在Minimax的基础上引入两个边界值：
– α（Alpha）：MAX节点目前已知的最好得分下界，只会增大。
– β（Beta）：MIN节点目前已知的最好得分上界，只会减小。
3.1 剪枝条件
- 在MAX节点，若某个子节点的返回值≥β，说明对手（MIN层）绝不会允许到达该节点，直接剪枝。
- 在MIN节点，若某个子节点的返回值≤α，说明我方（MAX层）已有更好的选择，直接剪枝。
3.2 伪代码
function alphabeta(board, depth, alpha, beta, isMaximizing):
if depth == 0 or gameOver:
return evaluate(board)
if isMaximizing:
for each move in legalMoves:
eval = alphabeta(board.after(move), depth-1, alpha, beta, false)
alpha = max(alpha, eval)
if beta <= alpha:
break // Beta剪枝
return alpha
else:
for each move in legalMoves:
eval = alphabeta(board.after(move), depth-1, alpha, beta, true)
beta = min(beta, eval)
if beta <= alpha:
break // Alpha剪枝
return beta
3.3 剪枝效果
- 理想情况下（ moves按好坏排序），复杂度可降至O(b^(d/2))。
- 实际中即使随机排序，也能剪掉30%~50%的分支。
四、估值函数：量化棋局优劣
估值函数是AI的”棋感”来源，决定了在无法搜到终局时的判断质量。黑白棋的估值通常包含以下维度：
4.1 棋子数（Disc Count）
- 直接统计双方棋子数量差。
- 权重：前期低（甚至为负，鼓励少子以保留行动力），后期高。
4.2 行动力（Mobility）
- 统计双方合法落子位置数量差。
- 行动力高意味着选择多，对方选择少。这是中前期最重要的指标。
4.3 角落控制（Corner Control）
- 角落棋子永远不会被翻转，是”稳定子”的源头。
- 占据角落可获得大量稳定子，权重极高。
4.4 稳定子（Stable Discs）
- 无论如何后续落子都不会被翻转的棋子。
- 通常位于边缘、角落附近，计算较复杂，可用近似估计。
4.5 前沿子（Frontier Discs）
- 与空格相邻的棋子数量。前沿子少意味着棋子更”紧凑”，不易被翻转。
4.6 位置权重表（Positional Weights）
- 根据棋盘位置预先设定权重，例如角落为正、C位（角落邻位）为负、边缘为正。
五、Java完整实现
以下代码实现了完整的黑白棋游戏，包含棋盘管理、合法落子判定、翻转逻辑、Minimax+Alpha-Beta剪枝AI，以及命令行人机对战界面。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* 黑白棋（Reversi）完整实现
* 包含：棋盘逻辑、合法落子判定、翻转规则、Minimax+Alpha-Beta剪枝AI
*/
public class Reversi {
// 棋盘大小
private static final int SIZE = 8;
// 方向向量：8个方向（横、竖、斜）
private static final int[][] DIRECTIONS = {
{-1, -1}, {-1, 0}, {-1, 1},
{ 0, -1}, { 0, 1},
{ 1, -1}, { 1, 0}, { 1, 1}
};
// 棋子颜色
private static final int EMPTY = 0;
private static final int BLACK = 1;
private static final int WHITE = 2;
// 位置权重表（基于经验与棋谱统计）
// 角落=100, 边缘=10, C位=-25, X位=-25, 中心=0
private 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}
};
// AI搜索深度
private static final int SEARCH_DEPTH = 6;
private int[][] board;
private int currentPlayer;
public Reversi() {
board = new int[SIZE][SIZE];
// 初始棋盘：中央四子
board[3][3] = WHITE;
board[3][4] = BLACK;
board[4][3] = BLACK;
board[4][4] = WHITE;
currentPlayer = BLACK; // 黑方先行
}
/**
* 检查在(row, col)落子是否合法
* 必须至少在一个方向上能翻转对方棋子
*/
public boolean isValidMove(int row, int col, int player) {
if (row < 0 || row >= SIZE || col < 0 || col >= SIZE || board[row][col] != EMPTY) {
return false;
}
for (int[] dir : DIRECTIONS) {
if (getFlips(row, col, player, dir).size() > 0) {
return true;
}
}
return false;
}
/**
* 获取某一方向上能翻转的对方棋子坐标列表
*/
private List<int[]> getFlips(int row, int col, int player, int[] dir) {
List<int[]> flips = new ArrayList<>();
int opponent = (player == BLACK) ? WHITE : BLACK;
int r = row + dir[0];
int c = col + dir[1];
// 先遇到连续的对方棋子
while (r >= 0 && r < SIZE && c >= 0 && c < SIZE && board[r][c] == opponent) {
flips.add(new int[]{r, c});
r += dir[0];
c += dir[1];
}
// 最后必须以己方棋子结尾，否则不合法
if (r >= 0 && r < SIZE && c >= 0 && c < SIZE && board[r][c] == player && flips.size() > 0) {
return flips;
}
return new ArrayList<>();
}
/**
* 获取当前玩家的所有合法落子位置
*/
public List<int[]> getLegalMoves(int player) {
List<int[]> moves = new ArrayList<>();
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (isValidMove(i, j, player)) {
moves.add(new int[]{i, j});
}
}
}
return moves;
}
/**
* 执行落子，返回是否成功
*/
public boolean makeMove(int row, int col, int player) {
if (!isValidMove(row, col, player)) {
return false;
}
board[row][col] = player;
for (int[] dir : DIRECTIONS) {
for (int[] flip : getFlips(row, col, player, dir)) {
board[flip[0]][flip[1]] = player;
}
}
return true;
}
/**
* 复制当前棋盘状态
*/
public Reversi copy() {
Reversi copy = new Reversi();
for (int i = 0; i < SIZE; i++) {
System.arraycopy(this.board[i], 0, copy.board[i], 0, SIZE);
}
copy.currentPlayer = this.currentPlayer;
return copy;
}
/**
* 统计棋子数量
*/
public int countDiscs(int player) {
int count = 0;
for (int[] row : board) {
for (int cell : row) {
if (cell == player) count++;
}
}
return count;
}
/**
* 计算前沿子数量（与空格相邻的棋子）
*/
public int countFrontier(int player) {
int count = 0;
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (board[i][j] == player) {
for (int[] dir : DIRECTIONS) {
int ni = i + dir[0], nj = j + dir[1];
if (ni >= 0 && ni < SIZE && nj >= 0 && nj < SIZE && board[ni][nj] == EMPTY) {
count++;
break;
}
}
}
}
}
return count;
}
/**
* 综合估值函数
* 从黑方视角返回分数（正数表示黑方优势）
*/
public int evaluate(int player) {
int opponent = (player == BLACK) ? WHITE : BLACK;
int totalPieces = countDiscs(BLACK) + countDiscs(WHITE);
// 终局：直接按棋子数决定胜负
if (getLegalMoves(BLACK).isEmpty() && getLegalMoves(WHITE).isEmpty()) {
return (countDiscs(player) - countDiscs(opponent)) * 10000;
}
int score = 0;
// 1. 位置权重评分
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] == opponent) {
score -= POSITION_WEIGHT[i][j];
}
}
}
// 2. 行动力（Mobility）
int myMoves = getLegalMoves(player).size();
int oppMoves = getLegalMoves(opponent).size();
if (myMoves + oppMoves != 0) {
score += (myMoves - oppMoves) * 10;
}
// 3. 棋子数（后期权重增加）
int discDiff = countDiscs(player) - countDiscs(opponent);
if (totalPieces > 50) {
score += discDiff * 5; // 终局前重视子数
} else if (totalPieces < 20) {
score += discDiff * (-1); // 开局少子反而灵活
}
// 4. 前沿子（越少越好）
int myFrontier = countFrontier(player);
int oppFrontier = countFrontier(opponent);
if (myFrontier + oppFrontier != 0) {
score -= (myFrontier - oppFrontier) * 2;
}
return score;
}
/**
* Minimax + Alpha-Beta剪枝
* @param depth 剩余搜索深度
* @param alpha 当前MAX节点的最好得分下界
* @param beta 当前MIN节点的最好得分上界
* @param maximizingPlayer true表示当前是MAX节点（AI方）
* @return 该局面下的评估分数
*/
public int alphabeta(int depth, int alpha, int beta, boolean maximizingPlayer, int aiPlayer) {
int current = maximizingPlayer ? aiPlayer : ((aiPlayer == BLACK) ? WHITE : BLACK);
List<int[]> moves = getLegalMoves(current);
// 终局或到达深度限制
if (depth == 0 || (getLegalMoves(BLACK).isEmpty() && getLegalMoves(WHITE).isEmpty())) {
return evaluate(aiPlayer);
}
// 无合法落子则轮空，切换玩家继续搜索
if (moves.isEmpty()) {
return alphabeta(depth - 1, alpha, beta, !maximizingPlayer, aiPlayer);
}
if (maximizingPlayer) {
int maxEval = Integer.MIN_VALUE;
for (int[] move : moves) {
Reversi next = copy();
next.makeMove(move[0], move[1], current);
int eval = next.alphabeta(depth - 1, alpha, beta, false, aiPlayer);
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[] move : moves) {
Reversi next = copy();
next.makeMove(move[0], move[1], current);
int eval = next.alphabeta(depth - 1, alpha, beta, true, aiPlayer);
minEval = Math.min(minEval, eval);
beta = Math.min(beta, eval);
if (beta <= alpha) {
break; // Alpha剪枝
}
}
return minEval;
}
}
/**
* AI选择最佳落子
*/
public int[] findBestMove(int aiPlayer, int depth) {
List<int[]> moves = getLegalMoves(aiPlayer);
if (moves.isEmpty()) return null;
int[] bestMove = null;
int bestValue = Integer.MIN_VALUE;
for (int[] move : moves) {
Reversi next = copy();
next.makeMove(move[0], move[1], aiPlayer);
int value = next.alphabeta(depth - 1, Integer.MIN_VALUE, Integer.MAX_VALUE, false, aiPlayer);
if (value > bestValue) {
bestValue = value;
bestMove = move;
}
}
return bestMove;
}
/**
* 打印棋盘
*/
public void printBoard() {
System.out.println("\n 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++) {
if (board[i][j] == EMPTY) System.out.print(". ");
else if (board[i][j] == BLACK) System.out.print("● ");
else System.out.print("○ ");
}
System.out.println();
}
System.out.println("黑(●): " + countDiscs(BLACK) + " 白(○): " + countDiscs(WHITE));
}
/**
* 判断游戏是否结束
*/
public boolean isGameOver() {
return getLegalMoves(BLACK).isEmpty() && getLegalMoves(WHITE).isEmpty();
}
/**
* 主程序：人机对战
*/
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Reversi game = new Reversi();
int humanPlayer = BLACK; // 玩家执黑
int aiPlayer = WHITE; // AI执白
System.out.println("=== 黑白棋（Reversi）人机对战 ===");
System.out.println("玩家执黑(●)，AI执白(○)");
System.out.println("输入格式：行 列（如：3 2）");
while (!game.isGameOver()) {
game.printBoard();
if (game.currentPlayer == humanPlayer) {
List<int[]> legalMoves = game.getLegalMoves(humanPlayer);
if (legalMoves.isEmpty()) {
System.out.println("玩家无合法落子，轮空。");
game.currentPlayer = aiPlayer;
continue;
}
System.out.print("请落子：");
int row = scanner.nextInt();
int col = scanner.nextInt();
if (game.makeMove(row, col, humanPlayer)) {
game.currentPlayer = aiPlayer;
} else {
System.out.println("非法落子，请重新输入！");
}
} else {
List<int[]> legalMoves = game.getLegalMoves(aiPlayer);
if (legalMoves.isEmpty()) {
System.out.println("AI无合法落子，轮空。");
game.currentPlayer = humanPlayer;
continue;
}
System.out.println("AI思考中...");
int[] bestMove = game.findBestMove(aiPlayer, SEARCH_DEPTH);
if (bestMove != null) {
game.makeMove(bestMove[0], bestMove[1], aiPlayer);
System.out.println("AI落子：" + bestMove[0] + " " + bestMove[1]);
game.currentPlayer = humanPlayer;
}
}
}
game.printBoard();
int blackCount = game.countDiscs(BLACK);
int whiteCount = game.countDiscs(WHITE);
System.out.println("\n游戏结束！");
if (blackCount > whiteCount) System.out.println("黑方获胜！" + blackCount + " : " + whiteCount);
else if (whiteCount > blackCount) System.out.println("白方获胜！" + whiteCount + " : " + blackCount);
else System.out.println("平局！" + blackCount + " : " + whiteCount);
scanner.close();
}
}
六、代码关键设计解析
6.1 翻转逻辑
getFlips方法沿8个方向搜索，检查是否存在”己方—连续对方—己方”的结构。这种显式的方向枚举确保了翻转规则的正确性，且时间复杂度为O(8×8)=O(1)（棋盘尺寸固定）。
6.2 状态复制
copy()方法用于AI搜索时生成临时局面。由于棋盘仅8×8，复制开销极小（64个整数），远小于增量更新的复杂度。
6.3 估值函数的分阶段策略
- 开局（<20子）：优先行动力与位置权重，子数权重为负（少子更灵活）。
- 中局（20~50子）：位置权重+行动力为主。
- 终局（>50子）：直接以子数差决定胜负，因为此时已难以大幅翻转。
6.4 搜索深度与性能
- 深度6时，每步搜索约10^5~10^6个节点，Java中响应时间在几百毫秒到1秒内。
- 若追求更强棋力，可将深度提升至8，配合迭代加深与移动排序（优先搜索角落和边缘）进一步优化剪枝效率。
七、复杂度分析
| 项目 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 合法落子判定 | O(1) | O(1) | 棋盘固定8×8，8方向扫描 |
| 估值函数 | O(1) | O(1) | 遍历64格计算各维度得分 |
| Minimax（深度d） | O(b^d) | O(d) | b为平均分支因子（约8~10） |
| Alpha-Beta剪枝 | O(b^(d/2)) ~ O(b^d) | O(d) | 理想排序下指数减半 |
| 单步AI决策（深度6） | ~10^6 节点 | O(6) | 实际响应<1秒 |
八、扩展方向
- 迭代加深搜索（IDS）：逐层加深搜索，在时间限制内找到最深的最优解。
- 置换表（Transposition Table）：用哈希表缓存已评估的局面，避免重复计算。
- 开局库（Opening Book）：预先录入高水平对局的前15步，跳过搜索直接进入中局。
- 终局精确求解：最后12~14空位时，可用完全穷举或Proof-Number Search找到最优解。
- 并行搜索：利用Java多线程将不同分支分配到多核并行评估。
九、总结
黑白棋虽小，却浓缩了博弈算法的核心精华：
– Minimax构建了理性的决策框架，假设对手同样聪明；
– Alpha-Beta剪枝在不改变结果的前提下大幅削减搜索量；
– 估值函数将人类棋感量化为可计算的数学表达式。
本文提供的Java代码是一个完整可运行的原型，读者可以在此基础上调整估值权重、加深搜索深度或加入更高级的优化策略，体验算法与博弈结合的乐趣。
