Facebook田淵棟：德州撲克上戰勝人類的AI究竟用的是什麼算法？| 解析
雷鋒網(公眾號：雷鋒網)按：本文作者田淵棟，卡耐基梅隆大學機器人系博士學位、上海交通大學碩士學位和學士學位，前Google無人車項目組成員，現任Facebook人工智能組研究員，主要負責Facebook的智能圍棋項目Dark Forest。文章轉載自知乎專欄，雷鋒網已獲授權。
最近聽説我的母校卡耐基梅隆大學德州撲克的AI Libratus以很大的優勢贏得了與職業玩家的比賽，非常興奮。在同時期，還有一篇來自加拿大阿爾伯塔大學（Univ of Alberta）的文章介紹了DeepStack，同樣在3000局的比賽中擊敗了幾位職業玩家。這樣在非對稱信息遊戲上人類再一次輸給了AI。
當然有AlphaGo的先例，這個對廣大吃瓜羣眾的衝擊可能沒有那麼大。但我個人覺得非對稱信息博弈的實用價值更大些。因為非對稱信息博弈的應用範圍非常廣泛，涵括我們每天遇到的所有決策，上至國家戰略，下至日常瑣事，全都可以以同樣的方法建模。
非對稱信息博弈難在哪裏？
比如説玩石頭剪刀布，在看不到別人出招的時候輪到自己出招，如果別人一直用石頭剪刀布各1/3的混合策略，那自己就會發現好像怎麼出招收益都是0，於是每次都出石頭，但是這樣的話，對手就可以利用這個策略的弱點提高自己的收益。所以一個好的算法就要求，基於別人已有策略得到的新策略儘可能地少被別人利用(low exploitability)。
這次的遊戲是Head-up unlimited Texas Hold'em，直譯過來是兩人無限注德州撲克。所謂兩人就是一對一的零和遊戲，不是多人遊戲。所謂無限注，就是在加籌碼的時候可以任意加（比如著名的把全部籌碼都押上的All in），而限注（limited），是指在加籌碼的時候只能加一個固定的數字（通常是前兩輪和大盲注一樣，後兩輪是大盲注兩倍）。
兩人有限注德州撲克（HULHE）因為玩家的選擇比較少可以暴力計算，已經在2015年被Univ of Alberta解決，得到的策略離納什均衡點非常近了（見這篇文章，發上了Science，AI叫Cepheus，用的方法是CFR+）。
這次CMU和Alberta用的方法，也和之前的類似，都是Counterfactual regret minimization (CFR)的變種。這次的主要貢獻在於：
CFR的思路非常簡單，從隨機策略開始，每次優化一個玩家的策略以提高其收益並反覆迭代，最後取平均策略作為最終策略。每次優化用的是悔恨值最小化（Regret minimization）的辦法，所謂悔恨值就是事後最優選擇的收益，減去當時選擇的收益，悔恨值最小化就是把到目前為止的累計悔恨值拿過來，看哪一步累計悔恨值高，以後就多走這一步，至於多走的概率，有各種算法（比如説Regret Matching和Hedge）。
對於兩人零和遊戲，可以證明CFR會收斂到納什均衡點，也就是“反正我就這麼一招，你怎麼也破不了”這樣的終極招數。所以計算機現在使用的算法，最終目的並不是要利用對方弱點獲得勝利，而是找出神功以達到無人可敵的境界。當然要達到這個境界，訓練過程中仍然是不斷找對方弱點讓自己變強。
CFR是個帶有理論界的通用算法，説它可以解決一切的非對稱信息博弈問題也不為過。但是世界上自然沒有免費午餐，在跑CFR的時候，每次都要遍歷一次遊戲所有可能的狀態，而任何一個稍微複雜點的遊戲都有指數級的狀態，所以運行時間上肯定是不能接受的。
這就有很多折中辦法，比如説狀態量化（認為2到9都是小牌用同一個策略處理），剪枝（對方不太可能走這一步，那就不用再搜索下去了），隨機採樣（採樣一些路徑以代替全部的遊戲分支），函數擬合（比如説用值網絡來代替深層搜索），等等。
總的來説，CFR和幾年前的RL很像，都是傳統AI的帶理論界的老方法，都是在現實問題中有指數複雜度，都是現在漸漸開始深度學習化，所以我相信以後會有更廣闊的發展。
雷鋒網特約稿件，未經授權禁止轉載。詳情見轉載須知。
資料來源：雷鋒網
作者/編輯：田淵棟
最近聽説我的母校卡耐基梅隆大學德州撲克的AI Libratus以很大的優勢贏得了與職業玩家的比賽，非常興奮。在同時期，還有一篇來自加拿大阿爾伯塔大學（Univ of Alberta）的文章介紹了DeepStack，同樣在3000局的比賽中擊敗了幾位職業玩家。這樣在非對稱信息遊戲上人類再一次輸給了AI。
當然有AlphaGo的先例，這個對廣大吃瓜羣眾的衝擊可能沒有那麼大。但我個人覺得非對稱信息博弈的實用價值更大些。因為非對稱信息博弈的應用範圍非常廣泛，涵括我們每天遇到的所有決策，上至國家戰略，下至日常瑣事，全都可以以同樣的方法建模。
非對稱信息博弈難在哪裏？
- 一方面是因為對於同樣的客觀狀態，各個玩家看到的信息不同，因此增加了每個玩家狀態空間的數目和決策的難度；
- 另一方面即使在同樣的狀態數下，解非對稱信息遊戲所需要的內存也要比解對稱信息要多得多，這個主要是對於對稱信息博弈來説，只要記得當前局面並且向下推演找到比較好的策略就可以了；但對非對稱信息博弈，只記得當前（不完整的）局面是不夠的，即使盤面上的情況相同，但對手之前的各種招法會導致事實上局面不同，只有把它們全都羅列出來進行分析，才能保證想出的應對策略不被別人利用。
比如説玩石頭剪刀布，在看不到別人出招的時候輪到自己出招，如果別人一直用石頭剪刀布各1/3的混合策略，那自己就會發現好像怎麼出招收益都是0，於是每次都出石頭，但是這樣的話，對手就可以利用這個策略的弱點提高自己的收益。所以一個好的算法就要求，基於別人已有策略得到的新策略儘可能地少被別人利用(low exploitability)。
這次的遊戲是Head-up unlimited Texas Hold'em，直譯過來是兩人無限注德州撲克。所謂兩人就是一對一的零和遊戲，不是多人遊戲。所謂無限注，就是在加籌碼的時候可以任意加（比如著名的把全部籌碼都押上的All in），而限注（limited），是指在加籌碼的時候只能加一個固定的數字（通常是前兩輪和大盲注一樣，後兩輪是大盲注兩倍）。
兩人有限注德州撲克（HULHE）因為玩家的選擇比較少可以暴力計算，已經在2015年被Univ of Alberta解決，得到的策略離納什均衡點非常近了（見這篇文章，發上了Science，AI叫Cepheus，用的方法是CFR+）。
這次CMU和Alberta用的方法，也和之前的類似，都是Counterfactual regret minimization (CFR)的變種。這次的主要貢獻在於：
- DeepStack用上了Continuous Resolving，即動態地解子游戲以避開存儲海量策略時內存不足的問題，還有值網絡；
- CMU用了endgame solving以細化狀態空間和策略空間，當然他們的文章似乎還沒有公佈，細節還不明朗（比如説剪枝應該是用上的）。
CFR的思路非常簡單，從隨機策略開始，每次優化一個玩家的策略以提高其收益並反覆迭代，最後取平均策略作為最終策略。每次優化用的是悔恨值最小化（Regret minimization）的辦法，所謂悔恨值就是事後最優選擇的收益，減去當時選擇的收益，悔恨值最小化就是把到目前為止的累計悔恨值拿過來，看哪一步累計悔恨值高，以後就多走這一步，至於多走的概率，有各種算法（比如説Regret Matching和Hedge）。
對於兩人零和遊戲，可以證明CFR會收斂到納什均衡點，也就是“反正我就這麼一招，你怎麼也破不了”這樣的終極招數。所以計算機現在使用的算法，最終目的並不是要利用對方弱點獲得勝利，而是找出神功以達到無人可敵的境界。當然要達到這個境界，訓練過程中仍然是不斷找對方弱點讓自己變強。
CFR是個帶有理論界的通用算法，説它可以解決一切的非對稱信息博弈問題也不為過。但是世界上自然沒有免費午餐，在跑CFR的時候，每次都要遍歷一次遊戲所有可能的狀態，而任何一個稍微複雜點的遊戲都有指數級的狀態，所以運行時間上肯定是不能接受的。
這就有很多折中辦法，比如説狀態量化（認為2到9都是小牌用同一個策略處理），剪枝（對方不太可能走這一步，那就不用再搜索下去了），隨機採樣（採樣一些路徑以代替全部的遊戲分支），函數擬合（比如説用值網絡來代替深層搜索），等等。
總的來説，CFR和幾年前的RL很像，都是傳統AI的帶理論界的老方法，都是在現實問題中有指數複雜度，都是現在漸漸開始深度學習化，所以我相信以後會有更廣闊的發展。
雷鋒網特約稿件，未經授權禁止轉載。詳情見轉載須知。
資料來源：雷鋒網
作者/編輯：田淵棟