圖5：DeepStack 在第五張牌開始前特定公共狀態(tài)下的攻擊性和分解迭代數(shù)量之間的方程。
算法DeepStack ：讓機器擁有“直覺”
DeepStack 是一大類的序列不完美信息博弈的通用算法。我們將解釋 DeepStack 在 HUNL（heads-up no-limit，一對一無限注）德州撲克中的作用。撲克游戲的狀態(tài)可以分為玩家的私人信息，即兩張牌面朝下的手牌，以及公共狀態(tài)，包括牌面朝上的公共牌和玩家的下注順序。游戲中公共狀態(tài)的可能序列形成公共樹，每個公共狀態(tài)有一個相關(guān)聯(lián)的子公共樹。見下圖6：
圖6：HUNL公共樹的一部分。紅色和湖藍色代表玩家的動作。綠色代表被翻開的公共牌。
DeepStack 算法試圖計算玩游戲的低利用率策略，即，求解一個近似的納什均衡（Nash equilibrium）。DeepStack在玩牌期間計算這個策略，公共樹的狀態(tài)如圖7所示。這種本地的計算使得 DeepStack 在對現(xiàn)有算法來說規(guī)模太大的游戲中可推理，因為需要抽象出的游戲的10的160次方?jīng)Q策點下降到10的14次方，這讓算法變得易處理。
圖7：DeepStack 概覽圖。（a）DeepStack 對在每個公共狀態(tài)的動作進行 re-solves，使用 depth-limited lookahead，其中子樹值的計算用訓練好的深度神經(jīng)網(wǎng)絡(luò)（b）通過隨機生成的撲克狀態(tài)在玩牌前進行訓練（c）最終狀態(tài)如圖3.
DeepStack 算法由三個部分組成：針對當前公共狀態(tài)的本地策略計算（local strategy computation），使用任意撲克狀態(tài)的學習價值函數(shù)的 depth-limited lookahead，以及預(yù)測動作的受限集合。
連續(xù) Re-Solving
Own Action：將對手的反事實值替換為在為我們自己選擇動作的解決策略中計算的值。使用計算策略和貝葉斯規(guī)則更新我們自己的動作范圍。
Chance Action：用從最后一次分解為這個動作計算出的反事實值替換對手反事實值。通過清除在任何新公共牌不可能的手牌范圍，更新我們自己的范圍。
Opponent Action：不用做什么。
Limited Lookahead 和 Sparse Trees
連續(xù)re-solving在理論上是可行的，但實際使用上不現(xiàn)實。它沒有維持一個完整的策略，除非游戲接近結(jié)束，re-solving本身就很棘手。例如，對于第一次動作的re-solving需要為整個游戲臨時計算近似解決方案。
Deep Counterfactual Value Networks
深度神經(jīng)網(wǎng)絡(luò)（DNN）已被證明在圖像和語音識別、自動生成音樂以及玩游戲等任務(wù)上是強有力的模型。DeepStack 使用DNN和定制的架構(gòu)作為它的 depth-limited lookahead其的價值函數(shù)。如圖8。訓練兩個獨立的網(wǎng)絡(luò)：一個在第一次三張公共牌被處理（flop網(wǎng)絡(luò)）后估計反事實值，另一個在處理第四張公共牌（turn網(wǎng)絡(luò)）后估計反事實值。一個輔助網(wǎng)絡(luò)用于在發(fā)任意公共牌之前加速對前面的動作的re-solving。
圖8：Deep Counterfactual Value Networks。網(wǎng)絡(luò)的輸入是pot的大小，公共牌和玩家范圍，玩家范圍先被處理為bucket ranges。輸出來自七個完全連接的隱藏層，被后處理以保證值滿足零和限制（zero-sum constraint）。
CMU 又被截胡
近日，新智元在報道中提到，被稱為“人腦 vs 人工智能：跟不跟 ” 的賽事將于1月11日在匹茲堡的 Rivers 賭場啟幕。比賽期間，職業(yè)撲克手 Jason Les， Dong Kim， Daniel McAulay 和 Jimmy Chou 將在20天的時間和 CMU 計算機程序玩120000手一對一不限注的德州撲克。
CMU的人工智能系統(tǒng)名叫 Libratus ，相比去年失敗的 Claudico，其終于策略發(fā)生了改變。 Libratus 會用 Bridges 計算機實時計算新的終局解決方法和算法，而不是像 Claudico 那么依賴終局。
另外，Claudico 常用的策略是 limping，這是一個撲克術(shù)語，指跟注混進去看看，而不是加注或者放棄。而 Libratus 偶爾也會這樣。