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.
GUO Qian-yu
,
CHEN You-guang
. Recursive algorithm for NoGo based on value evaluation[J]. Journal of East China Normal University(Natural Science), 2019
, 2019(1)
: 58
-65
.
DOI: 10.3969/j.issn.1000-5641.2019.01.007
[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.
[2] 秦笃烈. 计算机与国际象棋世界冠军的较量[J]. 今日电子期刊, 1996(4):120-121.
[3] 谷蓉. 计算机围棋博弈系统的若干问题研究[D]. 北京:清华大学, 2003.
[4] 澎颖, 王方, 罗平. 基于数学形态学的围棋形势判断算法[J]. 湘潭大学自然科学学报, 2011, 33(1):110-112.
[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.
[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.
[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.