五子棋机器博弈系统评估函数的设计

doi:10.3724/SP.J.1087.2012.01969

计算机应用 ›› 2012, Vol. 32 ›› Issue (07): 1969-1972.DOI: 10.3724/SP.J.1087.2012.01969

五子棋机器博弈系统评估函数的设计

张明亮¹,²,吴俊¹,李凡长²

1. 苏州科技学院电子与信息工程学院，江苏苏州215011
2. 苏州大学计算机科学与技术学院，江苏苏州215006

收稿日期:2012-01-13 修回日期:2012-03-15 发布日期:2012-07-05 出版日期:2012-07-01
通讯作者: 张明亮
作者简介:张明亮(1965-)，男，江苏赣榆人，副教授，硕士，主要研究方向：博弈论、计算机应用系统；吴俊(1978-),男，江苏苏州人，工程师，硕士，主要研究方向：人工智能、计算机图形学；李凡长(1964-)，男，云南宣威人，教授，博士生导师，主要研究方向：人工智能、李群机器学习、动态模糊逻辑。
基金资助:
国家自然科学基金资助项目(60775045);苏州科技学院科研基金资助项目(xky201010)

Design of evaluation-function for computer gobang game system

ZHANG Ming-liang¹,²,WU Jun¹,LI Fan-zhang²

1. College of Electronics and Information Engineering, Suzhou University of Science and Technology, Suzhou Jiangsu 215011, China
2. School of Computer Science and Technology, Soochow University, Suzhou Jiangsu 215006, China

Received:2012-01-13 Revised:2012-03-15 Online:2012-07-05 Published:2012-07-01
Contact: ZHANG Ming-liang

摘要/Abstract

摘要： 针对五子棋机器博弈需借助棋型评估棋局产生的速度瓶颈，提出了棋型识别粒度与搜索深度相关联的多层架构评估函数设计方法。实验证实粗颗粒度估值在深层搜索时整体效率更高；多层次判读棋型能明显加快评估速度；走法生成函数引入快速评估，提前进行博弈树自然剪枝收效显著；非关键棋型依据棋局浮动分值平衡搜索深度，对五子棋亦见成效；以及估值函数针对性地延伸评估来减少地平线效应的开销更少；从而表明估值函数动态评估更加合理。

关键词: 博弈树, PVS, MTD(f), 评估函数, 五子棋

Abstract: Concerning the speed bottleneck of the gobang machine game when relying on the configuration of the stones to evaluate the game states, this paper proposed a multi-layer evaluation-function method combining identification granularity of the stones' configuration with the search depth. The experimental results have proved: the overall efficiency of coarse-grained evaluation was higher when the deep-layer searches were processing; multi-layer judging for the configuration of the stones could obviously accelerate the evaluation; if the move-generating functions were introduced into the rapid evaluation, it was more efficient to prune certain branches from game-tree in advance; gobang game tree searches also benefited if floating the values of non-critical stone's configuration to balance the search depth. Therefore, dynamic evaluation of evaluation-function is more reasonable.

Key words: game-tree, Principal Variation Search (PVS), MTD(f), evaluation-function, gobang

中图分类号:

TP181

张明亮吴俊李凡长. 五子棋机器博弈系统评估函数的设计[J]. 计算机应用, 2012, 32(07): 1969-1972.

ZHANG Ming-liang WU Jun LI Fan-zhang. Design of evaluation-function for computer gobang game system[J]. Journal of Computer Applications, 2012, 32(07): 1969-1972.

参考文献

［1］ KNUTH D E, MOORE R W. An analysis of alpha-beta pruning ［J］. Artificial Intelligence, 1975, 6(4): 293-326.

［2］ KJELDSEN T H. John von Neumann's conception of the minimax theorem: a journey through different mathematical contexts ［J］. Archive History Exact Sciences, 2001, 56(1): 39-68.

［3］尚宇红.极小极大值理论的历史发展［J］.西北大学学报:自然科学版,2003,33(2):245-248.

［4］ FISHBURN J, FINKEL R. Parallel alpha-beta search on Arachne ［R］. Madison, USA: University of Wisconsin, Department of Computer Sciences, 1980.

［5］ PEARL J. Asymptotic properties of minimax trees and game searching procedures ［J］. Artificial Intelligence, 1980, 14(2): 113-138.

［6］ PLAAT A, SCHAEFFER J, PIJLS W, et al. A new paradigm for minimax search, TR-CS-94-18 ［R］. Edmonton, Canada: University of Alberta, Department of Computing Science, 1994.

［7］ PLAAT A, SCHAEFFER J, PIJLS W, et al. Best-first fixed-depth minimax algorithms ［J］. Artificial Intelligence, 1996, 87(1/2): 255-293.

［8］ SLAGLE J R, DIXON J K. Experiment with some programs that search game trees ［J］. Journal of the Association for Computing Machinery, 1969, 16(2): 189-207.

［9］张明亮,李凡长.一种新的博弈树搜索方法［J］.山东大学学报:工学版,2009,39(6):1-8.

［10］张明亮.一种新的博弈树搜索算法及其应用研究［D］.苏州：苏州大学,2007.

［11］张明亮,吴俊,李凡长.极小树叶结点数定理的补充证明及有关分析［J］.模式识别与人工智能,2011,24(4):521-526.

［12］叶品星.一种博弈树静态估值算法——△Feature状态估值［J］.计算机工程与设计,2004,25(7):1214-1217.

［13］徐长明,马宗民,徐心和.一种新的连珠棋局面表示法及其在六子棋中的应用［J］.东北大学学报:自然科学版,2009,30(4):514-517.

［14］王秀坤,刘健男.优化博弈问题评估函数参数的自适应遗传算法［J］.计算机工程与应用,2009,45(20):42-44.

［15］ CAMPBELL M, HOANE A, HU F-H. Deep blue ［J］. Artificial Intelligence, 2002, 134: 57-83.

［16］王晓鹏,王骄,徐心和,等.中国象棋与国际象棋比较分析［J］.重庆工学院学报:自然科学版,2007,21(1):71-76.

［17］莫建文,林士敏,张顺岚.基于TD强化学习智能博弈程序的设计与实现［J］.计算机应用,2004,24(S1):287-288.

［18］ CRACRAFT S. Bitmap move generation in chess ［J］. Journal of the International Computer Chess Association, 1984, 7(3): 146- 153.

［19］ HYATT R M. Rotated bitmaps a new twist on an old idea ［ J］. Journal of the International Computer Chess Association, 1999, 22(4): 213- 222.

[1]	毛丽民, 朱培逸, 卢振利, 彭伟伟. 基于LabVIEW的五子棋博弈算法[J]. 计算机应用, 2016, 36(6): 1630-1633.
[2]	范小勤胡能发. 双适应函数单亲遗传算法[J]. 计算机应用, 2009, 29(07): 1887-1889.
[3]	林永民朱卫东 . 基尼指数在文本特征选择中的应用研究[J]. 计算机应用, 2007, 27(10): 2584-2586.
[4]	廖里. 围棋死活问题的计算机求解[J]. 计算机应用, 2005, 25(11): 2720-2722.

五子棋机器博弈系统评估函数的设计

Design of evaluation-function for computer gobang game system

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics