围棋AI

**電腦圍棋**是人工智慧（AI）的一個領域，該領域致力於開發出可以下圍棋的電腦程式。圍棋是棋盤遊戲的一種，有很古老的歷史。

## 歷史

### alpha-beta 剪枝法

最先電腦圍棋也試圖用類似處理西洋棋的演算法 ——alpha-beta 剪枝法，即一般認為的暴力搜尋法，但成長非常慢。1986 年，應昌期懸賞 100 萬美金，徵求可以打敗人類的圍棋軟體，並以 15 年為期限，但沒有任何人拿走獎金。到了 20 世紀末，這類程式表現最好的是陳志行製作的手談，其宣稱可以接近業餘初段，至少與低段職業差距 9 子以上，其他如 GNU Go 更是只有業餘 5~10 級左右。

代表：

* 手談 (圍棋軟體)
* GNU Go

### 蒙地卡羅搜尋樹

Crazy Stone 首次引進了蒙地卡羅搜尋樹，其原理是用蒙地卡羅法快速的把棋局下至終局，然後藉此判斷局勢，用這個方法，電腦圍棋得到飛快性的成長，並突破了業餘初段的壁障。這時代表現最好的是 Zen，在 AlphaGo 出現的前一年，Zen 的平行運算版本可以達到與職業棋士差距 3~4 子的水平。

這時期開始，開始出現了 UEC 杯等電腦圍棋比賽。在其中發生一個插曲，2010 年時，黃士傑的 Erica 在 2010 電腦奧林匹亞獲得 19 路圍棋的冠軍，隔年又在 UEC 盃拿下亞軍，這在當時引起許多注目，因為 Erica 是單機程式，而其對手都是使用大型電腦，這也使得他獲得 DeepMind 公司的邀請。

代表程式：

* Zen
* Crazy Stone
* 石子旋風
* Fuego

### 深度學習

深度學習原本主要應用是圖像分析，利用電腦類比神經元，可以訓練電腦有類似人類「直覺」的反應，2014 年左右，Google DeepMind 和 facebook 等公司意識這可能可以用在處理電腦圍棋。最直接的想法是輸入人類的圍棋棋譜，並在程式中設定圍棋規則，以及各棋譜的最後勝負，利用監督學習讓電腦得到「棋感」，電腦因而可以給出特定局面下有哪些可能的行棋方法，後來這個方法在 AlphaGo 的論文中被稱為「走子網路」。2015 年左右，DeepMind 的大衛・席爾瓦意識到，其實圍棋的形勢判斷也可以交由神經網路決定，「價值網路」因此誕生。接著 DeepMind 團隊再使用強化學習 —— 大眾媒體稱之為左右互搏 —— 增強兩種神經網路，在大約三千萬盤的左右互搏後，超越了職業選手水平，這使得 DeepMind 最終贏得這項與 facebook 的競賽。

2016 年 1 月 27 日，《自然》發表了 Google DeepMind 開發 AlphaGo 的論文，於 2015 年 10 月，在未讓子的挑戰中，以 5:0 戰績，擊敗歐洲圍棋冠軍 —— 職業圍棋二段樊麾。這是電腦程式首次在公平比賽中擊敗職業棋手。2016 年 3 月，AlphaGo 在韓國首爾以 4:1 擊敗棋士李世乭。 2017 年 5 月，AlphaGo 在中國烏鎮圍棋峰會的三局比賽中以 3:0 擊敗當時世界排名第一的中國棋手柯潔。

代表程式：

* AlphaGo
* AlphaGo Zero
* CGI
* Darkforest（Facebook 最終失敗的計畫）
* DeepZenGo
* ELF OpenGo
* KataGo
* Leela
* Leela Zero
* PhoenixGo
* SAI
* 絕藝

## 難點

圍棋給程式設計師們帶來了許多人工智慧領域裡的挑戰。當如 IBM 深藍那樣的超級電腦，已經能夠擊敗世界上最好的西洋棋棋手的同時；卻有不少人能擊敗圍棋軟體。可見，要編寫出超越初級水平的電腦圍棋程式，是極其困難的一回事。

### 棋盤太大

圍棋的棋盤很大（19×19），因此通常被認為是難以編寫圍棋程式的一個重要原因。

### 可行的著法太多

與其它棋盤遊戲相比，圍棋的著法幾乎不受規則限制。中國象棋第一步有 42 種選擇，西洋棋有 20 種選擇，但圍棋有 361 種選擇。有些著法較常見，有些幾乎從未走過（例如第一步下在邊線上），但所有著法都有可能。

象棋（以及大部分棋盤遊戲如西洋跳棋和雙陸棋）棋局過程中，棋子數逐漸減少，使遊戲簡化。但是，圍棋中每下一子，都可能有其戰略意義，使得單純分析戰術並不管用，會使局勢變得更複雜。

### 估值函式

### 組合問題

## 策略搜尋

## 狀態表示

## 系統設計

### 處理問題的新方法

### 程式語言選擇

### 設計哲學

#### Minimax 樹搜尋

#### 蒙特卡羅方法

#### Knowledge-based 系統

#### 機器學習

## 電腦圍棋程式的競賽

### 歷史

第一個電腦圍棋競賽是由 USENIX 贊助，在 1984 年到 1988 年間舉行。

宏碁電腦公司與應昌棋圍棋基金會從 1986 年開始，聯合舉辦電腦圍棋競賽，獲得冠軍的程式，可以挑戰職業棋士，獲勝獎金美金一百萬元。有效期至 2000 年。

### 電腦對電腦程式中的問題

## 注釋和參考

### 參考文獻

1. AI-oriented survey of Go（頁面存檔備份，存於網際網路檔案館）
2. Monte-Carlo Go, presented by Markus Enzenberger, Computer Go Seminar, University of Alberta, April 2004
3. Monte-Carlo Go（頁面存檔備份，存於網際網路檔案館）, written by B. Bouzy and B. Helmstetter from Scientific Literature Digital Library
4. Static analysis of life and death in the game of Go（頁面存檔備份，存於網際網路檔案館）, written by Ken Chen & Zhixing Chen, 20 February 1999
5. Co-Evolving a Go-Playing Neural Network（頁面存檔備份，存於網際網路檔案館）, written by Alex Lubberts & Risto Miikkulainen, 2001

## 參見

* 圍棋 #圍棋軟體與人工智慧
* 電腦象棋
* 電腦將棋
* 圍棋程式列表
* Go Text Protocol

## 外部連結

### General info

* Online Computer Go bibliography.
* Computer Go（頁面存檔備份，存於網際網路檔案館） and Computer Go Programming（頁面存檔備份，存於網際網路檔案館） pages at Sensei's Library（頁面存檔備份，存於網際網路檔案館）
* computer-go mailing list
* The Computer Go Room on the Kiseido Go Server（頁面存檔備份，存於網際網路檔案館） (KGS) for online discussion and running "bots"
* Playing with Shannon: a forum about computer go programming

### Specific info

* Information on the Go Text Protocol（頁面存檔備份，存於網際網路檔案館） commonly used for interfacing Go playing engines with graphical clients and internet servers
* Kinger, Tim and Mechner, David. _An Architecture for Computer Go_ (1996 年)
* Published articles about computer go on Ideosphere（頁面存檔備份，存於網際網路檔案館） gives current estimate of whether a Go program will be best player in the world
* XS4All Internet B.V.（頁面存檔備份，存於網際網路檔案館）
* Minimalism in Ubiquitous Interface Design（頁面存檔備份，存於網際網路檔案館） by Wren and Reynolds describes a simple computer vision system for playing Go

### 電腦程式

* Go++ by Michael Reiss
* Handtalk（頁面存檔備份，存於網際網路檔案館）, developed in China by Zhixing Chen
* The Many Faces of Go（頁面存檔備份，存於網際網路檔案館） by David Fotland
* KCC（頁面存檔備份，存於網際網路檔案館） Igo, from Korea (sold as Silver Star in Japan)
* Go Intellect（頁面存檔備份，存於網際網路檔案館） by Ken Chen
* GNU Go （頁面存檔備份，存於網際網路檔案館）, the strongest open source Go program
* Smart Go（頁面存檔備份，存於網際網路檔案館） by Anders Kierulf, inventor of the Smart Game Format
* Free Go Software（頁面存檔備份，存於網際網路檔案館）
* GoKnot, a Windows solution open for developing
* MIni GO Solver
* AYA by Hiroshi Yamashita
* CrazyStone（頁面存檔備份，存於網際網路檔案館） by Rémi Coulom
* GNU Go, the strongest open source Go program
* Go++ by Michael Reiss (sold as _Strongest Go_ or Tuyoi Igo in Japan)
* Go Intellect by Ken Chen
* Handtalk/Goemate, developed in China by Zhixing Chen (sold as Shudan Taikyoku in Japan)
* Haruka by Ryuichi Kawa (sold as Saikouhou in Japan)
* Indigo by Bruno Bouzy
* Katsunari by Shin-ichi Sei
* KCC Igo, from North Korea (sold as Silver Star or Ginsei Igo in Japan)
* The Many Faces of Go（頁面存檔備份，存於網際網路檔案館） by David Fotland (sold as AI Igo in Japan)
* MoGo by Sylvain Gelly
* Smart Go（頁面存檔備份，存於網際網路檔案館） by Anders Kierulf, inventor of the Smart Game Format
* Leela 及 Leela Zero

### Computer Go vs human/computer & tournament

* Comprehensive list of past computer go events（頁面存檔備份，存於網際網路檔案館）
* All systems Go by David A. Mechner, discusses the game where professional go player Janice Kim won a game against program Handtalk after giving a 25-stone handicap.
* Two Representative Computer Go Games（頁面存檔備份，存於網際網路檔案館）, an article about two computer go games, the one with two computers players, and the other, a 29-stone handicap human-computer game