引言
自走棋（Auto Chess）将策略棋盘与角色收集巧妙结合，玩家从共享卡池中抽取棋子，组建具有特定羁绊效果的阵容。核心算法挑战在于：给定当前持有的棋子和卡池状态，如何搜索出最强的羁绊组合？ 本文用Java实现阵容羁绊的回溯搜索算法，通过剪枝策略应对组合爆炸问题，并结合贪心近似解法，为每一步决策提供算法支撑。
核心机制建模
自走棋的核心数据结构包括：棋子、羁绊、阵容规则。
基础数据模型
import java.util.*;
/**
* 棋子：具有名称、费用、种族、职业等属性
*/
class ChessPiece {
public final String name;
public final int cost; // 购买费用（1-5金币）
public final String origin; // 种族（如：约德尔人、虚空）
public final String clazz; // 职业（如：刺客、法师）
public final int tier; // 星级（1-3星）
public ChessPiece(String name, int cost, String origin, String clazz) {
this.name = name;
this.cost = cost;
this.origin = origin;
this.clazz = clazz;
this.tier = 1;
}
@Override
public String toString() {
return name + "(" + cost + "金 " + origin + "/" + clazz + ")";
}
}
/**
* 羁绊定义：达到特定数量棋子时触发效果
*/
class Synergy {
public final String name; // 羁绊名称
public final String type; // "origin"或"clazz"
public final int[] thresholds; // 触发阈值，如[2,4,6]
public final String[] descriptions; // 各等级的描述
public final double[] powerBonus; // 各等级的战力加成系数
public Synergy(String name, String type, int[] thresholds,
String[] descriptions, double[] powerBonus) {
this.name = name;
this.type = type;
this.thresholds = thresholds;
this.descriptions = descriptions;
this.powerBonus = powerBonus;
}
/**
* 根据棋子数量计算当前激活的羁绊等级（0表示未激活）
*/
public int getActiveLevel(int count) {
int level = 0;
for (int t : thresholds) {
if (count >= t) level++;
}
return level;
}
/**
* 获取指定等级的战力加成
*/
public double getPowerAtLevel(int level) {
if (level <= 0) return 0;
return powerBonus[Math.min(level - 1, powerBonus.length - 1)];
}
}
/**
* 阵容：场上的棋子组合
*/
class Team {
public static final int MAX_SIZE = 9; // 最大上场人数
private final List<ChessPiece> pieces = new ArrayList<>();
public boolean addPiece(ChessPiece piece) {
if (pieces.size() >= MAX_SIZE) return false;
pieces.add(piece);
return true;
}
public List<ChessPiece> getPieces() {
return new ArrayList<>(pieces);
}
/**
* 统计各羁绊的触发数量
*/
public Map<String, Integer> countSynergies() {
Map<String, Integer> counts = new HashMap<>();
for (ChessPiece p : pieces) {
counts.merge(p.origin, 1, Integer::sum);
counts.merge(p.clazz, 1, Integer::sum);
}
return counts;
}
/**
* 计算阵容总战力（基础战力 + 羁绊加成）
*/
public double calculatePower(Map<String, Synergy> synergyMap) {
double basePower = pieces.stream().mapToDouble(p -> p.cost * 10.0 * p.tier).sum();
Map<String, Integer> counts = countSynergies();
double synergyBonus = 0;
for (Map.Entry<String, Integer> entry : counts.entrySet()) {
Synergy syn = synergyMap.get(entry.getKey());
if (syn != null) {
int level = syn.getActiveLevel(entry.getValue());
synergyBonus += basePower * syn.getPowerAtLevel(level);
}
}
return basePower + synergyBonus;
}
}
羁绊数据库
/**
* 羁绊数据库：预定义所有可用的羁绊规则
*/
class SynergyDatabase {
public static Map<String, Synergy> createDefaultSynergies() {
Map<String, Synergy> map = new HashMap<>();
// 种族羁绊
map.put("虚空", new Synergy("虚空", "origin",
new int[]{2, 4},
new String[]{"虚空单位获得护甲穿透", "虚空单位造成真实伤害"},
new double[]{0.15, 0.40}));
map.put("约德尔人", new Synergy("约德尔人", "origin",
new int[]{3, 6},
new String[]{"约德尔人有20%闪避", "约德尔人有50%闪避且攻击回复法力"},
new double[]{0.10, 0.35}));
map.put("海盗", new Synergy("海盗", "origin",
new int[]{3},
new String[]{"战斗后获得额外金币"},
new double[]{0.05}));
map.put("龙族", new Synergy("龙族", "origin",
new int[]{2, 4},
new String[]{"龙族获得魔法抗性", "龙族免疫魔法伤害"},
new double[]{0.20, 0.60}));
map.put("贵族", new Synergy("贵族", "origin",
new int[]{3, 6},
new String[]{"随机一名友军获得护甲和治疗", "所有友军获得护甲和治疗"},
new double[]{0.15, 0.45}));
// 职业羁绊
map.put("刺客", new Synergy("刺客", "clazz",
new int[]{3, 6, 9},
new String[]{"刺客+10%暴击", "刺客+20%暴击和+50%爆伤", "刺客+30%暴击和+100%爆伤"},
new double[]{0.08, 0.25, 0.55}));
map.put("法师", new Synergy("法师", "clazz",
new int[]{3, 6},
new String[]{"法师技能伤害+40%", "法师技能伤害+100%"},
new double[]{0.20, 0.50}));
map.put("骑士", new Synergy("骑士", "clazz",
new int[]{2, 4, 6},
new String[]{"骑士格挡15伤害", "骑士格挡30伤害", "骑士格挡60伤害"},
new double[]{0.10, 0.25, 0.50}));
map.put("射手", new Synergy("射手", "clazz",
new int[]{2, 4},
new String[]{"射手额外攻击1个目标", "射手额外攻击2个目标"},
new double[]{0.12, 0.30}));
map.put("护卫", new Synergy("护卫", "clazz",
new int[]{2},
new String[]{"战斗开始时护卫为相邻友军加护甲"},
new double[]{0.15}));
return map;
}
}
回溯搜索算法
回溯搜索通过递归尝试每一种可能的阵容组合，记录最优解。对于9人口上限和50个候选棋子，组合数为C(50,9) ≈ 2.5×10⁹，必须进行强力剪枝。
/**
* 阵容搜索器：使用回溯+剪枝寻找最优阵容
*/
public class TeamCompositionSolver {
private final List<ChessPiece> candidatePool; // 候选棋子池
private final Map<String, Synergy> synergyMap; // 羁绊规则
private final int maxTeamSize; // 人口上限
// 搜索状态
private double bestPower = 0;
private List<ChessPiece> bestTeam = new ArrayList<>();
private int searchCount = 0; // 统计搜索节点数
private int pruneCount = 0; // 统计剪枝次数
public TeamCompositionSolver(List<ChessPiece> pool,
Map<String, Synergy> synergyMap,
int maxTeamSize) {
this.candidatePool = new ArrayList<>(pool);
this.synergyMap = synergyMap;
this.maxTeamSize = maxTeamSize;
}
/**
* 主入口：启动回溯搜索
*/
public SearchResult solve() {
bestPower = 0;
bestTeam.clear();
searchCount = 0;
pruneCount = 0;
List<ChessPiece> current = new ArrayList<>();
backtrack(0, current, 0.0, new HashMap<>());
return new SearchResult(bestTeam, bestPower, searchCount, pruneCount);
}
/**
* 回溯核心：从index开始尝试选择棋子
* @param index 当前考虑的候选棋子索引
* @param current 当前已选阵容
* @param currentBasePower 当前阵容基础战力（不含羁绊，用于剪枝）
* @param synergyCounts 当前各羁绊的计数
*/
private void backtrack(int index, List<ChessPiece> current,
double currentBasePower, Map<String, Integer> synergyCounts) {
searchCount++;
// 终止条件：阵容已满或候选池耗尽
if (current.size() >= maxTeamSize || index >= candidatePool.size()) {
double power = calculateCurrentPower(current, synergyCounts);
if (power > bestPower) {
bestPower = power;
bestTeam = new ArrayList<>(current);
}
return;
}
// 剪枝策略1：剩余位置即使全选最高费棋子也无法超越当前最优
int remainingSlots = maxTeamSize - current.size();
int remainingCandidates = candidatePool.size() - index;
if (remainingCandidates < remainingSlots) {
pruneCount++;
return; // 棋子不够填满阵容
}
// 计算理论上界：当前基础战力 + 剩余位置最高费棋子的战力 + 最大羁绊加成
double upperBound = currentBasePower + getMaxPossibleAddition(index, remainingSlots);
if (upperBound <= bestPower) {
pruneCount++;
return; // 即使最优情况也无法超越当前最优
}
ChessPiece piece = candidatePool.get(index);
// 选择分支：尝试将当前棋子加入阵容
if (current.size() < maxTeamSize) {
current.add(piece);
synergyCounts.merge(piece.origin, 1, Integer::sum);
synergyCounts.merge(piece.clazz, 1, Integer::sum);
backtrack(index + 1, current,
currentBasePower + piece.cost * 10.0 * piece.tier,
synergyCounts);
// 回溯：撤销选择
synergyCounts.merge(piece.origin, -1, Integer::sum);
if (synergyCounts.get(piece.origin) == 0) synergyCounts.remove(piece.origin);
synergyCounts.merge(piece.clazz, -1, Integer::sum);
if (synergyCounts.get(piece.clazz) == 0) synergyCounts.remove(piece.clazz);
current.remove(current.size() - 1);
}
// 不选择分支：跳过当前棋子
backtrack(index + 1, current, currentBasePower, synergyCounts);
}
/**
* 计算当前阵容总战力（含羁绊加成）
*/
private double calculateCurrentPower(List<ChessPiece> team, Map<String, Integer> counts) {
double basePower = team.stream().mapToDouble(p -> p.cost * 10.0 * p.tier).sum();
double bonus = 0;
for (Map.Entry<String, Integer> entry : counts.entrySet()) {
Synergy syn = synergyMap.get(entry.getKey());
if (syn != null) {
int level = syn.getActiveLevel(entry.getValue());
bonus += basePower * syn.getPowerAtLevel(level);
}
}
return basePower + bonus;
}
/**
* 剪枝策略1辅助：计算剩余位置能带来的最大战力增量（乐观估计）
*/
private double getMaxPossibleAddition(int fromIndex, int slots) {
// 取剩余候选中费用最高的slots个
List<Integer> costs = new ArrayList<>();
for (int i = fromIndex; i < candidatePool.size(); i++) {
costs.add(candidatePool.get(i).cost);
}
costs.sort(Collections.reverseOrder());
double addition = 0;
for (int i = 0; i < Math.min(slots, costs.size()); i++) {
addition += costs.get(i) * 10.0 * 3; // 假设3星（乐观）
}
// 加上最大羁绊加成（乐观估计50%）
return addition * 1.5;
}
public static class SearchResult {
public final List<ChessPiece> bestTeam;
public final double bestPower;
public final int searchNodes;
public final int pruneNodes;
public SearchResult(List<ChessPiece> team, double power, int nodes, int prunes) {
this.bestTeam = team;
this.bestPower = power;
this.searchNodes = nodes;
this.pruneNodes = prunes;
}
@Override
public String toString() {
return String.format("最优阵容战力: %.1f | 搜索节点: %d | 剪枝: %d | 效率提升: %.1fx",
bestPower, searchNodes, pruneNodes,
(double)(searchNodes + pruneNodes) / Math.max(1, searchNodes));
}
}
}
贪心近似算法
当候选池过大时，回溯搜索仍可能太慢。贪心策略每一步选择”边际收益最高”的棋子，虽然不能保证全局最优，但在实际游戏中表现优异。
/**
* 贪心阵容构建器：每一步选择能带来最大边际战力提升的棋子
*/
public class GreedyTeamBuilder {
private final Map<String, Synergy> synergyMap;
public GreedyTeamBuilder(Map<String, Synergy> synergyMap) {
this.synergyMap = synergyMap;
}
/**
* 贪心构建阵容
* @param pool 候选棋子池
* @param teamSize 目标阵容大小
*/
public List<ChessPiece> buildGreedy(List<ChessPiece> pool, int teamSize) {
List<ChessPiece> selected = new ArrayList<>();
Set<ChessPiece> available = new HashSet<>(pool);
Map<String, Integer> synergyCounts = new HashMap<>();
for (int i = 0; i < teamSize && !available.isEmpty(); i++) {
ChessPiece bestPiece = null;
double bestMarginalGain = -1;
for (ChessPiece candidate : available) {
double gain = calculateMarginalGain(candidate, selected, synergyCounts);
if (gain > bestMarginalGain) {
bestMarginalGain = gain;
bestPiece = candidate;
}
}
if (bestPiece == null) break;
selected.add(bestPiece);
available.remove(bestPiece);
synergyCounts.merge(bestPiece.origin, 1, Integer::sum);
synergyCounts.merge(bestPiece.clazz, 1, Integer::sum);
}
return selected;
}
/**
* 计算加入某个候选棋子带来的边际战力提升
*/
private double calculateMarginalGain(ChessPiece candidate,
List<ChessPiece> current,
Map<String, Integer> currentCounts) {
double baseGain = candidate.cost * 10.0 * candidate.tier;
// 计算羁绊增量
double synergyGain = 0;
// 种族羁绊增量
int oldOriginCount = currentCounts.getOrDefault(candidate.origin, 0);
Synergy originSyn = synergyMap.get(candidate.origin);
if (originSyn != null) {
int oldLevel = originSyn.getActiveLevel(oldOriginCount);
int newLevel = originSyn.getActiveLevel(oldOriginCount + 1);
if (newLevel > oldLevel) {
// 羁绊升级，计算全队因此获得的额外加成
double teamBase = current.stream().mapToDouble(p -> p.cost * 10.0 * p.tier).sum();
synergyGain += teamBase * (originSyn.getPowerAtLevel(newLevel)
- originSyn.getPowerAtLevel(oldLevel));
}
}
// 职业羁绊增量（同理）
int oldClassCount = currentCounts.getOrDefault(candidate.clazz, 0);
Synergy classSyn = synergyMap.get(candidate.clazz);
if (classSyn != null) {
int oldLevel = classSyn.getActiveLevel(oldClassCount);
int newLevel = classSyn.getActiveLevel(oldClassCount + 1);
if (newLevel > oldLevel) {
double teamBase = current.stream().mapToDouble(p -> p.cost * 10.0 * p.tier).sum();
synergyGain += teamBase * (classSyn.getPowerAtLevel(newLevel)
- classSyn.getPowerAtLevel(oldLevel));
}
}
return baseGain + synergyGain;
}
}
完整运行示例
public class AutoChessSolver {
/**
* 创建测试用候选棋子池
*/
public static List<ChessPiece> createTestPool() {
List<ChessPiece> pool = new ArrayList<>();
// 虚空刺客体系
pool.add(new ChessPiece("卡兹克", 1, "虚空", "刺客"));
pool.add(new ChessPiece("雷克塞", 2, "虚空", "斗士"));
pool.add(new ChessPiece("卡莎", 4, "虚空", "刺客"));
pool.add(new ChessPiece("科加斯", 4, "虚空", "斗士"));
// 约德尔法师体系
pool.add(new ChessPiece("波比", 1, "约德尔人", "骑士"));
pool.add(new ChessPiece("璐璐", 2, "约德尔人", "法师"));
pool.add(new ChessPiece("维迦", 3, "约德尔人", "法师"));
pool.add(new ChessPiece("纳尔", 4, "约德尔人", "换形师"));
pool.add(new ChessPiece("提莫", 4, "约德尔人", "射手"));
// 贵族骑士体系
pool.add(new ChessPiece("盖伦", 1, "贵族", "骑士"));
pool.add(new ChessPiece("薇恩", 1, "贵族", "射手"));
pool.add(new ChessPiece("剑姬", 1, "贵族", "剑士"));
pool.add(new ChessPiece("卢锡安", 2, "贵族", "枪手"));
pool.add(new ChessPiece("蕾欧娜", 4, "贵族", "护卫"));
pool.add(new ChessPiece("凯尔", 5, "贵族", "骑士"));
// 通用刺客
pool.add(new ChessPiece("派克", 2, "海盗", "刺客"));
pool.add(new ChessPiece("阿卡丽", 3, "忍者", "刺客"));
pool.add(new ChessPiece("伊芙琳", 3, "恶魔", "刺客"));
pool.add(new ChessPiece("卡特琳娜", 3, "帝国", "刺客"));
// 通用法师
pool.add(new ChessPiece("莫甘娜", 3, "恶魔", "法师"));
pool.add(new ChessPiece("死歌", 5, "虚空", "法师"));
// 护卫
pool.add(new ChessPiece("布隆", 2, "冰川", "护卫"));
return pool;
}
public static void main(String[] args) {
List<ChessPiece> pool = createTestPool();
Map<String, Synergy> synergies = SynergyDatabase.createDefaultSynergies();
System.out.println("=== 自走棋阵容羁绊回溯搜索 ===\n");
System.out.println("候选棋子池（" + pool.size() + "个）:");
for (ChessPiece p : pool) {
System.out.println(" " + p);
}
// 1. 回溯搜索（适用于小规模候选池）
System.out.println("\n--- 回溯搜索（9人口）---");
TeamCompositionSolver solver = new TeamCompositionSolver(pool, synergies, 9);
TeamCompositionSolver.SearchResult result = solver.solve();
System.out.println(result);
System.out.println("最优阵容:");
for (ChessPiece p : result.bestTeam) {
System.out.println(" " + p);
}
// 2. 贪心算法（适用于大规模候选池）
System.out.println("\n--- 贪心近似算法（9人口）---");
GreedyTeamBuilder greedy = new GreedyTeamBuilder(synergies);
List<ChessPiece> greedyTeam = greedy.buildGreedy(pool, 9);
Team tempTeam = new Team();
for (ChessPiece p : greedyTeam) tempTeam.addPiece(p);
double greedyPower = tempTeam.calculatePower(synergies);
System.out.printf("贪心阵容战力: %.1f%n", greedyPower);
System.out.println("贪心阵容:");
for (ChessPiece p : greedyTeam) {
System.out.println(" " + p);
}
// 3. 对比分析
System.out.println("\n=== 算法对比 ===");
System.out.printf("回溯最优战力: %.1f%n", result.bestPower);
System.out.printf("贪心阵容战力: %.1f%n", greedyPower);
System.out.printf("贪心解与最优解比值: %.2f%%%n",
greedyPower / result.bestPower * 100);
// 4. 不同人口规模的搜索效率
System.out.println("\n=== 不同人口规模的搜索效率 ===");
for (int size = 3; size <= 9; size += 2) {
TeamCompositionSolver s = new TeamCompositionSolver(pool, synergies, size);
TeamCompositionSolver.SearchResult r = s.solve();
System.out.printf("人口%d: 最优战力=%.1f | 节点=%d | 剪枝=%d%n",
size, r.bestPower, r.searchNodes, r.pruneNodes);
}
}
}
算法复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 回溯搜索 | O(2^N) 最坏 | O(N) | N≤30的小规模候选池 |
| 带剪枝回溯 | O(C(N,K)) 实际远小于 | O(N) | 9人口、50棋子约需数秒 |
| 贪心近似 | O(K × N) | O(N) | 大规模候选池，实时决策 |
| 动态规划 | O(N × K × 2^S) | O(K × 2^S) | S=羁绊种类数，状态压缩 |
实际游戏中，由于人口上限（通常9人）和候选池大小的限制，带剪枝的回溯搜索在数十个候选棋子的情况下完全可行。对于超过100个候选的大规模场景，贪心算法在毫秒级给出接近最优的解。
扩展方向
-
装备与站位建模：将装备效果（如攻速、暴击）和棋盘站位（前后排）纳入战力计算，使阵容评估更精确。
-
对手反制搜索：不仅搜索己方最强阵容，还考虑对手可能的阵容分布，用博弈论寻找纳什均衡策略。
-
卡池概率动态更新：随着游戏进行，已出局的玩家释放其棋子回卡池，动态调整候选池的概率分布。
-
多目标优化：除战力外，同时优化经济曲线、血量容错、转型灵活性等多维度目标。
总结
本文用Java实现了自走棋的核心阵容搜索算法，展示了回溯搜索配合剪枝策略在组合优化问题中的强大威力。从理论上看，阵容选择是NP-hard的组合优化问题；但从实践角度，合理的剪枝和贪心近似使得算法在游戏中完全可用。读者可以在此基础上加入更多游戏机制（装备、站位、经济），打造更完善的自走棋AI助手。
