计算机围棋

此条目需要扩充。 (2010年11月28日)
请协助改善这篇条目，更进一步的信息可能会在讨论页或扩充请求中找到。请在扩充条目后将此模板移除。

计算机围棋是人工智能（AI）的一个领域，该领域致力于开发出可以下围棋的电脑程序。围棋是棋盘游戏的一种，有很古老的历史。

历史

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]的中国棋手柯洁。

代表程序：

难点

编辑

围棋给程序员们带来了许多人工智能领域里的挑战。当如IBM深蓝那样的超级计算机，已经能够击败世界上最好的国际象棋棋手的同时；却有不少人能击败围棋软件。可见，要编写出超越初级水平的计算机围棋程序，是极其困难的一回事。

棋盘太大

编辑

围棋的棋盘很大（19×19），因此通常被认为是难以编写围棋程序的一个重要原因。

可行的着法太多

编辑

与其它棋盘游戏相比，围棋的着法几乎不受规则限制。中国象棋第一步有42种选择，国际象棋有20种选择，但围棋有361种选择。有些着法较常见，有些几乎从未走过（例如第一步下在边线上），但所有着法都有可能。

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

估值函数

编辑

组合问题

编辑

策略搜索

编辑

此章节尚无任何内容，需要扩充。

状态表示

编辑

此章节尚无任何内容，需要扩充。

系统设计

编辑

此章节尚无任何内容，需要扩充。