游戏智能(Game AI)

2021 年 6 月 8 日
AI

在这稍作总结一些近几年的游戏AI算法，仅供入门了解。涉及并不全部，主要涉及技术点：强化学习，MCTS，博弈算法等

游戏本质是一个资源获取分配与博弈的过程，并且博弈的英文是Game，所以这里我们从Game（博弈）角度进行分类介绍（主线）和随机过程（MDPs）角度（副线）进行分析。

其中涉及到的一些冗余的额外知识总结在这里【基础知识】。

博弈论主要研究的是多人（2人以上）竞争合作的策略，且每个人的收益都受其他人的策略影响，这里我们主要考虑简单的竞争关系，比如二人零和博弈。

从博弈角度，基于一些研究比较多的游戏，大体可以分为三类

单机Atari，没有其他人参与
完美信息博弈，如棋盘完全可观测到的围棋、象棋（对手怎么走的看得到）
非完美信息博弈，扑克、麻将，dota、王者、星际等（对手状态行为不可完全知晓）

从以上三类我们依次讨论一些常规解法，solve a game！

单机类

单机Atari类，因为不涉及其他玩家，玩家的得分完全取决于自己的策略。这类游戏主要就是基于强化学习进行，比如当年DeepMind的DQN，openAI PPO等。提到强化学习一般都是基于MDP（Markov Decision Process）进行求解和分析，因为几年前写过一个Anticoder：强化学习基础知识是从直观角度进行介绍，这里从偏数学角度介绍下。

强化学习用MDP语言翻译就是：一个 $MDP<S,A,P,R,\gamma>$ （依次代表状态集合、动作集合、状态转移概率( $P: S\times A \rightarrow S$ )、奖励、折扣率（对未来奖励的折损，参考金融discount rate）），我们的目标是学习一个 $policy \ \pi(a|s)$ ，可以最大化回报（未来全部奖励） $G=\sum_{t=0}^{\infty}{\gamma^tR(s_t)}$ 。

为了求解policy，引入长期价值state utility(value) $v_\pi(s) = E_\pi[G_t|S_t=s]$ 和state-action utility(value) $Q_\pi(s,a)=E[G_t|S_t=s,A_t=a]$ .因为utility是通过未来价值定义，所以很容易得到V和Q的关系（Bellman Equation），并且天然它本身蕴含一个optimal substructure（Bellman optimal Equation），所以可以用DP来解。这里求解的核心如下

Bellman Equation

$v=R+\gamma Pv \rightarrow v = (I-\gamma P)^{-1}R$
$v_\pi(s) = \sum_{a\in A}{\pi(a|s) Q_\pi(s,a)}$
$Q_\pi(s,a) = R_s^a+\gamma \sum_{s'}{P_{ss'}^a} \sum_{a' \in A}{}\pi(a'|s')Q_\pi(s',a')$

求解核心方程，Bellman最优方程： $v_*(s) = \max_{a}Q_{*}(s,a)$

基本思想：就是因为v记录了每个state能拿到的未来价值，那其实贪心就可以保证最优。

最优策略： $\pi_*(a|s) = \begin{cases} 1& \text{if a = argmax}_{{a \in A}}Q_*(s,a)\\ 0& \text{otherwise} \end{cases}$

以上介绍的就是model base（就是我们可以得到P，整个东西都基本上是解析的），但其实我们看的更多是什么DQN，PPO等，这些都是model free类的探索式方法，因为大多时候我们是无法预测环境的。因为我们无法预测P，但是为了更好的解这个game，那就要不断去试，所以errors and trials以及如何权衡探索就是关键了。（其实后面会发现，基本sovle a game都是去大量的试，个人理解最核心的优化点就是如何试，如何剪枝，是否可以预测explore）

再简单罗列一下model free方法，也根据是否学习policy分为value base（DQN，DDPG）和policy base（PPO），还有一些结合的比如A2C等

RL的reward还是比较关键，甚至决定是否work。一些任务reward比较少的，涉及sparse reward优化方法，比如reward shaping；甚至有些任务没有reward，涉及Imitation learning，比如IRL，behavior clone（监督学习）等

完美信息博弈

接下来是围棋这种双人博弈游戏，每个人的操作大家都是可见的，这种叫完美信息（相对于打牌这种，你不知道对方拿了什么牌）。完美信息类主要解法就是模拟，比较经典的就是MCTS。MC本质上是一种爆搜的算法，如何高效搜索就是核心优化点，比如搜索的宽度(state-action value)和深度(state value)。比较火的就是alphaGo，alphaZero等这种，在搜索过程中结合强化学习，来提升搜索精准度和效率。

这里我们结合alphaGo类算法介绍

一般这种多步决策的game叫扩展式博弈，由game tree表示，node为state，边为action. alphaGo边存了action value Q(s, a)、visit count N(s, a)、prior probability P(s, a).

基本思想：类比RL中的state utility，我可以在每个s下暴力搜索，然后记录从s出发能拿到的平均reward，就可以得到当前策略下s的value，然后基于这些s的value进行行动并不断优化。主要分为一下几步，对应如图

selection：基于当前state信息，进行行动选择，考虑E&E. $a_t =argmax_{a \in A}{(Q(s,a) + u(s,a))}$ , u主要考虑explore比如PUCT $u(s,a) =\frac{ P(s,a)\sqrt{\sum_{b}{N(s,b)}}}{1+N(s,a)}$
expansion：遇到一个新的state s’时，我们不知道它价值，那就从这开始进行模拟，这个过程叫rollout，模拟策略叫rollout policy
simulation（Evaluation）：一般是rollout 到叶子结点也就是游戏结束，拿到reward
backprop：多轮模拟后，根据拿到的reward，从s’开始bp更新边状态（Q, N值）

alphaGo核心就是基于MCTS，使用policy net和value net来优化训练的搜索效率，最后基于max visit count N进行游戏。

alphaGo用到的网络主要有

SL policy：根据玩家局进行的监督学习，用于初始化prior probability P(s, a)
fast policy：也是监督学习学的，用于rollout policy，结构简单，预测快速
RL policy：基于SL policy热启，用 self-play进行RL训练
value net：预测当前s下self-play的winner（回归）

alphaGo的evaluation由rollout结果和value net决定， $V(S_L)=(1-\lambda)v_\theta(s_L)+\lambda z_L$

以上为训练阶段，之后采用max visit count N(s, a)进行行动！

alphaGo Zero

alphaZero主要的改进就是不使用监督学习（不使用domain knowledge），直接self-play，毕竟有钱有资源。我不懂围棋，但毕竟棋盘有限，规则严格，self-play能玩出个什么花，我不懂，噱头还是有的，故事还是要讲的，这个仁者见仁了！

除了这个在搜索上也有一些简化，比如不进行rollout模拟，直接使用网络value作为输出，我觉得这个还是很大的效率提升，对于像实时竞技MOBA类，就没有反馈时间给你；且只用一个网络输出value和policy $(p, v)=f_\theta(s)$ ，之前alphaGo搞那么多网络太冗余，且能有多大提升？

整体思想：还是基于MCTS为核心，然后基于学到的policy和value指导search；search根据N(s,a)输出一个policy $\pi(a|s)$ 结合游戏最终胜负z，更新网络参数，使v接近z，且p接近 $\pi(a|s)$ ，具体如下图，也很清晰

self-play的动作都是由MCTS决定 $a_t \sim \pi_t$ ， $\pi(a|s)= \sim N(s,a)^{1/\tau}\sum_{b}{N(s,b)^{1/\tau}}$

其中和alphaGo类似，边存了Q，P，N，其中 $Q(s,a)=1/N(s,a)\sum_{s'|s,a\rightarrow s'}{V'(s)}$

总结说就是，MCTS看成目标，他的输出 $\pi$ 和最终胜负z作为网络输出(p,v)的target

完美信息博弈，也是一个MDP，MDP特点就是具有马尔科夫性，所以当下的状态已经包含了全部历史信息！

非完美信息博弈

最后介绍一下扑克这种，你可以看到对手出什么牌，但是不能完全确定对方的牌，称为非完美信息扩展式博弈，非完美信息主要是基于博弈的纳什均衡类算法优化，代表有CFR（counterfactual regret minimization）

为了文章的完备性，简单介绍下纳什均衡。纳什均衡就是一种均衡算法，在多人博弈过程中，对方不改变策略条件下，我无论怎么改变都不能获得更多的收益。纳什均衡是一种保守的策略，并非最优策略，且在一般有限步的博弈中，都是存在纳什均衡策略的（但不一定找得到），几乎所有的博弈都是在找纳什均衡策略。

一般NE的研究都是基于二人零和游戏进行，这里默认此类。

此类算法比较火的就是德扑等的研究，简单介绍一些Notation，更多细节参考【基础知识】。

$<P, A, u>$

分别代表玩家集P, 动作集A, 回报u (在叶节点Z获取),

策略 $\sigma$ ( 玩家i策略 $\sigma_i$ ；其他玩家策略 $\sigma_{-i}$ )
history h：历史状态动作序列；history 集合H
非完美信息通过信息集infoset $I$ 表示，表达出用户无法确认对手的状态，所以infoset包含了所有可能的状态 $h \in I_i$ ,言外之意就是玩家无法获取s, 所以无法使用 $\sigma(s)$ ,只能用 $\sigma(I)$

Note：每个玩家的infoset内的节点，玩家是无法区分的，否则就不叫非完美信息了

玩家到达某个h的概率表达为 $\pi_i^\sigma(h)$

没有直观的图，大家应该比较难理解这些notation，上一个Kuhn Poker的图，图里解释非常清晰

所以我们可以看到，这里game主要基于Game tree表示，所以tree的每个节点就代表一个玩家的状态，边代表action，每个节点就是h (蕴含了祖先节点们)

基于以上Notation，纳什均衡(NE)可以表达为 $\forall i, u_i(\sigma_i^*, \sigma_{-i}^*)=max_{\sigma'_i}u_i(\sigma'_i, \sigma_{-i}^*)$

基本思想：找到一个策略 $\sigma_i^*$ 可以逼近NE!

这里涉及一些数学推论，具体可以参考文献，我们直接说结论。

Average Strategy

$\bar{\sigma_i}^t(a|I)=\frac{\sum_{t=1}^{T}{\pi_i^{\sigma^t}(I)\sigma^t(a|I)}}{\sum_{t=1}^{T}\pi_i^{\sigma^t}(I)}$

Strategy Regret：目前策略与最好策略的差距

$R_i^T=\frac{1}{T}max_{\sigma^*_i \in\Sigma_i}\sum_{t=1}^{T}{(u_i(\sigma_i^*,\sigma_{-i}^t)-u_i(\sigma^t))}$

定理1：二人零和博弈T时刻， $\forall i , R_i^T<\varepsilon$ ，则 $\bar{\sigma}^T_i \sim 2\varepsilon$ NE-strategy

所以，基于以上定理，我们只要能最小化strategy regret，则average strategy就是一个纳什均衡策略！

介绍几个概念

Counterfactual Regret

counterfactual value $v_i(\sigma,I)=\sum_{h \in I, z \in Z}{\pi_{-i}^{\sigma}(h)\pi^{\sigma}(z|h)u_i(z)}$

意义为其他玩家到达h，且由h到达z玩家i获得的平均回报，可以衡量这个infoset的价值

counterfactual regret $R_i^T(I,a)=\frac{1}{T}\sum_{t=1}^{T}{(v_i(\sigma^t_{I\rightarrow a}, I) - v_i(\sigma^t,I))}$

意义为infoset上采取行动a的收益，类似RL中的Q value

定理2：Counterfactual Regret $R_i^T(I, a)$ 为 $R_i^T$ 提供了上界

$R^T_i \leq \sum_IR^{T,+}_{i, imm}(I)$

$R^T_{i, imm}(I) = max_{a \in A(I)}R^T_i(I,a)$
$R^{T,+}_{i, imm}(I)=max(R^T_{i, imm}(I), 0)$

到这我们整理一下思路：我们为了得到NE策略，基于定理1知道我们需要最小化 $R_i^T$ ; 基于定理2我们知道最小化 $R_i^T$ 可以最小化它的上界（由counterfactual regret $R_i^T(I,a)$ 定义）,且 $R_i^T(I,a)$ 是定义在infoset上的，我们可以分别最小化每个infoset上的counterfactual regret，降低了复杂度。最后得到的average strategy为NE策略！

到这只剩最后一步，就是如何得到一个可以最小化每个infoset上的counterfactual regret的策略—-Regret Matching

$\sigma^{T+1}(a|I) = \begin{cases} \frac{R_i^{T,+}(I,a)}{\sum_{a' \in A(I)}{R_i^{T,+}(I,a')}}& \text{if denominator>0}\\ \frac{1}{|A(I)|}& \text{otherwise} \end{cases}$ ,其中 $R^{T,+}_i(I,a) = max(R_i^T(I,a), 0)$

以上就是完整的CFR算法！

这里一些核心优化点

$\sigma^t$ 以及 $R_i^t(I,a)$ 不同t时刻给不同权重的收敛速率研究DCFR
计算 $R_i^t(I,a)$ 模拟优化，比如Monte Carlo CFR，如何采样（outcome sampling、External Sampling）
如何整合一些状态和动作空间Abstraction
深度限制、搜索剪枝等

最后再从随机过程角度看

这里因为无法获取状态s，所以无法用MDP表示，因为只能观测到部分状态，所以非完美信息博弈可以用POMDP (partially observable Markov decision process)

POMDP因为只能获取部分观测，所以不具有马尔可夫性，需要历史全部行为和动作来表达当下信息(非马性)

所以传统的RL+Search算法不能直接拿来主义了！

但是牛逼的地方在于，POMDP可以通过引入belief state转化成continuous-state MDP

belief state通过引入概率总述存在于每个真实state的几率，总结了全部之前经历，所以通过引入belief state， POMDP具有马尔可夫性，则之前的方法就都可以用了！

Note: 这里引入的belief state其实就是类似机器学习中引入隐变量，然后基于贝叶斯公式得到所有的分布，最近一篇ReBeL就是类似的思想，把POMDP转化成continuous-state MDP，再结合RL+search拿到打败人类的非限制德扑的agent

具体细节就不展开了～

补充

应网友需求，在这补充些POMDP转化方法，让文章更加完备～

在部分可观测条件下我们无法使用policy $\pi(s)$ ，因为我们无法获取s（注意，s的意义就是完备的信息）。在一些应用领域包括游戏或者机器人等，最简单的方法就是基于一个最近的观测（或者最有可能的s）直接预测action，但是可能产生在很多相似的观测场景下都是同一个动作，无法做到最优，POMDP提供了一个系统解决方案

考虑一个POMDP $<S, A, P, R, \Omega, O>$ . 其中S, A, P, R与MDP一样， $\Omega ：S\times A \rightarrow \Pi(\Omega)$ 为观测函数，表达为 $O(s',a,o)$ ；玩家无法得到s，目标为最大化expected discounted future reward

belief state

很直观的思考就是引入不确定性，基于当下和历史的信息得到一个所有s的分布 (belief state)，那这个分布就包含了全部历史！所以基于belief state b，POMDP就为一个MDP
基于历史b，观测o，动作a来更新b’

$b'(s') = Pr(s'|o,a,b)=\frac{Pr(o|s',a,b)\sum_{s \in S}Pr(s'|a,b,s)Pr(s|a,b)}{Pr(o|a,b)}=\frac{O(s',a,o)\sum_{s \in S}P(s,a,s')b(s)}{Pr(o|a,b)}$
policy基于b进行决策 $\pi(a|b)$

现在就非常直观了，由于belief state是个s的分布，所以POMDP转化为了continuous state MDP，由以下组成 $<B,A, \tau(b,a,b'), \rho(b,a)>$ ，B为b集合；A为动作集

$\tau(b,a,b') = Pr(b'|a,b)=\sum_{o \in \Omega}{Pr(b'|a,b,o)Pr(o|a,b)}$ 为状态转移
$\rho(b,a)=\sum_{s \in S}{b(s)R(s,a)}$ 为reward

转化之后就可以解了，常规的解法是基于policy tree进行状态搜索剪枝，具体可以参考Witness算法

整个流程分为2步骤：1.更新b’. 2.根据b’进行决策.

具体细节就不展开了～

【NOTE】当然基于以上分析可以看出，其实POMDP就是通过belief state表达历史全部信息，进而转化为MDP问题；那除了POMDP框架，结合DNN，我们可以通过RNN来抽取历史信息，一样可以达到同样的目标！

参考文献

Equilibrium Finding for Large Adversarial Imperfect-Information Games
Mastering the Game of Go without Human Knowledge
A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play
Mastering the Game of Go with Deep Neural Networks and Tree Search
Combining Deep Reinforcement Learning and Search for Imperfect-Information Games
Planning and acting in partially observable stochastic domains
Monte Carlo Tree Search: A Review of Recent Modifications and Applications
Reinforcement Learning: An Introduction

游戏智能(Game AI)