強化學習具體是如何應用于德州撲克游戲的？

最近，強化學習（RL）的成功（如 AlphaGo）取得了大眾的高度關注，但其基本思路相當簡單。下面我們用大家最喜愛的無限制一對一德撲游戲模擬該問題。為了盡可能清楚地展示，我們將從零開始開發一個解決方案，而不需要預設的機器學習框架（如 Tensorflow）。讓我們用 Python3 Jupyter notebook 開始吧！

目錄

? 問題初始化

? 強化學習

? 特征：Q^ 的輸入

? 關于 Q^ 的線性模型

? 模擬撲克游戲

? 學習：更新 Q^

? 整合

? 結論

? 解釋模型

? 可視化策略

? 結論

問題初始化

規則提醒：德撲是一個2人無限制的撲克游戲，其中：

兩名選手均以 S 籌碼和隨機發放的2張手牌開始。

BB（大盲注）玩家下1.0個盲注，SB（小盲注）玩家下0.5個盲注。

SB 可以全押（all-in）或棄牌（fold）。

面對全押，BB 可以跟注（call）或棄牌。

我們可以將規則可視化為圖中所示的決策樹。游戲開始于 E，這時 SB 可以全押或棄牌。如果他棄牌，我們轉移到狀態 A，游戲結束。如果他全押，我們轉移到狀態 D，BB 必須在跟注和棄牌之間決定。如果一個玩家棄牌，另一個玩家就會得到盲點，如果兩個玩家全押，使用5張公共牌，并且金額按照撲克的正常規則進行分配。

這個游戲有著名的解決方案，其它方法有如虛擬游戲和直接優化。在這里，我們將使用 RL 估算解決方案。

這里有

不重復的 2 張手牌組合的初始化可能情況。因此，我們可以給所有手牌排序，并從 0 到 1325 編號。只要前后編號一致，具體的順序就不重要了。以下函數隱含地定義了這樣一個排序，并創建了從手牌編號到相關決策信息的映射：卡牌的排序和適用性。

請注意，輸出元組中的第一個元素（代碼中的 r2）始終排序靠前，如果有的話。例如，手牌編號 57 恰好是 6?2?，我們有：

當玩家全押時，他們平均獲得的底池（他們的權益）是由游戲規則給出的。文件pf_eqs.dat包含一個 numpy 矩陣 pfeqs（請參閱 numpy.savetxt，其中 pfeqs [i,j] 是當對手持有手牌 j 時持有手牌 i 的權益。

當然，有時候兩人起始手牌有一張牌是相同的，在這種情況下，他們不能同時被處理，這時取得他們的權益說不通。文件 pf_confl.dat（http://willtipton.com/static/pf_confl.dat）包含另一個 1326×1326 矩陣，其中每個元素為 0 或 1。A 0 表示組合沖突，a 1 表示組合沒有沖突。

例如，由于手牌 56 是 6?2?，57 是 6?2?，58 是 6?2?，我們有：

為什么結果不是正好是 0.5 呢？

強化學習

下面進入 RL 教程。RL 問題有三個重要組成部分：狀態（state）、動作（action）、獎勵（reward）。它們合在一起如下：

我們處于某「狀態」（即我們觀察到的世界狀態）。

我們使用這個信息來采取某「動作」。

我們會得到某種「獎勵」。

重復以上過程。

一遍又一遍地重復以上過程：觀察狀態、采取行動、獲得獎勵、觀察新的狀態、采取另一個行動、獲得另一個獎勵等。RL 問題只是找出如何選擇行動的方案以獲得盡可能多的獎勵。事實證明是一個非常普遍的框架?？梢酝ㄟ^這種方式考慮許多問題，解決這些問題有很多不同的方法。一般來說，解決方案涉及隨機游走，在不同狀態選擇各種行為，記住哪些組合能夠獲得獎勵，然后嘗試利用這些信息以便在未來做出更好的選擇。

RL 如何適用于德撲游戲呢？在任何決策點上，玩家知道他的2張底牌和他所處的位置，這就是狀態。然后他可以采取行動：要么棄牌，要么 GII。（GII 對于 SB 意味著全押，對于 BB 意味著跟注）。然后得到獎勵 ——這是玩家贏得的錢數，在最后的手牌中我們將使用玩家的總籌碼大小。例如，如果初始籌碼大小為 S=10，SB 全押 BB 棄牌，則玩家的獎勵分別為11和9。

我們會通過模擬手牌組合來找到游戲的策略。我們會同時處理兩個玩家的隨機手牌，讓他們做出關于如何玩的決定，然后觀察他們每次結束時最終得到多少錢。我們將使用該信息來學習（估計）Q 函數 Q(S,A)。Q 的參數為狀態 S 和動作 A，輸出值為在該狀態下采取該動作時得到的最終獎勵值。一旦我們有Q（或其一些估計），策略選擇就很容易：我們可以評估每個策略，看哪一個更好。

所以，我們這里的工作是估計 Q，我們將使用 Q^（發音為“Q hat”）來指代這個估計。初始化時，我們將隨機猜測一些 Q^。然后，我們將模擬一些手牌，兩名玩家根據 Q^ 做出決定。每次手牌之后，我們將調整估計值 Q^，以反映玩家在特定狀態下采取特定動作后獲得的實際值。最終，我們應該得到一個很好的 Q^ 估計，這就是確定玩家策略所需的所有內容。

這里需要注意一點 —— 我們要確保在所有狀態采取所有動作，每個狀態-動作組合至少嘗試一次，這樣才能很好地估計出最終每個可能的值。所以，我們會讓玩家在一小段時間ε內隨機地采取行動，使用他們（當前估計的）最佳策略。首先，我們應該積極探索選擇的可能性，頻繁地隨機選擇。隨著時間的推移，我們將更多地利用我們獲得的知識。也就是說，ε將隨著時間的推移而縮小。有很多方法可以做到這一點，如：

Q 被稱為「動作價值函數（action-value function）」，因為它給出了采取任何特定動作（從任何狀態）的值。它在大多數 RL 方法中有重要的作用。Q^ 如何表示？如何評估？是否在每次手牌之后更新？

特征：Q^ 的輸入

首先，Q^ 的輸入：狀態和動作。將這個信息傳遞給 Q 函數，作為位置（比如，SB為1，BB為0），手牌編碼（0到1325），動作（比如，GII為1，棄牌為0）。不過，我們將會看到，如果我們做更多的工作，會得到更好的結果。在這里，我們用7個數字的向量描述狀態和動作：

由函數 phi 返回的向量φ將是 Q 函數的輸入，被稱為特征向量，各元素都是特征（φ發音為“fee”）。我們將看到，我們選擇的特征可以在結果的質量上產生很大的不同。在選擇特征（稱為「特征工程」）中，我們利用了有關問題的相關領域知識。它和科學一樣藝術化。在這里，我們將判斷哪些為相關信息（在這種情況下）的知識用以下幾種方式編碼。讓我們來看看。

為方便起見，第一個元素始終為1。考慮接下來的四個元素。這些代表玩家的手牌。我們已經從手牌編碼轉換為 rank1、rank2 和 isSuited。這三個變量技術上給出與手牌編碼相同的信息（忽略特定的組合），但是該模型將更好地利用這種格式的信息。除了原始排序，我們還包含了 abs(rank1-rank2)**0.25。我們碰巧知道 connectedness 是德撲的重要屬性，正如其名。此外，如果所有特征都量綱一致，該模型的學習效果會更好。在這里，所有的特征大致介于0和1之間，我們通過將 rank 除以 numRanks 得到。

最后，如果 not isGII（即如果動作是棄牌），我們實際上將這些數字設置為0。我們知道，當玩家棄牌時，特定的持有手牌對結果沒有任何影響（忽略小概率的卡牌移除效果） ，所以我們在這種情況下刪除無關的信息。

現在考慮最后兩個元素。第一個直接編碼玩家的位置，但第二個同時取決于 isSB 和 isGII。為什么會這樣？稍后我們會顯示這個「交叉項」的必要性。

關于 Q^ 的線性模型

我們將學習一個線性函數用于估計的 Q^ 函數。這意味著我們將真正學習一個參數向量，通常稱為θ，它的長度（7）與特征向量相同。然后，我們將針對特定的φ來估計 Q^ ：

這里，下標 i 指代向量的特定元素，并將參數列表寫為 (φ;θ)，其表示 Q^ 的值取決于φ和θ，但是我們可以認為是φ的函數，θ為固定值。代碼很簡單：

雖然這個函數普遍使用，但是這個算法沒有什么特別之處，以使它成為這個問題的最佳選擇。這只是其中一種方法：將某些學習參數與某些特征相結合以獲得輸出，并且完全由我們定義一個θ向量，使它產生我們想要的輸出。然而，正確選擇θ將為我們很好的估計在有特定的手牌時采取特定行動的價值。

模擬撲克游戲

我們接下來要「玩」手牌了。我們將在接下來的幾個部分中進行，不過現在我們先構建三個重要的概念。這些概念與 RL 問題的三個重要組成部分相關：狀態、動作和獎勵。首先，狀態 —— 每次手牌，我們將以隨機發牌的方式為每個玩家初始化。

第二點，采取動作。每個玩家將使用當前的模型（由 theta 給出）和已知的手牌和身份（為 SB）來選擇動作。在以下函數中，我們估計 GII 和棄牌/FOLD（qGII 和 qFOLD）的值。然后選擇當下的最優項（1-ε），否則隨機選擇動作。返回所采取的動作，以及相應的價值估計和特征向量，這兩項我們之后會用到。

第三點，一旦我們知道每個玩家當下的手牌和動作，我們就模擬剩下的手牌來得到玩家的獎勵。如果任一個玩家棄牌，我們可以立即返回正確的獎勵值。否則，我們參考玩家的狀態和 equity，在正確的時間段隨機選擇一個贏家。

在玩家全押的情況下，我們用小技巧規避了模擬。與通過使用5張公共牌實際模擬游戲并評估玩家的手牌來查看誰贏不同，我們現在根據預先計算的概率隨機選擇一個贏家。這在數學上是等同的（瑣碎的證明忽略）；這只是一個更方便和更有計算效率的方法。

最重要的是，我們的學習過程沒有利用這些 equity 或有關游戲規則的信息。正如我們馬上將要看到的那樣，即使是完全模擬，學習過程也沒有什么不同，甚至 agent 還會與外部黑盒的撲克游戲系統進行交互從而可能遵循不同規則！那么，學習過程究竟如何進行？

學習：更新 Q^

一次手牌結束之后，我們需要更新 theta。對于每個玩家，我們已知其狀態和采取的動作。我們還有動作對應的估計價值以及從游戲中獲得的實際獎勵。從某種意義上說，實際獲得的獎勵是“正確解”，如果動作的估計價值與此不同，則我們的模型有誤。我們需要更新 theta 以使 Q^(φ;θ) 更接近正確的答案。

令φ'為一個玩家所在的特定狀態，R 是她獲得的實際獎勵。令 L=(R-Q^(φ;θ))^2。L 被稱為損失函數。L 越小，R 越接近 Q^(φ;θ)，如果 L 為0，則 Q^ 恰好等于 R。換句話說，我們想要微調整 θ，使 L 更小。（注意，有許多可能的損失函數，使得隨著 Q^ 越來越接近 R，L 越來越小。這里的損失函數只是一個常見的選擇）。

所以「更新Q」是指改變θ使 L 更小。有不止一種方法可以做到這一點，一種簡單的方法為隨機梯度下降（stochastic gradient descent）。詳見維基百科，但簡而言之，更新 θ 的規則是：

我們需要選擇「超參數」α（稱為學習率），它能控制每次更新的幅度。如果α太小，學習速度很慢，但是如果它太大，則學習過程可能無法收斂。將 L 代入到這個更新規則，并進行幾行微積分計算，我們得到

最后一行提供了更新參數的準則，我們將依此編寫代碼。注意這里的 θ 和 φ 都是長度為7的向量。這里更新參數的準則分別適用于每個元素。

整合

最后，該整合所有內容了。重復以下步驟：

隨機發給每個玩家手牌。令玩家各自選擇一個動作。得到結果。使用觀測到的（狀態，動作，結果）元組更新模型。

下面的函數 mc 實現了這種蒙特卡羅算法，并返回學習模型的參數 theta。

特別注意，上節推導出的參數更新規則在代碼中得到了實現。

結論

解釋模型

本例中，固定 S=10。

我們得到了數字，但是它們有意義嗎？實際上有幾種方法可以幫助我們判斷，并通過它們得到一些模型的解釋。

首先，我們考慮某些具體的情況。當 SB 棄牌（FOLD）時，她的估計值是多少？很容易得到，因為在這種情況下 φ 比較簡單。實際上，除了第1個（固定為1）和第6個（對應于 isSB）之外，所有元素都為0：phi = [1,0,0,0,0,1,0]。所以，我們的線性模型的 Q^ 僅相當于加總 theta 的第1個和第6個元素：

現在我們知道，根據游戲的規則，SB 選擇棄牌的價值是9.5。所以，非常酷，模型與真實情況非常接近！這是一個很好的邏輯判斷，并用例子說明了如何估計我們模型可能的誤差值大小。

另一種情況：BB 棄牌。只有 phi 的第1個元素是非零的，我們發現一個估計值

雖然不清楚正確的答案應該是什么，除了知道它肯定應該在9（如果 SB 總是 GII）和 10.5（如果 SB 總是棄牌）之間。事實上，這個數字更接近9而不是10.5，這與SB 更傾向于 GII 而不是相一致。

有一個更一般的方法來思考每個 θ 輸入。每個元素 θi 都會造成 Q^ 的增加，因為對應的特征 φi 會增加1。例如，當有合適的手牌同時執行 GII 策略時，θ 的第5個元素會增加1。因此，有適合手牌的估計獎勵值是0.22571655 —— 一個小的正向的獎勵?？瓷先ナ呛侠淼摹?/p>

θ 的第2個元素（對應于玩家排名較高的手牌）是6.16764962。這對應于特征：如果 isGII 則為 rank2/numRanks，否則為 0，意思為玩家排名較高手牌時的 GII 策略。這里 rank2 除以 numRanks，所以特征每增加 1 約等于 2 和 ace 之間的差。以一個額外的 6 BB 加上1個 ace 而不是 2 來取得勝利似乎是合理的。（但是，為什么你會覺得有第二張更高的手牌顯然是負的？）

檢查與第6個特征相對應的 θ 的元素（如果 isSB 則為 1，否則為 0），如果所有其它特征相等，則在 SB 中的附加值顯然為-0.15230302。我們或許可以把這解釋為位置上的劣勢：由于不得不首先采取行動的小懲罰。

然而，其它一切并不一定相同。如果 SB 執行 GII 策略，則最后一個特征也非零。所以，-0.15230302 為 SB 執行棄牌時的附加值。當執行 GII 時，我們總結最后一個特征的貢獻，發現獎勵為-0.15230302 + 0.14547532 = -0.0068277。顯然，當 SB 采取更激進的策略時，位置劣勢就變少了！

我們在這里看到，在本問題范疇內，選擇有意義的特征可以幫助我們有效地解釋結果。有趣的是，有一個被稱為 SAGE 的老規則來玩德撲游戲。這個規則在錦標賽現場容易被記住。原則是為你的手構建「能力指數」，它按照排序、合適性和手牌對子進行規則構建，然后用它來決定是否 GII。它們的特征組合與我們的特征組合相比如何？它們的結果怎么樣？

最后，為什么我們選擇 isSB 和 isGII 來決定最后一個特征，而不僅僅是 isGII？思考如下。（BB，FOLD）的估計值只是 θ 的第1個元素，所以這個第1個元素需要能夠隨意變化，以獲得正確的（BB，FOLD）值。那么，第6個元素是在 SB 中的額外貢獻，它需要能夠隨意變化以獲得正確的（SB，FOLD）。

一旦我們從棄牌轉換到 GII，元素 2-5 變為非零狀態，并根據玩家調整為特定值，但這些決策同樣適用于 SB 和 BB。該模型需要為 SB 全押提供一些不同于 BB 全押的決策。

假設我們的最終特征為：如果 isGII 則為 1，否則為 0。這不取決于玩家，所以 SB 和 BB 的估計值之間的唯一差異將在于 isSB 項。這個數字必須考慮在執行棄牌時 SB 和 BB 之間的差異，以及在執行 GII 時 SB 和 BB 之間的差異。模型必須在這兩個差異之間挑選一個數字，最終可能會導致一些差的折中。相反，我們需要：如果 isGII 和 isSB 則為 1，否則為 0。這樣，該模型可以區分 SB GII 與 BB GII 的增量值。

注意，該模型仍然無法捕獲很多細微的細節。例如，由于模型完全內置的函數形式，我們看到的 GII 的估計值的差異在兩個特定手牌組合下，如 A2 和 K2，對于 SB 和 BB 是完全相同的。不管θ的值如何，我們的模型都不可能預測。

這樣的模型有很高的偏差值（bias）。它是不靈活的，并且有一個強大的內置“觀點”來決定結果將是什么樣子。這就是為什么特征工程如此重要。如果我們沒有嘗試為算法提供精心設計的特征，那么它或許就沒有能力表征一個很好的解決方案。

可以為模型添加更多的特征，如其它交叉項，以獲得偏差較低的模型，但這可能會帶來缺點。這會很快失去可解釋性，也可能會遇到更多的技術問題，比如過擬合。（當然，在多數使用中這并不是首要問題，準確性比可解釋性更重要，而且有辦法處理過擬合）。

可視化策略

要找到完整的策略，我們將評估該模型，以了解在每個玩家的1326種手牌組合中，GII 或棄牌哪個更好：

看上去，對于 SB，大約55％的手牌選擇全押，而對于 BB，大約49％的時間選擇跟注：

最后，我們可以生成一些 SVG 來在 Jupyter 環境中繪制 GII 范圍：

我們怎么選擇呢？這里有我們期望的很多定性的特征：大的手牌很好、有對子很好、合適性好于不合適、SB 比 BB 打法松等。然而，邊界手牌的打法有時候會與在真正的平衡策略中不同。

結論

這篇介紹性的應用 RL 技術的文章給我們提供了一些合理的策略來進行德撲游戲。該學習過程不依賴于任何結構或游戲規則。而是純粹地通過讓 agent 自己進行游戲、觀察結果，并根據此來做出更好的決定。另一方面，重要特征工程需要一些領域專業知識才能學習一個好的模型。

最后，介紹一些背景。許多合適的問題都可以闡述為 RL 問題，也有許多不同的方法來解決它們。這里的解決方案可能具有以下特征：無模型（model-free）、基于價值的（value-based）、蒙特卡羅、策略型（on policy）、無折現型（undiscounted），并使用線性函數逼近器。

無模型：agent 通過采取行動和觀察獎勵來學習。它不需要任何關于如何產生這些獎勵的先驗知識（例如關于諸如范圍、權益、甚至游戲規則），也沒有試圖匆忙地學習這些東西。在撲克游戲中，事實上我們很了解某些手牌和動作能導致何種特定獎勵（我們可以利用這一點），但是在許多其它情形中并不是這樣。

基于價值的：我們專注于找出每個狀態下每個動作的價值，然后確定實際的策略，這或多或少是事后想法。還有基于策略的方法（如虛擬游戲），其重點是直接學習在每個狀態采取的動作。

蒙特卡羅：我們對整個手牌組合（情節）進行抽樣，并根據我們在手牌后獲得的價值進行學習?！笗r序差分（temporal difference）」方法可以在手牌結束之前對所有中間狀態的預期值進行估計，并且可以更有效地利用這些值來學習?？紤]到每個玩家在結束之前只能在德撲游戲中進行單一動作，雖然這對我們來說并不重要，但它可以在更多的狀態的問題上產生很大的影響。

策略型：我們估計玩家策略的價值。實際上這并不簡單。因為玩家有時候會采取隨機（非最優）的動作，所以我們估計的價值不是最優策略的值，這不是我們真正想要的。即使在探索非最優選擇的同時，更為復雜的「非策略（off policy）」方法也可以了解實際的最優策略。

無折現型：大多數 RL 問題從始至終包含很多（可能無限多）狀態。當然，在這種情況下，agent 希望最大化所有未來獎勵的總和，而不是最大化即刻獎勵。在這種情況下，假設相對于將來的某個時間獲得獎勵，agent 對于當下獲得獎勵的偏好較小。德撲游戲的一局手牌時間總是很短，所以我們不需要擔心。

線性函數逼近器：本例中學習的是一個線性函數，它將（狀態-動作）對的表征映射到數值。其它替代方法包括簡單的表（它將每個狀態的每個動作的估計數值單獨存儲），以及許多其它類型的函數逼近器。特別地，這種方法在神經網絡中非常成功。在某種程度上，這是因為它們不需要很多特征工程來獲得好的結果。神經網絡通常可以學習一組好的特征，以及學習到如何使用它們！但本文暫不探討這個話題。

參考文獻

Sutton 和 Barto 的教科書（http://incompleteideas.net/sutton/book/the-book-2nd.html）

David Silver 講座（http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html）