Re: [請益] 關於一些遊戲的AI

看板GameDesign作者Eric0605 (米青金兌口觜石包)時間11年前 (2012/12/02 02:27)推噓5(5推 0噓 10→)

留言15則, 7人參與討論串8/22 (看更多)

圍棋AI到底有多難？是不是最難寫的AI我不知道不過從1969年有人寫出圍棋程式之後到現在依然距離職業圍棋手有約3~4子的差距跟頂尖的圍棋手的差距可就更大了。這還是最近5年左右有人發現蒙地卡羅演算法可以應用到圍棋上的成果不然如果使用傳統的暴力法或比較Pattern法也許50年以上也無法下贏人類。很多人提到圍棋是屬於公開化資訊的比賽,規則又很簡單聽起來AI應該不難寫才是，理論上超級電腦越來越快將來可預期的某一天大概輕易KO這個問題。但圍棋難的地方不在規則，在於提子(吃子),又可以打劫 (棋盤同個位置有重複落子的可能性) 讓他的計算量大幅提昇, 甚至超過 10^600種變化(有爭議,也有人認為更多) 這個計算數量基本上比宇宙中原子的總和還要多想要算出必勝下法可說絕無可能。圍棋有趣的地方在於你問那些棋手為何要下這裡, 常常獲得的答案也是說這是靠「感覺」而不是計算給十個人來看這手棋，十一個人的看法都不一樣。甚至有時看似壞棋，到尾盤時又意外變成好棋。也有故意將子送給對方以為是來送死，其實是陷阱等等方法這些都是由於變化量實在太大，人腦也算不清楚的原因。但人腦最強的地方,剛好在於對未知的"答案"可以靠過去的經驗做某種程度的"預測"跟推估，即使是沒看過的情況也可以做出"大概方向正確" 的判斷(雖然這判斷也是見仁見智)，而電腦並沒有這種能力。在這種既不能用暴力法求解的情況下，電腦就失去了優勢，過去傳統圍棋程式的寫法只能靠歷史棋譜取出的pattern 或人類一些"經典"下法的pattern來"教"電腦怎樣下較好，例如早期的世界冠軍 GNU GO就是這樣寫的，這種電腦圍棋軟體的特色就是下棋方法跟人類很像。但這樣的軟體需要依靠程式設計師很會下圍棋才行，還必須想出個邏輯給電腦實際上人類無法也很難把自我的模糊判斷邏輯寫出來，所以電腦圍棋的棋力一直都很掙扎。即使後來有發明類神經演算法,基因演算法等但因為變化量實在太大，也很難藉由大量的棋譜訓練讓電腦歸納出下圍棋的邏輯基於以上幾點理由在2000年左右時，對於圍棋AI可以下贏電腦這件事所有人都很悲觀。直到最近五年終於有一個革命性的演算法 -蒙地卡羅演算法被發明應用在圍棋讓電腦圍棋AI突飛猛進，目前已經變成主流的圍棋演算法(沒有之一) 簡單介紹一下蒙地卡羅演算法，其實發明的來由也挺有趣的這演算法本來是使用在賭場來模擬哪台吃角子老虎比較容易贏錢。有很多種應用，現在則是被發現可以拿來模擬圍棋。原理其實很簡單就是對手下完每一步後用電腦隨便亂下到終局看誰贏再倒推當時下哪手贏棋的機率較高，說穿了也是某種暴力法 (本來是用在賭博機,去玩幾道看看機台看營收,再推估哪台機台之後贏錢機率較高)。這種演算法好處是程式人員不用太懂圍棋，一切回歸數學跟演算法，但一樣相當吃系統資源。而這類演算法的圍棋程式有個特色是下棋不太像是人類常常使用不可思議的手段(正常人類不會有的思維)來跟人類對奕這也正是圍棋令人著迷之處，也許我們從小也是被老師或書籍教導圍棋，所謂的經驗法則也是前人遺傳下來的，這種演算法反而沒有這種包袱，只要可以贏棋就好，故可以下出人世間驚世駭俗的手段或許我們人類所找出的"合理"的下法也只是眾多下法的一小部分而已呢！當然啦，這個演算法雖然是圍棋AI的明日之星，常有佳作但圍棋一盤棋雙方可以下出幾百手，不是幾手棋就可以決定勝負, 目前棋力上還是無法跟頂尖棋手對抗,仍有待程式設計師持續努力。在這裡提供個連結是目前圍棋世界冠軍ZEN的程式人員的訪談筆記，簡體的,有興趣的人可以去看看。 http://9songs.cn/thread-1104-1-1.html 目前開源的圍棋AI程式最有名的就是GNU GO 每一版本的程式都可以下載來看，我有實際下載過在linux comiler可以跑，有興趣也可以去抓來看XD 最新開發中的程式好像也有寫基本的蒙地卡羅演算法。這個AI的難度，人類差不多也要學半年以上才有可能可以下贏他算是挺厲害的程式了啦！當然目前在世界圍棋程式排行榜應該已經落到十名以外了，但想要學棋類遊戲AI的還是很有參考價值。 GNU GO開發首頁 http://www.gnu.org/software/gnugo/gnugo.html 另外還有一個對岸的圍棋AI論壇，裡面也有一些有價值的程式資訊可以參考 http://www.computergo.net/forum/index.php ※ 引述《yoco315 (眠月)》之銘言： : ※ 引述《LaPass (LaPass)》之銘言： : : 總而言之，在圍棋中要面對的是很模糊的計算 : : 這跟SLG跟其他棋類是很明顯的差異 : 其實我也覺得這是一個很常見的誤解耶。 : 我先講結論：一般戰棋類的 SLG 複雜度比圍棋高。 : 這好像很難想像，但是原因其實是因為一般人根本沒「想」過這個問題。 : 小弟試問一個問題：有人認真的去分析過一般 SLG 的複雜度嗎？ : 比方說魔喚精靈、風色幻想、或是星海爭霸？甚至一般 RPG 的戰鬥？ : 不要誤會，我不是說圍棋簡單， : 圍棋很難，我是說那些遊戲更難。 : 圍棋的難因為有被展現跟強調出來，所以大家都知道圍棋很難。 : 因為圍棋是一個有長久歷史跟大量人類在從事，而且已經職業化的活動。 : 廣為人知，也有很多研究者在做這個題目，所以人們注意到他很難， : 不過這不代表他最難。 : 別的不說，光是 partial observe 在 AI 就是一個讓難度翻好幾翻的因素。 : 圍棋的玩家可以看到全部的盤面(full observe)， : 但是絕大部分 full observe 的 AI，到了 partial observe 就根本不能用， : 看不到的東西，你連 search 都沒辦法，這才是真的模糊運算 :( : 又或是「混亂」，這種狀態的轉移帶有隨機性的， : 還要導入 Markov Decision Process 才能分析。 : "Partial observe" 加上 "Markov Decision Process" 這兩個東西放在一起， : 念 AI 的看到都會嚇到閃尿 Q_Q 不知道的可以 google 一下 "POMDP" 看一下。 : 假設未來有一天，電腦的計算力強到可以在圍棋上打贏人類， : 那個時候大家會發現在很多別的遊戲上面，AI 跟人差很多， : 才會注意到原來很多別的遊戲都比圍棋難。 -- 快樂的時光,總是過得特別快, 等到想珍惜時,卻已經變成回憶 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.169.43.171

推

Hevak

12/02 10:26, , 1^F

12/02 10:26, 1^F

推

gonzdevour

12/02 11:19, , 2^F

12/02 11:19, 2^F

→

hermitwhite

12/02 12:35, , 3^F

12/02 12:35, 3^F