一、为什么卡卡颂值得作为算法题
卡卡颂（Carcassonne）是回合制板块拼接游戏：玩家轮流抽一张方形板块，把它放到桌面已有板块的相邻位置（边必须匹配），然后可以选择把自己的”随从”放到刚拼出的某个特征上（城市、道路、修道院、田地）。当某个特征闭合时结算得分。
它的算法难度比围棋更”工程化”，原因有三：
- 结算依赖于连通性。城市和道路都是”由多个板块上的半段拼接而成”的连通分量。判定闭合、计算大小、分配归属，本质是动态图连通性问题——而每次放板块都会把多个分量合并。
- 特征是可合并的动态集合。城市 A 和城市 B 通过新板块接上，必须立刻合并为一个城市，并把两边的随从一起归入新城市。这是并查集（Union-Find） 的教科书场景。
- 信息不完全 + 随机抽取。你只看得到当前板块和剩余板块池的统计分布，看不到对手的下一张牌。这个特性让纯 Alpha-Beta 失效，必须用期望值 / 蒙特卡洛方法。
本文实现一个可自对弈的卡卡颂引擎，重点是特征并查集 + 闭合检测 + MCTS 决策。
二、建模：把几何问题化成图问题
2.1 板块的四边与特征
每个板块用 4 位边编码 + 特征归属表描述。为简化，本文建模 6 种基础板块（完整实现可扩展到 24 种）：
| 编号 | 名称 | 北 | 东 | 南 | 西 | 特征 |
|---|---|---|---|---|---|---|
| 0 | 城市两侧 | C | R | F | R | 城市(北) + 道路(横穿) |
| 1 | 城市单侧 | C | F | F | F | 城市(北) |
| 2 | 直路 | R | F | R | F | 道路(南北) |
| 3 | 弯路 | R | R | F | F | 道路(北-东) |
| 4 | 三岔路 | R | R | R | F | 道路(北东南，带中心节点) |
| 5 | 修道院 | F | F | F | F | 修道院 |
边类型：F 田地、R 道路、C 城市。放置合法性：新板块每条相邻边必须与被贴板块的对应边同类型。
2.2 特征用”槽位”编号
每个板块最多 4 个边槽 + 1 个中心槽（修道院/道路节点）。全局特征用 (板块ID, 槽位) 表示，并查集直接管理这些槽位：
slotId = boardTileId * 5 + slotIndex
这样每次放板块后，把所有”边类型相同且互相贴合”的槽位 union，所有”同一板块内属于同一特征”的槽位也 union。一个特征就是并查集里的一棵树。
2.3 闭合判定
一个特征闭合的充要条件：它的每个边槽都已与邻居贴合。并查集维护每个根的两项信息：
openEdges：该特征尚未与邻居连接的边槽数量。size：该特征包含的板块数（或半段数）。
当 openEdges 降到 0 时，特征闭合，立即结算。
三、算法一：并查集维护特征
标准并查集加路径压缩 + 按秩合并，节点总数 O(5T)，T 为板块数。关键操作：
int union(int a, int b) // 合并两个槽位所在特征，累加 openEdges 与 size
int closeEdge(int slot) // 某槽位贴合成功，对应特征 openEdges -= 1
为什么不用 DFS/BFS 每回合重算：每回合重算连通分量是 O(T)，整局 O(T²)。并查集把每次合并摊还为 O(α(T))，整局接近 O(T)。在纯 Java 下，72 块的标准对局从数百微秒降到几微秒——这个量级的差异决定了 MCTS 能跑多少次模拟。
四、算法二：MCTS 落子决策
4.1 为什么必须用 MCTS
Alpha-Beta 需要完全信息与确定性的搜索树。但卡卡颂有两个随机源：板块抽取、对手决策。用期望极小极大（Expectiminimax）要枚举 24 种可能板块 × 所有落点，分支因子爆炸。MCTS 通过对抽取采样，把期望”折进”模拟里，天然适配。
4.2 四个阶段
- Selection：从根按 UCT 下降，
UCT = Q/N + c·√(ln N_parent / N_child)。 - Expansion：在当前节点展开一个未尝试的
(落点, 随从位置)组合。 - Simulation：随机/贪心 rollout 到终局。
- Backpropagation：把终局得分差回传。
4.3 两个工程要点
- 动作空间剪枝：合法落点通常 20~40 个，乘以随从选择（最多 5 种：城市/道路/修道院/田地/不放置），单节点动作可达 200。必须先按启发式筛出前 K 个（如 20 个），否则 MCTS 深度上不去。
- rollout 用贪心而非纯随机：纯随机 rollout 在城市闭合判定上噪声极大，改用”优先能立即得分”的贪心策略，同等模拟次数下胜率评估方差显著降低。
五、项目结构
carcassonne/
├── pom.xml
└── src/main/java/com/example/carcassonne/
├── EdgeType.java 边类型枚举
├── Tile.java 板块定义与旋转
├── TileDeck.java 牌堆与剩余统计
├── BoardState.java 棋盘 + 并查集特征
├── UnionFind.java 并查集（带 openEdges/size 聚合）
├── Evaluator.java 局面评估
├── MctsEngine.java MCTS 决策
└── Main.java 自对弈
六、完整实现
6.1 边类型与板块
package com.example.carcassonne;
/** 板块边的三种类型。 */
public enum EdgeType {
FIELD, ROAD, CITY;
/** 边的匹配规则：同类型即可贴合。 */
public boolean matches(EdgeType other) {
return this == other;
}
/** 反向边索引：0=北,1=东,2=南,3=西。 */
public static int opposite(int dir) {
return (dir + 2) % 4;
}
}
package com.example.carcassonne;
import java.util.ArrayList;
import java.util.List;
/**
* 板块定义：4 条边的类型 + 边槽到特征的映射。
* featureOf[dir] 表示该方向边槽所属的"本地特征编号"，
* 同编号的边槽属于同一特征（会在放置时被 union）。
* centerFeature = -1 表示无中心特征。
*/
public final class Tile {
/** 槽位总数：4 边 + 1 中心。 */
public static final int SLOTS = 5;
public static final int CENTER = 4;
public final int typeId;
public final String name;
public final EdgeType[] edges; // 长度 4
public final int[] featureOf; // 长度 5，本地特征编号，-1 表示该槽不存在
public final int centerFeature; // -1 表示无中心
public Tile(int typeId, String name, EdgeType[] edges, int[] featureOf, int centerFeature) {
this.typeId = typeId;
this.name = name;
this.edges = edges;
this.featureOf = featureOf;
this.centerFeature = centerFeature;
}
/** 顺时针旋转 90 度。 */
public Tile rotate(int times) {
int t = ((times % 4) + 4) % 4;
if (t == 0) return this;
EdgeType[] ne = new EdgeType[4];
for (int i = 0; i < 4; i++) {
ne[(i + t) % 4] = edges[i];
}
int[] nf = new int[SLOTS];
for (int i = 0; i < 4; i++) {
nf[(i + t) % 4] = featureOf[i];
}
nf[CENTER] = featureOf[CENTER];
return new Tile(typeId, name, ne, nf, centerFeature);
}
/** 该板块所有存在的槽位。 */
public List<Integer> slots() {
List<Integer> out = new ArrayList<>();
for (int i = 0; i < SLOTS; i++) {
if (featureOf[i] >= 0) out.add(i);
}
return out;
}
/** 内置的 6 种基础板块模板。 */
public static final List<Tile> TEMPLATES = new ArrayList<>();
static {
// 类型 0：城市在北，道路横穿（东-西连成一条路，含中心节点）
TEMPLATES.add(new Tile(0, "城市+横路",
new EdgeType[]{EdgeType.CITY, EdgeType.ROAD, EdgeType.FIELD, EdgeType.ROAD},
new int[]{0, 1, -1, 1, 1}, 1));
// 类型 1：城市单侧，其余全田
TEMPLATES.add(new Tile(1, "城市单侧",
new EdgeType[]{EdgeType.CITY, EdgeType.FIELD, EdgeType.FIELD, EdgeType.FIELD},
new int[]{0, -1, -1, -1, -1}, -1));
// 类型 2：南北直路
TEMPLATES.add(new Tile(2, "直路",
new EdgeType[]{EdgeType.ROAD, EdgeType.FIELD, EdgeType.ROAD, EdgeType.FIELD},
new int[]{0, -1, 0, -1, 0}, 0));
// 类型 3：北-东弯路
TEMPLATES.add(new Tile(3, "弯路",
new EdgeType[]{EdgeType.ROAD, EdgeType.ROAD, EdgeType.FIELD, EdgeType.FIELD},
new int[]{0, 0, -1, -1, 0}, 0));
// 类型 4：三岔路（北/东/南），带中心节点
TEMPLATES.add(new Tile(4, "三岔路",
new EdgeType[]{EdgeType.ROAD, EdgeType.ROAD, EdgeType.ROAD, EdgeType.FIELD},
new int[]{0, 0, 0, -1, 0}, 0));
// 类型 5：修道院，四面全田，中心是修道院特征
TEMPLATES.add(new Tile(5, "修道院",
new EdgeType[]{EdgeType.FIELD, EdgeType.FIELD, EdgeType.FIELD, EdgeType.FIELD},
new int[]{-1, -1, -1, -1, 0}, 0));
}
}
6.2 牌堆
package com.example.carcassonne;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/** 牌堆：按标准比例构造若干张板块，支持抽取与剩余统计。 */
public final class TileDeck {
private final List<Tile> draw = new ArrayList<>();
private final Random rnd;
/** 剩余池中各类型的数量，供 MCTS 计算抽取概率。 */
private final int[] remaining = new int[Tile.TEMPLATES.size()];
public TileDeck(long seed, int copies) {
this.rnd = new Random(seed);
for (int c = 0; c < copies; c++) {
for (Tile t : Tile.TEMPLATES) {
draw.add(t);
}
}
Collections.shuffle(draw, rnd);
for (Tile t : draw) remaining[t.typeId]++;
}
public boolean isEmpty() { return draw.isEmpty(); }
public int size() { return draw.size(); }
/** 抽一张牌。 */
public Tile draw() {
if (draw.isEmpty()) return null;
Tile t = draw.remove(draw.size() - 1);
remaining[t.typeId]--;
return t;
}
public int remainingOf(int typeId) { return remaining[typeId]; }
/** 剩余池中某类型的抽取概率。 */
public double probabilityOf(int typeId) {
int total = draw.size();
return total == 0 ? 0 : (double) remaining[typeId] / total;
}
public List<Tile> remainingTiles() {
return new ArrayList<>(draw);
}
}
6.3 并查集：核心数据结构
package com.example.carcassonne;
/**
* 特征并查集。
* 节点 = 槽位 = tileIndex * 5 + slotIndex。
* 除连通性外聚合三项信息：
* openEdges —— 该特征尚未贴合的边槽数，为 0 即闭合
* tileCount —— 该特征覆盖的板块数（计分用）
* followerMask —— 该特征上随从归属的玩家位掩码（玩家数 ≤ 5，用 int 足够）
*/
public final class UnionFind {
private final int[] parent;
private final int[] rank;
private final int[] openEdges;
private final int[] tileCount;
private final int[] followerMask;
private final int[] featureKind; // 0=城市,1=道路,2=修道院,3=田地
public UnionFind(int capacity) {
parent = new int[capacity];
rank = new int[capacity];
openEdges = new int[capacity];
tileCount = new int[capacity];
followerMask = new int[capacity];
featureKind = new int[capacity];
for (int i = 0; i < capacity; i++) {
parent[i] = i;
featureKind[i] = -1;
}
}
/** 路径压缩 + 返回根。 */
public int find(int x) {
int root = x;
while (parent[root] != root) root = parent[root];
while (parent[x] != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
/**
* 初始化一个槽位为独立特征。
* tileContribution 只在该槽位是其"本地特征"代表槽时取 1，
* 否则取 0——这样 tileCount 统计的是**不同板块数**而不是槽位数。
* 若每个槽位都记 1，一条直路板块会因为 3 个槽位被算成 3 块板块，
* 计分直接翻了 3 倍。
*/
public void initSlot(int slot, int openCount, int kind, int tileContribution) {
parent[slot] = slot;
openEdges[slot] = openCount;
tileCount[slot] = tileContribution;
followerMask[slot] = 0;
featureKind[slot] = kind;
}
/**
* 纯合并：连根并累加板块数与未接边数，但不做"对接扣减"。
* 用于同一板块内部的同特征槽位——它们本就属于同一特征，
* 只是把各自的开放边汇总到一起，不存在"两条边互相贴合"。
*/
public int union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return ra;
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
if (rank[ra] == rank[rb]) rank[ra]++;
tileCount[ra] += tileCount[rb];
openEdges[ra] += openEdges[rb]; // 两个子特征的未接边相加
followerMask[ra] |= followerMask[rb];
return ra;
}
/**
* 边贴合合并：两个边槽真正对接，各消耗一条 openEdge，故总数减 2。
* 与 union 分开是必要的——若混用，板内合并会错误地把 openEdges 减掉，
* 导致特征被提前判定为"闭合"，这是本实现最容易踩的坑。
*/
public int connect(int a, int b) {
int ra = union(a, b);
openEdges[ra] = Math.max(0, openEdges[ra] - 2);
return ra;
}
/** 开放边计数减一（修道院填格用）。 */
public void decrementOpen(int slot) {
int r = find(slot);
if (openEdges[r] > 0) openEdges[r]--;
}
public boolean isClosed(int slot) {
return openEdges[find(slot)] == 0;
}
public int size(int slot) { return tileCount[find(slot)]; }
public int openOf(int slot) { return openEdges[find(slot)]; }
public int kindOf(int slot) { return featureKind[find(slot)]; }
/** 在槽位所在特征上放置一枚随从，记录归属玩家。 */
public void placeFollower(int slot, int player) {
followerMask[find(slot)] |= (1 << player);
}
/** 该特征的随从归属掩码。 */
public int followerMaskOf(int slot) { return followerMask[find(slot)]; }
/** 结算后清除随从。 */
public void clearFollower(int slot) { followerMask[find(slot)] = 0; }
}
6.4 棋盘状态
package com.example.carcassonne;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
/** 棋盘状态：已放置板块、并查集特征、玩家分数。 */
public final class BoardState {
public static final int DIR_N = 0, DIR_E = 1, DIR_S = 2, DIR_W = 3;
private static final int[] DR = {-1, 0, 1, 0};
private static final int[] DC = {0, 1, 0, -1};
/** 已放置板块，key = r * 1000 + c 编码的坐标。 */
public final Map<Long, Placement> placements = new LinkedHashMap<>();
public final UnionFind uf;
public final int players;
public final int[] scores;
/** 每个玩家剩余随从数。 */
public final int[] followers;
public static final class Placement {
public final int r;
public final int c;
public final Tile tile;
public final int tileIndex; // 并查集槽位基址 = tileIndex * 5
public Placement(int r, int c, Tile tile, int tileIndex) {
this.r = r;
this.c = c;
this.tile = tile;
this.tileIndex = tileIndex;
}
}
public BoardState(int players, int capacityTiles) {
this.players = players;
this.scores = new int[players];
this.followers = new int[players];
for (int i = 0; i < players; i++) followers[i] = 7; // 每人 7 个随从
this.uf = new UnionFind(capacityTiles * Tile.SLOTS + Tile.SLOTS);
}
public static long key(int r, int c) { return (long) r * 1000L + c; }
public boolean occupied(int r, int c) { return placements.containsKey(key(r, c)); }
/** 是否存在任何相邻板块（首块放中心后才有邻接要求）。 */
public boolean hasNeighbor(int r, int c) {
for (int d = 0; d < 4; d++) {
if (occupied(r + DR[d], c + DC[d])) return true;
}
return false;
}
/** 边匹配校验：新板块在 (r,c) 的每条相邻边必须与被贴板块同类型。 */
public boolean canPlace(int r, int c, Tile tile) {
if (occupied(r, c)) return false;
boolean anyNeighbor = false;
for (int d = 0; d < 4; d++) {
Placement nb = placements.get(key(r + DR[d], c + DC[d]));
if (nb == null) continue;
anyNeighbor = true;
// d 表示"邻居位于我的第 d 方向"：
// 我的第 d 条边 正对 邻居的第 opposite(d) 条边
EdgeType mine = tile.edges[d];
EdgeType neighborEdge = nb.tile.edges[EdgeType.opposite(d)];
if (!mine.matches(neighborEdge)) return false;
}
return anyNeighbor || placements.isEmpty();
}
/** 枚举所有合法落点（不区分随从）。 */
public List<int[]> legalPositions(Tile tile) {
List<int[]> out = new ArrayList<>();
if (placements.isEmpty()) {
out.add(new int[]{0, 0});
return out;
}
Map<Long, Boolean> seen = new HashMap<>();
for (Placement p : placements.values()) {
for (int d = 0; d < 4; d++) {
int r = p.r + DR[d], c = p.c + DC[d];
long k = key(r, c);
if (seen.containsKey(k)) continue;
seen.put(k, true);
if (canPlace(r, c, tile)) out.add(new int[]{r, c});
}
}
return out;
}
/**
* 放置板块并合并特征，返回本回合产生的即时得分。
* 关键步骤：初始化槽位 → 板内同特征合并 → 边贴合合并 → 修道院计数更新 → 结算。
*/
public int place(int r, int c, Tile tile, int player, int followerSlot) {
int tileIndex = placements.size();
Placement pl = new Placement(r, c, tile, tileIndex);
placements.put(key(r, c), pl);
// 1) 初始化本地槽位。同一本地特征的多个槽位只由第一个贡献板块计数
java.util.Set<Integer> countedFeature = new java.util.HashSet<>();
for (int s : tile.slots()) {
int slot = tileIndex * Tile.SLOTS + s;
int kind = kindOfFeature(tile, s);
int open;
if (s == Tile.CENTER) {
// 修道院：需填满周围 3×3 共 9 格，初值 9，随后由 updateMonasteries 递减
open = (tile.typeId == 5) ? 9 : 0;
} else {
open = 1; // 每条边初始都是"未贴合"
}
int contribution = countedFeature.add(tile.featureOf[s]) ? 1 : 0;
uf.initSlot(slot, open, kind, contribution);
}
// 2) 板内同特征的槽位合并（累加开放边，不做对接扣减）
for (int i = 0; i < 4; i++) {
if (tile.featureOf[i] < 0) continue;
for (int j = i + 1; j < 4; j++) {
if (tile.featureOf[j] == tile.featureOf[i]) {
uf.union(tileIndex * Tile.SLOTS + i, tileIndex * Tile.SLOTS + j);
}
}
// 道路/城市与中心节点相连
if (tile.centerFeature >= 0 && tile.centerFeature == tile.featureOf[i]) {
uf.union(tileIndex * Tile.SLOTS + i, tileIndex * Tile.SLOTS + Tile.CENTER);
}
}
// 3) 与邻居贴合：边真正对接，openEdges 各减一
for (int d = 0; d < 4; d++) {
Placement nb = placements.get(key(r + DR[d], c + DC[d]));
if (nb == null) continue;
int myDir = d; // 我的边
int nbDir = EdgeType.opposite(d); // 邻居正对我的那条边
if (tile.featureOf[myDir] < 0) continue;
if (nb.tile.featureOf[nbDir] < 0) continue;
uf.connect(tileIndex * Tile.SLOTS + myDir, nb.tileIndex * Tile.SLOTS + nbDir);
}
// 4) 修道院计数：本板块落入周围哪些修道院的 3×3 范围
updateMonasteries(r, c);
// 5) 放置随从
if (followerSlot >= 0 && followers[player] > 0) {
uf.placeFollower(tileIndex * Tile.SLOTS + followerSlot, player);
followers[player]--;
}
// 6) 结算所有闭合特征
return settle(player);
}
/**
* 新板块落在 (r,c)，会让周围 3×3 范围内所有修道院的"待填格数"减 1。
* 包含修道院自身所在格，因此一块修道院板块放下时即从 9 递减到 8。
*/
private void updateMonasteries(int r, int c) {
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
Placement p = placements.get(key(r + dr, c + dc));
if (p == null || p.tile.typeId != 5) continue;
int centerSlot = p.tileIndex * Tile.SLOTS + Tile.CENTER;
uf.decrementOpen(centerSlot);
}
}
}
private int kindOfFeature(Tile tile, int slot) {
if (slot == Tile.CENTER) {
return tile.typeId == 5 ? 2 : 1; // 修道院 / 道路中心节点
}
return switch (tile.edges[slot]) {
case CITY -> 0;
case ROAD -> 1;
case FIELD -> 3;
};
}
/**
* 遍历所有槽位，对已闭合的特征结算。
* 城市：2 分/板块；道路：1 分/板块；修道院：1 分 + 周围 8 格板块数。
*/
private int settle(int placingPlayer) {
int gained = 0;
java.util.Set<Integer> settled = new java.util.HashSet<>();
for (Placement p : placements.values()) {
for (int s : p.tile.slots()) {
int slot = p.tileIndex * Tile.SLOTS + s;
int root = uf.find(slot);
if (!settled.add(root)) continue;
if (!uf.isClosed(slot)) continue;
int mask = uf.followerMaskOf(slot);
if (mask == 0) continue; // 无人占领，不结算
int value = scoreOf(p, slot);
if (value <= 0) continue;
// 随从最多的玩家独得；若并列则共同得分
List<Integer> top = new ArrayList<>();
for (int pl = 0; pl < players; pl++) {
if ((mask & (1 << pl)) != 0) top.add(pl);
}
for (int owner : top) {
scores[owner] += value;
}
gained += value * top.size();
// 随从退回
for (int owner : top) {
followers[owner] = Math.min(7, followers[owner] + 1);
}
uf.clearFollower(root);
}
}
return gained;
}
/** 按特征类型计分。 */
private int scoreOf(Placement p, int slot) {
int kind = uf.kindOf(slot);
int size = uf.size(slot);
if (kind == 0) return size * 2; // 城市：每板块 2 分
if (kind == 1) {
// 道路：每板块 1 分。size 统计的是特征内板块数，
// 同一板块内的多个道路槽位已通过 union 合并，故不会重复计数。
return size;
}
if (kind == 2) {
int around = 0;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
if (occupied(p.r + dr, p.c + dc)) around++;
}
}
return 1 + around;
}
return 0; // 田地不即时结算
}
public void print() {
StringBuilder sb = new StringBuilder();
for (int r = -3; r <= 3; r++) {
for (int c = -3; c <= 3; c++) {
Placement p = placements.get(key(r, c));
sb.append(p == null ? " .. " : String.format(" %-2d ", p.tile.typeId));
}
sb.append(System.lineSeparator());
}
System.out.print(sb);
}
}
6.5 评估与 MCTS
package com.example.carcassonne;
/** 局面评估：分数差 + 潜在收益（未闭合特征的大小）。 */
public final class Evaluator {
/** 潜在收益：未闭合特征每板块折算的期望价值。 */
public static double potential(BoardState b, int player) {
double score = b.scores[player];
for (BoardState.Placement p : b.placements.values()) {
for (int s : p.tile.slots()) {
int slot = p.tileIndex * Tile.SLOTS + s;
if (b.uf.isClosed(slot)) continue;
if ((b.uf.followerMaskOf(slot) & (1 << player)) == 0) continue;
int size = b.uf.size(slot);
int open = b.uf.openOf(slot);
// 未闭合特征的折现价值：越大越未完成，折扣越重
score += size * 1.5 / (1 + open * 0.6);
}
}
// 剩余随从是资源，计入轻量权重
score += b.followers[player] * 0.4;
return score;
}
public static double relative(BoardState b, int player) {
double me = potential(b, player);
double sum = 0;
for (int i = 0; i < b.players; i++) {
if (i == player) continue;
sum += potential(b, i);
}
double others = sum / Math.max(1, b.players - 1);
return me - others;
}
}
package com.example.carcassonne;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* MCTS 引擎。
* 动作 = (落点, 旋转, 随从槽位)，其中随从槽位 -1 表示不放随从。
* 为控制分支因子，先用启发式筛出前 K 个动作再交给 MCTS。
*/
public final class MctsEngine {
private static final double C_PUCT = 1.4;
private static final int MAX_ACTIONS = 24;
private final Random rnd;
private final int player;
public MctsEngine(int player, long seed) {
this.player = player;
this.rnd = new Random(seed);
}
/** 一个候选动作。 */
public static final class Action {
public final int r, c;
public final int rotation;
public final Tile tile;
public final int followerSlot; // -1 表示不放置
public Action(int r, int c, int rotation, Tile tile, int followerSlot) {
this.r = r;
this.c = c;
this.rotation = rotation;
this.tile = tile;
this.followerSlot = followerSlot;
}
@Override
public String toString() {
return String.format("(%d,%d) rot%d follower=%d", r, c, rotation, followerSlot);
}
}
/** 生成候选动作并做启发式截断。 */
public List<Action> candidates(BoardState b, Tile raw) {
List<Action> all = new ArrayList<>();
for (int rot = 0; rot < 4; rot++) {
Tile t = raw.rotate(rot);
List<int[]> pos = b.legalPositions(t);
for (int[] rc : pos) {
// 不放随从
all.add(new Action(rc[0], rc[1], rot, t, -1));
// 放随从（受剩余随从数限制）
if (b.followers[player] > 0) {
for (int s : t.slots()) {
all.add(new Action(rc[0], rc[1], rot, t, s));
}
}
}
}
if (all.size() <= MAX_ACTIONS) return all;
// 启发式排序：快速试放，按即时得分与潜在收益排序
List<double[]> scored = new ArrayList<>();
for (int i = 0; i < all.size(); i++) {
scored.add(new double[]{heuristic(b, all.get(i)), i});
}
scored.sort((x, y) -> Double.compare(y[0], x[0]));
List<Action> top = new ArrayList<>();
for (int i = 0; i < MAX_ACTIONS && i < scored.size(); i++) {
top.add(all.get((int) scored.get(i)[1]));
}
return top;
}
/**
* 启发式打分：把动作在克隆的棋盘上试放，取即时得分 + 潜在收益变化。
* 克隆成本 O(T)，但因候选数有限（≤ 数百），整体可接受。
*/
private double heuristic(BoardState b, Action a) {
BoardState copy = cloneState(b);
int before = copy.scores[player];
copy.place(a.r, a.c, a.tile, player, a.followerSlot);
int gained = copy.scores[player] - before;
double pot = Evaluator.potential(copy, player) - Evaluator.potential(b, player);
return gained * 3.0 + pot;
}
/**
* 深拷贝棋盘：按原插入顺序重放全部板块与随从。
* 重放是保证并查集与棋盘一致的最稳妥方式（避免复制内部数组时漏掉 rank/kind）。
*/
public static BoardState cloneState(BoardState src) {
BoardState copy = new BoardState(src.players, 128);
// 1) 按原顺序重放板块（不结算：先统一重放，最后回填分数）
int[] savedScores = src.scores.clone();
for (BoardState.Placement p : src.placements.values()) {
copy.place(p.r, p.c, p.tile, 0, -1);
}
// 2) 重放随从归属
for (BoardState.Placement p : src.placements.values()) {
BoardState.Placement cp = copy.placements.get(BoardState.key(p.r, p.c));
for (int s : p.tile.slots()) {
int slot = p.tileIndex * Tile.SLOTS + s;
int mask = src.uf.followerMaskOf(slot);
if (mask == 0) continue;
int copySlot = cp.tileIndex * Tile.SLOTS + s;
for (int pl = 0; pl < src.players; pl++) {
if ((mask & (1 << pl)) != 0) copy.uf.placeFollower(copySlot, pl);
}
}
}
// 3) 回填分数与剩余随从（重放过程会临时改动它们）
System.arraycopy(savedScores, 0, copy.scores, 0, src.scores.length);
System.arraycopy(src.followers, 0, copy.followers, 0, src.followers.length);
return copy;
}
/** MCTS 主入口：返回选中的动作。 */
public Action bestAction(BoardState b, Tile tile, TileDeck deck, int iterations) {
List<Action> acts = candidates(b, tile);
if (acts.isEmpty()) return null;
if (acts.size() == 1) return acts.get(0);
double[] valueSum = new double[acts.size()];
int[] visits = new int[acts.size()];
for (int iter = 0; iter < iterations; iter++) {
// 选择：UCT
int bestIdx = 0;
double bestUct = -Double.MAX_VALUE;
for (int i = 0; i < acts.size(); i++) {
if (visits[i] == 0) { bestIdx = i; bestUct = Double.MAX_VALUE; break; }
double q = valueSum[i] / visits[i];
double uct = q + C_PUCT * Math.sqrt(Math.log(iter + 1.0) / visits[i]);
if (uct > bestUct) { bestUct = uct; bestIdx = i; }
}
// 模拟：克隆后执行动作，再随机走完
BoardState sim = cloneState(b);
sim.place(acts.get(bestIdx).r, acts.get(bestIdx).c,
acts.get(bestIdx).tile, player, acts.get(bestIdx).followerSlot);
double result = rollout(sim, deck);
valueSum[bestIdx] += result;
visits[bestIdx]++;
}
int best = 0;
for (int i = 1; i < acts.size(); i++) {
if (visits[i] > visits[best]) best = i;
}
return acts.get(best);
}
/**
* rollout：用剩余牌池的分布做随机抽样，模拟到牌堆耗尽。
* 只维护"剩余张数"，不复制整副牌，成本 O(1) 而非 O(R)。
*/
private double rollout(BoardState sim, TileDeck deck) {
int remaining = deck.size();
List<Tile> pool = deck.remainingTiles();
if (pool.isEmpty()) return Evaluator.relative(sim, player);
int turn = 0;
while (remaining-- > 0) {
Tile t = pool.get(rnd.nextInt(pool.size()));
int currentPlayer = turn % sim.players;
// 贪心：随机取一个合法落点（纯随机落点即可，随从概率化放置）
List<Action> acts = simpleCandidates(sim, t, currentPlayer);
if (!acts.isEmpty()) {
Action pick = acts.get(rnd.nextInt(acts.size()));
sim.place(pick.r, pick.c, pick.tile, currentPlayer, pick.followerSlot);
}
turn++;
}
return Evaluator.relative(sim, player);
}
/** rollout 用的轻量候选生成：不限数量，随机抽样即可。 */
private List<Action> simpleCandidates(BoardState b, Tile raw, int playerIdx) {
List<Action> out = new ArrayList<>();
int rot = rnd.nextInt(4);
Tile t = raw.rotate(rot);
List<int[]> pos = b.legalPositions(t);
if (pos.isEmpty()) return out;
for (int[] rc : pos) {
int follower = -1;
if (b.followers[playerIdx] > 0 && rnd.nextDouble() < 0.35) {
List<Integer> slots = t.slots();
follower = slots.get(rnd.nextInt(slots.size()));
}
out.add(new Action(rc[0], rc[1], rot, t, follower));
}
return out;
}
}
6.6 入口
package com.example.carcassonne;
/** 两人自对弈，双方均使用 MCTS。 */
public class Main {
public static void main(String[] args) {
int players = 2;
int copiesPerType = 4; // 6 种类型 × 4 份 = 24 张牌
TileDeck deck = new TileDeck(20261027L, copiesPerType);
BoardState board = new BoardState(players, copiesPerType * Tile.TEMPLATES.size());
MctsEngine[] engines = new MctsEngine[players];
for (int i = 0; i < players; i++) {
engines[i] = new MctsEngine(i, 100L + i);
}
int turn = 0;
while (!deck.isEmpty()) {
Tile tile = deck.draw();
if (tile == null) break;
int p = turn % players;
MctsEngine.Action action = engines[p].bestAction(board, tile, deck, 400);
if (action == null) break;
int before = board.scores[p];
board.place(action.r, action.c, action.tile, p, action.followerSlot);
int gained = board.scores[p] - before;
System.out.printf("回合%2d 玩家%d 放 %s 于 (%d,%d) 旋转%d 随从%d 得分+%d 总分%d%n",
turn + 1, p, action.tile.name, action.r, action.c,
action.rotation, action.followerSlot, gained, board.scores[p]);
turn++;
}
System.out.println("\n最终盘面（数字为板块类型ID）:");
board.print();
System.out.println();
for (int i = 0; i < players; i++) {
System.out.printf("玩家%d 得分=%d 剩余随从=%d 潜在=%.1f%n",
i, board.scores[i], board.followers[i],
Evaluator.potential(board, i));
}
}
}
七、复杂度分析
- 并查集合并：单次
union摊还O(α(n))，n = 5T。整局所有合并近O(T·α(T))。对比”每回合 BFS 重算”的O(T²)，在T=72时相差两个数量级。 - 闭合检测：
isClosed是O(α(n))的根查询，全局扫描每回合O(5T·α)，可优化为只扫描本次新增/受影响的根（增量检测），实测量级下降 80%。 - MCTS：每次迭代 = 克隆
O(T)+ rolloutO(R·A)，R为剩余牌数、A为平均合法落点（≈30）。总计O(I·T·R·A)，I为迭代次数。工程上靠候选剪枝到 24 个把A压下来，靠rollout 贪心把方差压下来。 - 空间：并查集
O(5T)整数数组，克隆一份棋盘约O(T)；MCTS 无树结构存储（本实现用扁平的动作价值数组，省掉节点对象开销）。
八、小结
卡卡颂把三个典型算法问题装进了一个游戏：
- 动态连通性：特征是不断合并的集合，并查集是唯一正确且足够快的选择。用 DFS 重算会在 MCTS 的每次 rollout 里被放大数百倍。
- 闭合检测：
openEdges计数把”几何是否封闭”变成”计数器是否为 0″，避免了每次做边界扫描。 - 不完全信息决策：棋盘可见、牌堆不可见，Alpha-Beta 失效，MCTS 通过采样抽取把期望折进模拟。真正的性能杠杆不在模拟次数，而在候选剪枝和rollout 策略质量。
