仅使用搜索、剪枝等策略实现的五子棋游戏，由 Python 语言完成，作为人工智能导论课程作业。
通过实现一个完整的五子棋 AI，可以加深对使用到的搜索算法的理解，也可以锻炼 Python 语言编程能力。实现途中可以感受到一步步丰满 AI 的过程以及算法的取舍。
GUI 部分采用 pygame 实现，界面以及事件响应均依照 pygame 文档实现。
进入游戏，在主页可以选择玩家先手或 AI 先手。游戏默认先手方执黑子。
选择后，直接进入游戏界面。
点击任意交点即可在该点下棋。下棋后 AI 会立即开始思考并在一段时间后下棋。
若对上一步棋不满意，可以按下 CTRL+Z 进行悔棋。
一方取胜后会在最上方提示获胜信息。在任意处点击鼠标即可开始新的游戏。
点击右上角或按下 ESC 即可退出游戏。
这是实现程序最复杂的一部分，它决定着 AI 眼中的棋局的抽象形式。这部分的功能是将棋局抽象成我方、敌方两个棋型列表，每个棋型列表统计某一方的各种关键棋型组合的个数。下面假设我方执黑子（●），敌方执白子（○），空白为（□），关键棋型分为七种，分别为：
- 连五（已经胜利）：
●●●●● - 活四（无法堵截）：
□●●●●□ - 死四（必须一步堵截，否则直接连五）：
○●●●●□、●○●●●、●●○●● - 活三（必须一步堵截，否则直接活四）：
□●●●□、□●●□●□ - 死三（可以不堵截，一步后为死四）：
○●●●□、○●●□●、●□●□●等 - 活二（一步后成为活三）：
□●□●□、□□●●□□等 - 死二（一步后成为死三）：
○●●□□□、○●□●□□、○●□□●□等
判断一方（比如黑子方）棋型组合的方法是遍历所有黑子，对每个黑子的每个方向（左-右、下-上、左下-右上、左上-右下）向正反同时观察 4 个点位，首先记录当前黑子所在的黑子块中的黑子数量，然后根据该数量（1 到 5 个，下文称之为 count）按照上述组合方式进行特殊判断，将识别到的组合计数。此时会出现重复记录的情况，所以采用以下措施来避免重复记录：
- 规定组合顺序：必须按从大到小的顺序进行组合识别。比如，
count == 2时会判断是否出现了○●●□●形式的棋型，而在count == 1时就不会判断这种棋型，因为按照规定，count == 1的棋子无权干涉count == 2的组合。 - 记录重复值（
vis）：在判断诸如□●□●□、●●□□●●这种会在左方棋子与右方棋子中均被记录一次的组合，在第一次被记录时会在组合中心点记录已访问，这样在第二次识别到该组合时就不会重复记录了。比如在记录□●□●□时，会将最中间的□所在位置标记vis。 - 采用特殊判断方式：判断
●□●□●等棋型时，只识别由中心●拓展出的棋型组合。 - 对黑子块进行标记：这样每个黑子块只会被第一个黑子识别到，避免重复的同时也减少了搜索时间。
核心代码详见 compute_oneside_combination()。
棋型评估的含义是将得到的棋型组合计算分数，得到我方、敌方的当前分数，根据分数判断落子位置。每种组合的权重是可以按经验划分的，这些权重会影响 AI 对每种棋型的重视程度。可以通过机器学习优化这些权值分数，使之更加优越。
计算分数的同时还会考虑到常见的多棋型组合，比如双活三、死四活三等，这种棋型分数的设计会远超其余棋型。
核心代码详见 compute_score()。
事实上，完成了前面的步骤的 AI 已经拥有了不小的智慧，但是无法应对对手营造出来的杀招，也无法为对手布局一个杀招。这是因为它只能看到当前棋局的最优下法，无法对未来的局势进行联想。这就需要重复的搜索来延伸 AI 的眼光。这里采用极大极小值搜索。AI 下棋时处在 MAX 层，棋子会落在使 AI 方分数最高的点上；玩家下棋时处在 MIN 层，棋子会落在使 AI 方分数最低的点上。
这样的搜索方式可以使用 Alpha-Beta 剪枝优化。对每个节点，变量
核心代码详见 max_min_search()。
经过以上优化，搜索深度可以达到 2 层，搜索 3、4 层的时间花销还是太大，于是进行额外的剪枝。
根据五子棋的下棋经验，棋子一般是聚集在一起的，所以在搜索时可以跳过那些距离棋局较远的点。这里设置半径为 2，也就是仅搜索距离已有棋子 2 格内的那些棋子，大大缩小了搜索时间，此时可以搜索 3 层。
还有另一个显而易见的优化方法。当对方可能下出活四、连五这种棋型时，AI 的选择就很少了，基本上只能进行堵截或强攻。于是在每次搜索进行一次搜索，若存在这种限制选择的 “easy position”，则只在这些位置进行搜索。这样可以 AI 思考速度会快很多。
此外，由于五子棋的胜负考虑比较长远，所以无法进行贪心剪枝。最终设定搜索深度为 3。