设为首页 - 加入收藏
广告 1000x90
您的当前位置:E乐彩票app下载 > 博弈树搜索 > 正文

零和博弈-极大极小搜索Alpha-Beta剪枝(井字游戏)

来源:未知 编辑:admin 时间:2019-04-20

  二人利益对立完备信息博弈过程,在我们分析表达中就是对一个过程进行按规定双方交替操作,每次操作即搜索时选择对自己有利的情况(获益选最大,损失选最小),借助的数据结构自然是树。博弈树中每一层是某一方的走法选项。假设先手为MAX,后手为MIN。MAX可选的方案间为or关系(MAX自己掌握选项),MAX可选的方案对于可供 MIN选的方案为and关系(MAX无法决定,是MIN决定,也就是说MAX选完,MIN将自由选择)。 MAX在博弈中需要朝着自己的利益最大化出发,同时避免对自己不利的情况出现。

  3.整个博弈过程始终站在一方角度,所以可使自己胜利的结局都是本原问题,相应的节点是可解节点,所有使对方胜利的节点为不可解节点。

  4.博弈树从一开始产生,他包含问题所有可能情况,但是我们在使用时,他可能并不会全部展开(生成),这取决于我们要预测多远(搜索深度)以及已经做出的操作,事实上我们在最大最小搜索中某一时期所用的搜索树只是博弈树的一部分。

  为了选择最好,避免最差,我们需要一个对于做出选择后的评估函数evaluate(),来作为我们选择的标准。假设博弈双方为MIN,MAX,规定对于有利于MAX方的态势,evaluate取正值,对于有利于MIN的evaluate取负值。对双方利益相同时evaluate取0

  3.评价往回倒推时,交替1.2来计算传递评价(通俗地讲就是生成几层搜索树,然后再依据MIN-MAX选择返回上层,由返回值决定最初的选择)

  最上层的MAX选手走,其有两种选择,每种选择后MIN选手走,最后如此重复,生成4层搜索树(这里只是向前估计2步,所以设置为4层,生成树的过程就是一个简单的广搜)。

  2.    依据极大极小原则从底层返回上层(图中红色笔标记出返回路径),即MIN节点的选择其下属的节点的最小值作为自身的值,MAX选择其下属的最大的值。

  3.    顶层依据返回方向,选择合理下一步,图中表现为MAX选择走左边的节点对应的那一步。

  4.    重复再每一步时使用1-4的判决策略,直到某一方胜利或者平局。

  由上可以看出,单纯的极大极小搜索需要在每一步判断时对问题进行所有可能性的枚举,并且依据对于搜索深度的要求,生成一个空间复杂度较高的树。每一步判断如此累加,将导致整个算法树的生成与搜索效率降低。

  在极大极小搜索生成博弈搜索树的时候,会生成规定深度内的所有节点,然后估值倒推。这样把生成与估值倒推分离,降低了效率。我们来介绍Alpha-Beta算法(以后简称α-β剪枝)。他的原理是把生成后继节点与倒退估值结合,减去无用分支,以此来提高效率。

  借助极大极小搜索的特点---MAX节点对应A值,不会下降,MIN节点对应的B值不会上升。这里的A-B值分别指倒推时对应节点的值。

  对于MAX来说,其某个后继节点MIN的B值小于该MAX或者更早的先辈节点的A值时,停止对该MIN节点的搜索。同理,当某个MAX节点的A值大于等于其先辈MIN节点的B值时,停止对该节点的搜索。由此,我们可以得到,A-B必须要求搜索树某一部分达到最深计算出一部分MAX的A值或者MIN的B值,随着搜索,不断改进A-B值。

  1.    A剪枝:任何MIN的B小于任何他的先辈MAX的A时,停止该MIN以下的所有搜索,这个MIN的最终倒推值为当前的B值。(该B可能与真正的不同,但是没关系,不影响最终结果)

  2.    B剪枝:任何MAX的A大于或者等与他的先辈MIN的B时,停止该MAX节点以下的所有搜索,这个MAX的最终倒推值为当前的A值。

  A-  剪枝的效率与最先生成的A-B值与最终的倒推值有关,越相近,剪枝越提前并越快。

  最佳情况下搜索深度为d的叶节点数相当于单纯MINMAX生成的深度为d/2的博弈树的节点数。有效分支系数为sqrt(b),而不是b,即假设某一步有4种情况,而用上A-B剪枝,情况变为2种。

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

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

  极大极小搜索 和 与/或图搜索基本写起来差不多吧.下面是一些题目,自己从题目中体会吧...... 最主要用到的也就是 进制压缩+记忆化搜索+αβ剪枝,其他也没什么了... HD...博文来自:671coder的专栏

  计算机科学中最有趣的事情之一就是编写一个人机博弈的程序。有大量的例子,最出名的是编写一个国际象棋的博弈机器。但不管是什么游戏,程序趋向于遵循一个被称为Minimax算法,伴随着各种各样的子算法在一块。...博文来自:我的专栏

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

  最近正在做一个人工智能的中国象棋,所以不可避免的接触到了博弈论,因为考虑到以后还会有所涉及 (alpha-beta search),所以写成了一片文章 这里以中国象棋为前提,AI首先需要一个博弈树 (...博文来自:Racal

  Alpha-Beta搜索作为棋类算法最常用的一种搜索算法,也是最基本的一种博弈搜索算法。Alpha-Beta主要考虑了最大最小搜索中的冗余搜索问题,极大的减少了冗余搜索量,提高了搜索效率。最小-最大的...博文来自:九三智能控

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

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

  【摘要】本文讨论了搜索算法中“剪枝”这一常见的优化技巧. 首先由回溯法解决迷宫问题展开论述,介绍了什么是剪枝; 而后分析剪枝的三个原则正确、准确、高效,并分别就剪枝的两种思路:可行性剪枝及最优性剪枝,...博文来自:woshizhazha的专栏

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

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

  极小极大算法 (The Minimax Algorithm) [说明] 本文基于 , 本文中的图片均来源于此笔记。 极小极大算法常用于二人博弈游戏,目的是寻找...博文来自:housong_csdn的博客

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

  极大极小搜索算法: 用于围棋,五子棋,象棋等棋类,结果有三种可能:胜利、失败和平局。理论上可以穷举所有的走法,这就需要生成整棵博弈树。实际上不可行。因此搜索时可以限 定博弈树的深度,到达该深度则不再往...博文来自:BRCOCOLI的博客

  1.说明: 这是学极大极小搜索的第二(三)天,昨天因为思路较为混乱,且对评估函数不甚了解,因此自己写出来的AI井字棋宛若ZZ,不过仔细查看了学长的PPT并且钻研了一番,总算对Minimax算法有了比...博文来自:cprimesplus的博客

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

  初学者的个人笔记,不足之处还请指正,谢谢 极小化极大算法(minimax) Lalgorithm minimax 极小化极大算法是一个深度优先的搜索算法,树形结构递归,一般在棋类等两方较量的游戏...博文来自:Lingshu_M的博客

  搜索算法的通用优化方法 [DFS][搜索剪枝]在很多情况下,我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣”的其他解,搜索到后也只能回溯。为了避免出现这种情况,我们需要灵活...博文来自:超

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

  POJ 1190要制作一个体积为Nπ的M层生日蛋糕,每层都是一个圆柱体。 设从下往上数第i(1 Hi+1。 由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积Q...博文来自:sun897949163的博客

  总述:五子棋问题可以化为一个博弈问题。从开始落子到最后赢,输或和的每一步落子构成了一个解,而解空间就是一个树。解就是这个树中的一条路径,只不过这个解空间的是由电脑和人的共同选择构成的。我们可以使用极大...博文来自:cs1612900的博客

  极小化极大算法(The minimax algorithm)前面部分描述的技术适用于简单,完全可解决的游戏,如Nim(因为其所有的情况也不算大)。然而,随着游戏变得越来越复杂,很快就无法检查每一个可能...博文来自:redAnt的博客

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

  零和博弈算法之极大极小搜索和α−β剪枝\alpha-\beta剪枝算法解决 486. Predict the Winner极大极小搜索算法介绍Minimax算法 又名极小化极大算法,是一种找出失败的最...博文来自:rjx博客

  1.     问题定义 一字棋游戏,包括两个选手。用户可以在一个3*3的棋盘上任意的选择空闲的位置拜访棋子,最早在水平方向上,或者垂直方向上或者对角线方向上形成三子一线所示。这里我...博文来自:Work Hard, Play Harder!

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

  对人工智能中“极大极小值”的博弈算法的资料整理。博文来自:dale13的博客

  2.1   Min-Max方法 假设在博弈过程中,对抗者1总是选择使得博弈值最小的移动,那么作为对手的对抗者2则总会选择是的博弈值最大的移动,对抗者1称为min,对抗者2称为max.由于博弈双方是交...博文来自:李希的博客

  2015年9月7日周一 由Jeff Bradberry留       与游戏AI有关的问题一般开始于被称作完全信息博弈的游戏。这是一款对弈玩家彼此没有信息可以隐藏的回合制游戏且在游戏技术里没有运气元...博文来自:z84616995z的专栏

  CSS Grid Layout规范中的minmax()函数是一个非常有用的新特性。这个函数能够让我们用最简单的CSS控制网格轨道的大小。这个函数包括一个最小值和最大值。minmax()函数minmax...博文来自:taotaomin99的博客

  alpha:表示目前为止找到的最小数 beta:表示目前为止找到的最大数 1.极大层的上一层是极小层。一方面极大层找的是自己的子节点中的最大值,另一方面极大层的上一层找的是极大层们提供的节点中的最小一...博文来自:脚踏实地,仰望星空

  之前在极大化极小算法minimax说得不够清楚而且也没有附带伪代码,所以这里再写一篇专门关于剪枝的blog 博文来自:joshualiunsw的博客

  alpha-β修剪的好处在于可以消除搜索树的分支。这样,搜索时间可以限制在“更有希望”的子​​树中,并且可以在同一时间执行更深入的搜索。该算法和极小化极大算法一样,都是分支限界类算法。若节点搜索顺序达...博文来自:emoheithree的博客

  alpha-beta剪枝算法及实践 算法原理 算法伪码 中国象棋AI实践 算法原理 alpha-beta剪枝算法是基于极大极小搜索算法的。极大极小搜索策略是考虑双方对弈若干步之后,从可能...博文来自:洋葱的博客

  剪枝是必须的上一篇讲了极大极小值搜索,其实单纯的极大极小值搜索算法并没有实际意义。可以做一个简单的计算,平均一步考虑 50 种可能性的话,思考到第四层,那么搜索的节点数就是 50^4 = 625000...博文来自:言川的博客

  这篇笔记主要介绍了零和博弈,借用最小最大定理以及LP对偶来处理这一类混合策略纳什均衡...博文来自:初木的学习笔记

  Tic-Tac-Toe算法笔记 这几天在用Python写Tic-Tac-Toe小游戏,顺便接触了一些简单的人机博弈算法,其实在算法方面我完全算是个新手,所以这也算是一个反复折腾学习的过程。而Tic-T...博文来自:网站架构札记

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

  极小极大的定义 Minimax算法 又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)。通常以递归形式来实现。 Minimax算法常用于棋类等由两方较量...博文来自:Weirenren_027的专栏

  1. 前言 隐马尔科夫HMM模型是一类重要的机器学习方法,其主要用于序列数据的分析,广泛应用于语音识别、文本翻译、序列预测、中文分词等多个领域。虽然近年来,由于RNN等深度学习方法的发展,HMM模型...博文来自:tostq的专栏

  有了上篇单目标定示例程序的经验,双目标定就是小菜一碟哈。 本人目前菜鸟,但还是愿意厚着脸皮分享我一下午的成果。不要拍我... 1.找到目录   ...\opencv\sources\sam...博文来自:t247555529的博客

  reids是一个key-value存储系统,为了保证效率,缓存在内存中,但是redis会周期性的把更新的数据写入磁盘或者把修改操作写入追加的记录文件,以保证数据的持久化。   所以:redis是一...博文来自:那么好,

  帐号相关流程注册范围 企业 政府 媒体 其他组织换句话讲就是不让个人开发者注册。 :)填写企业信息不能使用和之前的公众号账户相同的邮箱,也就是说小程序是和微信公众号一个层级的。填写公司机构信息,对公账...博文来自:小雨同学的技术博客

  XML基础+Java解析XML 一:XML基础 XML是什么: 可扩展的标记语言 XML能干什么: 描述数据、存储数据、传输(交换)数据。 XML与HTML区别: 目的不一样 XML...博文来自:NWK工作者的博客

  最近在公司做一个项目,老大让我们实现加解密的方法,我把工作直接推给了java服务端,他们也是直接在网上copy的代码,说我直接放到我的android代码中就可以了,不需要太多的更改。我就照做了,但是在...博文来自:HarryWeasley的专栏

  多重背包问题:有N种物品和容量为V的背包,若第i种物品,容量为v[i],价值为w[i],共有n[i]件。怎样装才能使背包内的物品总价值最大?网上关于“多重背包”的资料倒是不少,但是关于怎么实现O(N*...博文来自:flyinghearts的专栏

  最近比较有空,大四出来实习几个月了,作为实习狗的我,被叫去研究Docker了,汗汗! Docker的三大核心概念:镜像、容器、仓库 镜像:类似虚拟机的镜像、用俗话说就是安装文件。 容器:类似一个轻量...博文来自:我走小路的博客

  强连通分量: 简言之 就是找环(每条边只走一次,两两可达) 孤立的一个点也是一个连通分量   使用tarjan算法 在嵌套的多个环中优先得到最大环( 最小环就是每个孤立点)   定义: int Ti...博文来自:九野的博客

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

  详细过程见下面的链接: 需要更新的是: 1. 原文中bag 数据的下载地...博文来自:feixin620的博客

  默认maven的本地仓库的位置是在C盘,如果重装了系统,仓库就没了,因此,把仓库位置改到其他盘。     第一步:打开maven安装位置下的conf/settings.xml;   第二步:在第5...博文来自:a24b86的博客

  花了几天,终于把matlab版的人脸检测运行成功了,虽然正确率不是很高,看着各种论文上的人脸检测正确率都出奇的高,我是不怎么相信的,有的论文连基于平均脸的人脸检测正确率都能达到98%,汗啊~~  也许...博文来自:海海人生

  最近在学习大数据,在学习的时候碰到了一个问题就是给CentOS虚拟机配置静态IP后,就无法访问网络了,这个问题纠结了我好长时间,现在终于找到解决方法了,赶紧记录下来,以备以后查询。注: 我这里说的方法...博文来自:u012453843的专栏

  上一篇文章讲解了SNMP的基本架构,本篇文章将重点分析SNMP报文,并对不同版本(SNMPv1、v2c、v3)进行区别! 四、SNMP协议数据单元 在SNMP管理中,管理站(NMS)和代理(Age...博文来自:假装在纽约

  CGLIB介绍与原理(部分节选自网络) 一、什么是CGLIB? CGLIB是一个功能强大,高性能的代码生成包。它为没有实现接口的类提供代理,为JDK的动态代理提供了很好的补充。通常可以使用Java的动...博文来自:zghwaicsdn的专栏

  分页实现的效果:      /**/ 组图0-1.分页实现效果图一       /**/ 组图0-2.分页实现效果图二 一、从效果可以看出内容由两部分组成: 1.学生信息     数据库中插入一些记录...博文来自:niaonao

  在MATLAB中,可以注释一段程序。 使用“%{”和“%}”。 例如 %{ 。。。 %} 即可。 经典方法是用 if 0,但缺点是不够直观,注释掉的内容仍然保持代码的颜色。现在可以用 ...博文来自:知识小屋

  weixin_43878432:[reply]hffhjh111[/reply]嗯嗯,谢谢博主,今天解决这个问题了

  hffhjh111:[reply]weixin_43878432[/reply] 看懂本文以及你所列文章足以完成你的要求,具体做法要靠你自己,这是你的毕设,,,

  weixin_43878432:[reply]hffhjh111[/reply] 博主您好,我是做的毕设。老师是想得到如果相机面前同时站了六个人,但是只显示(追踪)一副骨架的效果。我现在考虑只识别(显示)离镜头最近的那个人骨架。查到一个资料。,但是我照着做没有成功。还是可以同时显示两个人的骨架。希望博主您能帮帮小白。/抱拳

  hffhjh111:[reply]M_D_lufy[/reply] 那个kinectV2深度图的位数是固定的,所以你输入的depthBitmap大小要与他配置一致,不可随意更改。另外,那个图暗or亮并不取决于你的图像灰阶。当然你觉得太暗的话,可以对输出的图像进行直方图正规化等增强方法(参照数字图像处理)。

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

相关推荐:

网友评论:

栏目分类

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

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

Top