---

1. 游戏背景

今天将以“火影忍者Online”为案例，写一个智能布阵的脚本。我最早差不多是在十年前接触到这个游戏，相比于普通的回合制游戏，他里面有一个特别的机制，叫做 “追击”，简单来说，普通的回合制是你一下我一下，而“追击”是在一定的条件下会触发的额外攻击。例如下图的右侧说明，当某个角色进行攻击后，造成了“大浮空”的状态，当这个状态符合另一个角色追击的触发条件时，另一个角色将会进行追击。这就完成了一次追击，当触发的状态链路越长，则说明额外的攻击次数越多。

尽管最终对局输赢的因素非常多且复杂，但许多玩家包括我在内，希望自己的搭配出的阵容，能在每个回合内有一个较高的追击次数（期望），在同等战力水平下，这个目标确实会提高对局的赢面。而为了达到这个目标，依稀记得当年我常常在本子上记下各个角色的追击信息（触发条件，和造成的条件），并尝试不同的搭配，以及参考其他玩家的阵容搭配。

从专业一点的角度而言，尝试不同的阵容搭配，是属于启发式构造和仿真验证的方法，即我不确定这几个角色的追击能不能串起来，我要么进行不同的组合尝试，要么基于核心的角色进行阵容扩展；而参考其他玩家的阵容的方法，就有点像是元启发式方法中的群体智能，即每个玩家都是一个智能体，当有些玩家开发出强力的阵容时，且该阵容越强，大家模仿的速度越快，如果不能经常更新角色库，或者刷新战力系统（群体的多样性弱），那么最后大家都会稳定地趋于这些个阵容。

但是，随着游戏的发展，角色池越来越深，自主搭配往往不能实现过多的搭配方案，而越来越多样的角色特性和战力体系，使得大家在后期的阵容百花齐放，对这些方案的验证以及模仿具有较大的滞后性。而本文打算将该角色布阵问题视为一个组合优化问题，并用约束求解器CP-SAT进行求解。

2. 确定决策边界

这个布阵问题很典型的是 NP-Hard 问题，相比于典型的车辆路径问题，还多了很多特定的因素，例如，相同的追击路线（从一个状态到另一个状态）可能存在多个、并非所有忍者都会追击、以及追击路线可以出现多个子环路、追击路线并不需要回到初始的触发状态等等。这些特定因素使得这个问题比路径问题的问题规模更复杂，但同样的，这个问题在确定一个方案之后，却能在多项式时间内准确返回出方案的最长追击路线，但无法确定该追击路线就是最优的。

这里，我们对布阵问题的决策边界进行说明，智能布阵问题进行了一定的简化后，主要的决策内容包括：

1. 角色选择：在一个阵容当中，只能包含 $4$ 名忍者，其中一个是不可或缺的核心忍者，暂且称之为“主角”，另外 $3$ 个是从角色池当中挑选的辅助忍者，除了主角，这 $3$ 个辅助忍者的选择，是一个决策点；
2. 主角能力选择：辅助忍者的能力（攻击、奥义、追击）都是固定的，而主角的能力可以在若干组选择在确定，这是关于主角能力的选择决策，合适的选择能够与辅助忍者搭配出较好的追击方案。

本文中的决策目标是如何选择主角能力，搭配不同的辅助忍者，使得阵容 每回合的期望追击数最大。

注意：这里仅仅是以追击数作为目标，这个目标并不总能决定对局的输赢。

3. 布阵数据

建立布阵模型需要用到的基础数据如下。

3.1 追击状态

这个追击状态既可以是触发追击的状态，也可以是追击造成的状态。本文中只考虑如下的 $4$ 种追击状态：

all_status = ["倒地", "大浮空", "击退", "小浮空"]

在原游戏当中，还有一种能触发追击的特殊状态，叫 “xx连击”，例如 “十连击”，意思是某一方的阵容，连续击打另一方 $10$ 次及以上时，会触发一次 “十连击” 的追击。之所以不考虑该状态，最最主要的原因还是难以预估，首先，连击可以是一个角色的攻击或者技能造成连击（连击是有概率的，且连击率受角色特殊技能的影响会发生变化），其次如果连击是由一方多个角色完成，那就要考虑对战双方的 “先攻” 属性，例如己方全体先攻属性碾压另一方，那么只有等到己方所有角色攻击结束，对方才会开始行动。再次，连击还跟被攻击方的人数有关，例如，同样释放一个全体技能（单次打击），如果对方 $4$ 个人，那么会累计 $4$ 次攻击，如果对方 $1$ 个人，那么会累计 $1$ 次攻击。最后，是由于这种追击不会触发新的可被追击的状态，顶多会触发新的连击，因此，即使有，也是作为收尾动作，这使得少考虑该状态并不影响主体的追击路线。

3.2 角色信息

（1）可选择的角色池

接着是必须有待选择的角色池，需包含每个角色攻击、技能会触发的可被追击的状态，以及每个角色的可触发的追击弧，和可触发的次数。这里我们只罗列了 $9$ 个角色，如下所示：

character_pool = {
      "我爱罗": {"skill": "倒地", "attack": "大浮空", "chase": {"大浮空": ["倒地", 1]}},
      "凯": {"skill": "击退", "attack": "大浮空", "chase": {"大浮空": ["小浮空", 1]}},
      "佩恩-修罗道": {"skill": "", "attack": "大浮空", "chase": {"大浮空": ["击退", 2], "小浮空": ["大浮空", 1]}},
      "干柿鬼鲛": {"skill": "倒地", "attack": "小浮空", "chase": {"击退": ["小浮空", 1]}},
      "金角-尾兽状态": {"skill": "", "attack": "小浮空", "chase": {"小浮空": ["击退", 1]}},
      "宇智波带土-暴走": {"skill": "", "attack": "倒地", "chase": {"小浮空": ["倒地", 1]}},
      "阿斯玛": {"skill": "倒地", "attack": "击退", "chase": {"击退": ["倒地", 1]}},
      "佩恩-人间道": {"skill": "倒地", "attack": "小浮空", "chase": {"击退": ["倒地", 1]}},
      "西瓜山河豚鬼-秽土转生": {"skill": "击退", "attack": "小浮空", "chase": {"小浮空": ["大浮空", 2]}}
}

其中，skill 键的值为技能会触发的状态，attack 键的值为普通攻击会触发的状态，chase 表示追击路线，每个追击的起始状态为键，结束状态在值当中，而数字表示相应追击路线的可触发次数。

（2）主角的可配置项

前面提到，在阵容当中，主角必须在场，但区别于其他的角色，主角有专属的一系列攻击、技能和追击，因此决策的一块重点是要考虑主角的可配置项，可配置项包括：技能、攻击、追击、通灵兽（额外追击）。以雷属性的主角为例，可配置项如下：

central_character = {"skill": {"封雷斩": "", "千鸟刀": "倒地", "雷遁铠甲": ""},
                     "attack": {"体术攻击": "击退", "一闪": "倒地", "雷光暗杀剑": "大浮空"},
                     "chase": {"居合斩": {"击退": ["倒地", 1]}, 
                               "千鸟锐枪": {"大浮空": ["小浮空", 1]},
                               "雷光奈落剑": {"倒地": ["小浮空", 1]},
                               "弦月斩": {"小浮空": ["击退", 1]}},
                     "pet": {"镰鼬": {"击退": ["小浮空", 1]},
                             "地狱犬": {"小浮空": ["击退", 1]},
                             "幻术鸦": {"大浮空": ["小浮空", 1]},
                             "白虎": {"大浮空": ["击退", 1]},
                             "忍猿": {"大浮空": ["倒地", 1]},
                             "小蛞蝓": {"倒地": ["小浮空", 1]},
                             "蛤蟆忠": {"击退": ["倒地", 1]},
                             "鲛鲨": {"小浮空": ["大浮空", 1]}}}

根据不同的主角，配置不同的可配置项，以及配置可以解锁使用的通灵兽。

3.3 个性化要求

由于一些辅助角色非常强势，因此有些人在布阵时希望阵容必须包含这些角色，其他的角色再围绕主角和强势角色进行扩展。这里可以进行如下的配置：

strong_character = ["宇智波带土-暴走"]
assert len(strong_character) <= 3, "阵容角色不超过 4 位！"

由于 strong_character 中的角色是必上场角色，因此增加了一个判断是，除了主角外，必上场角色数量不能超过 $3$ 个。

此外，火影$OL$ 还有一个设定是，相同角色的不同系列不能同时上场，例如：“我爱罗”和“我爱罗[五代风影]” 就是同一个源体的不同系列的忍者，不能同时出现到一个阵容当中，如下配置一个 not_both_appear 变量：

not_both_appear = []

如果不能同时在阵容上的角色并不都同时出现在角色池中，not_both_appear可以不用设置。

4. 智能布阵模型

整体的思路很简单，就是把决策点设为决策变量，最后获得一个包含决策变量的目标函数（阵容单回合期望追击数最多），然后优化该目标函数返回决策变量的值，在建模时，由于变量的值相当于是未知的，此时模型需要囊括所有的决策空间。

首先建立模型框架：

from ortools.sat.python import cp_model

m = cp_model.CpModel()

4.1 主要的决策变量

通过前面在决策边界以及数据准备的介绍，大家也都知道主要的决策变量有哪些，包括：辅助角色的选择、主角技能、攻击、追击、通灵兽的选择，具体如下：

select_character = {character: m.NewBoolVar(name=character) for character in character_pool}
select_skil = {skill_name: m.NewBoolVar(name=skill_name) for skill_name in central_character["skill"]}
select_attack = {attack_name: m.NewBoolVar(name=attack_name) for attack_name in central_character["attack"]}
select_chase = {chase_name: m.NewBoolVar(name=chase_name) for chase_name in central_character["chase"]}
select_pet = {pet_name: m.NewBoolVar(name=pet_name) for pet_name in central_character["pet"]}

这些是主要的决策变量，而在添加约束的过程当中，会增加其他的辅助决策变量，之所以叫辅助决策变量，因为它们的值在主要决策变量确定之后也是确定的，但最终的目标函数与这些主要决策变量的关系又是非线性的，因此需要增加这些辅助变量作为过渡的桥梁。

4.2 约束条件（含辅助决策变量）

约束条件是对决策变量之间关系的限制，前面提到，为了使得从主要决策变量到目标函数的形式是线性的，需要加入一些辅助变量，而这些辅助变量和主要决策变量之间的关系也需要通过约束来进行限制。

（1）角色选择的硬约束

角色选择的硬性限制包括，前面提到的强力角色必定上场，且需要从角色池当中选出 $3$ 位角色，同时，如果有同源的角色，则他们不能同时上场，约束如下：

for character in strong_character:
      m.Add(select_character[character] == 1)
m.Add(sum(select_character[_] for _ in select_character) == 3)

for pair in not_both_appear:
      m.Add(sum(select_character[character] for character in pair) <= 1)

对于主角而言，每个可配置项都需要进行一次选择，代码如下：

m.Add(sum(select_skill[_] for _ in select_skill) == 1)
m.Add(sum(select_attack[_] for _ in select_attack) == 1)
m.Add(sum(select_chase[_] for _ in select_chase) == 1)
m.Add(sum(select_pet[_] for _ in select_pet) == 1)

（2）方案的追击弧数

当前面的主决策变量定义好之后，我们获得了一个“布阵方案”，当然在还没到最后求解之前，这个方案是未知的，但在模型当中，我们可以把中间的辅助变量都写成确定的约束关系，这样，当决策变量的值发生变化时，辅助变量也会联动发生变化，就有点类似于最终的结果取决于决策变量的值固定之后，因此我在后文有时会说成，基于给定的方案怎么怎么样，但这个“给定的方案”到最后才能确定。

这里基于一个给定的方案，我们就能知道每个状态到另一个状态的追击弧数量 chase_path_num ，包括辅助角色的追击弧，主角的追击弧，主角的通灵兽的追击弧，这能方便后续计算追击路线的长度。如下：

chase_path_num = {(status1, status2): 0 for status1 in all_status for status2 in all_status
                  if status1 != status2}
for character in character_pool:
    chase_info = character_pool[character]["chase"]
    for status1 in chase_info:
        status2 = chase_info[status1][0]
        chase_path_num[status1, status2] += chase_info[status1][1] * select_character[character]
for chase_name in central_character["chase"]:
    chase_info = central_character["chase"][chase_name]
    for status1 in chase_info:
        status2 = chase_info[status1][0]
        chase_path_num[status1, status2] += chase_info[status1][1] * select_chase[chase_name]
for pet_name in central_character["pet"]:
    chase_info = central_character["pet"][pet_name]
    for status1 in chase_info:
        status2 = chase_info[status1][0]
        chase_path_num[status1, status2] += chase_info[status1][1] * select_pet[pet_name]

（3）状态是否能直接转移

显然地，如果两个状态之间的追击弧数至少为 $1$，则说明这两个状态是能直接进行转移的，设立相应的辅助变量 direct_chase，约束如下：

direct_chase = {}
for status1 in all_status:
    for status2 in all_status:
        if status1 != status2:
            direct_chase[status1, status2] = m.NewBoolVar(name=f"direct_chase_{status1}_{status2}")
            m.Add(chase_path_num[status1, status2] >= 1).OnlyEnforceIf(direct_chase[status1, status2])
            m.Add(chase_path_num[status1, status2] == 0).OnlyEnforceIf(direct_chase[status1, status2].Not())

（4）方案的追击弧左右两端的状态数量

来看一个简单的例子：假如现有的追击弧有$(a\to b)(a\to c)(c\to b)(b\to a)(d\to e)$，那么从 $a$ 出发，最长的能触发的追击路线为 $a\to c\to b\to a$，显然，拼接两个弧的需要消耗左（$l$）右（$r$）两端各 $1$ 个状态，且起始状态固定，因此当某状态（i）能直接或间接去往另一些状态（$related\_statu{s}_i$ $\subset$ $all\_status$）时，从该状态出发可以触发的追击路线最长长度为：

$$l_i=\min (l_i-1,r_i)+\sum _j\min$$