用极小极大搜索实现井字棋游戏

1.实验目的

学习和掌握博弈搜索中常用的极小极大搜索方法，理解其在棋类游戏中进行决策的过程和应用方式。

2.实验内容

（1）使用Python，采用极小极大搜索实现井字棋游戏。

（2）利用启发值实现2层预判极小极大搜索实现该游戏。

实验参考代码说明：

参考代码文件名为“game.py”，在命令行方式下实现该游戏。代码中定义了一个Tic Tac Toe类，它包括和棋盘相关的各种基本操作，比如打印棋盘函数show（）、检查获胜方check Win（）、下棋到指定位置（即扩展节点makeMove（position，player））等。

极小极大搜索算法在Tic Tac Toe类的minimax方法中实现，采用的是递归操作，递归结束条件为depth==0 or node.gameOver（），如果是平局，则返回分数为50，计算机方依靠AI算法和人类下棋，参考代码中，计算机方的棋子固定为“O”，所以在算法中O即表示MAX方，并将O获胜的分值定为100向上传递。人类玩家棋子为“X”，即表示MIN方，获胜的状态分值为0。

参考代码中函数make_best_move（board，depth，player）用来控制极小极大搜索过程，为计算机提供最佳下棋的位置并存入choices列表，当存在某个分值比平局分值大时，会直接选择该位置作为移动位置，否则将等于平均分值的没有优势的位置全部添加进choices列表，并从中随机选一个位置下棋。

changePlayer函数用于控制轮流切换计算机玩家和人类玩家。(www.xing528.com)

game.py代码中并未提供利用启发值实现2层预判的极小极大搜索，需要自行设计。

3.实验扩展

参考以下启发信息，在15×15的棋盘上实现五子棋游戏。

对五子棋中的各种状态赋予分值。分值越大，表示自己的优势越大；分值越小，表示对方的优势越大；分值为0，表示双方局势持平。对于分值的设定，可以采用如下规则：

5个子相连，此时为赢的状态，给予最大分值100 000分；

4个子相连，两边都未封死，称为活4，给予10 000分，如果有一侧被封死，另一侧则没有，评分降低一档，设为1000分；

依次类推，活3设为1000分，活2设为100分，活1设为10分，对应地，死3设为100分，死2设为10分。

对方状态需要搜索极小值，可以将对方状态对应分值设为负的作为我方分值，比如对方出现活3，取其分值为-1000分。

参考代码见本书所附资料gobang_minimax.py文件。