游戏智能(Game AI)

  • 2021 年 6 月 8 日
  • AI

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

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

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

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

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

  1. 单机Atari,没有其他人参与
  2. 完美信息博弈,如棋盘完全可观测到的围棋、象棋(对手怎么走的看得到)
  3. 非完美信息博弈,扑克、麻将,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进行行动并不断优化。主要分为一下几步,对应如图

AlphaGo
  1. selection:基于当前state信息,进行行动选择,考虑E&E. a_t =argmax_{a \in A}{(Q(s,a) + u(s,a))} , u主要考虑explore比如PUCTu(s,a) =\frac{ P(s,a)\sqrt{\sum_{b}{N(s,b)}}}{1+N(s,a)}
  2. expansion:遇到一个新的state s’时,我们不知道它价值,那就从这开始进行模拟,这个过程叫rollout,模拟策略叫rollout policy
  3. simulation(Evaluation):一般是rollout 到叶子结点也就是游戏结束,拿到reward
  4. 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

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

MCTS,过程为a-c来几轮,然后d选择action

其中和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的图,图里解释非常清晰

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