最近聽說我的母?？突仿〈髮W(xué)德州撲克的AI Libratus以很大的優(yōu)勢(shì)贏得了與職業(yè)玩家的比賽，非常興奮。在同時(shí)期，還有一篇來自加拿大阿爾伯塔大學(xué)（Univ of Alberta）的文章介紹了DeepStack，同樣在3000局的比賽中擊敗了幾位職業(yè)玩家。這樣在非對(duì)稱信息游戲上人類再一次輸給了AI。
當(dāng)然有AlphaGo的先例，這個(gè)對(duì)廣大吃瓜群眾的沖擊可能沒有那么大。但我個(gè)人覺得非對(duì)稱信息博弈的實(shí)用價(jià)值更大些。因?yàn)榉菍?duì)稱信息博弈的應(yīng)用范圍非常廣泛，涵括我們每天遇到的所有決策，上至國家戰(zhàn)略，下至日常瑣事，全都可以以同樣的方法建模。
非對(duì)稱信息博弈難在哪里？
一方面是因?yàn)閷?duì)于同樣的客觀狀態(tài)，各個(gè)玩家看到的信息不同，因此增加了每個(gè)玩家狀態(tài)空間的數(shù)目和決策的難度；
另一方面即使在同樣的狀態(tài)數(shù)下，解非對(duì)稱信息游戲所需要的內(nèi)存也要比解對(duì)稱信息要多得多，這個(gè)主要是對(duì)于對(duì)稱信息博弈來說，只要記得當(dāng)前局面并且向下推演找到比較好的策略就可以了；但對(duì)非對(duì)稱信息博弈，只記得當(dāng)前（不完整的）局面是不夠的，即使盤面上的情況相同，但對(duì)手之前的各種招法會(huì)導(dǎo)致事實(shí)上局面不同，只有把它們?nèi)剂_列出來進(jìn)行分析，才能保證想出的應(yīng)對(duì)策略不被別人利用。
比如說玩石頭剪刀布，在看不到別人出招的時(shí)候輪到自己出招，如果別人一直用石頭剪刀布各1/3的混合策略，那自己就會(huì)發(fā)現(xiàn)好像怎么出招收益都是0，于是每次都出石頭，但是這樣的話，對(duì)手就可以利用這個(gè)策略的弱點(diǎn)提高自己的收益。所以一個(gè)好的算法就要求，基于別人已有策略得到的新策略盡可能地少被別人利用(low exploitability)。
這次的游戲是Head-up unlimited Texas Hold'em，直譯過來是兩人無限注德州撲克。所謂兩人就是一對(duì)一的零和游戲，不是多人游戲。所謂無限注，就是在加籌碼的時(shí)候可以任意加（比如著名的把全部籌碼都押上的All in），而限注（limited），是指在加籌碼的時(shí)候只能加一個(gè)固定的數(shù)字（通常是前兩輪和大盲注一樣，后兩輪是大盲注兩倍）。
兩人有限注德州撲克（HULHE）因?yàn)橥婕业倪x擇比較少可以暴力計(jì)算，已經(jīng)在2015年被Univ of Alberta解決，得到的策略離納什均衡點(diǎn)非常近了（見這篇文章，發(fā)上了Science，AI叫Cepheus，用的方法是CFR+）。
這次CMU和Alberta用的方法，也和之前的類似，都是Counterfactual regret minimization (CFR)的變種。這次的主要貢獻(xiàn)在于：
DeepStack用上了Continuous Resolving，即動(dòng)態(tài)地解子游戲以避開存儲(chǔ)海量策略時(shí)內(nèi)存不足的問題，還有值網(wǎng)絡(luò)；
CMU用了endgame solving以細(xì)化狀態(tài)空間和策略空間，當(dāng)然他們的文章似乎還沒有公布，細(xì)節(jié)還不明朗（比如說剪枝應(yīng)該是用上的）。
CFR的思路非常簡(jiǎn)單，從隨機(jī)策略開始，每次優(yōu)化一個(gè)玩家的策略以提高其收益并反復(fù)迭代，最后取平均策略作為最終策略。每次優(yōu)化用的是悔恨值最小化（Regret minimization）的辦法，所謂悔恨值就是事后最優(yōu)選擇的收益，減去當(dāng)時(shí)選擇的收益，悔恨值最小化就是把到目前為止的累計(jì)悔恨值拿過來，看哪一步累計(jì)悔恨值高，以后就多走這一步，至于多走的概率，有各種算法（比如說Regret Matching和Hedge）。
對(duì)于兩人零和游戲，可以證明CFR會(huì)收斂到納什均衡點(diǎn)，也就是“反正我就這么一招，你怎么也破不了”這樣的終極招數(shù)。所以計(jì)算機(jī)現(xiàn)在使用的算法，最終目的并不是要利用對(duì)方弱點(diǎn)獲得勝利，而是找出神功以達(dá)到無人可敵的境界。當(dāng)然要達(dá)到這個(gè)境界，訓(xùn)練過程中仍然是不斷找對(duì)方弱點(diǎn)讓自己變強(qiáng)。
CFR是個(gè)帶有理論界的通用算法，說它可以解決一切的非對(duì)稱信息博弈問題也不為過。但是世界上自然沒有免費(fèi)午餐，在跑CFR的時(shí)候，每次都要遍歷一次游戲所有可能的狀態(tài)，而任何一個(gè)稍微復(fù)雜點(diǎn)的游戲都有指數(shù)級(jí)的狀態(tài)，所以運(yùn)行時(shí)間上肯定是不能接受的。
這就有很多折中辦法，比如說狀態(tài)量化（認(rèn)為2到9都是小牌用同一個(gè)策略處理），剪枝（對(duì)方不太可能走這一步，那就不用再搜索下去了），隨機(jī)采樣（采樣一些路徑以代替全部的游戲分支），函數(shù)擬合（比如說用值網(wǎng)絡(luò)來代替深層搜索），等等。
總的來說，CFR和幾年前的RL很像，都是傳統(tǒng)AI的帶理論界的老方法，都是在現(xiàn)實(shí)問題中有指數(shù)復(fù)雜度，都是現(xiàn)在漸漸開始深度學(xué)習(xí)化，所以我相信以后會(huì)有更廣闊的發(fā)展。
