[1]李学俊,王小龙,吴蕾,等.六子棋中基于局部“路”扫描方式的博弈树生成算法[J].智能系统学报,2015,10(2):267-272.[doi:10.3969/j.issn.1673-4785.201401022]
LI Xuejun,WANG Xiaolong,WU Lei,et al.Game tree generation algorithm based on local-road scanning method for connect 6[J].CAAI Transactions on Intelligent Systems,2015,10(2):267-272.[doi:10.3969/j.issn.1673-4785.201401022]
点击复制
LI Xuejun,WANG Xiaolong,WU Lei,et al.Game tree generation algorithm based on local-road scanning method for connect 6[J].CAAI Transactions on Intelligent Systems,2015,10(2):267-272.[doi:10.3969/j.issn.1673-4785.201401022]
六子棋中基于局部“路”扫描方式的博弈树生成算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
10
期数:
2015年第2期
页码:
267-272
栏目:
学术论文—机器学习
出版日期:
2015-04-25
- Title:
- Game tree generation algorithm based on local-road scanning method for connect 6
- Keywords:
- computer game; connect 6; road; local scanning; game tree; pruning algorithm; evaluation
- 分类号:
- TP31
- 文献标志码:
- A
- 摘要:
- 针对六子棋博弈比赛中基于“路”的全局扫描方式的博弈树生成算法效率较低问题,首先分析了基于“路”的全局扫描方式的计算规则和估值分析,然后将博弈树生成算法中的全局扫描方式改进为局部扫描方式,并给出其计算规则和估值分析,接着设计了基于局部扫描方式的博弈树生成算法,并集成到Alpha-Beta剪枝算法中。最后从搜索效率和博弈水平2个角度对全局扫描和局部扫描进行实验,实验结果表明,局部扫描方式在比赛时间要求的情况下,能够大幅度提高搜索效率,并且博弈水平显著优于全局扫描方式。
- 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.
- 参考文献/References:
-
[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.
- 相似文献/References:
-
[1]徐长明,南晓斐,王 骄,等.中国象棋机器博弈的时间自适应分配策略研究[J].智能系统学报,2006,1(2):39.
XU Chang-ming,NAN Xiao-fei,WANG Jiao,et al.Adaptive time allocation strategy in? computer game of Chinese Chess[J].CAAI Transactions on Intelligent Systems,2006,1():39.
[2]黄? 晨.棋类游戏中的先行权[J].智能系统学报,2007,2(3):91.
HUANG Chen.The firstmove advantage in board games[J].CAAI Transactions on Intelligent Systems,2007,2():91.
[3]徐心和,邓志立,王骄,等.机器博弈研究面临的各种挑战[J].智能系统学报,2008,3(4):287.
XU Xin-he,DENG Zhi-li,WANG Jiao,et al.Challenging issues facing computer game research[J].CAAI Transactions on Intelligent Systems,2008,3():287.
[4]张小川,唐艳,梁宁宁.采用时间差分算法的九路围棋机器博弈系统[J].智能系统学报,2012,7(3):278.
ZHANG Xiaochuan,TANG Yan,LIANG Ningning.A 9×9 Go computer game system using temporal difference[J].CAAI Transactions on Intelligent Systems,2012,7():278.
[5]张小川,王宛宛,彭丽蓉.一种军棋机器博弈的多棋子协同博弈方法[J].智能系统学报,2020,15(2):399.[doi:10.11992/tis.201812012]
ZHANG Xiaochuan,WANG Wanwan,PENG Lirong.A multi-chess collaborative game method for military chess game machine[J].CAAI Transactions on Intelligent Systems,2020,15():399.[doi:10.11992/tis.201812012]
[6]李霞丽,王昭琦,刘博,等.麻将博弈AI构建方法综述[J].智能系统学报,2023,18(6):1143.[doi:10.11992/tis.202211028]
LI Xiali,WANG Zhaoqi,LIU Bo,et al.Survey of Mahjong game AI construction methods[J].CAAI Transactions on Intelligent Systems,2023,18():1143.[doi:10.11992/tis.202211028]
备注/Memo
收稿日期:2014-1-9;改回日期:。
基金项目:国家自然科学基金资助项目(61202227).
作者简介:李学俊,男,1976年生,副教授,中国人工智能学会机器博弈专业委员会理事,主要研究方向为智能软件、云工作流;王小龙,男,1989年生,硕士,主要研究方向为机器博弈;吴蕾,女,1978年生,讲师,博士研究生,中国人工智能学会机器博弈专业委员会理事,主要研究方向为机器博弈,软件测试。
通讯作者:李学俊.E-mail:xjli@ahu.edu.cn.
更新日期/Last Update:
2015-06-15