人機(jī)對戰(zhàn)無疑是4月10日的新聞焦點(diǎn)之一。一邊在海南澄邁,德州撲克人工智能“冷撲大師”(Libratus)經(jīng)過5日激戰(zhàn),在33000手一對一無限注德?lián)浔荣愔型陝僦袊?ldquo;龍之隊(duì)”的6名高手,斬獲200萬人民幣獎(jiǎng)金;另一邊在北京的中國棋院,谷歌宣布被中國網(wǎng)民稱為“阿爾法狗”的圍棋人工智能AlphaGo將在5月下旬的烏鎮(zhèn)對陣柯潔領(lǐng)銜的中國頂尖棋手,上演終極一戰(zhàn)。
一南一北,一牌一棋,兩則人機(jī)對戰(zhàn)重磅消息在同一天出爐,雖然未必是有意針鋒相對,但也足夠令無心的觀眾相互比較。有些讀者認(rèn)為,連圍棋這樣高深的智力運(yùn)動(dòng)都早已被阿爾法狗拿下,撲克這樣門檻低、上手簡單的大眾娛樂又何足掛齒呢?但反方則指出,撲克不是單純靠計(jì)算的游戲,牽扯到很多心理上的博弈,有時(shí)甚至需要“飆演技”,AI能掌握這類游戲有些匪夷所思。
那么,德?lián)浜蛧暹@兩種智力游戲,對AI來說到底有什么區(qū)別?哪個(gè)難度更大一些?針對這些問題,澎湃新聞(www.thepaper.cn)就冷撲大師和阿爾法狗的相關(guān)資料進(jìn)行了梳理與比較。
托馬斯?桑德霍姆(Tuomas Sandholm) 資料圖
不過,冷撲大師的開發(fā)者、美國卡內(nèi)基梅隆大學(xué)(CMU)計(jì)算機(jī)系教授托馬斯?桑德霍姆(Tuomas Sandholm)在聽到阿爾法狗將來華挑戰(zhàn)的消息后,評價(jià)非常的簡單:問題的關(guān)鍵并不在于中國頂尖棋手能不能贏,而在于生活中幾乎不存在像圍棋這樣的“完美信息游戲”,因而阿爾法狗也缺乏實(shí)用場景。
圍棋和德?lián)鋵τ贏I來說,性質(zhì)是不是一樣的?
自1988年CMU開發(fā)的“奧賽羅”程序擊敗世界黑白棋冠軍以來,人類就在棋類游戲上節(jié)節(jié)敗退。1997年,IBM的計(jì)算機(jī)“深藍(lán)”擊敗了國際象棋棋壇神話卡斯帕羅夫,使人機(jī)對戰(zhàn)在當(dāng)時(shí)達(dá)到了輿論高峰,其影響力絕不亞于去年阿爾法狗擊敗韓國棋手李世石。
計(jì)算機(jī)程序攻克這些棋類游戲的方法在本質(zhì)上是一樣的:搜索。下每一步棋都是一個(gè)決策點(diǎn),在決策點(diǎn)上分化出不同的可能性,而整盤棋也就形成了一棵不停分叉的決策樹。而計(jì)算機(jī)所做的,就是在每一個(gè)決策點(diǎn)上搜索勝率最大的那條路徑。
因而難度主要取決于決策點(diǎn)的數(shù)量。決策點(diǎn)越多,搜索難度自然越大。黑白棋的搜索量只有10的十幾次方,國際象棋是10的四十幾次方,而圍棋的搜索量達(dá)到了驚人的10的170次方。
不過,也正因?yàn)閲宓乃阉髁刻?,完全精確的結(jié)果是不可能得到的。因而,阿爾法狗在蒙特卡洛樹搜索算法(Monte Carlo Tree Search)的基礎(chǔ)上,結(jié)合走棋網(wǎng)絡(luò)(Policy Network)、快速走子(Fast rollout)和價(jià)值網(wǎng)絡(luò)(Value Network)進(jìn)行預(yù)測和評估,得到盡可能接近最優(yōu)的解。雖然阿爾法狗這個(gè)過程中做出了巨大突破,但它本質(zhì)上還是在搜索。
德州撲克與棋類完全不同。圍棋是一種“完美信息游戲”,場面上所有的情況都黑白分明地?cái)[在棋面上,雙方掌握對等的信息。然而,德?lián)渲须[藏了很多信息,是一種“非完美信息游戲”。玩家不知道對手手中是什么牌,不知道五張公共牌會開出怎樣的結(jié)果,也不知道對手猜測自己握有怎樣的手牌。
因此,雖然一盤德?lián)涞臎Q策點(diǎn)數(shù)量是10的160次方,要少于圍棋,但光靠搜索是打不了德?lián)涞?。德?lián)溆纱颂隽嗽谒阉髁可系妮^量,對AI提出了另一個(gè)方向上的考驗(yàn):應(yīng)對隱藏的信息。
阿爾法狗和冷撲大師的原理有何不同?
谷歌曾在《自然》雜志上發(fā)表文章,公布阿爾法狗的幾個(gè)基本原理,分別為:走棋網(wǎng)絡(luò)(Policy Network),給定當(dāng)前局面,預(yù)測和采樣下一步的走棋;快速走子(Fast rollout),在適當(dāng)犧牲走棋質(zhì)量的條件下提高速度;價(jià)值網(wǎng)絡(luò)(Value Network),給定當(dāng)前局面,估計(jì)雙方勝率;蒙特卡羅樹搜索(Monte Carlo Tree Search,MCTS),把以上三個(gè)部分串聯(lián)成一個(gè)完整的系統(tǒng)。
冷撲大師的算法則主要基于以下三個(gè)模塊產(chǎn)生:
首先,納什均衡是德?lián)渌惴ǖ暮诵模碅I的目標(biāo)是找到一個(gè)無論對方怎么做,自己都不會產(chǎn)生損失的策略。根據(jù)博弈論,像一對一撲克這種零和游戲永遠(yuǎn)存在這樣的最優(yōu)解,就像在經(jīng)典的博弈論模型“囚徒困境”中,招認(rèn)罪行就是一個(gè)無論對方招認(rèn)不招認(rèn)都最優(yōu)的策略。因此,冷撲大師的開發(fā)團(tuán)隊(duì)提前在龐大的決策樹上利用虛擬遺憾最小化算法(Counterfactual Regret Minimization,CFR)推算出了均衡,即通過多次迭代計(jì)算博弈樹中每個(gè)信息集的動(dòng)作遺憾值和平均策略值,預(yù)測下一時(shí)刻的決策動(dòng)作,使其是當(dāng)前最小遺憾動(dòng)作。