基于Monte Carlo方法的五子棋算法设计与实现

摘  要

本文选择五子棋为研究课题，在对大量相关文献进行分析研究的基础上，使用Monte Carlo Tree Search算法的原理设计了五子棋博弈系统的模型。首先研究了五子棋在计算机中的表示问题，确定五子棋棋盘在计算机中的存储与表示方式。然后研究棋类游戏人机博弈方法中的权值法、极小极大算法，并总结了两种算法之间的联系与区别。 接着研究了Monte Carlo Tree Search算法的构造，针对Monte Carlo Tree Search算法的理论知识，以2 * 2棋盘为模型进行算法步骤演示，说明了不同步骤在整个算法中起到的作用。最后设计实现了一个五子棋游戏的Monte Carlo Tree Search算法。实验结果表明，该算法在模拟次数较多的情况下可以对棋局做出比较准确的判断。

关键词：蒙特卡洛；博弈；五子棋；人工智能；搜索算法

A Design and Implementation of Gobang Algorithm based on Monte Carlo Method

ABSTRACT

This paper focuses on Gobang AI Algorithm. Based on the analysis of a large number of related literatures, a prototype of Gobang game is designed using the principle of Monte Carlo tree search algorithm. Firstly, the representation of Gobang in computer is studied, and the storage and representation of Gobang board in computer is determined. Secondly, the weight method and minimax algorithm in the human-computer game of chess games are studied, and the relationship and difference between them are summarized. Thirdly, the Monte Carlo tree search algorithm is studied. According to the theoretical knowledge, the steps are demonstrated with 2 * 2 chessboard as a demo, and the role of different steps in the whole algorithm is explained. Finally, a Monte Carlo tree search algorithm of Gobang game is designed and implemented. The experimental results show that the algorithm can make a more accurate judgment of the chess game in the case of more simulation times.

Keywords: Monte Carlo; Game; Gobang; Artificial intelligence; Search algorithm