设为首页 - 加入收藏
广告 1000x90
您的当前位置:二四六天天好彩308K文字资料 > 博弈树搜索 > 正文

对极大极小搜索和阿尔法贝塔剪枝搜索算法的简单描述与理解--萌新

来源:未知 编辑:admin 时间:2019-07-01

  这是本人第一次正经写博客,排版技术不行,看起来可能有点难受,但我相信如果大家认真按顺序读下去一定能理解这个算法,如果还有不是很清楚或者觉得我哪里有讲错的地方欢迎评论留言!这段时间都在!会看和回复的!

  举个比较简单的例子。这里有两个包,在你知道两个包里有什么的情况下,你需要选一个包然后让你的竞争对手小明从这个包里的两张钱中选一张给你,但是你想让自己的钱越多越好而小明不想让你钱多,所以他会选一张相对最小的钱给你。也即对你而言,你需要从中获得最大利益,而小明只是想承受最小的对手变强程度。在这种情况下你应该选择包2,小明会给你2元。如果你选择了包1 ,你只能得到0.5元。

  这其实就是极大极小搜索,抽象到树的形式来看,这次我们来选数字,注意一点的是这个树的搜索顺序用人脑其实是反过来的,这个具体我会在后面的代码实现里讲,为了方便我们理解就暂时先从下往上看把。就比如是上一题的包里拿钱问题,0.5,100是第一个包内的钱,2,10是第二个包里的,当我们拿了一个包就往上推让B选其中一张较小钱,即0.5或2,最后我们从这两张钱里选一张拿到我们手上,因为这是我们自己在推演这个过程,所以要考虑完备也即所有可能的情况,也就是为什么这里B可以选两张钱(这个说出来了就很好理解甚至有点蠢,但是我刚学的时候思路卡了很久所以提一下),这样在实际情况中其实我们只能选一个包让b选一张钱给我们,所以一个完备的推演过程可以保证我们获得的利益也就是最上面的节点的数字最大。其实分析以下我们可以推广到n层,无非是分成了两个层:一个是MAX层,这一层由我们来选择从下一层拿上来的数字,为了自己的利益最大化,我们会从下一层的子节点选择极大的一个来存在这个节点,故称为MAX;一个是MIN层,由对手选,同理,他会想方设法降低我们获得的利益,所以他会从下一层选极小的节点来存,这样我们的MAX层在选的时候就只能拿到相对较小的极大。

  以上就是极大极小值搜索的内容了,但是单纯用极大极小搜索的意义不是很大,因为在博弈中,一步棋可能会有成千上万种招法,如果全部进行搜索时间耗费太长,效率不高,在规定时间内下棋肯定是行不通的。这个时候就需要进行一些优化,也就是阿尔法贝塔剪枝了。

  小插曲:感兴趣的朋友还可以看看负极大值搜索这个算法,跟极大极小内涵一样,只是人们嫌转换极大极小不方便,干脆把极小层加个负号,这样可以全搜极大,因为极大的负就是这层的最小!这里不多说了。

  剪枝,顾名思义就是剪去枝节,也就是我们的树的节点链。【请务必先理解透彻极大极小的搜索逻辑和顺序!】下图引用自英文的阿尔法贝塔剪枝维基百科

  它和我们上面的选钱游戏的搜索树长得很像,因为这个算法就是基于极大极小值搜索的,为什么叫阿尔法贝塔,因为有alpha,beta两个值。alpha表示我们需要的最好结果,beta表示对手能承受的最坏结果。基于最坏的打算的思想,把alpha初值设为负无穷即-INF,beta为正无穷INF。上图是已经搜索完毕并且剪枝节了的,所以我们从下往上从左往右分析一下,为什么这样选,为什么这样剪枝。【其实最下面的MAX层我感觉没必要标出来,它们是已经先存在待选的】在最左边,选第一个MIN层即B选,对B而言研究beta,即B能承受的最小,拿下面两个子节点和beta比较,此时beta初值为-INF,一定小于子节点的数,选出了5是较小的,往上走发现第三层【从上往下数,后面也一样】的第一个节点有另一个子节点,于是去搜索另一个子节点,第五层第一个是7,返回到第四层第二个节点,然后继续往后,第五层第二个节点是4,比7小于是第四层第二个节点更新为4,此时出现了第一个剪枝【关键点来了!】。因为对于第三层第一个节点,我们已经搜过一次,得到此时的alpha是5,第三层是max层,他会从第四层对应子节点选一个极大的值,而第四层是min层会从第五层选择极小值,也就是说,我们继续在第五层的对应第四层第二个节点的子节点搜索也只可能返回给第四层第二个节点比4更小的数字,但是第三层选的是极大,5已经比4大了,换句话说,无论第四层第二个节点再怎么更新值也只能小于等于4,也即小于5,所以第三层第一个节点一定不会去选第四层第二个节点了,也就没有必要再搜索后面了,这就使用了第一次剪枝节。【记住一个关键点,考虑父节点的min、max性质,比较兄弟节点来剪枝节】第二次剪枝即第四层第五个节点剪枝同理不再讲。对于第三次剪枝节也即第二层第三个节点,我们先搜索他的第一个子节点,一路搜上来返回了5,这里直接剪掉了一整条第三层第六节点。这里从我上面提到的关键点考虑,因为第一层是max层,他会从第二层选一个极大,此时我们已经搜索出来第二层第二个节点是6,而第三个节点是5,第二层是min层,第三个节点继续搜索也只可能比5小,也即小于6,所以直接剪去第二层第三节点的所有其他子节点,去搜索第四个节点【如果有的话】。

  相信到这里大家应该已经对概念理解的差不多了。上面我曾提到过,为了方便理解,我们从底部往上想,但是在代码里这样就不太好写了。对代码,我们可以利用递归返回来实现从下往上回溯,返回一个一个的节点搜索值。递归如果你比较熟悉的话应该会容易懂,即写的时候是从上往下写,但逻辑上其实是从下往上返回值。

  这个是一个三角点格棋的题,理解这个存储局面和连边可能会有点挫折,实在看不明白可以直接看他的alpha-beta函数,不去理会这个题本身,博主注释写的还是很清楚的!欢迎评论留言

  从人落子开始到出现胜负或者和局,之间所落的子,构成了一个解。而解空间就是一个树,解就是这解空间中的一条路径。只不过这个解空间是电脑的选择和人的选择共同构成的(奇数层是电脑(因为轮到电脑落子么),偶数层...博文来自:脚踏实地,仰望星空

  极小极大算法(TheMinimaxAlgorithm)[说明] 本文基于 , 本文中的图片均来源于此笔记。极小极大算法常用于二人博弈游戏,目的是寻找最优的方案使得自己能够利益最大化。基本思想就是假设...博文来自:housong_csdn的博客

  计算机博弈(也称机器博弈),是一个挑战无穷、生机勃勃的研究领域,是人工智能领域的重要研究方向,是机器智能、兵棋推演、智能决策系统等人工智能领域的重要科研基础。机器博弈被认为是人工智能领域最具挑战性的研...博文来自:的博客

  我在最近撰写五子棋AI程序设计报告时,翻阅了很多的资料博客,但却发现大佬们的博客,没有一篇是能让我只看它就能理解全部的AI算法。在看了众多博客后,我终于对博弈树、极大极小搜索、αβ剪枝恍然大悟,其实这...博文来自:的博客

  问题描述试题编号:201803-4试题名称:棋局评估时间限制:1.0s内存限制:256.0MB问题描述:问题描述Alice和Bob正在玩井字棋游戏。井字棋游戏的规则很简单:两人轮流往3*3的棋...博文来自:姬小野的博客

  想请教一下,五子棋中用极大极小搜索下一步,不晓得我理解的对不对... 比如考虑双方各一步,那么搜索树应该有3层,第一层为根节点,第二层表示电脑所有的走法,第三层表示对应的人的可能的走法,现在该电脑走棋论坛

  fivechess用到1.极小极大搜索方法   一般应用在博弈搜索中,比如:围棋,五子棋,象棋等。结果有三种可能:胜利、失败和平局。暴力搜索,如果想通过暴力搜索,把最终的结果得到的话,搜索树的深度太大...博文来自:tianzhijiaozi19的专栏

  偶数层  Max搜索奇数层  Min搜索在进行极大-极小搜索的时候,首先要在有限深度内展开全部叶子节点,并进行评估。然后自下而上地进行搜索计算,奇数层节点取其子节点估值的极小值,偶数层节点取其子节点估...博文来自:u011002533的博客

  参考书籍《人工智能基础教程》该算法的搜索策略是考虑双方若干步之后,从可能的步中选择相对较好的走发来走。以MAX表示程序方,MIN表示对手方,P表示局势,f(P)是根据当前局势做出的估计函数。则F(p)...博文来自:Elliebababa的博客

  AI实现的基本思路-极大极小值搜索算法五子棋看起来有各种各样的走法,而实际上把每一步的走法展开,就是一颗巨大的博弈树。在这个树中,从根节点为0开始,奇数层表示电脑可能的走法,偶数层表示玩家可能的走法。...博文来自:言川的博客

  由来最近人工智能很火,经常有各种新闻,作为一个程序员多少要懂一点吧,未来万一用得着呢。有心想去了解一下,奈何能力有限,皮毛都没学会。好吧,既然没法系统学,就不管那么多,就从现在开始动手,一步一步的往前...博文来自:feifei316631241的博客

  原文链接: 总结两点:1.深度优先搜索,只有在叶子节点计算评估分。2.max和min层只负责从分支中,...博文来自:大熊熊的专栏

  极大极小搜索策略一般都是使用在一些博弈类的游戏之中:这样策略本质上使用的是深度搜索策略,所以一般可以使用递归的方法来实现。在搜索过程中,对本方有利的搜索点上应该取极大值,而对本方不利的搜索点上应该取极...博文来自:如果这是你所爱的,要坚持,并踏实。

  一、博弈概述博弈特点:(1)博弈的初始格局是初始节点(2)在博弈树中,“或”和“与”是交替出现的。自己一方的扩展节点是“或”关系,对方扩展的节点是“与”关系。双方轮流扩展节点。(3)所有自己一方获胜的...博文来自:水野与小太郎的博客

  本文内容来自中科院大学张文生老师的人工智能课件,整理置换与合一.5归结原理.人工智能复习笔记,考试前还是没看懂,考试也来了,转过来好好看--    置换(substituti...博文来自:Modeala的专栏

  本文内容来自中科院大学张文生老师的人工智能课件,有改动3置换与合一.5归结原理.人工智能复习笔记    置换(substitution)    定义: 置换是一个形如{t1/v1,…, tn/vn}的...博文来自:持之以恒

  问题:给出一个4x4tic-tac-toe的棋局的局面,问先手x是不是能找在接下来的一步中找到一个必胜局面,如果有,输出第一个落子位置(按顺序)。极大极小搜索策略一般都是使用在一些博弈类的游戏之中...博文来自:浅空之下

  1.极小极大搜索方法   一般应用在博弈搜索中,比如:围棋,五子棋,象棋等。结果有三种可能:胜利、失败和平局。暴力搜索,如果想通过暴力搜索,把最终的结果得到的话,搜索树的深度太大了,机器不能满足,一般...博文来自:kingkong1024的专栏

  看了很多帖子,都没这个帖子讲的清楚.Alpha-Beta剪枝搜索是棋类走子计算的首选算法,由于估值函数问题,不适用于围棋...博文来自:正在编程

  1、简单的说明:一开始α和β是负正无穷,α表示到目前为止路径上发现的MAX的最佳(即极大值)选择,β表示到目前为止路径上发现的MIN的最佳(即极小值)选择。α-β搜索中不断更新α和β的值,并且当某个节...博文来自:potato_uncle的博客

  人工智能的期末大作业,最近几个项目都在单干。还是要养成整理的好习惯!开原地址:基于α-β剪枝算法的智能五子棋 一、基本介绍 游戏...博文来自:stackess

  最近课设,做一个五子棋游戏。其中涉及alpha-beta pruning search算法,我自己看了一下别人的代码,不太明白,麻烦各位大仙解释一下呗!感谢! abstract class Searc论坛

  alpha-beta剪枝算法实现中国象棋人机对战Github仓库:问题介绍  本实验要求编写一个中国象...博文来自:dick的博客

  Alpha-Beta剪枝用于裁剪搜索树中没有意义的不需要搜索的树枝,以提高运算速度。假设α为下界,β为上界,对于α≤N≤β:若α≤β 则N有解。若αβ则N无解。下面通过一个例子来说明Alpha-Be...博文来自:数据与算法之美

  原文链接关于AlphaBeta剪枝的文章太多,这个方法是所有其它搜索方法的...博文来自:rareyang的专栏

  极小化极大(minimax)算法顾名思义,就是让最大得情况最小,这里的最大一般是指最差的情况,比如游戏中最不利的情况。该算法需要满足零和博弈,初略的解释就是若有两个玩家进行游戏,如果其中一方得到利益那...博文来自:joshualiunsw的博客

  极小值极大值的适用条件:零和,完全信息假设有两个人在对弈,分别为Max和Min所谓的极大极小,即Max要极大化自己的分数,而Min则要极小化Max的分数(注意棋局的分数是相对于Max而言)如下是极大极...博文来自:abc8350712的博客

  最小-最大搜索BruceMoreland/ 文从浅显的地方开始在国际象棋里,双方棋手都知道每个棋子在哪里,他们轮流走并且可以走任何合理的着法。下棋的目的就是将死对方,或者避免被将死,或者有时争...博文来自:gettogetto的博客

  我用VC++做一个人机对弈五子棋,人机博弈的算法不好,改用αβ剪枝搜索算法,可这个算法我不会。文字性描述的文章有看,但还是看不懂,希望可以给出伪代码。最好是源码。 急用!!兄弟姐妹们帮帮忙!非常感谢!论坛

  Alpha-Beta剪枝算法用于减小极大极小算法所搜索的节点数目,Alpha-Beta剪枝算法的效率很大依赖于节点的排列,在理想的排序下,算法复杂度为O(b^(d/2)),可以使搜索节点的数量减小一半...博文来自:u012501320的专栏

  看本章之前,请先参看前一篇文章《Minimax算法及实例分析》由于Minimax算法有一个很大的问题就是计算复杂性。由于所需搜索的节点数随最大深度呈指数膨胀,而算法的效果往往和深度相关,因此这极大限制...博文来自:我的专栏

  最近在做中国象棋对弈程序,用到了alpha-beta算法。这个博文来自:贰到不行的专栏

  博弈树搜索在下图中,第一层节点表示开始局面,我方先走,第二层节点表示我方可走的三个位置,第三层节点表示对于我方的每一种走法对手的各种走法,下方数字代表了对每个局面的评价值。这里的评价值都是相对于我方来...博文来自:启人zhr的博客

  Alpha-Beta剪枝算法最近做了一个中国象棋项目,其中用到了Alpha-Beta剪枝算法,在此做个记录。Alpha-Beta剪枝算法是一种传统的搜索算法, 它在博弈算法中有着非常广泛的运用,它大大...博文来自:梦溪笔谈的博客

  jquery/js实现一个网页同时调用多个倒计时(最新的)nn最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦!nnnn//jsn...博文来自:Websites

  weixin_43484801:讲的很好哟,看懂了,非常感谢,顺便提个建议,讲过程的时候分点一条条来会让可读性更强 ~ 嘿嘿谢谢讲解

  weixin_38682398:通俗的解释更容易理解,看了很多文章都没懂,赞哈!

本文链接:http://mzi-ads.com/boyishusousuo/617.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top