计算机围棋

{{About|可下围棋的電腦程式|-{zh-hans:通过; zh-hant:通過; zh-tw:透過;}-網際網路下棋|網路圍棋}}

计算机围棋是人工智能（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选择。有些着法较常见，有些几乎从未走过（例如第一步下在边线上），但所有着法都有可能。

象棋（以及大部分棋盘游戏如西洋跳棋和双陆棋）棋局过程中，棋子数逐渐减少，使游戏简化。但是，围棋中每下一子，都可能有其戰略意義，使得單純分析戰術並不管用，会使局势变得更复杂。

估值函数
组合问题
策略搜索
状态表示
系统设计
处理问题的新方法
编程语言选择
设计哲学
Minimax 树搜索
蒙特卡罗方法
Knowledge-based 系统
机器学习
電腦圍棋程序的竞赛
历史
第一個電腦圍棋競賽是由USENIX贊助，在1984年到1988年間舉行。

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

电脑对电脑程序中的问题
注释和参考
参考文献
#[http://citeseer.ist.psu.edu/bouzy01computer.html AI-oriented survey of Go]
#[https://web.archive.org/web/20040919093249/http://www.cs.ualberta.ca/~emarkus/monte-carlo/monte-carlo.pdf Monte-Carlo Go], presented by Markus Enzenberger, Computer Go Seminar, University of Alberta, April 2004
#[http://www.math-info.univ-paris5.fr/~bouzy/publications/bouzy-helmstetter.pdf Monte-Carlo Go], written by B. Bouzy and B. Helmstetter from Scientific Literature Digital Library
#[http://www.cs.ualberta.ca/~games/go/seminar/2002/020703/ld.pdf Static analysis of life and death in the game of Go], written by Ken Chen & Zhixing Chen, 20 February 1999
#[http://nn.cs.utexas.edu/downloads/papers/lubberts.coevolution-gecco01.pdf Co-Evolving a Go-Playing Neural Network], written by Alex Lubberts & Risto Miikkulainen, 2001

参见

• 慧;}-
• 電腦象棋
• 電腦將棋
• 围棋程序列表
• 圍棋文字協議

外部链接
General info

• [https://web.archive.org/web/20070714221230/http://www.cs.ualberta.ca/~emarkus/compgo_biblio/ Online Computer Go bibliography].

*[http://senseis.xmp.net/?ComputerGo Computer Go] and [http://senseis.xmp.net/?ComputerGoProgramming Computer Go Programming] pages at [http://senseis.xmp.net Sensei's Library]
*[https://web.archive.org/web/20060823204015/http://computer-go.org/mailman/listinfo/computer-go/ computer-go mailing list]

• The Computer Go Room on the [http://kgs.kiseido.com Kiseido Go Server] (KGS) for online discussion and running "bots"

*[https://web.archive.org/web/20070519083703/http://mizarchessengine.agff.net/ Playing with Shannon]: a forum about computer go programming

Specific info
*[http://www.lysator.liu.se/~gunnar/gtp/ Information on the Go Text Protocol] commonly used for interfacing Go playing engines with graphical clients and internet servers

• Kinger, Tim and Mechner, David. [https://web.archive.org/web/20061029224917/http://www.cns.nyu.edu/~mechner/compgo/acg/ An Architecture for Computer Go] (1996年)

• Published articles about computer go on [http://www.ideosphere.com/fx-bin/Claim?claim=GoCh Ideosphere] gives current estimate of whether a Go program will be best player in the world
• [http://www.xs4all.nl/~janrem/Artikelen/Artikelen.html XS4All Internet B.V.]
• [http://affect.media.mit.edu/pdfs/04.wren-reynolds.pdf Minimalism in Ubiquitous Interface Design] by Wren and Reynolds describes a simple computer vision system for playing Go

计算机程序

• [https://web.archive.org/web/20030525163644/http://www.goplusplus.com/ Go++] by Michael Reiss
• [http://www.airgo.com.tw/progdetail_online.asp?id=G029&type=G Handtalk], developed in China by Zhixing Chen
• [http://www.smart-games.com/manyfaces.html The Many Faces of Go] by David Fotland
• [http://www.silverstar.co.jp KCC] Igo, from Korea (sold as Silver Star in Japan)
• [http://www.yutopian.com/go/soft/EAC19.html Go Intellect] by Ken Chen
• [http://www.gnu.org/software/gnugo GNU Go ], the strongest open source Go program
• [http://www.smartgo.com/ Smart Go] by Anders Kierulf, inventor of the Smart Game Format
• [http://www.gnu.org/software/gnugo/free_go_software.html Free Go Software]
• [https://web.archive.org/web/20100127065951/http://www.goknot.eu.com/ GoKnot, a Windows solution open for developing]
• MIni GO Solver
• [https://web.archive.org/web/20061211061341/http://www15.ocn.ne.jp/~yss/ AYA] by Hiroshi Yamashita
• [http://remi.coulom.free.fr/CrazyStone/ CrazyStone] by Rémi Coulom
• GNU Go, the strongest open source Go program
• [https://web.archive.org/web/20030525163644/http://www.goplusplus.com/ 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)
• [http://www.smart-games.com/manyfaces.html The Many Faces of Go] by David Fotland (sold as AI Igo in Japan)
• [https://web.archive.org/web/20061128074317/http://www.lri.fr/~gelly/MoGo.htm MoGo] by Sylvain Gelly
• [http://www.smartgo.com/ Smart Go] by Anders Kierulf, inventor of the Smart Game Format
• Leela及Leela Zero

Computer Go vs human/computer & tournament

• [http://www.computer-go.info/events/index.html Comprehensive list of past computer go events]
• [https://web.archive.org/web/20061029225411/http://www.cns.nyu.edu/~mechner/compgo/sciences/ 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.

*[http://www.cs.ualberta.ca/~mmueller/cgo/survey/twogames.html 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