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

1.本选题研究的理论意义和使用价值

五子棋是一项历史十分悠久的博弈游戏。从古发展至今，五子棋已经成为一项正式比赛。在20世纪40年代时，人们一直深信计算机无法进行博弈，即计算机无法在五子棋上胜过人类的判断。直到计算机第一次打赢人类后，这一固有观念被打破。直到21世纪初，计算机五子棋算法已经经过了很多方式的更迭，并产生出许多优秀的算法方案。而其中一种方案，则是基于蒙特卡洛树搜索的五子棋算法。

蒙特卡洛树是一种在一些广泛随机样本中获取权重较高的样本，并作出决策的一种模拟统计算法。通过这种算法，人们只能近似地得到最优解，却无法真正地获取最优解。但是有很多时候，我们并不需要获取最优解，而是只要满足在一定误差范围内的解就可以。比如有限双人零和回合制博弈。而五子棋博弈就是一种有限双人零和博弈。如果我们将五子棋博弈看成是一种实验，那么研究蒙特卡洛的算法的五子棋实现方式，不仅可以验证蒙特卡洛树算法的实际作用，还可以提升计算机的智能化程度。通过蒙特卡洛树方法，人们在很多情况下可以用计算机的模拟来代替复杂的数学推演过程。比如蒙特卡洛树可以用计算机模拟的方式代替手工实验。这使原本需要费时费力的事情变得十分简单。

2.本选题国内外研究现状

对于类似五子棋这种有限双人零和回合制博弈，当不知道对方的棋艺水平时，可以采用一种激进的策略——Minimax极小化极大算法作为计算机的博弈算法。此算法需要展开整个博弈树，这使生成的博弈树由于体积过于庞大而难以计算。必须在传统的极小化极大算法上进行优化。

最常见的两种优化措施是，一是限定博弈树的深度。这样就需要一个评估当前博弈状态的函数。二是通过Alpha-beta剪枝算法将博弈树中一开始就不可能是最优解的点排除。这样返回的最优值结果是和极小化极大算法相同，但是却通过减少搜索空间提升了搜索效率。而如果我们再将判断标准降低，将“获取最优点”变成“获取相对不错的点”，就变成了蒙特卡洛树搜索。蒙特卡洛树搜索（MCTS）会进行多次模拟博弈，并“尝试”预测最优行动。与极小化极大算法相同的是，蒙特卡洛也会向下遍历博弈树。但是蒙特卡洛会在遍历某一个节点的时候通过一个权值来筛选最不可能是最优解的值，并且根据这个权值还能改变遍历的次序，优先遍历最有可能是最优解的点。这个权值是由树的上限置信区间函数（UCT函数）确定的：

3.围绕本选题已做哪些准备工作，计划再做的工作

通过阅读和整理文献并结合代码试运行，我已经：

1. 明确了五子棋的博弈规则和判断逻辑。在本次设计中，我们采用gomocup中的Free-Style规则：棋盘为15 * 15，电脑为先手方、不做禁手、长连算赢。五子棋的判断逻辑是根据水平、竖直、45°和135°的线上是否有下一步落子能构成五子连珠的位置。如果有，则已经分出胜负。

2.明确蒙特卡洛方法的主要步骤。蒙特卡洛方法包括四方面：选择、搜索、模拟、反向传播。对于给定的一个点，选择连续的子节点向下遍历，并对这些子节点模拟得出值，然后将此值反向传播回最开始的那个点。在传播过程中，还会对传播路径上所有的点对应的值进行更新。最后返回的是值最优的节点，即电脑要走的位置。

下一步计划再做的工作：

1.明确类与类之间的调用关系、明确每个类实现的功能、明确返回值类型与参数列表。目前我简单地分成了以下几个部分：棋手类（实现通用功能）、人类棋手类（继承自棋手类）、电脑棋手类（继承自棋手类）、AI类（用于在电脑棋手类实现）、棋盘类、裁判类（用于判断输赢）、引擎类（聚合上面这些类，也是main方法所在的类）。随着研究深入，可能需要进一步定义接口。

2.明确AI类中蒙特卡洛方法的具体实现，关键在于如何使搜索直接按照最优到次优的顺序来进行，而不是传统的遍历方式，这一点是下一步需要解决的问题。

4.计划在哪些方面有所突破

蒙特卡洛方法仍然存在一定可优化的空间：1.这种方法要求设计人员必须要更加深入了解五子棋的玩法，能够对各种复杂的情形做出准确的评估。2.如果在程序中对大量的棋势进行存储，必将消耗很多内存资源，并且在UCT函数调用这些棋势的估值时，浪费的时间也会相应增加。这样，算法很有可能无法在有限的规定时间内完成最低搜索要求。

优化分为两个方面：1.快速计算出博弈树中每个子节点的权值；2.针对返回的权值，算法能够及时改变搜索次序，优先搜索比较符合要求的节点，使在设定最大搜索时间内能够更接近于最佳点。而这两个优化点，其本质上来说依然是与UCT函数有关，我们希望能够尽量优化这个函数，使计算机计算出的近似最优解能够更接近于真正最优解。

5.主要参考文献

[1]董红安.计算机五子棋博奕系统的研究与实现[D].山东:山东师范大学,2005.

[2]董慧颖.多种搜索算法的五子棋博弈算法研究[N].沈阳理工大学学报,2017.4(第36卷第2期).

[3]王杨.基于计算机博弈的五子棋算法研究[D].辽宁:沈阳理工大学,2016.