引言
炉石传说（Hearthstone）是暴雪娱乐开发的数字卡牌游戏。在对战中，玩家需要从牌库中抽取卡牌、管理法力水晶、计算伤害并做出最优决策。本文将用Java实现一个简化的炉石传说伤害评估系统，重点讲解蒙特卡洛模拟、概率期望计算与贪心最优出牌策略，帮助理解随机性游戏中的算法决策框架。
核心算法原理
1. 游戏状态建模
简化模型包含以下要素：
- 牌库：若干张卡牌，每张有费用、伤害、治疗效果
- 手牌：当前持有的卡牌集合
- 法力水晶：每回合增加1点（上限10），出牌需消耗法力
- 英雄生命：双方初始30点
- 场面：随从（简化模型中忽略，聚焦直伤法术）
2. 蒙特卡洛模拟
对于随机抽牌的回合，用蒙特卡洛估计期望伤害：
- 从当前牌库中随机抽取 $n$ 张手牌（$n$ 为抽牌数）
- 在当前法力限制下，用贪心或动态规划找最优出牌组合
- 重复 $N$ 次（如10000次），取伤害平均值
- 该平均值即为该回合的期望可输出伤害
3. 最优出牌子问题（0-1背包变体）
给定手牌集合和法力上限 $M$，选择出牌组合使伤害最大化：
$$
\max \sum_{i} d_i \cdot x_i \quad \text{s.t.} \quad \sum_{i} c_i \cdot x_i \leq M, \quad x_i \in {0,1}
$$
这是经典的0-1背包问题，可用动态规划 $O(n \cdot M)$ 求解。
Java完整实现
package hearthstone;
import java.util.*;
/**
* 炉石传说简化伤害评估系统
* 核心算法：蒙特卡洛模拟 + 0-1背包最优出牌 + 概率期望计算
*/
public class HearthstoneSimulator {
/**
* 卡牌定义
*/
static class Card {
String name;
int cost; // 法力消耗
int damage; // 对敌方英雄伤害
int heal; // 治疗效果
boolean isSpell; // 是否为法术（简化模型）
Card(String name, int cost, int damage, int heal) {
this.name = name;
this.cost = cost;
this.damage = damage;
this.heal = heal;
this.isSpell = true;
}
@Override
public String toString() {
return name + "(" + cost + "费," + damage + "伤)";
}
}
/**
* 游戏状态
*/
static class GameState {
List<Card> deck; // 牌库
List<Card> hand; // 手牌
int mana; // 当前法力水晶
int playerHealth; // 己方生命
int opponentHealth; // 敌方生命
int turn; // 当前回合
GameState(List<Card> deck) {
this.deck = new ArrayList<>(deck);
this.hand = new ArrayList<>();
this.mana = 0;
this.playerHealth = 30;
this.opponentHealth = 30;
this.turn = 0;
}
GameState copy() {
GameState gs = new GameState(new ArrayList<>(this.deck));
gs.hand = new ArrayList<>(this.hand);
gs.mana = this.mana;
gs.playerHealth = this.playerHealth;
gs.opponentHealth = this.opponentHealth;
gs.turn = this.turn;
return gs;
}
}
private Random rand = new Random(42);
/**
* 抽牌：从牌库随机抽取指定数量到手牌
*/
public void drawCards(GameState state, int count) {
for (int i = 0; i < count && !state.deck.isEmpty(); i++) {
int idx = rand.nextInt(state.deck.size());
state.hand.add(state.deck.remove(idx));
}
}
/**
* 核心算法：0-1背包求解最优出牌组合
* 返回最大可造成伤害值，并通过path参数记录选择的卡牌索引
*/
public int solveOptimalPlays(List<Card> hand, int mana, List<Integer> path) {
int n = hand.size();
int[][] dp = new int[n + 1][mana + 1];
// dp[i][m] = 考虑前i张牌、法力上限m时的最大伤害
for (int i = 1; i <= n; i++) {
Card card = hand.get(i - 1);
for (int m = 0; m <= mana; m++) {
dp[i][m] = dp[i - 1][m]; // 不出这张牌
if (card.cost <= m) {
int withCard = dp[i - 1][m - card.cost] + card.damage;
if (withCard > dp[i][m]) {
dp[i][m] = withCard;
}
}
}
}
// 回溯找出选择了哪些牌
if (path != null) {
int m = mana;
for (int i = n; i > 0; i--) {
if (dp[i][m] != dp[i - 1][m]) {
path.add(i - 1);
m -= hand.get(i - 1).cost;
}
}
Collections.reverse(path);
}
return dp[n][mana];
}
/**
* 贪心策略：按"伤害/费用比"降序选择
* 作为DP的对比基准
*/
public int greedyPlays(List<Card> hand, int mana, List<Integer> path) {
List<int[]> indexed = new ArrayList<>(); // [index, damagePerCost]
for (int i = 0; i < hand.size(); i++) {
Card c = hand.get(i);
int ratio = c.cost > 0 ? (c.damage * 100) / c.cost : c.damage * 100;
indexed.add(new int[]{i, ratio});
}
indexed.sort((a, b) -> Integer.compare(b[1], a[1]));
int totalDamage = 0;
int remainingMana = mana;
for (int[] item : indexed) {
int idx = item[0];
Card c = hand.get(idx);
if (c.cost <= remainingMana) {
remainingMana -= c.cost;
totalDamage += c.damage;
if (path != null) path.add(idx);
}
}
return totalDamage;
}
/**
* 蒙特卡洛模拟：估计当前回合的期望伤害
* @param state 当前游戏状态
* @param draws 本回合抽牌数
* @param simulations 模拟次数
* @return 期望伤害值
*/
public double monteCarloExpectedDamage(GameState state, int draws, int simulations) {
long totalDamage = 0;
for (int sim = 0; sim < simulations; sim++) {
GameState simState = state.copy();
// 模拟抽牌
drawCards(simState, draws);
// 计算该手牌下的最优伤害
int damage = solveOptimalPlays(simState.hand, simState.mana, null);
totalDamage += damage;
}
return (double) totalDamage / simulations;
}
/**
* 模拟完整对局：从初始状态到某一方生命归零
*/
public void simulateGame(List<Card> playerDeck, List<Card> opponentDeck, int maxTurns) {
GameState player = new GameState(playerDeck);
GameState opponent = new GameState(opponentDeck);
System.out.println("=== 对局开始 ===");
for (int turn = 1; turn <= maxTurns; turn++) {
// 玩家回合
player.turn = turn;
player.mana = Math.min(turn, 10); // 法力每回合+1，上限10
drawCards(player, 1); // 每回合抽1张
int playerDamage = solveOptimalPlays(player.hand, player.mana, null);
opponent.opponentHealth -= playerDamage; // 对对手造成伤害
System.out.printf("第%d回合 玩家输出%d伤害，对手生命%d%n",
turn, playerDamage, Math.max(0, opponent.opponentHealth));
if (opponent.opponentHealth <= 0) {
System.out.println("玩家获胜！");
break;
}
// 对手回合（简化：也使用最优策略）
opponent.turn = turn;
opponent.mana = Math.min(turn, 10);
drawCards(opponent, 1);
int opponentDamage = solveOptimalPlays(opponent.hand, opponent.mana, null);
player.opponentHealth -= opponentDamage;
System.out.printf("第%d回合 对手输出%d伤害，玩家生命%d%n",
turn, opponentDamage, Math.max(0, player.opponentHealth));
if (player.opponentHealth <= 0) {
System.out.println("对手获胜！");
break;
}
}
if (player.opponentHealth > 0 && opponent.opponentHealth > 0) {
System.out.println("达到最大回合数，平局！");
}
}
/**
* 卡组构建分析：评估不同卡牌组合的胜率
*/
public void deckAnalysis(List<List<Card>> candidateDecks, int simulationsPerDeck) {
System.out.println("=== 卡组强度分析 ===");
for (int d = 0; d < candidateDecks.size(); d++) {
List<Card> deck = candidateDecks.get(d);
double totalExpectedDamage = 0;
for (int sim = 0; sim < simulationsPerDeck; sim++) {
GameState state = new GameState(new ArrayList<>(deck));
state.mana = 5; // 评估第5回合
drawCards(state, 5); // 假设已抽5张
totalExpectedDamage += solveOptimalPlays(state.hand, state.mana, null);
}
double avgDamage = totalExpectedDamage / simulationsPerDeck;
System.out.printf("卡组%d: 第5回合期望伤害 = %.2f%n", d + 1, avgDamage);
}
}
public static void main(String[] args) {
HearthstoneSimulator sim = new HearthstoneSimulator();
// 构建示例卡组：以直伤法术为主的"火球法"
List<Card> fireMageDeck = Arrays.asList(
new Card("火球术", 4, 6, 0),
new Card("火球术", 4, 6, 0),
new Card("奥术飞弹", 1, 3, 0),
new Card("奥术飞弹", 1, 3, 0),
new Card("烈焰风暴", 7, 4, 0),
new Card("烈焰风暴", 7, 4, 0),
new Card("寒冰箭", 2, 3, 0),
new Card("寒冰箭", 2, 3, 0),
new Card("炎爆术", 10, 10, 0),
new Card("炎爆术", 10, 10, 0),
new Card("火把", 3, 4, 0),
new Card("火把", 3, 4, 0),
new Card("魔爆术", 2, 2, 0),
new Card("魔爆术", 2, 2, 0),
new Card("火冲", 2, 2, 0)
);
// 测试0-1背包最优出牌
GameState testState = new GameState(new ArrayList<>(fireMageDeck));
testState.mana = 5;
sim.drawCards(testState, 5);
System.out.println("手牌：" + testState.hand);
List<Integer> optimalPath = new ArrayList<>();
int optimalDamage = sim.solveOptimalPlays(testState.hand, testState.mana, optimalPath);
System.out.println("最优策略伤害：" + optimalDamage);
System.out.print("出牌顺序：");
for (int idx : optimalPath) System.out.print(testState.hand.get(idx) + " ");
System.out.println();
// 蒙特卡洛期望伤害
double expected = sim.monteCarloExpectedDamage(testState, 0, 10000);
System.out.printf("蒙特卡洛期望伤害（10000次模拟）：%.2f%n", expected);
// 对比贪心策略
List<Integer> greedyPath = new ArrayList<>();
int greedyDamage = sim.greedyPlays(testState.hand, testState.mana, greedyPath);
System.out.println("贪心策略伤害：" + greedyDamage);
}
}
复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 0-1背包（最优出牌） | $O(n \cdot M)$ | $O(n \cdot M)$ |
| 贪心出牌 | $O(n \log n)$ | $O(n)$ |
| 蒙特卡洛模拟 | $O(S \cdot n \cdot M)$ | $O(n \cdot M)$ |
| 抽牌模拟 | $O(k)$ | $O(k)$ |
其中 $n$ 为手牌数，$M$ 为法力上限（固定10），$S$ 为模拟次数。由于 $M \leq 10$ 是常数，背包实际为 $O(n)$。
扩展思考
- 随从系统扩展：引入随从后，状态空间急剧膨胀，需用Minimax + Alpha-Beta或MCTS处理
- 牌序敏感性分析：通过大量对局模拟，计算”起手留牌”的期望胜率，优化换牌策略
- 元游戏平衡：用蒙特卡洛评估不同卡组对抗矩阵，识别环境 dominant 卡组
总结
炉石传说的简化模型展示了随机游戏中的核心决策技术：蒙特卡洛模拟处理不确定性，0-1背包解决资源分配，贪心策略提供快速近似解。这些框架可迁移至其他带随机性的策略游戏，如杀戮尖塔、月圆之夜等卡牌构建类游戏。
