计算机围棋 - Wikiwand

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

此條目需要擴充。 (2010年11月28日)

歷史

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擊敗棋士李世乭。^[1]^[2] 2017年5月，AlphaGo在中國烏鎮圍棋峰會的三局比賽中以3:0擊敗^[3]當時世界排名第一^[4]^[5]的中國棋士柯潔。

代表程式：

難點

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

棋盤太大

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

可行的着法太多

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

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

估值函數

組合問題

策略搜尋

此章節尚無任何內容，需要擴充。

狀態表示

此章節尚無任何內容，需要擴充。

系統設計

此章節尚無任何內容，需要擴充。

處理問題的新方法

程式語言選擇

設計哲學

Minimax 樹搜尋

蒙特卡羅方法

Knowledge-based 系統

機器學習

電腦圍棋程式的競賽

歷史

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

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

電腦對電腦程式中的問題

註釋和參考

[1]
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel & Demis Hassabis. 深度神经网络加树形检索可以下围棋了. 2016-01-27 [2016-01-29]. （原始內容存檔於2019-09-24）（英語）.
[2]
開明. 面对谷歌围棋AI，人类最后的智力骄傲即将崩塌. 2016-01-28 [2016-01-29]. （原始內容存檔於2016-01-28）.
[3]
Google’s AlphaGo Continues Dominance With Second Win in China. 2017-05-25 [2017-05-27]. （原始內容存檔於2017-05-27）.
[4]
柯洁迎19岁生日雄踞人类世界排名第一已两年. May 2017 [2017-05-27]. （原始內容存檔於2017-08-11）（中文）.
[5]
World's Go Player Ratings. 24 May 2017 [2017-05-27]. （原始內容存檔於2017-04-01）.

參考文獻

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

參見

外部連結

維基教科書中的相關電子教學：Computer Go

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