人工智能课程大作业

1、人工智能课程大作业作业题目 摘要：机器博弈是人工智能的一个重要研究分支，本文通过设计一个五子棋智能博奕程序，采用传统的博弈树算法，利用剪枝和极大极小树搜索最佳位置，从而实现人机智能博弈。并对现有算法存在的问题进行探究改进，最后给出展示，结果表明效果比较理想。关键词：人工智能；五子棋；博弈本组成员： 本人分工：-剪枝实现1 引言人工智能1是一门综合新型的新兴边缘科学，与生物工程、空间技术并列为三大尖端技术，而机器博弈却是其一个重要的研究分支。它研究如何利用计算机去实现那些过去只能靠人的智力去完成的工作，博弈为人工智能提供了一个很好的应用场所。博弈过程可以采用与或树进行知识表达，这种表达形式称为博

2、弈树。剪枝技术是博弈树搜索中最常采用的策略。2 算法原理与系统设计根据五子棋游戏规则，此次五子棋游戏我们采用基于极大极小值分析法的剪枝算法来实现计算机走棋。剪枝技术是博弈树搜索中最常采用的策略，剪枝搜索由极大极小值分析法演变而来2。极大极小分析法其基本思想或算法是：(1) 设博弈的双方中一方为MAX，另一方为MIN。然后为其中的一方(例如MAX)寻找一个最优行动方案。(2) 为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较,具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。(3) 为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈

3、树端节点的得分。此时估算出来的得分称为静态估值。(4) 当端节点的估值计算出来后，再推算出父节点的得分，推算的方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。(5) 如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了-剪枝技术。-剪枝技术的基本思想或算法是，边生

4、成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：(1) 对于一个与节点MIN，若能估计出其倒推值的上确界，并且这个值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为剪枝。(2) 对于一个或节点MAX，若能估计出其倒推值的下确界，并且这个值不小于 MAX的父节点(一定是与节点)的估计倒推值的上确界，即，则就不必再扩展该MAX节

5、点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为剪枝。图2.1 系统流程图图2.2 系统结构图3 系统实现首先构造棋型估分，对五子棋当前局势的分析，对每步进行估分；然后应用博弈树，提高AI智能，考虑层数，提高AI智能，接下来应用-剪枝，提高AI速度，经过-剪枝，可以极大的减少搜索的数量，从而提高了的AI速度，极大的减少了搜索层数对AI速度的影响。4 实验或测试结果实验方案及结果：.检测双三或三活三 .判断剩余空间是否能成五子 .剪枝5 结论通过对AI的学习，了解了极大极小值分析法的原理，以及这种博弈树的不足，当搜索层数过多时，计算量太大，严重影响了计算机下棋的速度，我们采用剪枝技术来解决这一问题，减掉不必要的枝，从而极大地减少了搜索层数对计算时间的影响。虽然对极大极小分析法做了时间方面的改进，但仍有不足。由于AI是有一定的失误率存在，所以，要想提高计算机走棋的精准度，增加搜索层数是很有必要的，而搜索层数对计算速度的影响又是不可避免的，并且影响很大，仅仅依靠对博弈树进行剪枝是不够的，还需进一步优化。希望能在后续的课程学习中能进一步优化五子棋，提升AI的精准度，在增加搜索层数的同时，极大的减少对计算