為什麼目前計算機能夠打敗國際象棋冠軍，但還不能擊敗職業圍棋高手？

01-28

如題。

圍棋棋盤太大，每一步可下點太多，局面判斷對計算機來說太難。

---------------------------------------------------------------------------------------------------

現在開始展開說。

首先說一下計算機下棋的方法。當前局面可以看做一個節點，當前局面下如果有10中可以走棋的方案，那麼走完其中某一步就是一個該節點的一個子節點。這樣就組成了一個很大的樹。現在我們的目的方法就是在這個樹上做搜索。

讓我們來看看樹上的節點大概在什麼量級。就象棋來說，每步大約有數十種走法，算他20好了，每盤棋有幾十個回合，算他一共100步好了，這樣下來大約有20^100這樣的空間。圍棋呢，每一步有超過100個落子點，每局平均超過200手，那麼久超過100^200。他們之間有多少個數量級的差異呢，我算不太清楚，要不你算一下？從這個角度就可以看出兩個棋種的量級上的差異。

當然計算機搜索的時候不會從當前局面一直搜到終局。通常會有一個搜索深度。也就是說計算機算了幾步。就是說期望自己在若干步之後自己的局面最好。

方法是這樣的，比如說我打算算N步（比如說N=10,20...)。那麼就看書上第N層，我當然希望我在這個節點上的子節點中選最好的MAX，然後對手就在上一層節點中選出對你最不利的節點MIN。。。最後你再在當前局面選對你最好的子節點MAX（額。表達能力好差）。算作20層的話，象棋就是10^20怎麼大的空間，圍棋還是100^20。在實際操作中，有alpha-beta剪枝這樣的演算法，可以減去不需要搜索的局面，雖然絕大部分節點都不用算了，但是搜索空間的差異還是很大。演算法前人的資料很多，這裡不貼鏈接了。圖來自《人工智慧：一種現代方法》。

沒有判斷出輸贏時，究竟一個局面怎麼算好呢？計算機中這玩意兒叫估值函數。象棋這種棋種的估值函數相對「簡單」，比如我們可以給車10分，給馬炮各5分，給士相各2分。一個棋子佔據有利地形再加點分。。。總之量化起來很方面。下過象棋或者寫過程序的人一定會覺得我剛才的估值函數雖不好，但不差。但是圍棋就麻煩很多，圍棋裡面虛的東西太多。究竟我是占實地好呢，還是占外勢好呢，程序該怎麼判定？圍棋里子還有輕重之說，程序怎麼判定？下圍棋時有時需要保留「味道」，即有些棋局部不必變化走完，先給他留著，以後說不定更有用，這種「味道」程序該怎麼判定？哎呀，太麻煩了。

（@蓋聶，如果我說得不對或者不好，你來指正一下。）

---------------------------------------------------------------------------------------------------------------------------2006年呢，人們發展出一種新的圍棋博弈演算法，叫Monte-Carlo tree search.這是一種和之前在博弈樹上演算法不同思路的東西。通俗地說，計算機會隨機產生出一大堆（比如10萬個）對局，這些對局覆蓋當前局面下若干走法。如果在走法A下隨機對局的勝率最高，那麼我就選A了。我認為這條路在一定程度上突破了搜索空間太大的枷鎖，但它本身還有太多值得研究的地方。

其實說是隨機，其實也沒那麼隨機，裡面東西可多了。這裡不展開了。扔兩篇文獻給大家。

Monte-Carlo tree search and rapid action value estimation in computer Go

http://www.aaai.org/Papers/AIIDE/2008/AIIDE08-036.pdf

最近的結果是，依田紀基讓四子輸給軟體Zen了。雖然也是業餘水平，但大家都在這條路上不斷地走。

這個題目以前答過類似的

人與電腦下國際象棋，隨著計算機性能的提升，電腦最終會不可戰勝嗎？ - 張捷的回答

只是時間問題。