瓣瓣掂玩遊戲

正常人類會識得玩多種唔同嘅遊戲，而對普遍玩遊戲嘅研究目的旨在教 AI 做同樣嘅嘢。上圖嘅係國際象棋。

瓣瓣掂玩遊戲（英文：GGP），或者叫普遍玩遊戲，係人工智能上嘅課題，思考點樣設計出能夠用嚟「普遍」噉玩遊戲嘅 AI：廿世紀尾嘅電子遊戲 AI 技術表明，要編寫出能夠玩某隻特定遊戲嘅 AI 並唔難；不過問題係，一路直至二〇一〇年代為止，玩遊戲嘅 AI 程式全部都係專化嘅－即係每個程式都都淨係識玩某一隻遊戲。

舉個例說明，好似係設計嚟捉圍棋嘅 AI 程式 AlphaGo 噉，AlphaGo 喺二〇一六年取得巨大成功，打低咗九段（即係最高等級）圍棋棋手，但除咗捉圍棋之外，AlphaGo 就咩都唔識；噉係因為 AlphaGo 用嘅演算法唔具有普遍特性，淨係曉攞「玩緊嗰盤圍棋現時嘅狀態」做自己嘅輸入，唔會識得例如考慮玩緊嗰盤象棋現時嘅狀態，更加唔好話會識玩棋類之外嘅遊戲。

遊戲 AI 嘅高度專化對 AI 研究嚟講係問題：理論上，AI 研究嘅終極目的係想創造出喺智能上同人無異嘅 AI 程式，而齋靠日常觀察已經可知，智能正常嘅人類能夠學識玩多種唔同嘅遊戲，所以如果想創造出响智能上同人無異嘅 AI 程式，必需要成功達致普遍玩遊戲。除此之外，普遍玩遊戲嘅技術亦喺軍事同遊戲製作等方面有實用價值。

抽象遊戲概念

睇埋：遊戲同博弈論

遊戲係源自玩嘅重要文化產物。遊戲最主要嘅特徵係有一定嘅規則同埋定輸贏條件，會要求玩家思考點樣喺遊戲規則嘅限制下，最大可能噉達到自己嘅目的。遊戲好多時（但唔一定）仲有競爭性－好多遊戲都涉及多過一個玩家，要玩家各自選擇自己嘅策略，並且嘗試打低其他玩家，例如象棋、團隊運動以及各種各樣嘅射擊同格鬥電子遊戲等等，都屬於有競爭性嘅遊戲。有陣時瓣瓣掂玩遊戲嘅研究者會以「首先製作出能夠普遍噉玩某一類遊戲嘅 AI」做目的，諗住搞掂嗮某一個類型嘅遊戲先至去諗真正完全嘅瓣瓣掂玩遊戲，例如瓣瓣掂玩電子遊戲（GVGP）係瓣瓣掂玩遊戲嘅子領域，顧名思義研究能夠玩任何電子遊戲嘅 AI 。

一般認為喺最抽象嘅層面睇，遊戲可以想像成由以下部份組成嘅數學物體：

• 若干個遊戲狀態，例如以下係井字過三關嘅一啲可能遊戲狀態、

• 若干個玩家（井字過三關有兩個玩家）、
• 若干個可能選擇，而唔同玩家手上有嘅選擇可能唔同（井字過三關每個玩家可以揀霸邊個空位）、以及
• 指定玩家選擇點樣影響遊戲狀態嘅規則（如果玩家霸咗某個空位，嗰個位就會變成「俾人霸咗」嘅狀態）

... 等等。

達到普遍玩遊戲嘅 AI，要識得以任何遊戲嘅狀態做自己嘅輸入：最基本上，玩遊戲嘅 AI 程式要做嘅係攞「現時遊戲狀態做輸入」，並且以某啲類型嘅演算法計個輸出；達到普遍玩遊戲嘅 AI 就一定要能夠以任何遊戲嘅遊戲狀態做輸入，所以研究普遍玩遊戲嘅工作者第一步要做嘅係諗出一個抽象化嘅模型表示「遊戲」呢樣嘢，即係搵出一柞所有被視為「遊戲」嘅事物有嘅特性，並且以呢啲特性作為「個 AI 程式收到嘅輸入實會有嘅參數」。

馬可夫決策過程

内文：馬可夫決策過程

遊戲可以抽象噉想像成馬可夫決策過程：例如係以下呢幅圖當中嘅馬可夫決策過程噉；個過程模擬咗一個虛擬世界，個虛擬世界有三個狀態（$S_{0}$、$S_{1}$ 同 $S_{2}$），喺每個狀態當中，玩家都有兩個可能嘅選擇（$a_{0}$ 同 $a_{1}$）同埋相應嘅報償，而每個選擇有若干機會率會令到個世界變成另外一個狀態（由啲箭咀同箭咀側邊嘅數字表示）。呢個模型可以好容易噉用電腦程式表達出嚟，可以攞嚟教電腦喺玩遊戲嗰陣做決策。

如果要用程式語言嚟表達上述嘅馬可夫決策過程嘅話，設計者可以用好似以下噉嘅矩陣嚟表示唔同狀態之間轉化嘅機會率，當中每個橫行表示「如果喺呢個狀態揀咗呢個選擇，會去另外一個狀態嘅機會率」－喺狀態 $S_{0}$ 揀咗 $a_{0}$（$a_{0}{\text{ at }}S_{0}$）嘅話，遊戲狀態會有 50% 機會變成 $S_{0}$、50% 機會變成 $S_{2}$，如此類推：

$\mathbf {P} ={\begin{bmatrix}&(S_{0})&(S_{1})&(S_{2})\\(a_{0}{\text{ at }}S_{0})&0.5&0.0&0.5\\(a_{1}{\text{ at }}S_{0})&0.0&0.0&1.0\\(a_{0}{\text{ at }}S_{1})&0.7&0.1&0.2\\(a_{1}{\text{ at }}S_{1})&0.0&0.95&0.05\\(a_{0}{\text{ at }}S_{2})&0.4&0.0&0.6\\(a_{1}{\text{ at }}S_{2})&0.3&0.3&0.4\\\end{bmatrix}}$

齋用數字（冇咁易睇）嘅話：

$\mathbf {P} ={\begin{bmatrix}0.5&0.0&0.5\\0.0&0.0&1.0\\0.7&0.1&0.2\\0.0&0.95&0.05\\0.4&0.0&0.6\\0.3&0.3&0.4\\\end{bmatrix}}$

複雜度

内文：複雜

睇埋：啟發法

現實世界嘅遊戲好多時都好複雜，好少可會好似上面嗰個馬可夫決策過程（得三個可能狀態）咁簡單：例如係教個 AI 程式捉棋噉，國際象棋喺兩個棋手都行咗第一步之後個棋盤會有 400 個可能嘅形勢，喺兩個棋手都行咗第二步之後個棋盤會有 197,742 個可能嘅形勢，而喺兩個都行咗第三步之後呢個數字會超過 100 萬（可以睇組合爆發），就算用先進嘅電腦行都要嘥極大量嘅時間先能夠考慮嗮所有嘅可能性；而圍棋仲複雜，有成 10¹⁷⁰ 個可能情況－部電腦運算能力再勁都唔會喺限定時間之內計得嗮。

國際象棋開局嗰陣嘅樣

因為噉，AI 研究當中有好多都集中於思考點樣喺有限嘅數據同時間之內盡可能令 AI 程式學最多嘅嘢，其中一個方向係思考點由「所有可能嘅情況」當中揀一小部份最有可能啱用嘅情況出嚟考慮。例如係因為喺 2016 年打低咗九段（最高等級）圍棋棋手李世石而出名嘅 AI 程式 AlphaGo 噉，就用咗蒙地卡羅樹搜索嘅做法，噉講意思係指，foreach 棋步，AlphaGo 會用一啲特殊演算法估計邊啲可能棋步嘅後果最有需要睇，再做若干次嘅模擬，想像每個呢啲可能棋步行完之後自己嘅贏面（自己贏嘅機會率）會點變，然後就按模擬結果揀要行邊步。

遊戲描述語言

國際象棋；家陣黑色嘅國王俾白色嘅皇后將死，所以白色贏－人能夠靠聽遊戲規則想像遊戲嘅可能狀態。

内文：遊戲描述語言

達致瓣瓣掂玩遊戲嘅 AI 一定要做到能夠理解佢未接觸過嘅遊戲嘅規則：想像一個 AI，佢能夠攞遊戲嘅規則做輸入，由規則嗰度大致噉推算隻遊戲有乜可能狀態，並且再按經驗調整自己心目中描述隻遊戲嘅馬可夫決策過程嗰啲參數，做到「唔使設計者講明嗮俾佢知遊戲有邊啲可能狀態」嘅效果。遊戲描述語言（GDL）係瓣瓣掂玩遊戲研究上會用嘅邏輯編程語言，即係理論上可以用嚟描述任何遊戲嘅規則嘅形式化語言。

要枚舉嘅嘢

喺最抽象嘅層面嚟講，遊戲描述語言做嘅通常都係枚舉以下嘅嘢：

• 遊戲入面嘅物件，例如係象棋入面嘅每一隻棋同棋盤上嘅每一格，白色嘅國王叫 wk、棋盤上嘅第五行第三格叫 square (e,3)... 等等；
• 遊戲嘅玩家，例如象棋有兩個玩家，role(player 1) 同 role(player 2)；
• 每個玩家有乜嘢可能嘅行動，每個行動會點樣影響遊戲入面嘅物件嘅狀態同埋第啲玩家，例如 move 表示郁某一隻棋，move(e1,e2) 表示將某隻棋由 e1 移去 e2；
• 命題喺遊戲每一個可能狀態下一係真一係假嘅，例如「白色國王喺 e1 嗰格」（句法：true(p)，當中 p 係評估緊佢係咪真嗰句命題）呢一句嘢喺每一個遊戲可能狀態下一係一係真一係假，而呢句嘢係咪真會影響邊一啲可能行動係啱規矩－如果「白色國王喺 e1 嗰格」呢句嘢係真，噉 wk, move(e5,e6) 唔會係一個可能行動；
• 初時狀態，即係遊戲開始嗰陣狀態係點，例如喺國際象棋遊戲開始嗰陣，雙方嘅棋都係喺某個特定位置，個程式會有一柞 init(p)，當中 p 係一句喺遊戲開始嗰陣係真嘅命題；
• 遊戲喺乜嘢情況下結束同點定輸贏；

... 等等。例如井字過三關可以用以下噉嘅碼表達：

 ...
 role(x) # 遊戲有 X 同 O 兩個玩家
 role(o)
 ...
 input(R,mark(M,N)) :- role(R) & index(M) & index(N) #可能行動係「玩家 R 填 M, N 嗰格」
 input(R,noop) :- role(R)
 ...
 base(cell(M,N,x)) :- index(M) & index(N) # 命題類型 1：「M,N 嗰格俾 X 填咗」
 base(cell(M,N,o)) :- index(M) & index(N) # 命題類型 2：「M,N 嗰格俾 O 填咗」
 base(cell(M,N,b)) :- index(M) & index(N) # 命題類型 3：「M,N 嗰格係空嘅」
 base(control(x)) # 命題類型 4：「而家到 X 行」
 base(control(o)) # 命題類型 4：「而家到 O 行」
 ...
 init(cell(1,1,b)) # 遊戲原始狀態：1,1 嗰格係空嘅
 init(cell(1,2,b)) # 遊戲原始狀態：1,2 嗰格係空嘅
 ... # ... 如此類推
 legal(W,mark(X,Y)) :- # 啱規則嘅嘢之一：要喺「X,Y 嗰格係空嘅」同「到 W 行」呢兩句命題都係真嗰陣，「玩家 W 填 X, Y 嗰格」先至有可能發生。
   true(cell(X,Y,b)) &
   true(control(W))
 ...

如果隻遊戲係 foreach 玩家都有最少一個啱規則嘅可能行動嘅，噉呢隻遊戲就算係玩得（playable）。如果一隻遊戲係 foreach 玩家都有最少一串可能嘅玩家共同行動，係會令個玩家贏嘅，隻遊戲就算係弱可贏；如果一隻遊戲係 foreach 玩家都有最少一串嗰位玩家嘅單方面行動係會令個玩家贏嘅，隻遊戲就算係強可贏。單人遊戲必需要係強可贏，玩家可以靠自己單方面嘅行動引致遊戲結束，無論電腦控制嘅玩家做出乜嘢行動，而多人遊戲（由多位人類玩家一齊玩）淨係需要做到弱可贏。

玩家認知過程

捉國際象棋嘅人喺度諗要行邊步；喺佢嘅思考過程當中，佢個腦入面發生咗乜嘢認知過程？呢啲過程可唔可以用 AI 程式模擬？

睇埋：電子遊戲嘅人工智能

達到瓣瓣掂玩遊戲嘅 AI 必需要曉攞遊戲狀態做輸入，然後再做一啲運算，最後俾出一個表示「自己要作出乜嘢行動」嘅輸出；喺呢個過程當中，瓣瓣掂玩遊戲程式嘅運算過程好多時會模擬人類玩遊戲嗰陣用嘅認知功能。

玩遊戲嘅 AI 要做嘅運算類型視乎遊戲嘅複雜度而定：最傳統（廿世紀）嘅 AI 做法係所謂嘅老派 AI，老派 AI 做嘅係將所受嘅輸入數值用一大柞邏輯符號計算，再按呢啲計算俾個輸出數值出嚟睇；舉個例說明，如果家吓有個設計者想教部電腦幫手睇病（輸入值係「有關病人嘅資訊」，而輸出值係「診斷」），噉就要教佢

• 「if 普遍健康嘅大人發燒，then 佢有可能係感冒」、
• 「if 普遍健康嘅大人發燒，then 佢都有可能係肺炎」

... 等嘅若干條法則；呢種做法喺隻遊戲好簡單－例如係井字過三關－嗰陣仲行得通，不過事實表明，一旦隻遊戲有返咁上下複雜－例如頭先提到，國際象棋喺兩個棋手都行咗第一步之後，個棋盤會有成 400 個可能形勢－嗰陣，「吓吓要設計者教個 AI 程式要作出乜行動」嘅做法就會搞唔掂。

因為複雜度嘅問題，設計嚟玩遊戲嘅 AI 一般都唔會用老派 AI，而係會諗一啲相對簡單嘅法則（可以睇啟發法嘅概念）嚟解決問題。好似係有關普遍玩紅白機遊戲嘅 AI 嘅研究噉，有研究者就試過主張，好多遊戲嘅目標都可以簡化噉想像成「盡力令某個數字（叫進度變數）有咁大得咁大」－例如玩一隻平台遊戲過關可以想像成「令過咗嘅關嘅數量有咁大得咁大」，而 AI 可以用機械學習嘅方式嚟學「要將邊個數值最大化」，即係俾 AI 睇一大柞描述「玩家玩一隻遊戲玩到爆機為止」嘅數據，再要個程式搵出邊個或者邊啲變數嘅數值喺成個過程當中最會係噉垂直一路上升，跟住再教個程式用神經網絡等嘅方法學「邊樣或者邊啲行動最能夠令進度變數（長遠嚟講）上升」。

揀部份可能性

睇埋：蒙地卡羅樹搜索

要模擬人玩複雜嘅遊戲，研究者可以用啲方法教 AI 有技巧噉揀選一部份嘅可能性嚟考慮，而揀可能性嘅過程好多時會用到機械學習技術：例如可以用蒙地卡羅樹搜索（MCTS）；MCTS 簡單啲講就係有技巧噉搜索決策樹－會揀定一個深度值 $d$ 表示「要考慮幾多步」，並且喺每步按某啲準則揀邊啲節點嘅下一步值得睇，而如果上述嘅演算法設計得夠好，MCTS 可以有效噉教電腦普遍玩遊戲。

以 AlphaGo 做例子。AlphaGo 係由 Google 旗下嘅人工智能公司 Deepmind 開發嘅 AI 程式，採取咗一套當時嶄新嘅做法－AlphaGo 個程式包含兩組深度神經網絡，做條件概率計算：

• 一組係政策網絡，計算 $\Pr({\text{ 行 動 }}{\text{ }}|{\text{ 現 時 狀 態 }}{\text{ }})$ ，用 嚟決定行乜嘢棋步，而
• 另一組係價值網絡，計算 $\Pr({\text{ 勝 利 }}{\text{ }}|{\text{ 狀 態 同 行 動 }}{\text{ }})$ ，用嚟評估棋盤嘅形勢，

然後工作組用監督式學習訓練政策網絡，俾 AlphaGo 睇大量專業棋手捉棋嘅數據，學計 $\Pr({\text{ 行 動 }}{\text{ }}|{\text{ 現 時 狀 態 }}{\text{ }})$；然後用強化學習訓練政策網絡，俾 AlphaGo 係噉同佢自己捉棋同學計邊啲行動能夠帶嚟勝利；再用強化學習訓練價值網絡計已知狀態同行動，贏嘅機率。

喺真係捉棋嗰陣，個程式就會用 MCTS：喺價值網絡同政策網絡嘅引導下揀要行邊步，即係 foreach 步，按價值網絡同政策網絡嘅 output 決定要睇邊一個可能性，做若干次嘅模擬，然後再按模擬嘅結果揀要行邊一步。雖然 AlphaGo 淨係設計嚟捉圍棋，不過用機械學習教部電腦估算呢啲概率，理論上喺多數遊戲中都會用得著。

國際象棋棋步嘅圖解；初頭嘅棋盤狀態係狀態，「白色城塔向前行」係一個棋步（行動）而 $\Pr({\text{ 行 動 }}{\text{ }}|{\text{ 現 時 狀 態 }}{\text{ }})$ 同 $\Pr({\text{ 勝 利 }}{\text{ }}|{\text{ 狀 態 同 行 動 }}{\text{ }})$ 嘅數值可以用機械學習嘅方法由數據嗰度搵出嚟。

簡史

睇埋：人工智能史

瓣瓣掂玩遊戲嘅概念源於廿世紀尾：喺 1992 年，美國電腦科學家巴尼·啤開發出 meta-game playing（粵譯：廣義玩遊戲、高層玩遊戲）呢個系統，曉自動噉產生好似國際象棋噉嘅遊戲嘅規則（即係某程度上曉創作新遊戲）；巴尼·啤跟住開發咗 Metagamer 系統，個系統曉玩由 Meta-game Playing 製作出嚟嘅棋類遊戲。打後冇幾耐，有人開發出《Zillions of Games》呢隻棋類遊戲合輯，當中仲有曉學識玩多種棋類遊戲嘅 AI 。上述呢啲創新為「識玩多過一款遊戲嘅 AI」呢一個諗法創咗先河，而且仲有俾人應用落去博弈論領域嘅研究上。

喺廿一世紀初，瓣瓣掂玩遊戲係 AI 當中一個頗受重視嘅領域。加州史丹福大學喺 2005 年開咗個叫 General Game Playing 嘅項目，旨在想俾搞瓣瓣掂玩遊戲嘅人交流，會追求將瓣瓣掂玩遊戲研究標準化（例：要個個都用遊戲描述語言嚟做程式嘅輸入，等唔同嘅研究者交流起上嚟方便），而且仲會定時搞有相當份量（以千美元計）獎金嘅比賽，俾唔同人寫嘅瓣瓣掂玩遊戲 AI 程式互相競技，以求鼓勵人幫手推動瓣瓣掂玩遊戲技術嘅進步。

相關 AI 技術

• 電腦視覺，指教電腦處理視覺資訊嘅 AI 子領域；喺教 AI 玩電玩遊戲（以電腦程式存在嘅遊戲，好多時會以一個遊戲畫面嚟俾玩家知道遊戲狀態）嘅瓣瓣掂玩電子遊戲上，電腦視覺用嘅演算法可以攞嚟教 AI 好似人噉靠睇遊戲畫面了解遊戲狀態。
• 強化學習，機械學習上嘅一種學習範式；喺強化學習嘅過程當中，研究者唔會有數據 ${\displaystyle \textstyle x}$ 俾個機械學習程式睇同跟住學，而係俾個程式自主噉同周圍環境互動（個環境可以係現場，又可以係模擬嘅環境）：喺每一個時間點 ${\displaystyle \textstyle t}$，個程式會產生用輸出嘅數字表示嘅動作，而跟住佢周圍個環境會俾返一啲回輸－簡單啲講就係話返俾個程式聽，佢個動作啱唔啱。而個程式跟手就會根據呢個回輸計吓，睇吓要點樣改佢嗰啲參數，先可以令到下次佢做行動嗰陣得到正面回應嘅機會率高啲。
• 人工神經網絡，模擬生物神經網絡嘅 AI 運算方法，擅長處理高複雜度嘅問題，所以理論上可以用效噉處理玩複雜遊戲嘅問題，例如 AlphaGo 就用咗深度神經網絡嘅技術。
• 強人工智能，指喺智能上同人無異嘅 AI 程式；瓣瓣掂玩遊戲俾人指係強 AI 嘅第一步。

睇埋

• 學習遷移
• 遊戲設計
• 遊戲製作
• 強化學習
• 打機用語

文獻

• Genesereth, M., Love, N., & Pell, B. (2005). General game playing: Overview of the AAAI competition (PDF). AI magazine, 26(2), 62-62.
• Levine, John; Congdon, Clare Bates; Ebner, Marc; Kendall, Graham; Lucas, Simon M.; Miikkulainen, Risto; Schaul, Tom; Thompson, Tommy (2013). "General Video Game Playing" (PDF). Artificial and Computational Intelligence in Games. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 6: 77–83.
• Michael, Friedrich; Ignatov, Dmitry (2019). "General Game Playing B-to-B Price Negotiations" (PDF). CEUR Workshop Proceedings. Vol-2479: 89–99.
• Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Rusu, Andrei A.; Veness, Joel;... (26 February 2015). "Human-level control through deep reinforcement learning (PDF)". Nature. 518 (7540): 529–533.
• Neufeld, Xenija; Mostaghim, Sanaz; Perez-Liebana, Diego. "Procedural Level Generation with Answer Set Programming for General Video Game Playing" (PDF).
• Nielsen, Thorbjørn S.; Barros, Gabriella A. B.; Togelius, Julian; Nelson, Mark J. "Towards generating arcade game rules with VGDL" (PDF).
• Pell, Barney (1992). H. van den Herik; L. Allis (eds.). "Metagame: a new challenge for games and learning" (PDF). Ellis-Horwood.
• Perez Liebana, D., Dieskau, J., Hunermund, M., Mostaghim, S., & Lucas, S. (2015, July). Open loop search for general video game playing (PDF). In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (pp. 337-344).
• Świechowski, M., Park, H., Mańdziuk, J., & Kim, K. J. (2015). Recent advances in general game playing (PDF). The Scientific World Journal, 2015.

玩 Atari 2600：

• Guo, Xiaoxiao; Singh, Satinder; Lee, Honglak; Lewis, Richard L.; Wang, Xiaoshi (2014). "Deep Learning for Real-Time Atari Game Play Using Offline Monte-Carlo Tree Search Planning" (PDF). NIPS Proceedings.
• Korjus, Kristjan; Kuzovkin, Ilya; Tampuu, Ardi; Pungas, Taivo (2014). "Replicating the Paper "Playing Atari with Deep Reinforcement Learning"" (PDF). University of Tartu.

玩紅白機：

• Murphy, Tom (2013). "The First Level of Super Mario Bros. is Easy with Lexicographic Orderings and Time Travel ... after that it gets a little tricky" (PDF). SIGBOVIK.
• Teller, Swizec (October 28, 2013). "Week 2: Level 1 of Super Mario Bros. is easy with lexicographic orderings and". A geek with a hat.

拎

• （英文） 史丹福大學，瓣瓣掂玩遊戲 home page
• （英文） AiAi，Stephen Tavener
• （英文） PolyGamo Player Project
• （英文） Palamedes，瓣瓣掂玩遊戲 IDE
• （英文） 瓣瓣掂玩遊戲 AI 競賽