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

极大极小搜索-----不太傻的井字棋

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

  这是学极大极小搜索的第二(三)天,昨天因为思路较为混乱,且对评估函数不甚了解,因此自己写出来的AI井字棋宛若ZZ,不过仔细查看了学长的PPT并且钻研了一番,总算对有了比较细致的理解,在参考了一个大神的博客后,我有了新的想法,于是重新打了一遍。

  所谓极大极小搜索,是相对于一个对象而言、考虑两个对象的最佳招法的一种算法。

  假设轮到电脑落子,如何判断落子的最佳位置是一个难题。我们不妨设电脑是第0层(这样好对应深度是0的判定),因为井字棋有9个格,因此最多只能走9步,那么最初深度也就是8,之后每落一子,深度逐次递减。

  如果第0层是电脑,那么偶数层一定是电脑,而奇数层一定是玩家,假设第8层时电脑取胜,那么第七层的玩家一定想要尽可能缩小第八层电脑的取胜优势,而第六层的电脑又想在第七层玩家缩小自己优势的前提下,找到最大优势的落子位置…..一直递减到当前深度CurrentDepth=0为止。

  (1)用CountBlank(POS SaveBlank[STEP])来记录空格点,在空格点的基础之上,依次假设落点,选出估值最高的位置。

  (2)因为从0开始计数,所以初始的递归深度为8,我们希望保存这一步的最佳落子坐标,因此加设全局变量MarkBestPos用来记录,通过打擂台的方法,如果当前决策值为较好者并且递归的深度与当前深度相同,也就是说到了这一次决策,那么就记录下这个坐标。

  如果电脑输赢已定,返回INT_MAX或者 –INT_MAX,否则的话,我们将一个子放下后他所能造成的局势作为评估点,它放下后所能连成的线越多,则证明它的位置越好,那么它的值就越高,考虑行、列、对角线三个方向,将其平均值作为整体估值,同时考虑对手,如果对手下在这个点,那么他会有多大危害,因为一正一负,相加即为局势的好坏,相加越大者局势越佳。

  关于极大极小算法和alpha-beta剪枝可以参考文章的参考资料,这里仅对其进行代码实现。其实这个算法单纯的理解并不容易,下面用代码进行实现。说一下实现这个AI井字棋的思路:简单的来说就是计算机希望估...博文来自:yqtao的博客

  本程序使用alpha-beta算法解决井字棋人机对弈的问题,运行环境要求是jdk1.8。    初始化时,玩家需要选择棋子种类,输入1代表选择X,输入2代表选择O,输入其他的属于错误输入,默认...博文来自:Lawrence的小屋

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

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

  题目:问题描述Alice和Bob正在玩井字棋游戏。井字棋游戏的规则很简单:两人轮流往3*3的棋盘中放棋子,Ali...博文来自:偷吃了老鼠的土豆

  一:实验题目井字棋游戏设计利用面向对象程序设计的知识,通过设计board、player、game类,实现一个具有人人对弈、人机对弈以及机机对弈的井字棋游戏。要求:①对类设置和实现的要求1.封装:需要对...博文来自:Simon_coder的博客

  作者:知乎用户链接:来源:知乎著作权归作者所有。商业转载请联系作者获得授权,非商业转载请...博文来自:zebin的博客

  设计思路:通过接口获取信息来确定颜色,通过set_chess函数来确定落点。对每个点位给出两种颜色棋子的打分,分别存在两个15*15的数组里,数组下标代表点的位置。确定最大值所在数组之后,遍历该数组找...博文来自:black_kyatu的博客

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

  题意:给定一个3*3的一字棋棋盘,判断是否下一步是可赢状态如:1220011021为先手。思路:首先判断下步是先手走还是后手走,即判断1(用a标记)和2(用b标记)的个数。其次判断是否有胜利的可能【于...博文来自:琪露诺

  题目来源:问题描述 试题编号: 201803-4 试题名称: 棋局评估...博文来自:da_kao_la的博客

  Tic-Tac-Toe题意:给你一个3*3的井字棋,已经有了已经下的棋,问下三步之类,alice能不能赢。输入样例:3//三组测试数据.........o//alice执的棋。他先下oxoo.xxxo...博文来自:子灬丶逾

  下文参考博客通常的Nim游戏的定义是这样的:有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻...博文来自:iroy33的博客

  前两天写了关于极大极小搜索的文章,实际还是不够深入,而且有一定偏差。经过这两天的思考之后打算另写一篇来说一下我对极大极小搜索的的进一步理解(以井字棋为例)。在这之前,首先值得注意的一点是,如果说我将初...博文来自:cprimesplus的博客

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

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

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

  中国象棋项目中的极大值,极小值算法以及α-β剪枝技术技术极大值,极小值算法1.问题提出2.代码实现α-β剪枝优化1.代码实现,注意和上面的代码进行比较(其实差别并不大)2.代码分析3.其他可优化点极大...博文来自:wskywskywsky的博客

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

  定义:极大极小值算法(摘自百度百科)Minimax算法又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)。通常以递归形式来实现。=================...博文来自:Bryant_xw Is Growing~~

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

  C语言实现极小极大搜索算法五子棋极小极大算法α-β剪枝棋子生成局面分数评估程序代码本人只是一名大二学生,技术有限,代码比较乱,希望指正,这也是我第一次写博客,排版也不好,见谅。极小极大算法不管是什么棋...博文来自:的博客

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

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

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

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

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

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

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

  不考虑博弈的算法怎么能算是AI呢?max-min极大极小值算法就是考虑了博弈的算法。来看一个简单的例子在这个棋局中,电脑为白旗,白旗走哪一步更好呢,也许使用策略表会告诉你,应该冲4,但是冲4后,玩家就...博文来自:weixin_39788534的博客

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

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

  极小化极大算法(Minimax)    Minimax算法又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法。Minimax算法常用于棋类等由两方较量的游戏和程序,这类程序由两个游戏者轮流...博文来自:FlowShell的专栏

  朋友初入游戏开发,给了我一段代码,要求增加剪枝功能,我做普通应用开发,这种算法接触的不多,最近也挺忙的,看的心慌头大。。希望朋友们帮下忙,谢谢 部分源码: // 极小值极大值搜索函数 static i论坛

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

  2.5图图的表示掌握用邻接表建图最短路径:SPFA(队列实现,每次从队列中去除元素松弛);dijkstra(无负权边,分为两个集合,从未求出最短路径的集合中选出最小的松弛)最小生成树:kruscal(...博文来自:ohazyi(个人网站

  在使用pip安装某个包时,python install xxx,会报拒绝访问的错误,解决方式是修改python安装目录的权限博文来自:AI百科的博客

  用以前以前写过的自定义课表软件 ,Android 自定义View课程表表格 n原生View截图合成分享的图片 n n n n n n n n n 看到的是图片只显示到11节处,下面的没有...博文来自:ShallCheek

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

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

  cprimesplus:我把每行的最大值作为标准,对每行进行标准化的。你说的情况可能是别人把每行的首元素作为标准了吧。

  weixin_45396014:楼主,为啥你这个矩阵标准化和别的不太一样呀?别的里面有一列为1,你这个算出来没有

  cprimesplus:因为要依次为结点赋值,这个创建了n个结点的链表。

  cprimesplus:可能是我写的不太详细,这个算是尾插法,最后返回的是head;head的位置一直保持不变,pend用来记录尾结点的位置,pnew记录新结点,每次连接新结点后,让新结点变成尾结点,也就是p-end = pnew;

  :你这最后返回的是pend吗?这个是头插法吧,如果是pend返回的是最后插入的节点吗?那打印出来的是反的啊

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

相关推荐:

网友评论:

栏目分类

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

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

Top