红中麻将作为中国麻将的重要变体，因其红中赖子牌的设定而增加了巨大的策略复杂度。红中可以作为任意牌使用，这使得传统的麻将AI算法面临新的挑战。本文将深入探讨如何用Java构建一个具备实战能力的红中麻将AI，重点讲解Shanten数计算与蒙特卡洛树搜索(MCTS)两大核心算法。
一、问题建模：红中麻将的特殊性
标准麻将的牌型由34种基础牌构成（万、筒、条各1-9，东南西北白发中各1张）。红中麻将的赖子机制意味着：
- 红中可以作为任意牌补全面子（顺子、刻子）或对子
- 手牌中红中的数量直接影响牌型完成的可能性
- 传统Shanten算法需要扩展以处理”万能牌”
我们的目标函数是：在每一轮摸牌后，选择期望收益最大的打牌策略。
二、牌型编码与数据结构
高效的牌型表示是AI性能的基础。采用34维整数数组表示手牌，索引0-8为万子，9-17为筒子，18-26为条子，27-33为字牌。
public class Hand {
// 34种基础牌，索引: 0-8万, 9-17筒, 18-26条, 27-33字牌(东南西北白发中)
private final int[] tiles = new int[34];
private int redZhongCount = 0; // 红中赖子数量
// 红中在标准34牌中的索引为33
public static final int RED_ZHONG_INDEX = 33;
public void addTile(int index) {
if (index == RED_ZHONG_INDEX) {
redZhongCount++;
} else {
tiles[index]++;
}
}
public int[] getTiles() { return tiles.clone(); }
public int getRedZhongCount() { return redZhongCount; }
}三、核心算法：带赖子的Shanten数计算
Shanten数（向听数）表示手牌距离和牌（胡牌）还差几步。计算Shanten数是麻将AI的绝对核心——它决定了当前手牌的好坏程度，也是打牌决策的基础。
3.1 标准Shanten算法
标准麻将的Shanten数公式为：
Shanten = 8 – 2 × (面子数 + 雀头数) – (搭子数)
（14张手牌标准，13张时减1）
精确计算需要枚举所有可能的面子组合，采用深度优先搜索 + 记忆化。
public class ShantenCalculator {
/**
* 计算带红中赖子的Shanten数
* @param tiles 34维数组，不含红中
* @param redZhong 红中赖子数量
* @return 向听数，0表示听牌，-1表示已和牌
*/
public int calculateWithLaiZi(int[] tiles, int redZhong) {
int minShanten = Integer.MAX_VALUE;
// 枚举红中作为各种牌的分配方式
// 红中可以充当: 雀头、面子中的补缺牌、或者保持为红中本身
minShanten = dfs(tiles, redZhong, 0, 0, 0, false);
return minShanten;
}
/**
* DFS搜索最优牌型分解
* @param tiles 当前牌分布
* @param redZhong 剩余红中数量
* @param pos 当前扫描位置
* @param sets 已完成面子/刻子数
* @param pairs 雀头数(0或1)
* @param hasPair 是否已有雀头
*/
private int dfs(int[] tiles, int redZhong, int pos, int sets, int pairs, boolean hasPair) {
if (pos >= 34) {
// 计算剩余牌的搭子潜力
int taatsu = countTaatsu(tiles, redZhong);
return calculateShantenValue(sets, hasPair ? 1 : 0, taatsu, redZhong);
}
int minShanten = Integer.MAX_VALUE;
int count = tiles[pos];
if (count == 0) {
return dfs(tiles, redZhong, pos + 1, sets, pairs, hasPair);
}
// 策略1: 尝试组成刻子
if (count >= 3) {
tiles[pos] -= 3;
minShanten = Math.min(minShanten,
dfs(tiles, redZhong, pos, sets + 1, pairs, hasPair));
tiles[pos] += 3;
}
// 策略2: 用红中辅助组成刻子
if (count >= 2 && redZhong >= 1) {
tiles[pos] -= 2;
minShanten = Math.min(minShanten,
dfs(tiles, redZhong - 1, pos, sets + 1, pairs, hasPair));
tiles[pos] += 2;
}
// 策略3: 用2个红中辅助组成刻子
if (count >= 1 && redZhong >= 2) {
tiles[pos] -= 1;
minShanten = Math.min(minShanten,
dfs(tiles, redZhong - 2, pos, sets + 1, pairs, hasPair));
tiles[pos] += 1;
}
// 策略4: 尝试组成顺子（仅数牌）
if (pos <= 24 && pos % 9 <= 6) { // 数牌且可以组成顺子
if (count >= 1 && tiles[pos + 1] >= 1 && tiles[pos + 2] >= 1) {
tiles[pos]--; tiles[pos + 1]--; tiles[pos + 2]--;
minShanten = Math.min(minShanten,
dfs(tiles, redZhong, pos, sets + 1, pairs, hasPair));
tiles[pos]++; tiles[pos + 1]++; tiles[pos + 2]++;
}
// 用红中补缺顺子 (缺1张)
if (redZhong >= 1) {
// pos+1和pos+2存在，缺pos
if (tiles[pos + 1] >= 1 && tiles[pos + 2] >= 1) {
tiles[pos + 1]--; tiles[pos + 2]--;
minShanten = Math.min(minShanten,
dfs(tiles, redZhong - 1, pos, sets + 1, pairs, hasPair));
tiles[pos + 1]++; tiles[pos + 2]++;
}
// pos和pos+2存在，缺pos+1
if (count >= 1 && tiles[pos + 2] >= 1) {
tiles[pos]--; tiles[pos + 2]--;
minShanten = Math.min(minShanten,
dfs(tiles, redZhong - 1, pos, sets + 1, pairs, hasPair));
tiles[pos]++; tiles[pos + 2]++;
}
// pos和pos+1存在，缺pos+2
if (count >= 1 && tiles[pos + 1] >= 1) {
tiles[pos]--; tiles[pos + 1]--;
minShanten = Math.min(minShanten,
dfs(tiles, redZhong - 1, pos, sets + 1, pairs, hasPair));
tiles[pos]++; tiles[pos + 1]++;
}
}
// 用2个红中补缺顺子 (缺2张)
if (redZhong >= 2) {
if (tiles[pos + 2] >= 1) { // 缺pos和pos+1
tiles[pos + 2]--;
minShanten = Math.min(minShanten,
dfs(tiles, redZhong - 2, pos, sets + 1, pairs, hasPair));
tiles[pos + 2]++;
}
if (tiles[pos + 1] >= 1) { // 缺pos和pos+2
tiles[pos + 1]--;
minShanten = Math.min(minShanten,
dfs(tiles, redZhong - 2, pos, sets + 1, pairs, hasPair));
tiles[pos + 1]++;
}
if (count >= 1) { // 缺pos+1和pos+2
tiles[pos]--;
minShanten = Math.min(minShanten,
dfs(tiles, redZhong - 2, pos, sets + 1, pairs, hasPair));
tiles[pos]++;
}
}
}
// 策略5: 尝试组成雀头
if (!hasPair && count >= 2) {
tiles[pos] -= 2;
minShanten = Math.min(minShanten,
dfs(tiles, redZhong, pos, sets, pairs + 1, true));
tiles[pos] += 2;
}
// 策略6: 用红中辅助组成雀头
if (!hasPair && count >= 1 && redZhong >= 1) {
tiles[pos] -= 1;
minShanten = Math.min(minShanten,
dfs(tiles, redZhong - 1, pos, sets, pairs + 1, true));
tiles[pos] += 1;
}
// 策略7: 用2个红中组成雀头
if (!hasPair && redZhong >= 2) {
minShanten = Math.min(minShanten,
dfs(tiles, redZhong - 2, pos, sets, pairs + 1, true));
}
// 策略8: 不作为任何组合，保留为搭子/浮牌
minShanten = Math.min(minShanten,
dfs(tiles, redZhong, pos + 1, sets, pairs, hasPair));
return minShanten;
}
private int countTaatsu(int[] tiles, int redZhong) {
int taatsu = 0;
for (int i = 0; i < 34; i++) {
if (tiles[i] >= 2) {
taatsu++;
} else if (tiles[i] == 1 && redZhong >= 1) {
taatsu++;
redZhong--;
} else if (i <= 24 && i % 9 <= 7 && tiles[i] >= 1 && tiles[i + 1] >= 1) {
taatsu++;
} else if (i <= 24 && i % 9 <= 7 && redZhong >= 1 && (tiles[i] >= 1 || tiles[i + 1] >= 1)) {
taatsu++;
redZhong--;
}
}
return taatsu;
}
private int calculateShantenValue(int sets, int pairs, int taatsu, int redZhong) {
// 14张标准: 需要4面子+1雀头 = 5组
// 13张时: 4面子+1雀头，但有1张多余
int needed = 5;
int groups = sets + Math.min(pairs, 1);
int deficit = needed - groups;
// 剩余搭子可以补充 deficit
int usefulTaatsu = Math.min(taatsu + redZhong, deficit);
return deficit * 2 - usefulTaatsu - (pairs > 0 ? 0 : 1);
}
}3.2 算法优化：记忆化与剪枝
上述DFS算法在纯枚举时复杂度极高。实际工程中会采用以下优化：
- 牌型标准化：同种花色的1-9万与1-9筒在结构上完全等价，可以共享计算结果
- 位运算压缩：将34维数组编码为位掩码，加速比较和查表
- 查表法：对于不含红中的标准牌型，预先计算所有可能牌型的Shanten数存入查表库（约200MB），运行时直接查表
public class ShantenLookup {
// 使用HashMap存储查表: key为牌型指纹, value为Shanten数
private final Map<Long, Integer> lookupTable = new HashMap<>();
public int fastCalculate(int[] tiles, int redZhong) {
// 生成牌型指纹 (34种牌各4张，可用128位编码)
long fingerprint = encode(tiles);
Integer cached = lookupTable.get(fingerprint);
if (cached != null && redZhong == 0) {
return cached;
}
// 回退到精确计算
return new ShantenCalculator().calculateWithLaiZi(tiles, redZhong);
}
private long encode(int[] tiles) {
long fp = 0;
for (int i = 0; i < 34; i++) {
fp |= ((long) tiles[i] & 0xF) << (i * 4);
}
return fp;
}
}四、牌效评估：打牌决策引擎
知道手牌的Shanten数后，需要评估打哪张牌能让手牌最快进张（摸到有效牌）。核心指标是进张数（也叫有效牌数）。
public class TileEfficiencyEvaluator {
private final ShantenCalculator shantenCalc = new ShantenCalculator();
/**
* 评估打出每张牌的期望收益
* @return Map<牌索引, 进张数>
*/
public Map<Integer, Integer> evaluateDiscardOptions(Hand hand, Set<Integer> visibleTiles) {
Map<Integer, Integer> options = new HashMap<>();
int[] tiles = hand.getTiles();
int redZhong = hand.getRedZhongCount();
// 总牌数统计（用于计算剩余可用牌）
int[] totalTiles = new int[34];
Arrays.fill(totalTiles, 4);
for (int v : visibleTiles) {
totalTiles[v]--;
}
for (int i = 0; i < 34; i++) {
if (tiles[i] == 0) continue;
// 模拟打出这张牌
tiles[i]--;
int currentShanten = shantenCalc.calculateWithLaiZi(tiles, redZhong);
// 计算进张数: 摸到哪张牌能让Shanten数减少
int usefulTiles = countUsefulTiles(tiles, redZhong, currentShanten, totalTiles);
options.put(i, usefulTiles);
tiles[i]++; // 恢复
}
return options;
}
private int countUsefulTiles(int[] tiles, int redZhong, int currentShanten, int[] remaining) {
int count = 0;
for (int i = 0; i < 34; i++) {
if (remaining[i] <= 0) continue;
tiles[i]++;
int newShanten = shantenCalc.calculateWithLaiZi(tiles, redZhong);
tiles[i]--;
if (newShanten < currentShanten) {
count += remaining[i];
}
}
return count;
}
}五、蒙特卡洛树搜索(MCTS)：对手建模
仅考虑自身手牌的Shanten数是不够的——麻将是不完全信息博弈，对手的舍牌蕴含着他们的手牌信息。MCTS通过大量随机模拟来评估不同决策的长期收益。
5.1 MCTS四步骤
- 选择(Selection)：从根节点出发，按UCB1公式选择子节点，平衡探索与利用
- 扩展(Expansion)：到达未完全展开的节点时，添加新的子节点（可能的牌局状态）
- 模拟(Simulation)：从新节点开始，随机模拟牌局直到结束（和牌/流局）
- 回溯(Backpropagation)：将模拟结果（得分/胜负）回传到路径上所有节点
public class MahjongMCTS {
private static final int SIMULATION_COUNT = 1000;
private static final double EXPLORATION_CONSTANT = 1.414;
public int selectBestDiscard(Hand hand, GameState state) {
MCTSNode root = new MCTSNode(hand, state);
for (int i = 0; i < SIMULATION_COUNT; i++) {
MCTSNode node = select(root);
if (!node.isTerminal()) {
node = expand(node);
}
double reward = simulate(node);
backpropagate(node, reward);
}
return root.getBestChild().getDiscardTile();
}
private MCTSNode select(MCTSNode node) {
while (!node.isLeaf()) {
node = node.selectChildUCB(EXPLORATION_CONSTANT);
}
return node;
}
private MCTSNode expand(MCTSNode node) {
// 生成所有可能的打牌选项作为子节点
List<Integer> discards = node.getValidDiscards();
for (int tile : discards) {
node.addChild(tile);
}
return node.getFirstChild();
}
private double simulate(MCTSNode node) {
// 快速随机模拟: 随机补齐对手手牌和牌山，模拟到终局
GameSimulator simulator = new GameSimulator(node.getHand(), node.getState());
return simulator.randomPlayout();
}
private void backpropagate(MCTSNode node, double reward) {
while (node != null) {
node.update(reward);
node = node.getParent();
}
}
}
class MCTSNode {
private int visitCount = 0;
private double totalReward = 0;
private final List<MCTSNode> children = new ArrayList<>();
private MCTSNode parent;
private final int discardTile; // -1表示根节点
public MCTSNode selectChildUCB(double c) {
MCTSNode best = null;
double bestUCB = Double.NEGATIVE_INFINITY;
for (MCTSNode child : children) {
double ucb = child.getUCBValue(c, this.visitCount);
if (ucb > bestUCB) {
bestUCB = ucb;
best = child;
}
}
return best;
}
public double getUCBValue(double c, int parentVisits) {
if (visitCount == 0) return Double.POSITIVE_INFINITY;
return (totalReward / visitCount) + c * Math.sqrt(Math.log(parentVisits) / visitCount);
}
public void update(double reward) {
visitCount++;
totalReward += reward;
}
}5.2 模拟器设计
模拟器的关键是对手手牌的合理估计。不能简单随机分配，而应基于对手的历史舍牌进行约束采样：
public class GameSimulator {
/**
* 基于对手舍牌约束，生成合理的对手手牌分布
*/
public void sampleOpponentHands(GameState state) {
// 约束1: 对手已打出的牌不可能在他们手中
Set<Integer> opponentDiscards = state.getOpponentDiscards();
// 约束2: 对手未打出的牌，其持有概率与剩余牌数成正比
// 约束3: 对手连续打出某花色，该花色在其手中存量较低（偏听信号）
for (Player p : state.getOpponents()) {
int[] handEstimate = new int[34];
int[] remaining = state.getRemainingTiles();
for (int i = 0; i < 34; i++) {
if (opponentDiscards.contains(i)) {
handEstimate[i] = 0;
} else {
// 基于剩余牌数和对手行为模式估计
handEstimate[i] = probabilisticSample(remaining[i], p.getBehaviorProfile());
}
}
p.setEstimatedHand(handEstimate);
}
}
}六、系统架构与性能调优
一个完整的红中麻将AI系统架构如下：
┌─────────────────────────────────────────────┐
│ 决策层 (Decision Layer) │
│ ┌─────────────┐ ┌──────────────────┐ │
│ │ Shanten引擎 │◄────►│ MCTS决策器 │ │
│ │ (精确计算) │ │ (长期收益评估) │ │
│ └─────────────┘ └──────────────────┘ │
└──────────────────┬──────────────────────────┘
│
┌──────────────────▼──────────────────────────┐
│ 评估层 (Evaluation Layer) │
│ ┌─────────────┐ ┌──────────────────┐ │
│ │ 牌效评估器 │ │ 对手模型 │ │
│ │ (进张数) │ │ (行为分析) │ │
│ └─────────────┘ └──────────────────┘ │
└──────────────────┬──────────────────────────┘
│
┌──────────────────▼──────────────────────────┐
│ 数据层 (Data Layer) │
│ ┌─────────────┐ ┌──────────────────┐ │
│ │ 牌型编码器 │ │ Shanten查表库 │ │
│ └─────────────┘ └──────────────────┘ │
└─────────────────────────────────────────────┘性能优化要点
| 优化点 | 策略 | 效果 |
|---|---|---|
| Shanten计算 | 预计算查表 + 位运算编码 | 从秒级降到微秒级 |
| MCTS模拟 | 并行化(线程池/CompletableFuture) | 线性提升模拟次数 |
| 内存管理 | 对象池复用Hand/MCTSNode对象 | 降低GC压力 |
| JVM调优 | -XX:+UseG1GC -Xmx4g | 稳定低延迟 |
七、总结
红中麻将AI的核心挑战在于赖子牌带来的组合爆炸。通过以下策略可以构建一个具备实战能力的AI：
- Shanten计算是基石，DFS+红中分配枚举可以精确计算，配合查表法实现毫秒级响应
- 牌效评估（进张数）指导短期最优决策
- MCTS引入对手建模，评估长期收益，避免只关注自身牌型的短视行为
- 并行化与JVM调优将MCTS模拟次数提升到每秒数万次，使决策质量逼近理论最优
实际对战中，纯Shanten策略已经可以击败大多数人类新手，而加入MCTS后可以达到中级玩家的水平。若要进一步提升，需要引入深度学习价值网络来替代随机模拟中的快速走子策略——这将是下一代麻将AI的方向。
