基于模式匹配和静态评估的计算机围棋布局问题求解算法

余磊 陈涵

摘要：提出了一種基于模式匹配和静态评估的计算机围棋布局问题求解方法，包括候选棋步的产生、量化以及最佳棋步的确定等;并据此实现了一个围棋布局问题求解程序BeginGame。通过测试，职业棋手评估BeginGame处理布局问题的水平约为业余1段，其棋力完全可以应用于当前的围棋对弈软件中，在计算机博弈、人工智能、游戏软件的研究中具有实际应用意义。

关键词：模式匹配;静态评估;布局问题;围棋

中图分类号：R318.08 文献标识码：A 文章编号：1007-9416（2018）12-0113-01

1 候选棋步的产生和量化

布局时的行棋目标大致可以分为“占据空角”、“完成定式”、“挂角”、“拆边”、“模样”（包含“形成己方模样”和“破坏对方模样”）等5类。根据上述分类，BeginGame的数据库相应预设了一些由围棋的棋理和棋形而来的模式。实验表明，在模式的帮助下，程序可以较为容易的寻找出布局阶段的候选棋步。候选棋步越多，找寻到最佳棋步的概率也越大;但由于在实际对弈时思考时间有限，因此为了能够准确量化，候选棋步必须越少越好。根据大量的实战经验，BeginGame设定候选棋步的数量为10-20步。

1.1 占据空角棋步的产生和量化法则

围棋中，占据空角的方法一般有：三·三、小目、星位、目外和高目（五·五，超高目等特殊的占据空角的方法由于使用较少，且后续变化不易掌握，因此将其舍去）。

由于占据空角的形式变化较少，因此我们采用模式匹配来进行量化。在BeginGame中，占据空角的量化值如表1所示。

从表1可以看出，不论三·三、小目、星位、目外还是高目，每一种占据空角棋步的价值完全相等（都为20目），这表明占据空角的形式没有优劣，只是每种棋步的侧重点不同（侧重实空或外势）。根据表1，我们能获得占据空角棋步的对内和对外影响值，这对于将来选择偏重实空还是偏重外势的棋步至关重要。

1.2 定式中棋步的产生和量化法则

古今中外的棋手，经过多次对弈实践，对于角上着子，逐渐形成的一些被公认比较妥善的程式，被称之为“定式”。定式是棋手们长期的实践和理论上的归纳，一般是默认的最佳并且双方都能接受的走法。

为了给中盘战斗留出尽可能多的思考时间，我们需要在布局阶段尽可能快的做出决策;因此，在角部的战斗中，我们通常选择定式的着法。我们创建定式树，采用搜索法来解决定式问题。通过搜索当前节点的子节点，我们可以预知下一步能有多少种选择。这些子节点的位置就是定式的候选棋步。我们将定式中棋步的顺序输入数据库，并赋以相应的量化值。因此，我们可以通过搜索定式树中的节点来获得量化值。

1.3 拆边棋步的产生和量化法则

拆边是指棋子由角向边的展开过程。BeginGame中，我们采用模式匹配来产生候选棋步。模式匹配分为以下两种：

（1）根据一些围棋谚语（例如：“立二拆三”、“立三拆四”等等），获得相应模式;（2）围棋中，如果一条边上的两个空角已经被占据，那么这条边上离两个角上的子距离相等的点通常都是最佳棋步点;再根据角部棋子的位置和颜色，确定最佳棋步点在三线还是四线。

量化拆边棋步的过程主要遵循以下原则：

（1）计算拆边棋步的对内影响值;（2）计算拆边棋步的对外影响值;（3）如果此棋步能削弱对方棋块，计算削弱的价值;（4）计算对方占据此点的对内影响值，对外影响值，和对我方棋块的削弱值;（5）拆边棋步的量化值为 。

1.4 模样棋步的产生和量化法则

模样分为形成己方模样和破坏对方模样，其中最主要的棋步是：“一间跳”、“二间跳”、“小飞”、“大飞”等等。形成己方模样或破坏对方模样的棋步往往出现在棋盘中央，关乎双方此消彼长的重要一手通常在黑白棋阵之间的位置（围棋术语中称之为“急所”）。凭借上述围棋规律，我们能通过运用模式匹配的方法来找到候选棋步。

在量化模样棋步时，我们同样考虑棋步的对内和对外影响值，量化方法与拆边棋步的量化法则类似。模样棋步的量化值。

2 最佳棋步的确定

根据围棋本身的规律和实验经验，BeginGame在实战中优先考虑占据空角候选棋步;其次考虑定式候选棋步;如果没有占据空角候选棋步或定式候选棋步，则再比较拆边候选棋步、模样候选棋步的价值，从中选出价值最高的棋步作为最佳棋步。

3 结语

本文提出了一种基于模式匹配和静态评估的计算机围棋布局问题求解方法。根据棋局状态和行棋目的，将候选棋步分为占据空角、定式、拆边、模样棋步等四部分;采用模式匹配的方法解决占据空角和定式问题，采用静态评估算法解决拆边和模样问题。实验结果表明，BeginGame在布局问题的处理方面具备业余1段的水平，它已应用于计算机围棋程序CognitiveGo中，并取得了较好的实战效果。

参考文献

[1]周明明，高航，赵国安.UCT算法在计算机围棋中的应用与改进[J].数据采集与处理，2012，27（S2）：330-335.

[2]陈磊.计算机围棋领域概念网的设计与实现[D].北京邮电大学，2010（2）：1-4.

[3]王可佳，刘知青.通过围棋博弈棋谱分析进行棋手水平判定[J].中国科技论文在线，2009：1-12.

Algorithm for Solving Computer Go Layout Problem Based on

Pattern Matching and Static Evaluation

YU Lei， CHEN Han

（Key Laboratory of Nondestructive Testing Technology， Ministry of Education，

Nanchang Hangkong University， Nanchang Jiangxi 330063）

Abstract：A method for solving computer Go layout problems based on pattern matching and static evaluation is proposed， including the generation， quantification and determination of the best moves. The realization of a Go layout problem solving program BeginGame is realized. Through testing， the professional chess player evaluates the level of BeginGame's layout problem is about amateur 1 segment， and its chess power can be applied to the current game of chess game. It has practical application significance in the research of computer game， artificial intelligence and game software.

Key words：pattern matching;static evaluation;layout problem;Go