引言
中国跳棋（Chinese Checkers）是1893年由德国人发明的经典多人棋类游戏，因棋盘上六角星形的布局与中国文化元素相结合而得名。游戏支持2-6人对弈，目标是将己方全部棋子从大本营移动到对面的目标区域。看似简单的前进规则背后，隐藏着丰富的图论与路径规划问题——尤其是”连跳”机制使得搜索空间呈指数级增长。本文用Java实现中国跳棋AI，核心讲解BFS搜索最短移动路径、多跳贪心策略与目标区域评估函数。
游戏规则与数学建模
棋盘结构
中国跳棋使用六角星形棋盘，共121个棋位。将棋盘投影到二维坐标系，采用轴向坐标（Axial Coordinates）表示每个位置：
- 每个格子用坐标
(q, r)表示 - 六个邻居方向的偏移量为：
- 方向0:
(1, 0)— 右 - 方向1:
(1, -1)— 右上 - 方向2:
(0, -1)— 左上 - 方向3:
(-1, 0)— 左 - 方向4:
(-1, 1)— 左下 - 方向5:
(0, 1)— 右下
/**
* 六角网格坐标工具类
*/
public class HexCoord {
public static final int[][] DIRECTIONS = {
{1, 0}, {1, -1}, {0, -1}, {-1, 0}, {-1, 1}, {0, 1}
};
public int q, r;
public HexCoord(int q, int r) {
this.q = q;
this.r = r;
}
/**
* 获取邻居坐标
*/
public HexCoord neighbor(int direction) {
return new HexCoord(q + DIRECTIONS[direction][0],
r + DIRECTIONS[direction][1]);
}
/**
* 六角距离（棋盘距离）
* 公式: (|q| + |r| + |q+r|) / 2
*/
public int distanceTo(HexCoord other) {
return (Math.abs(q - other.q) + Math.abs(r - other.r)
+ Math.abs(q + r - other.q - other.r)) / 2;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof HexCoord)) return false;
HexCoord other = (HexCoord) o;
return q == other.q && r == other.r;
}
@Override
public int hashCode() {
return q * 31 + r;
}
@Override
public String toString() {
return "(" + q + "," + r + ")";
}
}
棋盘初始化
import java.util.*;
public class ChineseCheckersBoard {
// 棋盘半径（中心到顶点的距离）
public static final int RADIUS = 4;
// 棋位状态：-1=不存在, 0=空位, 1-6=玩家编号
private int[][] board;
// 有效棋位集合（用于遍历）
private Set<HexCoord> validPositions;
// 各玩家大本营和目标区域
private Map<Integer, Set<HexCoord>> camps;
private Map<Integer, Set<HexCoord>> goals;
public ChineseCheckersBoard() {
validPositions = new HashSet<>();
camps = new HashMap<>();
goals = new HashMap<>();
initBoard();
}
/**
* 初始化六角星形棋盘
* 中心区域为边长5的正六边形（轴向坐标范围 q+r 满足 |q|<=4, |r|<=4, |q+r|<=4）
* 六个角为各玩家的大本营和目标区域
*/
private void initBoard() {
// 收集所有有效棋位
for (int q = -RADIUS; q <= RADIUS; q++) {
for (int r = -RADIUS; r <= RADIUS; r++) {
if (Math.abs(q + r) <= RADIUS) {
validPositions.add(new HexCoord(q, r));
}
}
}
// 为简化，这里使用2人对弈的阵营设置
// 玩家1大本营：上方三角区域
camps.put(1, new HashSet<>());
goals.put(1, new HashSet<>());
for (int q = -RADIUS; q <= RADIUS; q++) {
for (int r = -RADIUS; r <= RADIUS; r++) {
if (Math.abs(q + r) <= RADIUS) {
HexCoord pos = new HexCoord(q, r);
// 玩家1大本营：r <= -3 的区域（上方）
if (r <= -3 && Math.abs(q) <= RADIUS + r + 1) {
camps.get(1).add(pos);
}
// 玩家1目标：r >= 3 的区域（下方）
if (r >= 3 && Math.abs(q) <= RADIUS - r + 1) {
goals.get(1).add(pos);
}
}
}
}
// 玩家2与玩家1对称
camps.put(2, new HashSet<>());
goals.put(2, new HashSet<>());
for (HexCoord pos : camps.get(1)) {
camps.get(2).add(new HexCoord(-pos.q, -pos.r));
}
for (HexCoord pos : goals.get(1)) {
goals.get(2).add(new HexCoord(-pos.q, -pos.r));
}
}
public boolean isValid(HexCoord pos) {
return validPositions.contains(pos);
}
public Set<HexCoord> getValidPositions() {
return validPositions;
}
public Set<HexCoord> getCamp(int player) {
return camps.getOrDefault(player, Collections.emptySet());
}
public Set<HexCoord> getGoal(int player) {
return goals.getOrDefault(player, Collections.emptySet());
}
}
BFS搜索所有合法移动
移动规则
中国跳棋的每次移动包含两种方式：
- 邻移（Step）：棋子移动到相邻的空位，每回合只能执行一次邻移
- 跳移（Hop）：棋子跳过相邻的一个棋子（己方或对方），落在其后的空位。跳移可以连续执行（连跳），形成一条跳跃链
BFS搜索连跳路径
/**
* 移动搜索器：使用BFS找出从某棋子出发的所有合法移动
*/
public class MoveGenerator {
private ChineseCheckersBoard board;
private Map<HexCoord, Integer> pieceMap; // 位置 -> 玩家编号
public MoveGenerator(ChineseCheckersBoard board, Map<HexCoord, Integer> pieceMap) {
this.board = board;
this.pieceMap = pieceMap;
}
/**
* 生成某棋子的所有合法移动（含连跳）
* @param start 棋子起始位置
* @return 所有可达目标位置及对应的移动路径
*/
public Map<HexCoord, List<HexCoord>> generateMoves(HexCoord start) {
Map<HexCoord, List<HexCoord>> moves = new HashMap<>();
// 1. 收集所有邻移
for (int d = 0; d < 6; d++) {
HexCoord neighbor = start.neighbor(d);
if (board.isValid(neighbor) && !pieceMap.containsKey(neighbor)) {
List<HexCoord> path = new ArrayList<>();
path.add(start);
path.add(neighbor);
moves.put(neighbor, path);
}
}
// 2. BFS搜索所有连跳路径
Queue<HexCoord> queue = new LinkedList<>();
Map<HexCoord, List<HexCoord>> jumpPaths = new HashMap<>();
Set<HexCoord> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
jumpPaths.put(start, Arrays.asList(start));
while (!queue.isEmpty()) {
HexCoord current = queue.poll();
List<HexCoord> currentPath = jumpPaths.get(current);
// 尝试六个方向的跳跃
for (int d = 0; d < 6; d++) {
HexCoord adjacent = current.neighbor(d);
HexCoord landing = adjacent.neighbor(d); // 跳跃落点
// 跳跃条件：相邻位置有棋子，落点为空且有效
if (!pieceMap.containsKey(adjacent)) continue;
if (!board.isValid(landing)) continue;
if (pieceMap.containsKey(landing)) continue;
if (visited.contains(landing)) continue;
// 记录新路径
List<HexCoord> newPath = new ArrayList<>(currentPath);
newPath.add(landing);
jumpPaths.put(landing, newPath);
visited.add(landing);
queue.offer(landing);
// 连跳到达的位置也加入合法移动
if (!landing.equals(start)) {
moves.put(landing, newPath);
}
}
}
return moves;
}
/**
* 生成某玩家的所有合法移动
*/
public Map<HexCoord, Map<HexCoord, List<HexCoord>>> generateAllPlayerMoves(int player) {
Map<HexCoord, Map<HexCoord, List<HexCoord>>> allMoves = new HashMap<>();
for (Map.Entry<HexCoord, Integer> entry : pieceMap.entrySet()) {
if (entry.getValue() == player) {
HexCoord pos = entry.getKey();
allMoves.put(pos, generateMoves(pos));
}
}
return allMoves;
}
}
连跳路径长度分析
BFS搜索连跳的时间复杂度为 O(6^k)，其中 k 为最大连跳次数。实际棋盘上由于棋子密度限制，连跳通常不超过5次，因此搜索空间可控。通过缓存已访问位置避免环路。
评估函数设计
多维度位置评估
中国跳棋AI的核心是评估函数，它量化当前局面对某玩家的有利程度：
/**
* 局面评估器
*/
public class Evaluator {
private ChineseCheckersBoard board;
// 评估权重参数（可通过自对弈调参）
private static final double W_PROGRESS = 10.0; // 前进进度权重
private static final double W_CENTER = 2.0; // 中心控制权重
private static final double W_GROUP = 3.0; // 集群度权重
private static final double W_JUMP_POT = 5.0; // 跳跃潜力权重
public Evaluator(ChineseCheckersBoard board) {
this.board = board;
}
/**
* 评估某玩家的局面得分（越高越有利）
*/
public double evaluate(int player, Map<HexCoord, Integer> pieceMap) {
double score = 0;
Set<HexCoord> myPieces = new HashSet<>();
for (Map.Entry<HexCoord, Integer> entry : pieceMap.entrySet()) {
if (entry.getValue() == player) {
myPieces.add(entry.getKey());
}
}
// 1. 前进进度：棋子到目标区域中心的距离之和（取负）
HexCoord goalCenter = computeGoalCenter(player);
for (HexCoord pos : myPieces) {
int dist = pos.distanceTo(goalCenter);
score -= W_PROGRESS * dist;
// 已到达目标区域的棋子给予额外奖励
if (board.getGoal(player).contains(pos)) {
score += 50;
}
}
// 2. 中心控制：棋子靠近棋盘中心的程度
HexCoord center = new HexCoord(0, 0);
for (HexCoord pos : myPieces) {
int centerDist = pos.distanceTo(center);
score -= W_CENTER * centerDist * 0.3;
}
// 3. 集群度：棋子之间的平均距离（越小越好）
if (myPieces.size() > 1) {
double totalDist = 0;
int pairs = 0;
for (HexCoord a : myPieces) {
for (HexCoord b : myPieces) {
if (a.equals(b)) continue;
totalDist += a.distanceTo(b);
pairs++;
}
}
score -= W_GROUP * (totalDist / pairs);
}
// 4. 跳跃潜力：棋子周围有邻居棋子可供跳跃的数量
for (HexCoord pos : myPieces) {
int jumpNeighbors = countJumpNeighbors(pos, pieceMap);
score += W_JUMP_POT * jumpNeighbors;
}
return score;
}
/**
* 计算目标区域中心
*/
private HexCoord computeGoalCenter(int player) {
Set<HexCoord> goal = board.getGoal(player);
int sumQ = 0, sumR = 0;
for (HexCoord pos : goal) {
sumQ += pos.q;
sumR += pos.r;
}
return new HexCoord(sumQ / goal.size(), sumR / goal.size());
}
/**
* 计算某位置周围可作为跳板的邻居数量
*/
private int countJumpNeighbors(HexCoord pos, Map<HexCoord, Integer> pieceMap) {
int count = 0;
for (int d = 0; d < 6; d++) {
HexCoord neighbor = pos.neighbor(d);
HexCoord landing = neighbor.neighbor(d);
if (pieceMap.containsKey(neighbor) && !pieceMap.containsKey(landing)
&& board.isValid(landing)) {
count++;
}
}
return count;
}
}
多跳贪心策略与Minimax决策
贪心策略：优先最远连跳
对于非终局阶段，采用贪心策略选择能带来最大评估值提升的移动：
/**
* 贪心移动选择器
*/
public class GreedyMoveSelector {
private Evaluator evaluator;
private MoveGenerator moveGen;
public GreedyMoveSelector(Evaluator evaluator, MoveGenerator moveGen) {
this.evaluator = evaluator;
this.moveGen = moveGen;
}
/**
* 选择当前最优移动（贪心）
* @return [起始位置, 目标位置, 移动路径, 评估得分]
*/
public Object[] selectBestMove(int player, Map<HexCoord, Integer> pieceMap) {
Map<HexCoord, Map<HexCoord, List<HexCoord>>> allMoves =
moveGen.generateAllPlayerMoves(player);
double bestScore = Double.NEGATIVE_INFINITY;
HexCoord bestFrom = null;
HexCoord bestTo = null;
List<HexCoord> bestPath = null;
for (Map.Entry<HexCoord, Map<HexCoord, List<HexCoord>>> fromEntry : allMoves.entrySet()) {
HexCoord from = fromEntry.getKey();
for (Map.Entry<HexCoord, List<HexCoord>> toEntry : fromEntry.getValue().entrySet()) {
HexCoord to = toEntry.getKey();
List<HexCoord> path = toEntry.getValue();
// 模拟执行移动
Map<HexCoord, Integer> newState = new HashMap<>(pieceMap);
newState.remove(from);
newState.put(to, player);
// 评估新状态
double score = evaluator.evaluate(player, newState);
// 连跳距离加成：连跳次数越多，移动价值越高
score += (path.size() - 2) * 3.0;
if (score > bestScore) {
bestScore = score;
bestFrom = from;
bestTo = to;
bestPath = path;
}
}
}
return new Object[]{bestFrom, bestTo, bestPath, bestScore};
}
}
两阶层Minimax搜索
为了考虑对手反制，实现两阶层Minimax：
/**
* Minimax搜索器（深度2）
*/
public class MinimaxSearcher {
private Evaluator evaluator;
private MoveGenerator moveGen;
private int maxPlayer;
private int opponent;
public MinimaxSearcher(Evaluator evaluator, MoveGenerator moveGen) {
this.evaluator = evaluator;
this.moveGen = moveGen;
}
/**
* 两阶层Minimax搜索
*/
public Object[] searchBestMove(int player, Map<HexCoord, Integer> pieceMap) {
this.maxPlayer = player;
this.opponent = (player == 1) ? 2 : 1;
Map<HexCoord, Map<HexCoord, List<HexCoord>>> myMoves =
moveGen.generateAllPlayerMoves(player);
double bestValue = Double.NEGATIVE_INFINITY;
Object[] bestMove = null;
for (Map.Entry<HexCoord, Map<HexCoord, List<HexCoord>>> fromEntry : myMoves.entrySet()) {
HexCoord from = fromEntry.getKey();
for (Map.Entry<HexCoord, List<HexCoord>> toEntry : fromEntry.getValue().entrySet()) {
HexCoord to = toEntry.getKey();
List<HexCoord> path = toEntry.getValue();
// 第一层：我方移动
Map<HexCoord, Integer> state1 = new HashMap<>(pieceMap);
state1.remove(from);
state1.put(to, player);
// 第二层：对手最优回应
double opponentBest = findOpponentBest(state1);
// Minimax值 = 我方评估 - 对手反制后的损失
double value = evaluator.evaluate(player, state1) - opponentBest * 0.5;
value += (path.size() - 2) * 2.0; // 连跳加成
if (value > bestValue) {
bestValue = value;
bestMove = new Object[]{from, to, path, value};
}
}
}
return bestMove;
}
private double findOpponentBest(Map<HexCoord, Integer> state) {
Map<HexCoord, Map<HexCoord, List<HexCoord>>> oppMoves =
moveGen.generateAllPlayerMoves(opponent);
double bestOppScore = Double.NEGATIVE_INFINITY;
for (Map.Entry<HexCoord, Map<HexCoord, List<HexCoord>>> fromEntry : oppMoves.entrySet()) {
HexCoord from = fromEntry.getKey();
for (Map.Entry<HexCoord, List<HexCoord>> toEntry : fromEntry.getValue().entrySet()) {
HexCoord to = toEntry.getKey();
Map<HexCoord, Integer> state2 = new HashMap<>(state);
state2.remove(from);
state2.put(to, opponent);
double score = evaluator.evaluate(opponent, state2);
if (score > bestOppScore) {
bestOppScore = score;
}
}
}
return bestOppScore == Double.NEGATIVE_INFINITY ? 0 : bestOppScore;
}
}
完整游戏模拟
/**
* 中国跳棋AI主类
*/
public class ChineseCheckersAI {
private ChineseCheckersBoard board;
private Map<HexCoord, Integer> pieceMap;
private Evaluator evaluator;
private MoveGenerator moveGen;
private GreedyMoveSelector greedySelector;
private MinimaxSearcher minimaxSearcher;
public ChineseCheckersAI() {
board = new ChineseCheckersBoard();
pieceMap = new HashMap<>();
initPieces();
evaluator = new Evaluator(board);
moveGen = new MoveGenerator(board, pieceMap);
greedySelector = new GreedyMoveSelector(evaluator, moveGen);
minimaxSearcher = new MinimaxSearcher(evaluator, moveGen);
}
private void initPieces() {
// 初始化玩家1棋子（上方大本营）
for (HexCoord pos : board.getCamp(1)) {
pieceMap.put(pos, 1);
}
// 初始化玩家2棋子（下方大本营）
for (HexCoord pos : board.getCamp(2)) {
pieceMap.put(pos, 2);
}
}
/**
* 执行AI移动
*/
public void makeMove(int player) {
moveGen = new MoveGenerator(board, pieceMap); // 更新moveGen状态
// 使用Minimax策略
Object[] result = minimaxSearcher.searchBestMove(player, pieceMap);
if (result == null) return;
HexCoord from = (HexCoord) result[0];
HexCoord to = (HexCoord) result[1];
@SuppressWarnings("unchecked")
List<HexCoord> path = (List<HexCoord>) result[2];
double score = (Double) result[3];
// 执行移动
pieceMap.remove(from);
pieceMap.put(to, player);
System.out.printf("玩家%d: %s -> %s (路径长度:%d, 评估值:%.1f)%n",
player, from, to, path.size(), score);
}
/**
* 检查某玩家是否获胜
*/
public boolean checkWin(int player) {
Set<HexCoord> goal = board.getGoal(player);
int count = 0;
for (HexCoord pos : goal) {
if (pieceMap.getOrDefault(pos, -1) == player) {
count++;
}
}
return count == goal.size();
}
/**
* 打印当前棋盘状态（简化文本表示）
*/
public void printBoard() {
System.out.println("\n--- 当前棋盘 ---");
for (int r = -ChineseCheckersBoard.RADIUS; r <= ChineseCheckersBoard.RADIUS; r++) {
// 打印缩进
for (int i = 0; i < Math.abs(r); i++) System.out.print(" ");
for (int q = -ChineseCheckersBoard.RADIUS; q <= ChineseCheckersBoard.RADIUS; q++) {
if (Math.abs(q + r) <= ChineseCheckersBoard.RADIUS) {
HexCoord pos = new HexCoord(q, r);
int owner = pieceMap.getOrDefault(pos, 0);
if (owner == 1) System.out.print("O ");
else if (owner == 2) System.out.print("X ");
else System.out.print(". ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
ChineseCheckersAI game = new ChineseCheckersAI();
game.printBoard();
// 模拟对局
for (int turn = 0; turn < 100; turn++) {
int player = (turn % 2) + 1;
game.makeMove(player);
if (game.checkWin(1)) {
System.out.println("玩家1获胜！");
break;
}
if (game.checkWin(2)) {
System.out.println("玩家2获胜！");
break;
}
}
game.printBoard();
}
}
复杂度分析
| 阶段 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| BFS连跳搜索 | O(6^k) | O(N) | k为最大连跳次数，N为棋盘格数 |
| 评估函数 | O(P² + P×6) | O(P) | P为某方棋子数（通常P=10） |
| 贪心选择 | O(P × M × E) | O(N) | M为每棋子平均移动数，E为评估耗时 |
| Minimax(深度2) | O(P₁×M₁ × P₂×M₂ × E) | O(N) | 双方移动数乘积 |
在121格的棋盘上，贪心策略可在10ms内完成决策，两阶层Minimax约需100-500ms。
总结
本文构建了中国跳棋的智能决策系统，核心算法层次如下：
- 六角坐标系统：轴向坐标实现高效的邻居查询与距离计算
- BFS连跳搜索：处理连跳组合爆炸，找到所有可达位置
- 多维度评估函数：前进进度、中心控制、集群度、跳跃潜力的加权综合
- 贪心 + Minimax决策：局部贪心快速响应，Minimax预判对手反制
读者可以进一步扩展：加入Alpha-Beta剪枝将搜索深度扩展到4层、使用UCT蒙特卡洛树搜索实现自对弈策略优化、或通过遗传算法自动调优评估函数的权重参数。中国跳棋的连跳机制也使其成为研究组合搜索与启发式评估的经典平台。
