2016 年 3 月，一場(chǎng)機(jī)器人與圍棋世界冠軍、職業(yè)九段棋手李世石展開的圍棋人機(jī)大戰(zhàn)受到全球的高度關(guān)注。我們知道，最后的結(jié)果是 DeepMind 的機(jī)器人 AlphaGo 以 4 比 1 的總比分獲勝。這是人工智能領(lǐng)域一個(gè)里程碑性的事件，也讓「博弈」成為一個(gè)熱門的 AI 研究方向。

AlphaGo 之后，DeepMind 又推出了贏得國(guó)際象棋的 AlphaZero、擊敗《星際爭(zhēng)霸 II》的 AlphaStar 等等。使用搜索和學(xué)習(xí)的方法，AI 在許多完美信息博弈中表現(xiàn)出強(qiáng)大的性能，而使用博弈論推理和學(xué)習(xí)的方法在特定的不完美信息博弈中表現(xiàn)出強(qiáng)大的性能。

然而，大多數(shù)成功案例有一個(gè)重要的共同點(diǎn)：專注于單一博弈項(xiàng)目。例如，AlphaGo 不會(huì)下國(guó)際象棋，而 AlphaZero 雖然掌握了三種不同的完美信息博弈，但 AlphaZero 無(wú)法玩撲克牌，也不清楚能否擴(kuò)展到不完美信息博弈。此外，現(xiàn)有研究往往會(huì)使用特定領(lǐng)域的知識(shí)和結(jié)構(gòu)使 AI 實(shí)現(xiàn)強(qiáng)大的性能。

現(xiàn)在，來(lái)自 Google Deepmind 的研究團(tuán)隊(duì)提出了一種利用自我博弈學(xué)習(xí)、搜索和博弈論推理實(shí)現(xiàn)強(qiáng)大博弈性能的通用學(xué)習(xí)算法 ——Student of Games（SoG）。研究論文發(fā)表在《Science Advances》上。

論文地址：https://www.science.org/doi/full/10.1126/sciadv.adg3256

SoG 算法結(jié)合了引導(dǎo)式搜索（guided search）、自我對(duì)弈（self-play）學(xué)習(xí)和博弈論推理（game-theoretic reasoning）。實(shí)驗(yàn)結(jié)果表明，SoG 可以在大型完美和不完美信息博弈中表現(xiàn)出強(qiáng)大的性能，這是邁向任意環(huán)境真正通用算法的重要一步。

方法簡(jiǎn)介

SoG 模型可以在不同的游戲中自由發(fā)揮，并教會(huì)自己如何與自己的另一個(gè)版本進(jìn)行對(duì)戰(zhàn)，能夠?qū)W習(xí)新策略并逐漸變得更有能力。雖然 AlphaZero 也可以適應(yīng)完美信息博弈，但 SoG 可以適應(yīng)完美和不完美信息博弈，從而具有更強(qiáng)的通用性。

SoG 采用成長(zhǎng)樹虛擬遺憾最小化（growing-tree counterfactual regret minimization，GT-CFR）算法。GT-CFR 算法是一種隨時(shí)可以進(jìn)行局部搜索，非均勻地構(gòu)建子博弈，并將樹擴(kuò)展至最相關(guān)的未來(lái)狀態(tài)，同時(shí)可以迭代地細(xì)化價(jià)值與策略。

此外，SoG 還采用了有效的自我對(duì)弈：利用博弈結(jié)果和遞歸子搜索來(lái)訓(xùn)練價(jià)值與策略網(wǎng)絡(luò)，并應(yīng)用于之前搜索中出現(xiàn)過(guò)的情況。

SoG 算法通過(guò)聲音自我對(duì)弈來(lái)訓(xùn)練智能體：每個(gè)玩家在面臨決策時(shí)，使用配備虛擬價(jià)值與策略網(wǎng)絡(luò)（Counterfactual Value-and-Policy Network，CVPN）的聲音 GT-CFR 搜索來(lái)生成當(dāng)前狀態(tài)的策略，并根據(jù)該策略采取行動(dòng)。

自我對(duì)弈過(guò)程會(huì)生成兩種類型的訓(xùn)練數(shù)據(jù)，用于更新價(jià)值與策略網(wǎng)絡(luò)，一種是搜索查詢，一種是完整博弈軌跡。在實(shí)際應(yīng)用中，自我對(duì)弈數(shù)據(jù)生成和訓(xùn)練是并行發(fā)生的：參與者生成自我對(duì)弈數(shù)據(jù)（并解決查詢）；訓(xùn)練者學(xué)習(xí)新網(wǎng)絡(luò)并定期更新參與者。

實(shí)驗(yàn)結(jié)果

眾所周知，傳統(tǒng)搜索在不完美信息博弈中存在缺陷，并且評(píng)估集中在單一領(lǐng)域（如撲克牌），SoG 填補(bǔ)了這一空白。通過(guò)重新解決子博弈，SoG 保證可以找到近似納什均衡，并且在小型博弈中保證可計(jì)算性。

具體來(lái)說(shuō)，SoG 在四種不同的游戲中展示了強(qiáng)大的性能：兩種完美信息博弈（國(guó)際象棋和圍棋）和兩種不完美信息博弈（撲克和 Scotland Yard）。值得注意的是，與撲克相比，Scotland Yard 的搜索范圍和游戲長(zhǎng)度要長(zhǎng)得多，需要長(zhǎng)期規(guī)劃。

SoG 與 AlphaZero 一樣，利用最少的領(lǐng)域知識(shí)，將搜索與自我對(duì)弈相結(jié)合。與 MCTS 不同，SoG 的搜索算法基于虛擬遺憾最小化，對(duì)完美和不完美信息博弈都是有效的。

下圖展示了 SoG 在不同數(shù)量 GT-CFR 下的可利用性。

A 表為 Leduc 撲克，B 表為蘇格蘭場(chǎng)

下圖展示了 SoG 隨著神經(jīng)網(wǎng)絡(luò)評(píng)估次數(shù)的增加與 AlphaZero 可擴(kuò)展性的比較，測(cè)量方式為相對(duì) Elo 評(píng)分尺度。

A 表為國(guó)際象棋，B 表為圍棋