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