五子棋人机博弈问题
摘 要
五子棋的人机博弈是two-agent对抗搜索算法的一个很具有标志性的应用，类似于其他的各种棋类问题，五子棋问题的求解最终都趋向于Minimax算法（极小化极大算法）。本次实验即利用这一算法给出了五子棋棋局形势的评价函数，通过该评价函数对当前棋局进行层次搜索，最终确定落子位置。
为了节约搜索时长，本次实验的搜索树采用了α-β剪枝算法，剪去了不会改变最终决策的分支，避免了大量无谓的计算。同时，本项目小组还根据五子棋的特点对普适的α-β剪枝算法进行了优化，例如不对周围八个位置没有棋的格点进行搜索等。
而在用户UI方面，本次实验采用了Qt框架来实现，通过使用Qt框架提供的一系列图形界面封装函数，可以实现鼠标点击位置的检测，从而实现简单的UI交互。
关键词：五子棋博弈，Minimax算法，α-β剪枝算法，Qt框架
Man-Machine Game of Gobang
ABSTRACT
The man-machine game of Gobang is a very symbolic application of two-agent anti search algorithm. Similar to other chess problems, the solution of Gobang problems eventually tends to minimax algorithm. In this experiment, we use this algorithm to give the evaluation function of the situation of the game of Gobang. Through this evaluation function, we search the current game hierarchically and finally determine the position of the drop.
In order to save the search time, the search tree in this experiment adopts the α-β pruning algorithm, which cuts off the branches that will not change the final decision and avoids a lot of unnecessary calculation. At the same time, the project team also optimized the general α-β pruning algorithm according to the characteristics of Gobang, such as not searching eight grid points without chess around.
In terms of UI interface, QT framework is used in this experiment. By using a series of graphical interface encapsulation functions provided by QT framework, the detection of mouse click position can be realized, so as to realize simple UI interaction.
Key words：Gobang game, minimax algorithm, α-β pruning algorithm, QT framework
目 录
1 实验概述 1
1.1 实验目的 1
1.2 实验内容 1
1.3 五子棋人机博弈问题简介 1
2 实验方案设计 2
2.1 总体设计思路与总体架构 2
2.1.1 内核部分思路说明 2
2.1.2 内核部分总体架构 2
2.1.3 UI部分思路说明 3
2.1.4 UI部分总体架构 3
2.2 核心算法及基本原理 3
2.2.1 Minimax算法 3
2.2.2 α-β剪枝算法 4
2.3 模块设计 4
2.3.1 内核部分模块设计说明 4
2.3.2 UI部分模块设计说明 5
2.3.3 各模块图示说明 5
2.4 其他创新内容或优化算法 6
2.4.1 评估函数说明 6
2.4.2 对搜索次序的优化 6
2.4.3 使用栈型结构来存储双方落子位置 7
3 实验过程 8
3.1 环境说明 8
3.1.1 内核部分开发环境说明 8
3.1.2 展示部分开发环境说明 8
3.2 源代码文件与主要函数清单 8
3.3 实验结果展示 10
4 总结 14
4.1 实验中存在的问题及解决方案 14
4.1.1 Qt框架下的格点监测不准确 14
4.1.2 评估函数总是远高于预期结果 14
4.2 心得体会 14
4.3 后续改进方向 15
4.4 总结 15
参考文献 16
小组分工 16
附录： 16
