圍棋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