電腦棋力的問題 - 圍棋

※ 引述《livedeader (歡迎找我下棋)》之銘言：
: 我不大會下圍棋
: 但至少懂些基本規則
: 幾乎大部分的棋類我都會
: 西洋棋象棋五子棋圍棋等
: 為什麼圍棋的電腦AI最難寫？
: 因為對圍棋不甚瞭解所以特來請教
: 如果可以我對象棋最為熟悉
: 可以拿象棋跟圍棋比較一下嗎？
: 謝謝回答
寫程式解決這些問題的時候
通常都是用搜尋的方式, 簡單的說是窮舉法
方法就是窮舉所有的步數
然後在一定的深度時停下來算分數
最後把結果一層層往上傳
(每個節點會選對該方有利的走法)
在使用搜尋方法解決棋類遊戲時
通常都會有幾個共通的難題

1. 可以選擇的步太多, 窮舉不太可能窮舉太深

舉例來說, 如果平均一方可以有 10 步選擇,
那麼搜尋 10 層就要看過 10^10 個節點, 哇! 天文數字.. orz

2. 最後要算分數時, 怎麼把一個盤面的好壞量化成數字

用您熟悉的象棋來說, 比如空頭炮好不好? 三子歸邊好不好?
哪個好? 要給幾分才能說明他有多好?
如果讓你選, 你可以取得空頭炮, 但是對方會三子歸邊, 你肯不肯?
有時候問題會更複雜, 好幾個組合, 要怎麼評分呢?

其他的比較和電腦本身限制相關的我先不提, 光這兩點就很頭痛了

對於象棋來說, 1. 其實還不會太嚴重
透過某些對搜尋演算法的改進, 其實仍然是可以做得很好
一來, 象棋的子數就比較少, (和西洋棋一樣, 只是格子多了點)
二來, 選擇性會隨著盤面上的子變少而漸漸減少
三來, 透過一些技巧或是某些 heuristic (我不知道怎麼翻譯好 @@")
可以讓需要搜尋的盤面數量減少不少
( 如果你有興趣, 可以看看類似 alpha-beta search 之類的東西
對 AI 熟的話應該就更有概念了 )

再者, 對於 2. 我們可以很清楚知道大致上
一車抵馬炮, 一馬抵雙相之類的概念
同時, 也有很多棋諺也告訴我們了一些評分的概念
雖然有一些還是很難量化, 但是仍然比較有線索可循

在圍棋來說, 1. 的問題就非常嚴重
他的走法選擇遠比象棋多很多
而且, 我們也沒有辦法很明確的告訴電腦
到底什麼時候要用什麼定石
什麼時候被衝了要補
什麼時候要手拔
這種整個局勢的概念, 不太容易描述成量化讓電腦了解
甚至是盤根錯節的死活問題
電腦也很難看清楚先後手哪邊大, 哪邊小
( 是人類都不一定找得出夠有效率的算法, 但是電腦得要人類教他算法才會算 )
簡言之, 這種選擇多又評分難的棋類, 完全是中了前述的兩個難題

目前在做電腦圍棋的大多採用 pattern match 的方式
把某些緊急一定要處理的 pattern 評分加高
然後局部算出來的結果再合起來看
哪邊最急切或是最大場先下哪邊
也許還會在緊急的部分定幾個關鍵點去作局部的搜尋
但是這些 pattern match 會有互相矛盾的地方
同時也很難真的把所有情況都概擴
所以遇到電腦資料庫裡沒有的棋形, 電腦就會亂下
( 常常有人說 GnuGo 有時會下得很無厘頭的一手, 也許是這種情形也不一定 XD )
把所有棋形都列舉出來就能解決問題嗎? 顯然不是這麼簡單
因為你還要決定哪個比較大, 但是有些還要考慮到棋形的組合
總之就是一團複雜...

總而言之, 電腦會看實利, 但不見得會看勢力
但是這種勢力的概念, 人類一眼就看得出來, 但是沒辦法講出個所以然來
只要你越是講不出個所以然來 (還要很 detail, 告訴電腦個好壞的順序)
那麼電腦就越不會解決這種問題

象棋程式目前遇到的問題也就是這個
搜尋的深度夠其實沒有意義, 重點是要知道什麼是真正的 "好" 棋

--

有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。
　存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你
　，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也
　是比較不容易被擊倒的人。

--