遊戲智能(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)