的父节点(一定是或节点)的估计倒推值的下确界α,即α≥β,则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为α剪枝。(2)对于一个或节点MAX,若能估计出其倒推值的下确界α,并且这个α值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界β,即α≥β,则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为β剪枝。图2.1系统流程图图2.2系统结构图3系统实现首先构造棋型估分,对五子棋当前局势的分析,对每步进行估分;然后应用博弈树,提高AI智能,考虑层数,提高AI智能,接下来应用α-β剪枝,提高AI速度,经过α-β剪枝,可以极大的减少搜索的数量,从而提高了的AI速度,极大的减少了搜索层数对AI速度的影响。4实验或测试结果实验方案及结果:1.检测双三或三活三2.判断剩余空间是否能成五子3.剪枝5结论通过对AI的学习,了解了极大极小值分析法的原理,以及这种博弈树的不足,当搜索层数过多时,计算量太大,严重影响了计算机下棋的速度,我们采用α-β剪枝技术来解决这一问题,,减掉不必要的枝,从而极大地减少了搜索层数对计算时间的影响。虽然对极大极小分析法做了时间方面的改进,但仍有不足。由于AI是有一定的失误率存在,所以,要想提高计算机走棋的精准度,增加搜索层数是很有必要的,而搜索层数对计算速度的影响又是不可避免的,并且影响很大,仅仅依靠对博弈树进行剪枝是不够的,还需进一步优化。希望能在后续的课程学习中能进一步优化五子棋,提升AI的精准度,在增加搜索层数的同时,极大的减少对计算时间的影响。参考文献[1] 王万良.人工智能及其应用[M].北京.高等教育出版社,2008[2] 王建雄.博弈树启发搜索算法在五子棋游戏中的研究应用[M].科技开发情报与经济,2011,21(29)
全文预览
