電腦圍棋

電腦圍棋是人工智慧（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是單機程式，而其對手都是使用大型電腦，這也使得他獲得Google 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），因此通常被認為是難以編寫圍棋程序的一個重要原因。

### 可行的著法太多

與其它棋盤遊戲相比，圍棋的著法幾乎不受規則限制。中國象棋第一步對稱的形狀不算有23種選擇，西洋棋有20種選擇，但圍棋對稱的形狀不算也有55種選擇,第二手,看是否有對稱情況可以有54-360選擇。有些著法較常見，有些幾乎從未走過（例如第一步下在邊線上），但所有著法都有可能。

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

## 電腦圍棋程序的競賽

### 歷史

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

宏碁電腦公司與應昌棋圍棋基金會從1986年開始，聯合舉辦電腦圍棋競賽，獲得冠軍的程式，可以挑戰職業棋士，獲勝獎金美金一百萬元。有效期至2000年。當時參加比賽的有來自英國、美國、荷蘭的各國好手、如Bruce Wilcox，及國內選手包括台灣大學資訊系的許舜欽教授和其學生王若曦、曹國明、高國元、劉東岳等人，以及台北醫學院學生杜貴崇、第三波雜誌推薦的張盛舒等共12名選手同台競技。

## 注釋和參考

### 參考文獻

- AI-oriented survey of Go
- Monte-Carlo Go, presented by Markus Enzenberger, Computer Go Seminar, University of Alberta, April 2004
- Monte-Carlo Go, written by B. Bouzy and B. Helmstetter from Scientific Literature Digital Library
- Static analysis of life and death in the game of Go, written by Ken Chen & Zhixing Chen, 20 February 1999
- Co-Evolving a Go-Playing Neural Network, written by Alex Lubberts & Risto Miikkulainen, 2001

## 外部連結

### 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