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

一字棋游戏设计-极大极小搜索

来源:未知 编辑:admin 时间:2019-08-28

  一字棋游戏,包括两个选手。用户可以在一个3*3的棋盘上任意的选择空闲的位置拜访棋子,最早在水平方向上,或者垂直方向上或者对角线方向上形成三子一线所示。这里我们实现的是用户和计算机进行对弈。本程序要实现的是让计算机可以自动的根据当前棋局计算下一步对自己最有利的走步,尽可能的朝着可以让计算机获胜的方向走步。需要采用极大极小搜索算法。

  目前一字棋作为各个高校的人工智能教学的典型范例,在技术方面一般都采用极大极小搜索算法,理论层面比较成熟,有很多资料可以参考。大部分教学资料的一字棋都采用C++语言编写,因为本人对C++语言不是很熟悉,更不熟悉C++语言的界面操作,所以在这里的所有实现都通过C#来实现。在刘峡壁老师编著的《人工智能导论——方法与系统》[1]一书中,对一字棋算法的极大极小搜索有着比较详细的介绍,本系统的实现,主要参照了刘峡壁老师一书中对一字棋算法的介绍。

  在本博弈算法中,采用极大极小搜索[2]方法搜索计算机的下一步走步方法,每一次走步的时候以计算机当前所面对的棋局状态作为根顶点,生成一棵有限深度的博弈子树,然后从该博弈子树的叶结点向上回溯,确定在根顶点处的当前最好的策略,找到一条当前最好行动的边。在生成博弈子树的过程中,计算机己方对应的走步状态的节点称为MAX节点,对应的对手走步的节点成为MIN节点。

  设计的棋局状态的估价函数为,当前棋盘下,在整个棋盘中己方可以三子一线的个数减去对方可以三字一线的个数。假设当前状态下己方三字一线的个数为E(MAX),对方的三字一线的个数为E(MIN),则当前棋局的估价函数为: e= E(MAX)- E(MIN)。对于MAX节点,MAX具有主动权,可以从中选择对自己最好的走步,既估值最大的走步。因此MAX顶点的子节点之间是“或”的关系,MAX顶点的倒退值应该取其子节点估值的极大值;MIN顶点,主动权掌握在MIN手中,为了取胜,MAX需要做最坏的打算,应该考虑到MIN会选择对自己最好的,从而对MAX最差的走步,既估值最小的走步,因此MIN顶点的子节点之间是“与”的关系,MIN顶点的倒推值应该取子节点的最小值。

  关于当前棋局的估值计算,请参考图2。图2是一个棋局状态,通过统计其中的不同棋子可以实现的三点一线的个数来计算当前棋局的估值。从图2中可以看出,叉子的棋子当前可以三子一线,分别为横行第三行,竖列第一列,还有次对角线。圆圈棋子的当前可以三点一线,分别为横行第一行,竖列第三列。然后可以得知,对于计算机(计算机持有叉子棋子),当前棋局的估值为3-2=1。

  在极大极小搜索过程中,首先生成博弈子树,然后计算各个顶点的估值,这一过程中,生成子树和计算顶点的估值是彼此分离的,在本程序中,构造博弈子树采用递归的方法构造,在递归退出的过程中,由子节点的估值计算返回节点的估值。但是极大极小搜索仍然会搜索很多不必要的分支,为了减少搜索的次数,本系统实现了α-β剪枝[3]。

  根据倒推结果,在非叶子节点的向下分支中,剪掉那些目前尚未扩展,但是无论其是否扩展都不会改变非叶子节点倒推值的分支。为了判断分支的扩展是否会影响非叶子节点的倒推结果,需要计算MAX顶点的倒退值的最小辩解,称为α值,以及MIN节点倒推值的最大边界,称为β值。由于MAX顶点的倒推值总是其子节点的最大值,因此如果MAX子节点的估值已经确定小于MAX顶点的α值,则无论该子节点下的为扩展分支情况如何,都不会影响MAX顶点的估值。这样就不必搜索这个子节点一下的所有分支。同理,如果MIN节点的子节点的估值已经确定大于β值,则不必再搜索该顶点下的为扩展分析,可以进行剪枝。

  在图4中,建立的搜索子树的起始点为S0,从S0开始搜索所有的可以的走步。S0为MAX节点,然后对应的下一层为MIN节点,然后MAX节点与MIN节点相互交错。在最后一层为MAX节点,每个节点的估值已经写在这个节点的下面。F节点为MIN节点,F节点的估值应该去子节点的最小值,F的子节点中最小值为K的估值4,所以F的估值为4。这样C节点为MAX节点,应该取子节点估值的最大值。G节点取子节点的最小值,G节点的子节点N的估值为1,所以不论G的其他的子节点的估值为何,G节点的估值都会小于等于1,这样,C节点取子节点估值的最大值,已经知道了G节点的估值肯定小于等于1,所以无论G节点的其他分支如何扩展,都不会影响C节点的现在的估值。所以这样就可以省去了G节点的其他的分支的扩展。其他的节点的剪枝同样的道理。

  由于一直没有想出如何用适合进化算法计算表示棋盘状态的数据结构,所以在采用进化算法[4-6]计算走步的时候,仍然采用了上面设计的棋盘状态表示。进化算法简单的采用了选择突变两个操作,没有选择交叉操作的原因也是因为没有合理的数据结构进行交叉运算。首先在当前的棋局状态下随机的生成一些走步,然后对这些走步以一定的概率进行突变,最后进行估值,选择估值最好的走步。

  在没有剪枝的计算机搜索走步的过程中,根据搜索的深度,需要搜索的走步的数量非常多。第一次计算机搜索了400步,第二次计算机搜索了156步,第三次走步计算机搜索了40步。一个典型的走步过程如图5-7所示。从图7中可以看到计算机获胜。

  带有α-β剪枝的搜索结果中,可以明显的看到搜索的次数很显著的减少了。图8-11展示了一个带有剪枝过程的搜索结果。在图11中可以看到计算机获胜。然而存在的问题是,添加α-β剪枝算法的极大极小搜索的效果不如上面直接的极大极小算法效果好,因为有一些棋局找到的不是最好的走步,这个应该和剪枝算法没有什么关系,而是程序写的不合理。

  由于一直没有想出如何用适合进化算法计算表示棋盘状态的数据结构,所以在采用进化算法计算走步的时候,仍然采用了上面设计的棋盘状态表示。进化算法简单的采用了选择突变两个操作,没有选择交叉操作的原因也是因为没有合理的数据结构进行交叉运算。首先在当前的棋局状态下随机的生成一些走步,然后对这些走步以一定的概率进行突变,最后进行估值,选择估值最好的走步。

  因为本程序中并没有写出进化算法的精华,也没有实现真正的进化算法,所以进化算法的效果非常的差。图12-14展示了进化算法的搜索。从这些图中可以看出,进化算法的搜索,往往不能找到最优解。

  通过以上实验结果,可以看出,极大极小搜索可以找到当前状态下的最优解之一,如果最优解同时有多个,则简单的选择第一个最优解。然而在极大极小的搜索过程中,可能会搜索很多无效的分支,这样就可以通过α-β剪枝方法剪去不必要的搜索分支,加快搜索速度。在本程序中,剪枝后与不剪枝的搜索速度没有什么差别,因为本程序中搜索的深度只有3层,而且棋盘非常小。如果是正规的五子棋盘或者象棋棋盘,那么剪枝就是非常有必要的了。否则搜索一个合适的走步的时间复杂度会非常高,而且也会带来空间的消耗,剪枝的时候,就减少了不必要分支的搜索,同时也就不用为这些不去搜索的分支建立搜索树中的节点,加快了搜索速度。进化算法本来可以进行搜索的优化,但是因为一直没有找到合理的用于进化算法的数据表现形式,所以这里的进化算法并没有展示出进化算的精髓,没有完全的体现进化算法的真正意义。

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

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

  零和博弈概念二人利益对立完备信息博弈过程,在我们分析表达中就是对一个过程进行按规定双方交替操作,每次操作即搜索时选择对自己有利的情况(获益选最大,损失选最小),借助的数据结构自然是树。博弈树中每一层是...博文来自:渣渣

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

  一字棋指的是:在一个九宫格内率先连成三个字的取胜首先,基于前面决策树的讲解博弈的棋类游戏等等只要找到合适的估值函数都可以使用博弈树来实现下面我们来使用博弈树完成一字棋的算法。根据前面的算法思想我们算法...博文来自:viafcccy的博客

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

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

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

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

  TSP_旅行商问题-贪心算法TSP_旅行商问题-贪心算法TSP_旅行商问题-模拟退火算法TSP_旅行商问题-遗传算法TSP_旅行商问题-基本蚁群算法问题描述寻找最短路径使得其经过所有城市测试数据集:t...博文来自:晨起尘又落

  题意:给定一个n个顶点组成的带权有向图的距离矩阵d(I,j)(INF表示没有边)。要求从顶点0出发,经过每个顶点恰好一次后再次回到顶点0.问所经过的边的总权重的最小值是多少?假设现在已经访问过的顶点的...博文来自:肘子的博客

  问题描述:旅行商问题(TravelingSalesmanProblem,TSP)是旅行商要到若干个城市旅行,各城市之间的费用是已知的,为了节省费用,旅行商决定从所在城市出发,到每个城市旅行一次后返回初...博文来自:轻锋的专栏

  题意:有一个推销员,要到n个城市推销商品,他要找出一个包含所有n个城市的具有最短路程的环路。(最后回到原来的城市)示例:从城市1出发经过所有城市后回到城市1,要使总路程最短。 代码:/**@回溯-旅行...博文来自:lfbcsdn博客

  前言我先啰嗦一下:不是很喜欢写计算智能的算法,因为一个算法就要写好久。前前后后将近有两天的时间。好啦,现在进入正题。巡回旅行商问题(TSP)是一个组合优化方面的问题,已经成为测试组合优化新算法的标准问...博文来自:Happy祥子的博客

  1.问题描述      TSP问题是指旅行家要旅行n个城市然后回到出发城市,要求各个城市经历且仅经历一次,并要求所走的路程最短。2.算法思想  贪心法求解TSP问题有两种贪心策略。     1)最近邻...博文来自:shujian_tianya的博客

  问题描述:从一个起点出发,可以重复经过其他点(若干个)多次,图为有向图且已有路径矩阵(有多个环),求经过所有点后回到起点的最短路径。论坛

  一、TSP问题TSP问题(TravellingSalesmanProblem)即旅行商问题,又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要...博文来自:旋风的技术

  TSP问题即旅行商问题,经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。应如何选择行进路线,以使总的行程最短。从图论的角度来看,该...博文来自:syddf

  给出一个n个顶点的带权有向图的距离矩阵d(i,j)(INF表示没有边)。要求从顶点0出发,经过每一个顶点恰好一次后再回到0.问最小权重。#include#include#includeusingnam...博文来自:zht的专栏

  转载声明:原文把蚁群解决旅行商问题写的很清楚,只不过本人认为原文中有一些小错误,特此更改(文中红色加粗字体为改正处),代码中出现的一些算法的小问题也进行了更正(比如代码中的贪心算法),代码也附在下面,...博文来自:Tan_HandSome的博客

  TSP问题(TravelingSalesmanProblem,旅行商问题),由威廉哈密顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出。问题描述如下:有若干个城市,任何两个城市之间的距离...博文来自:larry233的博客

  1. 蛮力法:基本思想:找出所有可能的旅行路线,即依次考查图中所有顶点的全排列,从中选择路径长度最短的哈密顿回路(也称简单回路).时间复杂性:Ω(n!)2. 动态规划法:伪代码:输入:图的代价矩阵ar...博文来自:wwt的博客

  问题描述:给定一个n个顶点组成的带权有向图的距离矩阵d(i,j)。要求从顶点0恰好经过每个顶点一次后再回到顶点0的权重和最小值。题解详见《挑战程序设计竞赛》119页代码:intn;intd[Max_n...博文来自:ó

  旅行商问题(TSP)旅行商问题是一个经典的组合优化问题。经典的TSP问题可以描述为:一个商品推销员要去若干个城市进行商品推销,该推销员从一个城市出发,需要经过所有城市,回到出发地。应如何选择行进路线,...博文来自:喵喵喵

  旅行包问题(TSP)---蛮力法(深度优先遍历算法DFS)问题描述蛮力法(深度优先遍历算法DFS)问题描述TSP问题(TravelingSalesmanProblem,旅行商问题),由威廉哈密顿爵士和...博文来自:私忆一秒钟的博客

  解题思路主要有两部分:   第一部分:i为当前节点(城市),S为还没有遍历的节点(城市集合),表示从第i个节点起,经历S集合中所有的点,到达终点的最短路径长度。因此有:   第二部分,回溯,找到最优的...博文来自:yg838457845的博客

  本文基于蛮力法(此处采用深度优先遍历,DFS)解决旅行商问题。通过遍历出所有满足条件的路径情况,并保持更新最优解,直到所有情况都遍历完,得到全局最优解。但是,使用蛮力法需要遍历的城市个数高达city_...博文来自:Houchaoqun_XMU的博客

  TSP_旅行商问题-基本蚁群算法旅行商系列算法TSP_旅行商问题-贪心算法TSP_旅行商问题-模拟退火算法TSP_旅行商问题-遗传算法TSP_旅行商问题-基本蚁群算法基于基本蚁群算法解决连续优化问题问...博文来自:晨起尘又落

  问题描述行商问题(TravellingSalesmanProblem,简记TSP,亦称货郎担问题):设有n个城市和距离矩阵,其中表示城市i到城市j的距离,i,j=1,2…n,则问题是要找出遍访每个城市...博文来自:嘿芝麻的树洞

  旅行商问题,即TSP问题(TravelingSalesmanProblem)是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最...博文来自:Geoooo的博客

  zerolulu:谢谢楼主答疑,学习.NET路上需要有人奉献经验和知识。

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

相关推荐:

网友评论:

栏目分类

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

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

Top