[心得] 電腦圍棋的小常識

作者: aaaba (小強)   2016-01-30 16:49:38
AlphaGo的問世,使得有些人會很好奇怎麼這麼強,甚至覺得懷疑,提出造假論
我想就我的理解來讓大家稍稍體會AG或一般程式裡面的運作模式。不過,因為
我不是專家,同時又要寫的通俗,難免背離實際設計難度而過度簡化,歡迎指正
與補充。
整個系統主要有幾個大的模組,簡介如下:
形勢判斷模組(value network)
這個模組要回答一個很單純的問題:給你看一個中盤,請問雙方獲勝機率為何?
訓練方式就是給非常非常大量的棋譜庫,隨機展示(中盤畫面,最終輸贏)這樣
的案例給電腦去學習,學習的方法是最近人工智慧的大熱門 deep learning,有
興趣且英文好的玩家推薦去看 udacity 上 google 專家的線上教學。
下一步去哪兒模組(policy network)
這個模組要回答一個很單純的問題:給你看一個中盤,請問棋盤上每個位置成為
下一手的機率為何?訓練方式就是給非常非常大量的棋譜庫,隨機展示(中盤畫
面,下一手)這樣的案例給電腦去學習。
賽局樹(Game tree)
用張圖舉個例子 http://imgur.com/XwQ6tmm
上圖:假設圓圈是該黑棋下,方塊是該白棋下,假設現在“下一步
模組”會提供兩個落子的可能性,黑棋任選其一下了之後,就會出
現兩個可能的盤面情形(分支),接著,請出“形勢判斷模組”來
打分數,分別給出-6和-11的得分,如果黑棋只滿足於最最簡單的
計算,那麼它就會挑-6這個相對較好的發展方向來落子,問號的位
置將被填入-6。
中圖:假設黑棋認為時間充裕或他的硬體強大,可以做更深入的
計算。那他或許覺得把-6這個局勢再多設想一步比較保險,於是
現在從-6這個盤面開始考慮,是該白棋落子了。同樣透過“下一步
模組”來提供兩個落子的可能性,白棋任選其一下了之後,就會出
現兩個可能的盤面情形,接著,請出“形勢判斷模組”來打分數,
分別給出21和-8的得分。
下圖:因為要站在白棋的角度思考,他想把盤面弄的對黑棋不利
,21和-8中,白棋應會選擇-8,於是,在第一張圖時原本認為導
向-6這個局面其實再更進一步思量之後,局面繼續發展方向沒那
麼樂觀,實際上只有-8分而已。至此,最頂層的黑棋便必須在-8
或-11中挑較佳的下,所以下圖裡面的問號將會被填上-8,代表以
黑棋目前的細算能力,他認為他會把棋盤導向最下排右邊那個得
分-8的盤面。
以此類推,輪流請出兩個模組的結果,就是這棵樹會越長越多層。
如果你的時間充裕或硬體強大,也可以讓“下一步模組”每次提供
三個以上的落子位置來候選,這樣樹就會長得比較寬(分支較多)
,又或者,你可以一次又一次的使用“下一步模組”來多往下發展
幾步,這樣樹就會長得比較深比較多層。總之,你有多少養分,就
可以種多大的樹,隨時可以喊停,不用去窮盡所有棋局變化,這樣
做是不切實際的。
最大最小法則(Minmax rule)
以這個圖作為例子 http://imgur.com/TsmiK04
現在該黑棋下,他當然希望局面分數越高越好(Max),但是他也
知道白棋不會讓他如意,會試圖把局面搞得越難看越好(Min),
於是,即使在他這棵0~4層的細算樹裡面也有著高達20分的分支,
黑棋是不可妄想去走到那個盤面的,他會從-8和-10選一個相對高
的,也就是問號的位置會被填入-8,代表目前黑棋可達到的最好形
勢。備註一下這裡的分數只是網路上隨便抓的圖,真正的分數可以
想成是落在0~1的獲勝機率。當然,這個最大最小法則只是最粗淺
的賽局策略而已,實際上AlphaGo有更好的細算方法,叫做蒙地卡羅
樹搜尋(Monte Carlo tree search),複雜許多,這裡就不細說了。
結語
近五年由於 deep learning 的問世,提煉出大量數據之精華的效果也變得超級好,
人工智慧的趨勢就是:得大數據/超級電腦者,得天下。舊的工程方法引入 deep
learning 改良後效能也都是巨幅提升,不僅僅是在電腦圍棋這塊而已。
作者: sky0302 (free)   2016-01-30 17:00:00
圍棋TV有說 以前電腦的演算法是硬算各種變化現在演算法比較像人類 會用刪去法 先排除可能比較差的棋不過就像不知道是不是李世石 還是哪位職棋說的這種演算法也有漏洞 因為那些被排除了 也可能剛好是好棋也就是現在的電腦是比較像人類了 但要贏人類還要打問號就算電腦最終贏人類 也不代表它每手棋都是一百分
作者: milkdragon (謝謝大家!!)   2016-01-30 18:15:00
你的圖是 min-max tree, 不是mcts喔,mcts是不平衡的樹mcts有別minmax的地方,其中一點就在於不用一視同仁地長到一樣的深度再呼叫評估函數,而可以往較好的方向長得較深,這當然是重點之一。要是長成平衡的樹,就變成worst case,大違MCTS本意了。呃……我沒有惡意,也很感謝你分享想法,不過那張圖擺明就是minmax的圖,最上層的選擇,是基於葉節點一層選min一層選max這樣推回來的,跟mcts「完全」不一樣。再說,這張圖沒有完全平衡,那是因為那些點沒辦法再往下長了,注意看那是無限的符號,代表某方獲勝了,當然不需要繼續往下長囉。mcrs當然「絕對」可以長出一顆平衡的樹,只要在selection步驟中把控制利用跟探索的平衡的參數調成一個很過分的值,這樣mcts會平均給每個候選點模擬的機會,這樣當然要多平衡有多平衡,但如此一來就成了worst casr,搜尋深度會很淺,對棋力沒有任何幫助。抱歉,手機打字,有的字打歪了,不過應該不影響閱讀吧
作者: pikachu2421 (皮卡@めぐ民)   2016-01-30 19:33:00
作者: GHowPan (豪洨)   2016-01-31 10:40:00
跟電腦下就是要下成亂鬥
作者: paulli (paulli)   2016-01-31 11:54:00
請問可借轉弈棋站嗎?謝謝
作者: aaaba (小強)   2016-01-31 21:22:00
可以轉,不過明天有空我會修正一些內容,現在的不盡正確。
作者: paulli (paulli)   2016-02-01 14:01:00
謝謝已轉文 http://goo.gl/nce6PC 謝謝您!
作者: bearching (Pandora`s Box)   2016-02-04 01:20:00
請教一下genetic programming有機會用在這個AI裡嗎
作者: ddavid (謊言接線生)   2016-02-04 03:21:00
基因演算法現今來看應該不算是很適合拿來解19x19圍棋它的本質還是search,只是找解的順序不同。然後它太依賴對好的目前盤面編碼以及評估函式,我覺得在計算時間上以及選取好著手兩個方面都不見得特別優秀
作者: ztdxqa (ztdxqa)   2016-02-04 12:38:00
基因演算法感覺好古老喔 最近有新突破嗎?
作者: wukevinboy (wukevinboy)   2016-02-04 13:27:00

Links booklink

Contact Us: admin [ a t ] ucptt.com