Python3实现AI五子棋对弈

项目背景

2016年3月15日，谷歌围棋人工智能AlphaGo与韩国棋手李世石在进行最后一轮较量，AlphaGo获得了本场比赛的胜利，最终双方总比分为4:1，由AlphaGo取得了人机围棋对决的胜利。谷歌董事长施密特曾在该比赛的开幕仪式上称：“无论比赛结果如何，胜者都是人类。” 从这一句豪迈的宣言开始，标志着AlphaGo的深度学习架构成功搭建，同时开启了机器智能的魔盒。而深度学习、机器学习的精髓是算法。今天，我们将从简单的五子棋入手，一睹算法在棋盘对战中的应用。

项目功能

通过minimax算法+alpha-beta剪枝算法实现电脑和人下五子棋的游戏。

项目架构

对于五子棋这样的博弈类AI项目，很自然的想法就是让计算机把当前所有可能的情况都尝试一遍，找到最优的落子点。但在这里有两个问题：（1）如何把所有可能的情况都尝试一遍；（2）如何定量判断某落子点的优劣。对于第一个问题，其实就是博弈树搜索，而第二个问题，即选择评估函数。评估函数的选取直接决定了AI算法的优劣，其形式也千变万化。可以说，每个评估函数就是一个选手，对不同的棋型每个选手自然有不同的看法和应对措施，当然他们的棋力也就因此而各不相同。但博弈树搜索比较固定，其核心思想是让计算机考虑当前局势下之后N步所有可能出现的情况，其中奇数步要让AI方的得分最大，偶数步要让AI方的得分最小（因为对手也就是人类，也可以在大脑中运算出最优策略）。这样的推演其计算量是极大的，这时候就需要通过剪枝来减少计算量。如下图：

其中A代表AI方，P代表人类方。AI方搜索最大值，人类方搜索最小值。因此Layer3的A1向下搜索的最终结果为4，Layer3的A2向下搜索，先搜索Layer4的P3，获得的分值为6，考虑到Layer2的P1向下搜索时取Layer3的A1和A2中的较小值，而Layer3的A2搜索完Layer4的P3时，其值就已经必大于Layer3的A1了，就没有搜索下去的必要了，因此Layer3到Layer4的路径3就可以剪掉了。上述搜索策略的实质是：minimax算法+alpha-beta剪枝算法。在了解了上述原理之后，就可以进行代码实现了。

项目展示

项目特色

本项目实现五子棋的人机对弈，是人工智能应用的入门项目。