在深度优先的最小最大法中,我们可以看到,博弈树的某些部分并不会产生任何有意义的值,因而也根本用不着去扩展博弈树的这一部分。识别博弈树中这些可忽略部分的技术,称之为α-β截断。之所以叫这个名字,是由于历史原因造成的。
我们可以看出,在轮到棋手下棋的节点上,其部分回溯值是10。而它的当前计算出来的子节点的部分回溯值是8。现在,由于该子节点是轮到对手下棋的节点,而对手总是要走那个具有最小值的棋局,故进一步探察的结果只会小于这个值。无论最后的确定值是多少,它总是小于或等于8。
从另一方面来看,该节点本身的部分回溯值是10。因为这时轮到棋手下棋,所以只有大于10的子节点的值才能改变这个部分回溯值。
所以我们得出的结论是:不需要去进一步扩展其子节点或其它任意后续节点。这是因为进一步的扩展至多只能减少其子节点的回溯值,而其目前的值已经足够小到不能影响其亲节点的部分回溯值了。这种情况就是所谓的α截断。
现在,我们把一般的原则叙述如下:
在考虑轮到棋手下棋的一个亲节点及轮到对手下棋的一个子节点时,如果该子节点的数值已经小于或等于其亲节点的回溯值,那么就不需要对该节点或者其后续节点做更多的处理了。计算的过程可以直接返回到亲节点上。
当亲节点是轮到对手下棋的一个节点时,该原则作相应的改动:
在考虑轮到对手下棋的一个亲节点及轮到棋手下棋的一个子节点时,如果该子节点的部分回溯值已经大于或等于其亲节点的部分回溯值,那么就不需要对该子节点或者其后裔节点做更多的处理了。计算过程可以直接返回到亲节点上。这就是所谓的β截断。
截断这一技术允许我们有时可以不去考虑某节点的某些子节点的情况。然而,由于非终节点的每一个子节点又是其后续节点所组成的整个博弈树的根,所以,如果我能忽略掉那些子节点的话,不仅仅是忽略了它们本身,还忽略了它们所有的后续节点。因此,这一技术可以删去数量相当大的节点,因而也就大大的节省了搜索博弈树所需要的时间。
分享到:
相关推荐
制作一个五子棋小游戏,实现人机对战,其中电脑在进行极大值极小值搜索时需要运用α-β剪枝算法。五子棋小游戏的核心是电脑端走步的选取,使用的方法是极大极小值搜索,并且题目要求使用α-β剪枝来提高搜索效率;除...
人工智能-项目实践-模型剪枝-基于博弈树α-β剪枝搜索的五子棋AI 最近机器学习很火, 乘着这把火,我也学习了一把,但是没有直接学习深度学习,而是遵从一位老前辈,一定要把人工智能的所有方法都了解掌握了,才能...
博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,提出在扩展未达到规定深度节点时,...
α-β剪枝实现的一字棋 <br>人机对战,MFC写的,基本功能都有,可以直接运行. <br>课程大作业,有详细设计文档.:-)
人工智能 博弈树的启发式搜索 α-β剪枝
这里只给出了源代码,没有解决方案文件,大家可以自行组装。VS2022编译通过。博弈树最大搜索深度目前是4层(代码中因为序号从0开始,所以是3,其实还是4层这,已经是上限了)。
对于博弈类人工智能,其中一个方法就是:博弈树极大极小值alpha-beta剪枝搜索。 是不是觉得这个名字很牛逼, 但经过我的详细解读, 你马上就会发现,原来不过如此。 对于要实现一个会智能下五子棋的AI,要怎么去...
人工智能α-β剪枝实现的一字棋实验报告.doc
本文设计了一种基于神经网络思想及α-β方法的五子棋算法。结合神经网络思想及α-β方法,本文探讨博弈的搜索方法及推理技术中优化五子棋算法的思路,并最终利用VB语言实现了五子棋最优路径的选择。
使用Python编程实现博弈树的构建,实现利用MinMax方法补全博弈树缺失值,并结合α-β剪枝算法,实现博弈树的剪枝。实现了整体算法与博弈树的可视化。全部代码压缩至该文件。
实验二:利用α-β搜索过程的博弈树搜索算法编写一字棋游戏.pdf
利用α-β搜索过程的博弈树搜索算法编写一字棋游戏.doc.doc
利用经典的α-β剪枝算法对博弈树剪枝 每次搜索仅搜索落子点周围 2*2 格范围内存在棋子的位置,这样可以避免搜索一些明显无用的节点,而且可以大幅度提升整体搜索速度 避免对必胜/负局面搜索,当搜索过程中出现了...
熟悉和掌握博弈树的启发式搜索过程、α-β 剪枝算法和评价函数,并利用 α-β 剪枝算法开发一个五子棋人机博弈游戏。 实验内容 以五子棋人机博弈问题为例,实现 α-β 剪枝算法的求解程序(编程语言不限),要求设计...
2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。...
原来想用博弈树 α-β剪枝法实现人工智能AI,试了2天没测试出来,但代码里有测试的demo已经测试通过,就跟五子棋还没结合起来,网上Java版的博弈树 α-β剪枝法我找不到,虽然最终没有完成,但对于这个算法本身我...
人工智能原理 五子棋 博弈 剪枝技术 实验 课程设计 源程序
基于alpha-beta剪枝博弈树算法实现的一字棋游戏
博弈论专题---------------博弈论
商战博弈---商务谈判.pptx