人工智能课程大作业
作业题目
摘要：机器博弈是人工智能的一个重要研究分支，本文通过设计一个五子棋智能博奕程序，采用传
统的博弈树算法，利用剪枝和极大极小树搜索最佳位置，从而实现人机智能博弈。并对现有算法存
在的问题进行探究改进，最后给出展示，结果表明效果比较理想。
关键词：人工智能；五子棋；博弈
本组成员：
本人分工：α-β 剪枝实现
1 引言
人工智能 是一门综合新型的新兴边缘科学，与生物工程、空间技术并列为三大尖端技术，而
[1]
机器博弈却是其一个重要的研究分支。它研究如何利用计算机去实现那些过去只能靠人的智力去完
成的工作，博弈为人工智能提供了一个很好的应用场所。
博弈过程可以采用与或树进行知识表达，这种表达形式称为博弈树。α—β 剪枝技术是博弈树
搜索中最常采用的策略。
2 算法原理与系统设计
根据五子棋游戏规则，此次五子棋游戏我们采用基于极大极小值分析法的 α—β 剪枝算法来实
现计算机走棋。α—β 剪枝技术是博弈树搜索中最常采用的策略，α—β 剪枝搜索由极大极小值分
析法演变而来 。
[2]
极大极小分析法其基本思想或算法是：
(1) 设博弈的双方中一方为 MAX，另一方为 MIN。然后为其中的一方(例如 MAX)寻找一个最
优行动方案。
(2) 为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较,具体地说，
就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。
(3) 为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得
分。此时估算出来的得分称为静态估值。
(4) 当端节点的估值计算出来后，再推算出父节点的得分，推算的方法是：对“或”节点，选其
子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最
有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最
坏的情况。这样计算出的父节点的得分称为倒推值。
(5) 如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。
上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析
法效率较低。于是在极小极大分析法的基础上提出了 α-β 剪枝技术。α-β 剪枝技术的基本思想或算
法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那
些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了
搜索效率。
具体的剪枝方法如下：
(1) 对于一个与节点 MIN，若能估计出其倒推值的上确界 β，并且这个 β 值不大于 MIN 的父节
1
资源评论
我是你的春哥！
- 粉丝: 4200
- 资源: 2万+
