﻿ 六子棋中基于局部“路”扫描方式的博弈树生成算法
 文章快速检索 高级检索

1. 安徽大学 计算机科学与技术学院, 安徽 合肥 230601;
2. 安徽大学 计算智能与信号处理重点实验室, 安徽 合肥 230039

Game tree generation algorithm based on local-road scanning method for connect 6
LI Xuejun1,2, WANG Xiaolong1, WU Lei1, LIU Huiting1
1. School of Computer Science and Technology, Anhui University, Hefei 230601, China;
2. Intelligent Computing and Signal Processing Laboratory, Anhui University, Hefei 230039, China
Abstract: Aiming at the problem that the game-tree generation algorithm generated by global scanning method is low in efficiency in the connect 6, this paper analyzes the calculation rules and valuation analysis of the global scanning method based on "road". Secondly, it develops the global scanning method of the game-tree generation algorithm into local scanning method, and introduces the calculation rules and valuation analysis. The game-tree generation algorithm is a local scanning method designed and integrated into the alpha-beta pruning search. Finally, the global and local scanning experiments are carried out from the two perspectives of search efficiency and playing skill. The experimental results showed that local scanning could greatly improve search efficiency within the competition time. The game ability is superior to that of the global scanning method.
Key words: computer game     connect 6     road     local scanning     game tree     pruning algorithm     evaluation

“路”扫描方式的引入避免了精确判断棋形的难题，减少了计算量；同时应用面向对象的思想，将“路”的信息抽象成类，易于实现。基于“路” 的扫描方式解决了因棋形判断不准确而影响博弈水平的问题，但是应用博弈树搜索时，在对每个子节点的扩展时都需要对棋盘进行全局扫描。受博弈竞赛时间约束，搜索深度和宽度都有所限制，博弈水平也达不到理想要求。因此本文在博弈树生成子节点时将基于“路”的全局扫描方式改进为局部扫描，并设计基于局部“路”扫描方式的博弈树生成算法。

1 基于“路”的全局扫描方式 1.1 计算规则

K子棋可用connect(m,n,k,p,q)表示[14]，对弈双方为黑方和白方，黑方先走。connect(m,n,k,p,q)的规则包括：1)棋盘的方格为 mn列，即含m×n个交叉点；2)对弈时双方轮流落p颗棋子(根据六子棋比赛黑方先手规则，第1次落q颗棋子)；3)在棋盘的水平、垂直或对角线上先形成k连获胜。若在规定时间内双方均无法获胜，则判为平局。

K子棋中“路”的计算规则：1)水平方向：m行×(n-k+1)路/行，如图 1(a)所示；2)垂直方向：n列×(m-k+1)路/列，类似于水平方向；3)左斜方向：由于k连需要k子连续相连，在左斜方向前k-1行不可能形成k连，故左斜方向路数为(m-k+1)行×(n-k+1)路/行，如图 1(b)；4)右斜方向：(n-k+1)列×(m-k+1)路/列，类似于左斜方向。

 图 1 水平及左斜方向路数计算示例 Fig. 1 Road number of horizontal and left diagonal direction

1.2 估值分析

2 基于“路”的局部扫描方式

2.1 计算规则

 图 2 局部扫描水平方向路数计算示例 Fig. 2 Road number of horizontal direction by the local-road scanning method

2.2 估值分析

1)落子前落子点位置影响的局部扫描的“路”估值 Vpre 与除局部扫描以外的“路”估值 V″pre 之和相当于落子前棋盘全局扫描估值 Vpre ，可表达为

2)落子后落子点位置影响的局部扫描的“路”估值 Vafter 与除局部扫描以外的“路”估值 Vafter 之和相当于落子后棋盘全局扫描估值 Vafter ,可表达为

3)由于每步落子不会对局部扫描以外的“路”估值产生影响，即落子后除局部扫描以外的“路”估值 Vafter 等于落子前除局部扫描以外的“路”估值 Vpre ，表达为

3 局部扫描方式的博弈树生成算法

/*Input:Color,Width Output:listWay(估值排名前Width的2步落子组合)*/

1) Localscanning(int Color,int Width){

3)for( i =0; i < ListPoints.Count-1; i ++)

4)for(j= i +1; j < ListPoints.Count; j ++){

5)scanPart(ListPoints[i].Point,ListPoints[j].Point);//落子前局部扫描

6)Part_preValue=Caculate();//计算模拟落子前局部扫描估值

7)SimulateMove();//模拟落子

8)scanPart(ListPoints[i].Point,ListPoints[j].Point);//落子后局部扫描

9)Part_afterValue=Caculate();//计算模拟落子后局部扫描估值

10)Value=Part_afterValue-Part_preValue;

11)RestoreMove();//撤销落子

13)}

14)GetListWay(ListWay,Width);

4 实验 4.1 实验环境

4.2 实验与分析

 路数 己方路的价值 对方路的威胁值 6路 1 000 000 1 000 000 5路 200 6 000 4路 200 6 000 3路 40 50 2路 20 25 1路 1 1
4.2.1 搜索效率实验

 图 3 2种扫描方式不同深度的搜索时间对比 Fig. 3 Search time two scanning method with different depths
4.2.2 博弈水平实验

 图 4 2种扫描方式在不同宽度的博弈结果 Fig. 4 Game results with different widths
 图 5 2种扫描方式在不同深度的博弈结果 Fig. 5 Game results with different depths
5 结束语

 [1] 张利群.五道棋计算机博弈程序的设计与实现[J]. 计算机工程, 2010(10): 227-228, 231.ZHANG Liqun. Design and realization of Wudao chess computer game program[J]. Computer Engineering, 2010(10): 227-228, 231. [2] 徐长明,马宗民,徐心和.一种新的连珠棋局面表示法及其在六子棋中的应用[J].东北大学学报:自然科学版, 2009(4): 60-63.XU Changming, MA Zongmin, XU Xinhe. A new board representation method for k-in-a-row games with its application to connect 6[J].Journal Northeastern University: Natural Science, 2009(4): 60-63. [3] QIAO Zhihua, YANG Ming, WANG Zijuan. Technologies analysis of connect6 computer game[J]. Advanced Materials Research, 2011, 1077 (171) : 679-682. [4] ZHANG Ruimei, LIU Changcheng, WANG Chuandui. Research on connect 6 programming based on mtd(f) and deeper-always transposition table[C]//2012 IEEE 2nd International Conference on Cloud Computing and Intelligence Systems. [S.l.], 2012: 254-255. [5] 徐长明.基于连珠模式的六子棋机器博弈关键技术研究[D]. 沈阳: 东北大学, 2010: 15-36.XU Changming. Research on key technologies of connection-pattern based computer connect 6[D]. Shenyang: Northeastern University, 2010: 15-36. [6] KNUTH D E, MOORE R W. An analysis of alpha-beta pruning[J]. Artificial Intelligence, 1975, 6(4): 293-326. [7] 李翠珠.六子棋计算机博弈系统的研究与实现[D]. 重庆: 重庆理工大学, 2010: 43-46.LI Cuizhu. Research and Implementation of the system of connect 6 game[D]. Chongqing: Chongqing University of Technology, 2010: 43-46. [8] 张颖.六子棋启发式搜索算法的优化与设计[J]. 西北师范大学学报: 自然科学版, 2008(4): 31-36, 58.ZHANG Ying. Optimization and design of connect6 heuristic searching algorithm[J]. Journal of Northwest Normal University: Natural Science, 2008(4): 31-36, 58. [9] 黄继平,苗华,张栋.用遗传算法实现六子棋评估函数参数优化[J]. 重庆工学院学报: 自然科学版, 2009(11): 91-95.HUANG Jiping, MIAO Hua, ZHANG Dong. Optimizing the evaluation function parameters of connect6 with genetic algorithms[J].Journal of Chongqing Institute of Technology: Natural Science, 2009(11): 91-95. [10] 陈光年.基于智能算法的六子棋博弈行为选择的应用研究[D]. 重庆: 重庆理工大学, 2010: 20-25.CHEN Guangnian. The research and application on the behavior election of connect 6 based on intelligent algorithms[D]. Chongqing: Chongqing University of Technology, 2010: 20-25. [11] 张小川, 陈光年, 张世强, 等.六子棋博弈的评估函数[J]. 重庆理工大学学报: 自然科学版, 2010(2): 68-72.ZHANG Xiaochuan, CHEN Guangnian, ZHANG Shiqiang. Research on evaluation functions for computer game of connect6[J]. Journal of Chongqing University of Technology: Natural Science, 2010(2): 68-72. [12] 徐长明, 马宗民, 徐心和, 等. 面向机器博弈的即时差分学习研究[J]. 计算机科学, 2010(8): 225-229.XU Changming, MA Zongmin, XU Xinhe. Study of temporal difference learning in computer games[J]. Computer Science, 2010(8): 225-229. [13] 徐心和, 邓志立, 王骄, 等.机器博弈研究面临的各种挑战[J]. 智能系统学报, 2008, 3(4): 10-15.XU Xinhe, DENG Zhili, WANG Jiao, et al. Challenging issues facing computer game research[J]. CAAI Transactions on Intelligent Systems, 2008, 3(4): 10-15. [14] 闵文杰. 六子棋计算机博弈关键技术研究[D]. 重庆:重庆交通大学, 2010: 12-18.MIN Wenjie. Research on the key technologies of the connect 6 computer game[D]. Chongqing: Chongqing Jiaotong University, 2010: 12-18. [15] MARTIN K, SVEN S, RAINER H. Improved tree-based strategies for a connect 6 threat-based hardware design[C]//2013 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM). [S.l.], 2013: 32-36. [16] 张明亮,吴俊,李凡长.五子棋机器博弈系统评估函数的设计[J]. 计算机应用, 2012(7): 189-192, 210.ZHANG Mingliang, WU Jun, LI Fanchang. Design of evaluation function for computer gobang game system[J]. Journal of Computer Applications, 2012(7): 189-192, 210.
DOI: 10.3969/j.issn.1673-4785.201401022

0

#### 文章信息

LI Xuejun, WANG Xiaolong, WU Lei, LIU Huiting

Game tree generation algorithm based on local-road scanning method for connect 6

CAAI Transactions on Intelligent Systems, 2015, 10(02): 267-272.
DOI: 10.3969/j.issn.1673-4785.201401022