基于价值评估的不围棋递归算法
|
摘要
介绍了不围棋及其规则,并且给出了当前不围棋人工智能的方法及其不足之处.通过分析不围棋博弈的特点,提出了价值评估模型函数;基于此,构造出了递归算法,实现了不围棋人工智能,解决了当前已有算法时间和空间复杂度过高的问题;给出了实现此算法的程序与著名开源软件OASE-NoGo的对弈结果:达到了90%以上的胜率.同时,通过一个常见局面展示了本文算法较传统算法在程序计算上的优势,证明了本文算法的可行性和高效性.
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.
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.
引文
[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.
[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.