前言：本文的目标

游戏王：决斗链接是一款DBG手游，其核心策略体现在卡牌资源（手卡、场上卡）与环境资源（通招点、卡位、生命值）的管理与合理运用。 如果想要为决斗链接设计一个AI，这个AI需要有能力“理解”卡牌的两项内容：

  1. 卡牌效果

  2. 连锁响应

1决定了AI如何定义卡牌的价值，最大化地利用自己的卡牌； 2决定了AI如何安排卡牌的使用顺序以及对抗对手的卡牌效果。 由于当前版本的决斗链接的AI机制还相当原始，所以本文主要针对游戏王：决斗链接的AI机制进行一定的分析并提出一个更优地运用卡牌的AI方案。 以下是两点前置说明：

  1. 游戏AI并不是越聪明越好，在对战中“适当地”输给玩家，也是一种游戏设计思路（AI卡牌强度高于玩家却由于运营失误告负，可以给玩家带来智力上的优越感。）
  2. 本文中的AI指的是脚本、程序控制策略，如何用规则描述卡牌使用方法，而非基于机器学习的胜率最大化模型。

炉石传说与决斗链接：炉石传说AI策略设计

横向对比炉石传说与决斗链接的AI，由于炉石传说具有两个特点： 1. 基本没有回合外反制 2. 大部分随从卡在放置后次回合才可以进行攻击

因此，在设计AI时，只需要考虑场上信息与手卡信息，当做完全信息博弈来最优化地使用卡牌，就可以得到一个看上去像是个莽夫的AI了

此外，炉石的卡牌是有标准模型的，什么身材的随从价值多少费，1/1/1吸血的鱼人和1/2/1白板的随从哪个应该优先消灭都能用一条公式来衡量。

综上所述，对于炉石传说而言，一个简单好用的方案就是：将手牌中，所有卡牌的任意使用序列构造一个搜索树，搜索时根据费用限制做剪枝，这样每一条搜索路径都代表一个合法的卡牌使用序列。对于每一张牌，通过价值公式判断其使用目标，对于每一个序列，根据价值公式演算对应的卡牌依次用后，场面上达成的最终价值作为该分支的最终效用值。效用(Utility)最高的分支即作为AI本回合的执行策略。如果实际应用中AI计算速度偏慢的话，还可以做一些优化：将深度优先搜索改为基于部分效用值的权重优先搜索，然后基于算法已执行时间进行剪枝。

上面的说法可能过于复杂，下面用一句话总结：遍历所有可能序列，哪个效果好就用哪个，如果遍历需要的时间太长，就根据前几张牌的效果来判断优先验证哪个序列，保证AI执行时间有上限。

炉石传说与决斗链接：决斗链接AI策略分析

相比于炉石传说，决斗链接的AI就难做的多，原因如下：

  1. 决斗链接的卡牌往往需要组合使用，单卡价值难以量化，此外卡牌效果价值往往远高于卡牌数值价值，卡牌效果价值难以评估。
  2. 在上一条的基础上，决斗链接还具有回合外响应机制，当一套卡牌组合的其中关键的一张被无效后，整套Combo的意义就会被消解。
  3. 在上两条的基础上，决斗链接的卡牌效果还具有一个特性，那就是先支付代价，再结算效果，这也意味着当卡牌被无效时其代价会白白损失。
  4. 炉石传说的致胜策略强调“场面”，场面可以被量化，而游戏王的致胜策略强调“展开”，离目标还差多远很难被量化。
  5. 决斗链接有“无名决斗者”这种PVE玩法，在其中游戏的基础规则会改变（例如：不能使用怪兽效果等），无法设置一张卡片的静态价值。
  6. 决斗链接的单回合分为多个阶段，卡牌有不同的触发阶段与发动条件。

我们先看下决斗链接现在的AI是怎么做的，进行一些分析：

  1. AI对于血量变化的评估优先级极高，不会进行任何会导致自己损失更多血量的策略。
  2. 可能是由于1的原因，AI会献祭弧光龙上级召唤青眼白龙（不考虑怪兽特效而是更偏向召唤更高的攻击力，以达到最大化血量变化的目的）。
  3. 能利用卡牌效果，知道在合适的阶段使用，但无法判断卡牌连锁后的结果，对于卡组内的卡牌情况未知。
  4. 根据上述的原因5、6与分析3，AI必然是基于反演（先假设进行一项操作，以评估结果判断进行这项操作的收益）来判断卡牌的使用价值，每次可以行动时，对所有可发动卡牌进行遍历评估。

根据上述的分析，我们猜测性地反推决斗链接目前的AI逻辑：

  1. 卡牌使用优先级：
    • 使对手生命值归0
    • 减少我方即将受到的生命损失(生命回复>攻击表示召唤攻击力高于对方场上怪兽攻击力的怪兽>守备表示召唤守备力最高的怪兽)
    • 对对手造成生命伤害 (生命伤害>攻击表示召唤攻击力最高的怪兽)
    • 使自己场上怪兽攻击力最大化（特殊召唤/上级召唤/召唤>装备魔法卡）
    • 使己方场上魔法陷阱卡数量增加（不放置通常魔法卡）
    • 使敌方场上魔法陷阱卡数量减少
    • 使己方手卡增加
    • 使敌方手卡减少
  2. 基于1所述的卡牌使用优先级，对于所有可使用的卡牌，判断卡牌使用优先级并直接发动（由于卡牌的使用效果可能被对手连锁无效，所以不能提前决定所有卡牌使用顺序）。对于魔法陷阱卡，如果卡牌使用后无法使优先级内任何一项发生变化，则不发动。
  3. 在1、2基础上，若卡牌包含投骰子概率效果，假定一定得到对己方有利的效果；若卡牌包含指名、卡组检索（涉及到手卡、卡组中其他卡牌时），一律忽略该效果。

以上是我反推的决斗链接的AI逻辑，游戏中实际应用的策略可能在这套框架下加一些额外的规则。尽管这套AI逻辑通用性较强，不用考虑卡牌的具体用法，出了新卡也能沿用而不是一张卡写一组规则。但其中最大的问题是：卡牌的实际用法可能被忽视; AI无法考虑对手的陷阱卡反制; 无法利用卡牌配合打出Combo。卡组检索与定向检索是游戏王的核心机制，例如“吸血鬼转换”这张卡可以将卡组中的场地魔法卡“吸血鬼帝国”直接从卡组使用，但通用AI完全不考虑卡组检索逻辑；又例如“二者一两损”在有“吸血鬼帝国”存在的情况下发动可以实际上起到破坏对手一张卡牌的效果，但这套AI逻辑不会考虑其他卡牌的效果，因此，二者一两损的实际效果得不到发挥。

决斗链接AI策略优化

因此，这里提出一个更能发挥AI潜力的方案：

  1. 将卡组内容暴露给AI，使卡牌定向检索可以被预演。
  2. 参考之前在炉石章节提出的搜索树，对所有(己方可行策略Action与对手可行策略Action)建立搜索树，每条根节点到叶子节点的路径即为行动预测序列。以搜索树的形式对每条序列进行评估。
  3. 对于2中的“对手可行策略Action”，由于对手里侧表示卡牌内容是不可见的，以如下规则评估对手卡牌：
    • 定义对方场上覆盖陷阱卡数量为a,每回合内产生一次[0-1]范围的随机值p1， 若 p1< a * pt (pt为预设的陷阱卡发动概率,由策划配表或是机器学习得到具体值，可以先假设其为0.1), 将“受欢迎的卡”（游戏内置的玩家卡牌使用频率模组）中前五(具体数量配表或由程序根据AI性能动态控制)的陷阱卡与速攻魔法卡加入搜索树进行估计。
    • 当且仅当搜索树中涉及使对方里侧表示怪兽翻面的行为时，以pm（类似上文，但其值会小于pt）概率将怪兽卡加入搜索树中进行估计。基于怪兽可能星级(召唤时已知大概范围)、可能种族(由对手场上加墓地怪兽卡最高出现频率估计种族）将“受欢迎的卡”内符合条件的前五张怪兽卡加入搜索树进行估计。

以上AI策略有几项优点：

  1. 可以利用定向检索（吸血鬼帝国、沉默魔导士）
  2. 可以利用到卡牌的组合效果（龙之灵庙、黑魔导+千把刀）
  3. 可以考虑到对方的效果反制卡牌（风暴、优化自己卡牌使用顺序骗康）