计算机围棋开题报告

选题的依据及意义

计算机围棋的研究和实现需要多门学科的知识交叉，至少会涉及到围棋、计算机、数学、生物乃至哲学等领域。从程序员角度狭义地看计算机围棋，它是计算机技术在围棋上的应用，即编写一个下围棋的程序，是计算机智能足以在棋局总得到发挥。从大的方面看，研究计算机围棋，也是探索机器智能、揭穿人类及其他生物智能秘密的一个重要的途径。

电脑围棋发展的历史约有三十年左右，目前世界上最强的电脑围棋程式棋力约业余二段（被让7-9个子），仅相当业余棋手的中等水平，更不是职业棋士的对手。围棋是目前唯一在世界各地有广大爱好者及职业制度，但电脑城是只停留在业余中等水准的对局游戏，所以电脑围棋可说是人工智慧的一项新的重大挑战。

围棋博弈的过程一般划分为3各阶段：序盘、中盘和收官。中盘泛指双方棋块短兵相接，攻击以防借助攻击对方不安定棋块获利，或杀死对方棋块而围成大空；而防守一方处理自己不安定棋块，将损失减少到最小的阶段。中盘的攻防大致发生在布局结束，到双方所有棋块皆进入安定状态，开始收官为止。中盘是围棋博弈过程中手数最多，同时也是最为重要的阶段。处理中盘问题能力的强弱直接影响围棋对弈软件水平的高低。因此，专门的中盘问题求解程序有着一定的实用价值。目前，围棋程序通常单纯以实空作为形势判断的依据，并以可成空目数最大作为最佳棋步的评判标准。然而，在围棋比赛中，输赢的结果与输赢多少目无关。职业棋手是本着赢下整场比赛而不是追求具体赢多少目的目标来思考棋步，但以实空为依据的程序却常会犯在遥遥领先时依然追杀对手不安定棋块的战略性错误，因为按照它的计算，追杀似乎可以获得更多的目数。

目前中盘系统还需增强的部分为对于棋块死活的判断，一个棋块死活的资讯将大大影响中盘的策略。这个问题应该归纳与电脑围棋形势判断的问题上，也就是说，我们必须再加强形势判断系统的准确度，才能使得中盘处理的能力更为加强。

二、国内外研究概况及发展趋势（含文献综述）

电脑围棋自Zobrist在1970年设计出第一個可与人对弈的程式以來[1]，至今已有

约三十年的历史。由于围棋本身的特质，使得电脑围棋在继西洋棋、象棋之後，成为人工智慧中一个相当引人注目的新挑战。

然而电脑围棋的难点之一，便在于缺乏良好的审局函数[2]，使其不能与西洋棋或象棋一般，运用设计良好的审局函数、搜寻树以及优秀的剪枝法，即可获得不错的棋力；电脑围棋大多藉由一些经验法则，以静态的评估为主，而动态的搜寻则僅用于局部的、目标明确的棋串攻杀，较少全局的搜寻。因此，人类的经验如何用于电脑围棋，就成了设计的重点。

自2003年起，Bouzy[3]试图打破这种情況。他运用蒙地卡罗法作为评估函数，并且试图运用此一评估函数，做全局性搜寻，然而在棋力上始终没有太大的突破。知道2006年，同样使用蒙地卡罗法的程式Crazy Stone[4,5]，才在杜林举行的第11届电脑奥林匹亚的九路围棋项目中获得金牌。虽然如此，Crazy Stone仅在19路围棋项目中获得第五名，仍未撼动以人类思维为主的围棋程式在19路围棋的地位。

然而，随着基于蒙地卡罗的搜寻法[UCT][9]的出现，以UCT为基础的围棋程式MoGo[6,7,8]也逐渐在一些较非正式的比赛中崭露头角。2007年6月，第12届电脑奥林匹亚于阿姆斯特丹举行，上届冠军GNUGO、亚军GO Intellect以及前文介绍过的Crazy Stone等程式均有参赛，MoGo在强敌环伺之下，以全胜战绩夺得了9路围棋项目的金牌，Crazy Stone也拿到了第二名，GNUGO退居第三。这象征着UCT的成功，也代表一個崭新的局面即将到來。

1.研究现状

当前，计算机围棋中活跃的电脑程式：

(1) MoGo

MoGo的作者为Sylvain Gelly，这个程式是第一个使用UCT为基础的电脑程式，他落子的特性为：布局很差，甚至没有布局，但是擅长于近距离接触战，也擅长收官，这可以说是所有以蒙地卡罗为基础的围棋程式共同特性。另一个特别之处在于，此程式若赢棋，则必赢半目；若输棋，则必输得极惨。此外，若给予其越多的思考用时，则棋力会越强。

如前所诉，UCT主要分为搜寻部分以及模拟棋局部分。就搜寻部分而言，MoGo运用CFG[10]来区分棋块，并且将距离上一手以及上上手的棋块太远的着手予以裁剪，以适应过大的棋盘：就模拟棋局而言，MoGo运用基本的Heuristic以及手工打造的Pattern以使模拟棋局的着手更有意义，以增强棋力。这个程式曾在九路的非正式对局中战胜过职业棋士[11]。

(2) Crazy Stone

Crazy Stone的作者为Rémi Coulom，此程式曾于2006年11届电脑奥林匹亚的九路围棋项目夺得金牌，也是运用蒙地卡罗法成功的案例之一。其特性与MoGo相当类似，在此不再赘述。

Crazy Stone引人注目的之处在于，它跳脱既有的传统Pattern思维。传统的Pattern，指的是棋子建的分布关系，也就是所谓的“棋形”：对于棋形以外的资讯，着墨甚少。Crazy Stone针对这部分的缺陷，提出了新的看法。首先，他对每一个着手，找出其特征，例如长、提、叫吃、与盘端距离、与上一手距离···等等，然后从业余高段棋士棋谱里学习，分析每一种特征的重要性，并据此得出了一份重要的表格。执行模拟棋局时，就分析每一个可能着手的特征，得出其重要的分数，并依此算出选择此着手的几率，依几率落子。使用这种新方法，Crazy Stone对GNUGO的胜率，从38%提升到了68%。

除此之外，它还采用了“Progressive Widening”的技术。这个技术跟“Progressive Unpruning”有异曲同工之妙，其出发点都是为了减少搜寻数的分支度。首先，Crazy Stone先依着手几率排序，随着模拟次数逐渐增多，再逐渐开放子点以供选择。此方法使其胜率从68%提升到了90%。

(3) GNUGO

GNUGO最特别之处在于，这个软体没有特定的作者，因为这是一个自由软体，遵守GNU规范，其作者统称为GNUGO Development。这个软体自2001年开始发展以来，有世界各地的作者们通力合作，棋力日强，曾获得2003、2006年电脑奥林匹亚19路围棋项目的冠军，其余大小比赛亦获奖无数。

这个软体是典型的以人类思维为基础的程式，他有一个相当精致的Pattern资料库[12]，它的棋风与MoGo等以蒙地卡罗为基础的程式完全不同，而更接近人类的下法，且由于Pattern的关系，此程式棋形一般而言都很漂亮。

2.发展趋势

计算机围棋发展至今的一些代表性程式为陈志行教授的HandTalk、陈克训教授的Go Intellect、Mark Boon的Goliath和许舜钦教授的学生们所制作的程式以及开放源代码GNUGO。还有一些计算机围棋软件的界面还是基于DOS命令下的，以字符界面方式工作，通过命令提示符输入坐标及相应的命令来下棋。计算机围棋发展初期的八十年代，围棋程式以大约每两级的速度在进步，而到了九十年代电脑围棋已经发展到某一程度，但仍以大约每年一级的速度在稳定进步中，由此看来，电脑围棋目前

仍在稳定发展之中，另一方面，由各围棋程式各有特色来看，电脑围棋还有相当大的发展空间。

三、研究内容及实验方案

1、研究内容

以获胜概率作为形势判断的依据，根据形势判断的结果动态调整攻防力度；并根

据组合赛局模型构建全局搜索算法，寻找最佳棋步。基于这种方法在Visual studio C++平台上实现了一个中盘问题求解程序。

(1) 攻防力度调整权值

(2) 候选棋步的产生和量化

(3) 最佳棋步的确定

2、实验方案

对于中盘着手策略的显示按照以下几个模块进行：

(1) 视频实时显示的用户界面的设计

为了使用起来的方便和有效，需要对19路棋盘的工作界面进行良好的设计，以使得用户在不具备具体专业知识的情况下能轻松使用该软件进行操作。

(2) 按键设计

新建：新建棋局

选择黑白：选择黑棋或者白棋

交替落子：黑白双方交替落子

(3) 落子设计

在棋盘上只有在棋盘上，只有交叉点才可以落下棋子，大多数时候我们不可能每次都下的那么准，都精确的落在交叉点上。这又涉及到坐标计算的问题，只有计算好坐标，我们才能精确的落下棋子，而且鼠标的捕捉为题也迎刃而解。而这又需要程序的支持。

(4) “着手菜单”选择

候选点：根据运算法则，搜索候选棋步，并标记于棋盘上

最佳棋步：评估候选棋步价值，根据“权值调整”的选项决定是否对评估值进行调整，最终获得最佳棋步，标记于棋盘上。

3、方案图解及流程图

3.1 系统软件功能模块图

3.2 系统流程图

四、目标、主要特色及工作进度

主要特色： 1.自由落子，操作方便

2.提供中盘时的落子点候选及最佳落子点 目 标：建立系统界面，提供中盘时的落子点候选及最佳落子点。

工作进度：01～03周：资料查找、方案论证、开题报告撰写和英文资料翻译。

04～11周：程序流程框图编制、源程序设计，初步调试。

12～15周：系统联调，实验测试。

16～18周：毕业论文撰写，答辩。

五、参考文献

[1] Zobrist,A.L.

[2] Jay Burmeister and Janet Wiles.

[3] Bouzy,B.and Helmstetter, B.

[4]Rémi Coulom.

[5] Rémi Coulom.

[6] Sylvain Gelly, Yizao Wang, Rémi Munos, and Olivier Teytaud.

[7] Sylvain Gelly and Yizao Wang.

[8] Sylvain Gelly and David Silver.

[9] L. Kocsis and C. Szepesvari.

[10] Thore Graepel, Mike Goutrie, Marco Krüger, and Ralf Herbrich. ―Learning on graphs in the game of Go.‖ In International Conference on Artificial Neural Networks (ICANN-01), Vienna, Austria, 2001.

[11] Sylvain Gelly and Yizao Wang ,

[12] Tanguy Urvoy and gnugo team.

[13] 颜士净、许舜钦，

[14] 颜士净、许舜钦，