基于价值评估的不围棋递归算法

郭倩宇; 陈优广

doi:10.3969/j.issn.1000-5641.2019.01.007

基于价值评估的不围棋递归算法

doi: 10.3969/j.issn.1000-5641.2019.01.007

郭倩宇,
陈优广^,

华东师范大学计算中心, 上海 200062

详细信息

作者简介:
郭倩宇, 女, 硕士研究生, 研究方向为人工智能.E-mail:guoqianyu72@163.com

通讯作者:
陈优广, 男, 高级工程师, 硕士生导师, 研究方向为图像处理.E-mail:ygchen@cc.ecnu.edu.cn

中图分类号: TP399
计量
- 文章访问数: 151
- HTML全文浏览量: 127
- PDF下载量: 182
- 被引次数: 0
出版历程
- 收稿日期: 2017-10-27
- 刊出日期: 2019-01-25

Recursive algorithm for NoGo based on value evaluation

GUO Qian-yu,
CHEN You-guang^,

Computing Center, East China Normal University, Shanghai 200062, China

摘要

摘要: 介绍了不围棋及其规则，并且给出了当前不围棋人工智能的方法及其不足之处.通过分析不围棋博弈的特点，提出了价值评估模型函数；基于此，构造出了递归算法，实现了不围棋人工智能，解决了当前已有算法时间和空间复杂度过高的问题；给出了实现此算法的程序与著名开源软件OASE-NoGo的对弈结果：达到了90%以上的胜率.同时，通过一个常见局面展示了本文算法较传统算法在程序计算上的优势，证明了本文算法的可行性和高效性.
- 人工智能 /
- 机器博弈 /
- 不围棋 /
- 价值评估 /
- 递归
Abstract: First, this paper introduces the rules of the game NoGo. Next, we review current methods of artificial intelligence and their respective shortcomings. Then, the article shows an analysis of the game theory characteristics of NoGo and proposes a value evaluation function. Based on this function, a multi-layer recursive algorithm to the artificial intelligence of NoGo can be constructed, which addresses the problem of high complexity in time and space in the present algorithm. Finally, the paper demonstrates the capability of this algorithm and provides results that the program against with the famous open source software OASE-NoGo, which achieved a winning rate of more than 90%. In a typical situation, it demonstrates that the algorithm is better than existing algorithms in computing, and proves the feasibility and effectiveness of this method.
- artificial intelligence /
- machine game /
- NoGo /
- value evaluation /
- recursion

HTML全文

图 1 权利示意1

Fig. 1 Right schematic 1

下载: 全尺寸图片幻灯片

图 2 权利示意2

Fig. 2 Right schematic 2

下载: 全尺寸图片幻灯片

图 3 实现结果图示

Fig. 3 Example of implementation results

下载: 全尺寸图片幻灯片

图 4 与OASE-NoGo高级版对弈图示

Fig. 4 A game with OASE-NoGo

下载: 全尺寸图片幻灯片

图 5 手机版运行示意图

Fig. 5 Illustration on Android

下载: 全尺寸图片幻灯片

图 6 常见局面示意图

Fig. 6 A typical scenario

下载: 全尺寸图片幻灯片

表 1 对弈结果统计

Tab. 1 Statistics of gaming results

测试系统	对手	测试盘数	胜利盘数	胜率/%
本文系统	OASE-NoGo V1.1初级	100	95	95
本文系统	OASE-NoGo V1.1高级	200	185	92.5

下载: 导出CSV

参考文献(10)

[1]	SILVER D, HUANG A, MADDISON C J, et al. Mastering the game of go with deep neural networks and tree search[J]. Nature, 2016, 529:484-489. doi: 10.1038/nature16961
[2]	秦笃烈.计算机与国际象棋世界冠军的较量[J].今日电子期刊, 1996(4):120-121. http://www.cnki.com.cn/Article/CJFDTOTAL-DZJR199604056.htm
[3]	谷蓉.计算机围棋博弈系统的若干问题研究[D].北京: 清华大学, 2003.
[4]	澎颖, 王方, 罗平.基于数学形态学的围棋形势判断算法[J].湘潭大学自然科学学报, 2011, 33(1):110-112. doi: 10.3969/j.issn.1000-5900.2011.01.024
[5]	黄晶.计算机围棋博弈中UCT算法的应用及改进[D].北京: 北京邮电大学, 2011.
[6]	LEE C S, WANG M H, CHEN Y J, et al. Genetic fuzzy markup language for game of NoGo[J]. Knowledge-Based Systems, 2012, 34:64-80. doi: 10.1016/j.knosys.2012.02.006
[7]	SUN Y X, WANG Y J, LI F.Pattern matching and Monte-Carlo simulation mechanism for the game of NoGo[C]//2012 IEEE 2nd International Conference on Cloud Computing and Intelligence Systems. IEEE, 2012: 61-64.
[8]	梁国军, 谢垂益, 胡伶俐, 等. UCT算法在不围棋博弈中的实现[J].韶关学院学报, 2015, 8:17-21. http://d.old.wanfangdata.com.cn/Periodical/sgxyxb201508004
[9]	SUN Y X, LIU C, QIU H K. The research on patterns and UCT algorithm in NoGo game[C]//Proceedings of the 25th Chinese Control and Decision Conference. IEEE, 2013: 1178-1182.
[10]	SUN Y X, RAO G J, SUN H M, et al. Research on static evaluation method for computer game of NoGo[C]//Proceedings of the 26th Chinese Control and Decision Conference. IEEE, 2014: 3455-3459.