「学園アイドルマスター」Contest 自动打牌算法解析

本文介绍的算法根据 v1.6.0 版本游戏 apk 逆向解析获取，不排除人为解析失误以及后续版本算法被修改的情形。
请注意游戏 AI 打牌算法的实现方式与游戏版本强相关，自从 v1.0.0 以来几乎每个 minor 版本更新都会修改 AI 的运算逻辑。
如果您在实践中发现游戏内行为出现与本文介绍的算法相违的情况，则很有可能是出现了以上的情形，欢迎提供样本联系我进行进一步解析与修正。

大约在两个月以前，我发布了一篇介绍学玛仕自动打牌算法的文章。

文章发布一段时间后，收到了来自 kanon511 的回复，称游戏中的实际自动打牌算法和文章介绍的算法有所出入，存在几个疑问点，希望能得到解答。
实际上，文章发布后，从我自己在游戏中的 Contest 体验来看，也确实感受到游戏 AI 会做出一些不可解的举动与该文章的结论相悖。但本着「反正这些文章也没人看懒得管了」的想法，虽然感觉到有不对劲儿的地方，但还是懒得继续研究，把问题放置下去了。

但以此回复为契机，我决定把 Contest 的打牌机制彻底弄清楚，于是肝了周末两天时间，把整个逻辑理顺了。

结论是，游戏中的四种 ExamPlayType，

enum ExamPlayType {
  Unknown = 0;
  AutoPlay = 1;
  ManualPlayLesson = 2;
  ManualPlayLessonHard = 3;
  ManualPlayAudition = 4;
}

中，上一篇文章中介绍的算法是适用于 Manual 的三种场次的，但 Contest 和 GvG 所属的 AutoPlay 存在额外的逻辑。

本文主要针对 AutoPlay 的算法进行展开介绍。

Outline

首先对游戏中自动打牌 AI 的行为做一个概述。

我们都知道，如果以准确率至上为原则，以穷举法模拟出牌永远是最佳的选择。因为只要把每一回合的所有出牌选项都模拟一遍，那么只要取出最后得分最高的一次模拟，便可以绘制出一条整场游戏的最佳出牌路线。
但现实中受到运算资源限制，穷举法是几乎不可能被采用的。例如模拟一场共 10 个回合的游戏，需要对整场游戏进行 $3^{10}$ 次模拟运算，这还是没有考虑一回合可能使用多张卡的情况。

于是 QA 的开发者们想出来一种方式，以阶段性的穷举 (a.k.a. 贪心) 来实现 AI 的运算逻辑。我将其称作阶段性深度优先遍历模拟算法。

阶段性是指以固定的回合数为一个 calculateTurn，对 calculateTurn 内的所有出牌可能性进行穷举模拟。
深度优先是指该穷举以深度优先遍历的方式实现。

实现方式可在 Campus.InGame.Contest.ExamDepthFirstSearchSimulator 中找到。

calculateTurn

calculateTurn 是 AI 模拟一轮出牌路线的间隔回合数。

calculateTurn 的值根据 planType 而变，目前游戏中定义的如下：

enum ProducePlanType {
  ProducePlanType_Unknown = 0;  // out of boundary
  ProducePlanType_Common = 1;   // Free, calculateTurn = 2
  ProducePlanType_Plan1 = 2;    // Sence, calculateTurn = 2
  ProducePlanType_Plan2 = 3;    // Logic, calculateTurn = 2
  ProducePlanType_Plan3 = 4;    // Anomaly, calculateTurn = 1
}

从 Campus.InGame.ExamExtensions.GetContestCalculateTurn 中可找到获取 calculateTurn 的逻辑。

对每一轮 calculateTurn 内的出牌选项穷举后，对每个结果计算 evaluation，取 evaluation 最大的一条出牌路线作为在该 calculateTurn 内最终出牌结果。

例如，在一轮总共 10 个回合的游戏局中，如果 calculateTurn = 2，则将游戏拆分为剩余回合数为 [10, 9], [8, 7], [6, 5], [4, 3], [2, 1] 的 5 个阶段，分别穷举模拟每个阶段的所有出牌选项，取其中 evaluation 最大的路线最为该阶段的出牌结果。
需要注意的是，后一个阶段的运算是建立在前一个阶段的基础之上的，也就是说计算是一种 waterfall 的模型，而不是并行计算。

remainingTerm

remainingTerm 是在获取主数据库 ProduceExamAutoEvaluation 中的 evaluation 值的时候对应的剩余模拟回合数。

请注意 remainingTerm 和 remainingTurn 的书写区别。remainingTerm 并不是指剩余回合数，而是剩余模拟回合数。
remainingTerm 通过以下公式计算：

remainingTerm = remainingTurns / calculateTurn + 1

即，如果当前实际剩余回合数为 8，则对应的主数据库中的 remainingTerm 应为 8 / 2 + 1 = 5。

evaluation 计算时机

evaluation 的计算时机分为最后一回合和除最后一回合两种情况。

• 除最后一回合外：下一回合开始时，特殊效果（道具、场地、预约效果；例如再动道具，以及「成就」的延迟得分效果等）发动后，抽卡前（此时手牌数为 0）

• 最后一回合：回合结束时，手牌丢弃后；此时剩余回合数为 0

例如，要计算剩余回合数为 [8, 7] 这个阶段的 evaluation，计算的时机是在剩余 6 回合的开始时。
要计算 [2, 1] 这个阶段的 evaluation，由于是最后一回合所以计算时机是在最终回合结束时。

evaluation 计算方法

由于版本更新，在 v1.6.0 版本中，计算 evaluation 所需的参数从 v1.4.0 的 19 个增加到了 29 个，所以这里对其重新进行介绍，也方便没有读过前一篇文章的读者理解。
参数一览如下。

r1_JudgeParameter
r2_Block
r3_Stamina
r4_LessonBuff
r5_Review
r6_Aggressive
r7_min_ParameterBuffTurn
r8_min_StaminaConsumptionDownTurn
r9_min_StaminaConsumptionAddTurn
r10_min_BlockAddDown
r11_LessonDebuff
r12_min_ParameterDebuff
r13_BlockAddDownFix
r14_min_SlumpTurn
r15_StaminaConsumptionDownFix
r16_PlayableValueAddCount
r17_min_ParameterBuffMultiplePerTurn
r18_ParameterBuffTurnOver
r19_ExtraTurn
r20_Concentration
r21_Preservation
r22_FullPower
r23_FullPowerPointGetSumCount
r24_StanceConcentrationChangeCount
r25_StancePreservationChangeCount
r26_StanceFullPowerChangeCount
r27_holdCount
r28 主数据库 ProduceExamAutoGrowEffectEvaluation 中的对应值
r29 特殊参数

evaluation 的值由上述 29 个参数的和加上 0.0000999999975 后舍弃小数点取整而得：

$$\boxed{\begin{equation} \begin{split} E_\mathrm{eva} &=\lfloor \sum_{\mathclap{1\le n\le 29}}r_n + 0.0000999999975 \rfloor \end{split} \end{equation} }$$

这里就不举例说明了（懒），想看如何求 $r_n$ 值的读者可以参考上一篇文章里的例子。

为了方便我们将 r1 ~ r27 称为一般参数，r28 称为卡片增长评估参数，r29 称为特殊参数。

r1 ~ r27 一般参数

r1 至 r27 由主数据库 ProduceExamAutoEvaluation 中对应的 evaluation 值与当前游戏中对应的效果层数的积而得：

$$\boxed{r_n = v_n \times e_\mathrm{eva}}$$

其中，
$e_\mathrm{eva}$ 代表主数据库 ProduceExamAutoEvaluation 中对应的 evaluation 值，
$v_n$ 代表游戏中各种效果的数值：

v1_JudgeParameter: 当前已获得的总分
v2_Block: 当前元气值
v3_Stamina: 当前体力值
v4_LessonBuff: 当前集中值
v5_Review: 当前好印象值
v6_Aggressive: 当前やる気值
v7_min_ParameterBuffTurn: min(当前好调回合数, 剩余回合数)
v8_min_StaminaConsumptionDownTurn: min(当前体力消费减少回合数, 剩余回合数)
v9_min_StaminaConsumptionAddTurn: min(当前体力消费增加回合数, 剩余回合数)
v10_min_BlockAddDown: min(当前不安回合数, 剩余回合数)
v11_LessonDebuff: 当前緊張值
v12_min_ParameterDebuff: min(当前不调回合数, 剩余回合数)
v13_BlockAddDownFix: 当前弱气值
v14_min_SlumpTurn: 当前スランプ回合数
v15_StaminaConsumptionDownFix: 当前消費体力削減数
v16_PlayableValueAddCount: 当前可使用卡片数（每回合自然分配的使用次数也算在其内）
v17_min_ParameterBuffMultiplePerTurn: min(当前绝好调回合数，剩余回合数)
v18_ParameterBuffTurnOver: 当前好调回合数
v19_ExtraTurn: 额外追加回合数
v20_Concentration: 当前強気层数
v21_Preservation: 当前温存层数
v22_FullPower: 当前全力层数
v23_FullPowerPointGetSumCount: （暂不知含义，待 anomaly 实装后验证）
v24_StanceConcentrationChangeCount: （暂不知含义，待 anomaly 实装后验证）
v25_StancePreservationChangeCount: （暂不知含义，待 anomaly 实装后验证）
v26_StanceFullPowerChangeCount: （暂不知含义，待 anomaly 实装后验证）
v27_holdCount: 当前手牌数

r1 在 battle 中的特殊情况

当且仅当计算 v1 时，会有一个补充条件分支。
如果该局游戏是 lesson，则直接使用当前已获分数；如果该局游戏是 audition 或者 contest 之类的有三属性得分加成的 battle，则由如下公式计算：

$$\boxed{r_1 = \mathrm{round(}\frac {v_1 \times 3000} {P_\mathrm{da} + P_\mathrm{vo} + P_\mathrm{vi}} + 0.0000999999975 \mathrm{,\ 6)}}$$

其中 $P_\mathrm{da}, P_\mathrm{vo}, P_\mathrm{vi}$ 分别代表该场游戏三属性得分加成的千分数（去掉千分号的整数部分）。

注意最后要将得到的结果四舍五入取 6 位小数。

r28 卡片增长评估参数

这是 v1.6.0 中新增的评估参数，似乎与还未实装的 “卡片参数增长” 效果有关。
计算方法如一般参数类似，是将对应的卡片参数成长值与主数据库 ProduceExamAutoGrowEffectEvaluation 中对应的值求积后累加起来而得。

$$\boxed{r_{28} = \sum_n (G_n \times e_\mathrm{eva_n})}$$

其中，
$e_\mathrm{eva_n}$ 是主数据库 ProduceExamAutoGrowEffectEvaluation 中对应的 evaluation 值，
$G_n$ 是效果 ProduceCardGrowEffectType 的层数，
下标 $n$ 是 ProduceCardGrowEffectType 对应的枚举序号。

目前存在的 ProduceCardGrowEffectType 如下：

enum ProduceCardGrowEffectType {
  ProduceCardGrowEffectType_Unknown = 0;
  ProduceCardGrowEffectType_LessonAdd = 1;
  ProduceCardGrowEffectType_LessonReduce = 2;
  ProduceCardGrowEffectType_LessonCountAdd = 3;
  ProduceCardGrowEffectType_LessonCountReduce = 4;
  ProduceCardGrowEffectType_BlockAdd = 5;
  ProduceCardGrowEffectType_BlockReduce = 6;
  ProduceCardGrowEffectType_FullPowerPointAdd = 7;
  ProduceCardGrowEffectType_FullPowerPointReduce = 8;
  ProduceCardGrowEffectType_CostBuffReduce = 10;
  ProduceCardGrowEffectType_CostBuffAdd = 11;
  ProduceCardGrowEffectType_CostReduce = 12;
  ProduceCardGrowEffectType_CostAdd = 13;
  ProduceCardGrowEffectType_CostPenetrateReduce = 14;
  ProduceCardGrowEffectType_CostPenetrateAdd = 15;
  ProduceCardGrowEffectType_ParameterBuffTurnAdd = 16;
  ProduceCardGrowEffectType_ParameterBuffTurnReduce = 17;
  ProduceCardGrowEffectType_LessonBuffAdd = 18;
  ProduceCardGrowEffectType_LessonBuffReduce = 19;
  ProduceCardGrowEffectType_ReviewAdd = 20;
  ProduceCardGrowEffectType_ReviewReduce = 21;
  ProduceCardGrowEffectType_AggressiveAdd = 22;
  ProduceCardGrowEffectType_AggressiveReduce = 23;
  ProduceCardGrowEffectType_CardDrawAdd = 24;
  ProduceCardGrowEffectType_CardDrawReduce = 25;
  ProduceCardGrowEffectType_ParameterBuffMultiplePerTurnAdd = 26;
  ProduceCardGrowEffectType_ParameterBuffMultiplePerTurnReduce = 27;
  ProduceCardGrowEffectType_StaminaConsumptionDownTurnAdd = 28;
  ProduceCardGrowEffectType_StaminaConsumptionDownTurnReduce = 29;
  ProduceCardGrowEffectType_StaminaConsumptionAddTurnAdd = 30;
  ProduceCardGrowEffectType_StaminaConsumptionAddTurnReduce = 31;
  ProduceCardGrowEffectType_EffectAdd = 32;
  ProduceCardGrowEffectType_EffectDelete = 33;
  ProduceCardGrowEffectType_EffectChange = 34;
  ProduceCardGrowEffectType_CardStatusEnchantChange = 35;
  ProduceCardGrowEffectType_PlayTriggerChange = 36;
  ProduceCardGrowEffectType_PlayEffectTriggerChange = 37;
  ProduceCardGrowEffectType_PlayMovePositionTypeChange = 38;
  ProduceCardGrowEffectType_InitialAdd = 39;
}

r29 特殊参数

特殊参数用于计算非直接效果的持续效果的 evaluation，比如「至高のエンタメ」「天真爛漫」这种不便于直接评估的卡片效果。

顺带一提，在上一篇文章中对特殊参数的计算方式的描述有误，请以本文为准。

r29 由两个 multiplier 变量计算而得：

$$\boxed{\begin{equation} \begin{split} r_{29} &=\sum_n \lfloor m_{1n} \times m_{2n} + 0.0001 \rfloor \end{split} \end{equation} }$$

其中，
$m_{1n}$ 是 multiplier1，
$m_{2n}$ 是 multiplier2，
下标 $n$ 表示玩家所持有的第 n 个持续效果。

注意在累加之前要舍弃每个值的小数点后的值。

multiplier1

multiplier1 由如下计算方式而来：

$$\boxed{m_1 = \frac {P_\mathrm{coeff}} {1000} \times T}$$

其中，
$P_{\mathrm{coeff}}$ 是主数据库 ProduceExamAutoTriggerEvaluation 中 coefficientPermil 的千分数，
$T$ 是当前剩余回合数。

如果主数据库中不存在对应的 coefficientPermil，则默认赋值 coefficientPermil = 1。

multiplier2

multiplier2 由如下计算方式而来：

$$\boxed{\begin{equation} \begin{split} m_2 &=\sum_{\mathclap{1\le n\le 28}}(r_n' \times \frac {P_\mathrm{enchant}} {1000}) \end{split} \end{equation} }$$

其中，
$r_n'$ 是持续效果在当前回合发动的实际效果由前述一般参数计算而得的 evaluation，
$P_\mathrm{enchant}$ 是主数据库 ProduceExamAutoEvaluation 中对应的 examStatusEnchantCoefficientPermil 的千分数。

实例

这里以本次 GvG 中 B 号场为例来说明。
由于阶段性穷举计算的排列组合太多，这里就不把所有的组合都计算一遍了，只计算最终 AI 所选择的路线的其中一小段。

首先来看几张截图。

↑ 剩余 10 回合开始时

↑ 剩余 10 回合第一张卡使用时

↑ 剩余 9 回合开始时

↑ 剩余 8 回合开始时

为了方便图中为每张手牌标上了序号。
整场游戏共 12 个回合，produce plan 是 sence，角色倾向是集中。三属性奖励的千分数为：18230, 17970, 19500。
由文章前述部分可知道 sence plan 的 calculateTurn 是 2，也就是每 2 回合为一个 step，穷举其中所有组合。这里以上图中剩余回合数为 [10, 9] 时作为例子。

在剩余回合数为 [10, 9] 这个 step 中，由于剩余 10 回合时可以发动两次卡片，所以可选择的排列组合有：

序号	剩余 10 回合第 1 次	剩余 10 回合第 2 次	剩余 9 回合	Eva.
1	0	0	0	1236855
2	0	0	1	1238476
3	0	0	2	2073874
4	0	1	0	1921587
5	0	1	1	1923409
6	0	1	2	3253198
7	1	0	0	1236232
8	1	0	1	1238202
9	1	0	2	2073251
10	1	1	0	1741882
11	1	1	1	1743399
12	1	1	2	2924189
13	2	0	0	1920964
14	2	0	1	1923135
15	2	0	2	3252575
16	2	1	0	1741882
17	2	1	1	1743399
18	2	1	2	2924189

共 18 种。
注意剩余 10 回合第 2 次时手牌中只剩两张卡，所以只有序号 0 和 1 两种选项。

实际中游戏 AI 会在剩余 8 回合开始时计算以这 18 种方式打出牌后的 evaluation 并选出其中最大。最右的一列已经将计算结果展示出来。
在这里出牌序号为 0-1-2 时的 evaluation 值最大，所以 AI 最终选择以这个顺序出牌。

我们来手动计算一下这个 evaluation 是如何得出来的。

如果在剩余回合数为 [10, 9] 的 step 中以 0-1-2 的序号出牌，在剩余 8 回合开始时（还记得前面的 evaluation 计算时机吗？是在效果发动后、抽牌前）玩家所持有的状态中不为 0 的是：

v1 = 2149  // 已获分数
v2 = 2     // 元气
v3 = 39    // 体力
v4 = 15    // 集中
v7 = 3     // min(好调, 剩余回合数)
v16 = 1    // 当前可使用卡片数
v18 = 3    // 好调
特殊效果 1： ちょちょいのちょい
特殊效果 2： 至高のエンタメ

同时，这时的 remainingTerm 为：

remainingTerm = 8 / 2 + 1 
              = 5

按照前述的计算方式可以算得：

r1  = 2149 * 96 * 3000 / (18230 + 17970 + 19500) + 0.0000999999975
    = 11111.526132
r2  = 2 * 151
    = 302
r3  = 39 * 500
    = 19500
r4  = 15 * 5435
    = 81525
r7  = min(3, 8) * 1108
    = 3324
r16 = 1 * 0
    = 0
r18 = 3 * 1
    = 3

一般参数的和为 115765.526132。

r28 由于目前没有实装，所以为 0。

r29 特殊参数由两个特殊效果来计算。

对于「ちょちょいのちょい」，效果是「ターン終了時、パラメータ+4」。
「パラメータ+4」如果在评估时点发动，获得的分数是：

ceiling((4 + 15) * 1.5) * 18.23 = 529

所以，

multiplier1 = (1000 / 1000) * 8 // 注意这里即使「ちょちょいのちょい」只剩 3 回合，仍然用当前剩余回合数 8 来计算
            = 8
multiplier2 = 529 * 96 * (4000 / 1000)
            = 203136

r29_1 = int(multiplier1 * multiplier2 + 0.0001)
      = 1625088

对于「至高のエンタメ」，效果是「アクティブスキルカード使用時、パラメータ+5」。
「パラメータ+5」如果在评估时点发动，获得的分数是：

ceiling((5 + 15) * 1.5) * 18.23 = 547

所以，

multiplier1 = (900 / 1000) * 8
            = 7.2
multiplier2 = 547 * 96 * (4000 / 1000)
            = 210048

r29_2 = int(multiplier1 * multiplier2 + 0.0001)
      = 1512345

于是，

r29 = r29_1 + r29_2 = 3137433

最终，把一般参数和特殊参数加在一起：

evaluation = int(115765.526132 + 3137433)
           = 3253198

以上，在剩余回合数为 [10, 9] 的 step 中以 0-1-2 的序号出牌的 evaluation 值计算完毕。
如果你有兴趣可以试着计算一下 0-0-1 或者 2-1-1 等组合的 evaluation 值，与上表对比一下看看是不是以 0-1-2 的序号出牌后的 evaluation 值最大。

结语

简单来说，自动打牌的逻辑可以总结为 “预先穷举 n 回合后的所有可能性，并选择其中评估值最高的一个进行重现”。相比只计算手牌打出后的即时效果的手动打牌推荐算法来说，将场地、道具、预约等效果都考虑在内，可以说是很全面的一种实现方式。
但这种方式也有其局限性，毕竟局部的最优解并不代表着全局的最优解。这一点对于以绝好调为主的角色来说尤其能体现出。例如本次 GvG 的 A 场，一共 10 回合，道具效果开局附加 9 回合好调，这使得万圣 hiro 的专属卡在第一回合获得的评估值异常地低下，因为即使发动该卡增加了 5 回合好调，在评估时也只会考虑其不超过剩余回合数的层数，即会被视为只增加了 1 回合的好调，导致该卡几乎不会被打出。

这种阶段性深度优先遍历模拟算法同时也证实了许多同僚在研究 Contest 时注意到的所谓的 “未来视” 是确实存在的。并且也解释了在 ExamPlayType 为 AutoPlay 时，PlayableValueAdd 的 evaluation 值为什么全部为 0 —— 因为无论是否再动，其造成的结果都已经被计算在了评估值里。