瓣瓣掂玩遊戲

出自維基百科,自由嘅百科全書
(由普遍玩遊戲跳轉過嚟)
跳去導覽 跳去搵嘢
一個正常人類會識得玩多種唔同嘅遊戲,而對普遍玩遊戲嘅研究目的旨在教 AI 做同樣嘅嘢。

瓣瓣掂玩遊戲粵拼faan6 faan6 dim6 waan2 jau4 hei3英文general game playingGGP),或者叫普遍玩遊戲,係人工智能(AI)上嘅一個課題,指思考點樣設計出能夠用嚟「普遍性」噉玩遊戲AI 程式:廿世紀尾嘅電子遊戲 AI 技術表明咗,要編寫出能夠玩某隻特定遊戲嘅 AI 程式並唔難[1][2];不過問題係,一路直至 2010 年代為止,玩遊戲嘅 AI 程式冚唪唥都係專化(specialized)嘅-即係每個程式都都淨係識一味玩死某一隻遊戲[3][4]

舉個例說明,好似係設計嚟捉圍棋嘅 AI 程式 AlphaGo 噉,AlphaGo 喺 2016 年勁到成功打低九段(即係最高等級)圍棋棋手,但除咗捉圍棋之外,AlphaGo 就乜嘢都唔識;噉係因為 AlphaGo 用嘅演算法唔具有普遍性(generality),淨係曉攞「玩緊嗰盤圍棋現時嘅狀態」做自己嘅輸入,唔會識得(例如)考慮「玩緊嗰盤象棋現時嘅狀態」,更加唔好話會識玩棋類之外嘅遊戲[5]

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

抽象遊戲概念[編輯]

睇埋:遊戲同埋博弈論

一個達到普遍玩遊戲嘅 AI 程式實要識得以任何遊戲嘅狀態做自己嘅輸入:最基本上,一個玩遊戲嘅 AI 程式要做嘅係攞「現時遊戲狀態做輸入」,並且以某啲類型嘅演算法計個輸出;一個達到普遍玩遊戲嘅 AI 程式就一定要能夠以任何遊戲嘅遊戲狀態做輸入,所以研究普遍玩遊戲嘅工作者第一步要做嘅係諗出一個抽象化嘅模型表示「遊戲」呢樣嘢,即係搵出一柞所有被視為「遊戲」嘅事物有嘅特性,並且以呢啲特性作為「個 AI 程式收到嘅輸入實會有嘅參數[3][7]。一般認為喺最抽象嘅層面睇,遊戲可以想像成由以下部份組成嘅數學物體:

  • 若干個遊戲狀態,例如以下係井字過三關嘅一啲可能遊戲狀態、
Tic-tac-toe-game-1.png
  • 若干個玩家(井字過三關有兩個玩家)、
  • 若干個可能選擇,而唔同玩家手上有嘅選擇可能唔同(井字過三關每個玩家可以揀霸邊個空位)、以及
  • 指定玩家選擇點樣影響遊戲狀態嘅規則(如果玩家霸咗某個空位,嗰個位就會變成「俾人霸咗」嘅狀態)

... 等等。

馬可夫決策過程[編輯]

內文:馬可夫決策過程

遊戲可以抽象噉想像馬可夫決策過程(Markov decision process):例如係以下呢幅圖當中嘅馬可夫決策過程噉;個過程模擬咗一個虛擬世界,個虛擬世界有三個狀態(),喺每一個狀態當中,玩家都有兩個可能嘅選擇()同埋相應嘅報償,而每個選擇有若干機會率會令到個世界變成另外一個狀態(由啲箭咀同箭咀側邊嘅數字表示)。呢一個模型可以好容易噉用電腦程式表達出嚟,可以攞嚟教電腦喺玩遊戲嗰陣做決策[8][9]

Markov Decision Process.svg

如果要用程式語言嚟表達上述嘅馬可夫決策過程嘅話,設計者可以用好似以下噉嘅一個矩陣(matrix)嚟表示唔同狀態之間轉化嘅機會率,當中每個橫行表示「如果喺呢個狀態揀咗呢個選擇,會去另外一個狀態嘅機會率」-喺狀態 揀咗 )嘅話,遊戲狀態會有 50% 機會變成 、50% 機會變成 ,如此類推[10]

齋用數字(冇咁易睇)嘅話:

複雜性[編輯]

內文:複雜性

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

一盤國際象棋

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

遊戲描述語言[編輯]

一盤國際象棋;家陣黑色嘅國王俾白色嘅皇后將死,所以白色贏-人能夠靠聽遊戲規則想像遊戲嘅可能狀態。
內文:遊戲描述語言

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

要枚舉嘅嘢[編輯]

喺最抽象嘅層面嚟講,遊戲描述語言做嘅通常都係枚舉(enumerate)以下嘅嘢[14][17]

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

... 等等。例如井字過三關可以用以下噉嘅碼表達[註 1][14]

 ...
 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 玩家都有最少一串可能嘅玩家共同行動係會令個玩家贏嘅,隻遊戲就算係弱可贏(weakly winnable);如果一隻遊戲係 foreach 玩家都有最少一串嗰位玩家嘅單方面行動係會令個玩家贏嘅,隻遊戲就算係強可贏(strongly winnable)。一隻單人遊戲必需要係強可贏(玩家可以靠自己單方面嘅行動引致遊戲結束,無論電腦控制嘅玩家做出乜嘢行動),而多人遊戲(由多位人類玩家一齊玩)淨係需要做到弱可贏[3]:p. 7

玩家認知過程[編輯]

一個捉國際象棋嘅人喺度諗要行邊步;喺佢嘅思考過程當中,佢個入面發生咗乜嘢認知過程?呢啲過程可唔可以用 AI 程式模擬?
睇埋:電子遊戲嘅人工智能

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

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

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

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

揀部份可能性[編輯]

睇埋:蒙地卡羅樹搜索

因為複雜性嘅問題,設計嚟玩遊戲嘅 AI 一般都唔會用老派 AI,而係會用啲方法有技巧噉揀選一部份嘅可能性,而揀可能性嘅過程好多時會用到機械學習(machine learning)技術:喺呢方面,蒙地卡羅樹搜索(Monte Carlo tree search,MCTS)係一種相當出名嘅技術;MCTS 簡單啲講就係有技巧噉搜索一樖決策樹-會揀定一個深度值 表示「要考慮幾多步」,並且喺每步按某啲準則揀邊啲節點嘅下一步值得睇[19][20],而如果上述嘅演算法設計得夠好,MCTS 可以有效噉教電腦普遍玩遊戲[21][22][23]

AlphaGo 做例子。AlphaGo 係由 Google 旗下嘅人工智能公司 Deepmind 開發嘅 AI 程式[5][24],採取咗一套當時嶄新嘅做法-AlphaGo 個程式包含兩組深度神經網絡(deep neural network):

  • 一組係政策網絡(policy network),計算 [註 2],用嚟決定行乜嘢棋步,而
  • 另一組係價值網絡(value network),計算 [註 3],用嚟評估棋盤嘅形勢,

然後工作組用監督式學習(supervised learning)訓練政策網絡,俾 AlphaGo 睇大量專業棋手捉棋嘅數據,學計 ;然後用強化學習(reinforcement learning)訓練政策網絡,俾 AlphaGo 係噉同佢自己捉棋同學計邊啲 能夠帶嚟勝利;再用強化學習訓練價值網絡計 [25]

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

一串國際象棋棋步嘅圖解;初頭嘅棋盤狀態係 ,「白色城塔向前行」係一個棋步 ,而 嘅數值可以用機械學習嘅方法由數據嗰度搵出嚟。

簡史[編輯]

睇埋:人工智能史

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

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

註釋[編輯]

  1. 為咗方便起見,以下嘅碼有某啲部份省略咗。
  2. 簡單講係「已知棋盤處於呢個狀態,大師級棋手會行呢步嘅機會率」;有關呢啲數學符號嘅意思,詳情可以睇概率論詞彙
  3. 簡單講係「已知棋盤處於呢個狀態同行咗呢步,我方會贏嘅機會率」。

睇埋[編輯]

參考文獻[編輯]

Atari 2600[編輯]

紅白機[編輯]

[編輯]

  1. Yannakakis, Geogios N (2012). "Game AI revisited" (PDF). Proceedings of the 9th Conference on Computing Frontiers: 285–292.
  2. Stanley, K. O., Bryant, B. D., & Miikkulainen, R. (2005). Evolving neural network agents in the NERO video game. Proceedings of the IEEE, 182-189.
  3. 3.0 3.1 3.2 3.3 3.4 Genesereth, M., Love, N., & Pell, B. (2005). General game playing: Overview of the AAAI competition (PDF). AI magazine, 26(2), 62-62.
  4. Pell, Barney (1992). H. van den Herik; L. Allis (eds.). "Metagame: a new challenge for games and learning" (PDF). Ellis-Horwood.
  5. 5.0 5.1 van den Herik, H., Uiterwijk, J. W. & van Rijswijck, J. Games solved: now and in the future. Artif. Intell. 134, 277–311 (2002).
  6. General intelligence (strong AI) is discussed in popular introductions to AI:
    • Kurzweil 1999 and Kurzweil 2005.
  7. Jesper Juul. Half-Real: Video Games Between Real Rules and Fictional Worlds. MIT Press, 2005.
  8. Hugh Brendan McMahan (2006), Robust Planning in Domains with Stochastic Outcomes, Adversaries, and Partial Observability, CMU-CS-06-166, pp. 3–4
  9. Filar, J. & Vrieze, K. (1997). Competitive Markov Decision Processes. Springer-Verlag.
  10. Getting Started with Markov Decision Processes: Reinforcement Learning. Data Science.
  11. 11.0 11.1 11.2 Intractability and efficiency and the combinatorial explosion:
    • Russell & Norvig 2003, pp. 9, 21–22.
  12. Domingos 2015, Chapter 2, Chapter 3.
  13. 13.0 13.1 Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., ... & Dieleman, S. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484.
  14. 14.0 14.1 14.2 Game Definition Language.
  15. Tagiew, Rustam (2011). Averkin, Alexey N.; Ignatov, Dmitry I.; Mitra, Sushmita; Poelmans, Jonas (eds.). "Beyond Analytical Modeling, Gathering Data to Predict Real Agents' Strategic Interaction" Soft Computing Applications and Knowledge Discovery. CEUR Workshop Proceedings. Moscow, Russia. Vol-758: 113--124.
  16. Schaul, Tom (August 2013). "A video game description language for model-based or interactive learning". 2013 IEEE Conference on Computational Intelligence in Games (CIG): 1–8.
  17. Thielscher, Michael (2017). "GDL-III: A Description Language for Epistemic General Game Playing" (PDF). Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. IJCAI. ISBN 978-0-9992411-0-3. Retrieved 1 July 2019.
  18. Flasiński, M. (2016). Symbolic Artificial Intelligence. In Introduction to Artificial Intelligence (pp. 15-22). Springer, Cham.
  19. Cameron Browne; Edward Powley; Daniel Whitehouse; Simon Lucas; Peter I. Cowling; Philipp Rohlfshagen; Stephen Tavener; Diego Perez; Spyridon Samothrakis; Simon Colton (March 2012). "A Survey of Monte Carlo Tree Search Methods". IEEE Transactions on Computational Intelligence and AI in Games. 4 (1): 1–43.
  20. Monte Carlo Tree Search. Towards Data Science.
  21. Finnsson, Hilmar (2012). "Generalized Monte-Carlo Tree Search Extensions for General Game Playing". Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence.
  22. Frydenberg, Frederik; Anderson, Kasper R.; Risi, Sebastian; Togelius, Julian. "Investigating MCTS Modifications in General Video Game Playing" (PDF).
  23. M. Swiechowski; J. Mandziuk; Y. S. Ong, "Specialization of a UCT-based General Game Playing Program to Single-Player Games," in IEEE Transactions on Computational Intelligence and AI in Games, vol.PP, no.99, pp.1-1.
  24. Allis, L. V. Searching for Solutions in Games and Artificial Intelligence. PhD thesis, Univ. Limburg, Maastricht, The Netherlands (1994).
  25. AlphaGo: How it works technically?. Medium.
  26. Mehat, J., & Cazenave, T. (2008). Monte-carlo tree search for general game playing (PDF). Univ. Paris, 8.
  27. "Metagame and General Game Playing". Metagame and General Game Playing.
  28. A review of Zillions of Games.
  29. Beckenkamp, Martin; Hennig‐Schmidt, Heike; Maier-Rigaud, Frank P. (1 March 2007). "Cooperation in Symmetric and Asymmetric Prisoner's Dilemma Games". Social Science Research Network.
  30. "General Game Playing". www.general-game-playing.de.

[編輯]