计算机围棋
此条目介绍的是可下围棋的计算机程序。关于通过互联网下棋，请见“网络围棋”。此条目需要扩充。 (2010年11月28日) |
历史
alpha-beta 剪枝法
最先计算机围棋也试图用类似处理国际象棋的算法——alpha-beta 剪枝法，即一般认为的暴力搜索法，但成长非常慢。1986年，应昌期悬赏100万美金，征求可以打败人类的围棋软件，并以15年为期限，但没有任何人拿走奖金。到了20世纪末，这类程序表现最好的是陈志行制作的手谈，其宣称可以接近业余初段，至少与低段职业差距9子以上，其他如GNU Go更是只有业余5~10级左右。
代表：
蒙地卡罗搜索树
Crazy Stone首次引进了蒙地卡罗搜索树，其原理是用蒙地卡罗法快速的把棋局下至终局，然后借此判断局势，用这个方法，计算机围棋得到飞快性的成长，并突破了业余初段的壁障。这时代表现最好的是Zen，在AlphaGo出现的前一年，Zen的平行运算版本可以达到与职业棋手差距3~4子的水平。
这时期开始，开始出现了UEC杯等计算机围棋比赛。在其中发生一个插曲，2010年时，黄士杰的Erica在2010计算机奥林匹亚获得19路围棋的冠军，隔年又在UEC杯拿下亚军，这在当时引起许多注目，因为Erica是单机程序，而其对手都是使用大型机，这也使得他获得DeepMind公司的邀请。
代表程序：
深度学习
深度学习原本主要应用是图像分析，利用计算机模拟神经元，可以训练计算机有类似人类“直觉”的反应，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]的中国棋手柯洁。
代表程序：
- 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年。
电脑对电脑程序中的问题
注释和参考
- ^ 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） （英语）.
- ^ 开明. 面对谷歌围棋AI，人类最后的智力骄傲即将崩塌. 2016-01-28 [2016-01-29]. （原始内容存档于2016-01-28）.
- ^ Google’s AlphaGo Continues Dominance With Second Win in China. 2017-05-25 [2017-05-27]. （原始内容存档于2017-05-27）.
- ^ 柯洁迎19岁生日 雄踞人类世界排名第一已两年. May 2017 [2017-05-27]. （原始内容存档于2017-08-11） （中文）.
- ^ 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
参见
外部链接
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