精华内容
下载资源
问答
  • 五子棋的博弈树实现
    2021-03-13 08:42:33

    五子棋是一种受大众广泛喜爱的游戏,其规则简单,变化多端,非常富有趣味性和消遣性。这里设计和实现了一个人机对下的五子棋程序,采用了博弈树的方法,应用了剪枝和最大最小树原理进行搜索发现最好的下子位置。介绍五子棋程序的数据结构、评分规则、胜负判断方法和搜索算法过程。

    一、相关的数据结构

    关于盘面情况的表示,以链表形式表示当前盘面的情况,目的是可以允许用户进行悔棋、回退等操作。

    CList   StepList;

    其中Step结构的表示为:

    struct   Step

    {

    int     m;   //m,n表示两个坐标值

    int     n;

    char   side;   //side表示下子方

    };

    以数组形式保存当前盘面的情况,

    目的是为了在显示当前盘面情况时使用:

    char   FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];

    其中FIVE_MAX_LINE表示盘面最大的行数。

    同时由于需要在递归搜索的过程中考虑时间和空间有效性,只找出就当前情况来说相对比较好的几个盘面,而不是对所有的可下子的位置都进行搜索,这里用变量CountList来表示当前搜索中可以选择的所有新的盘面情况对象的集合:

    CList   CountList;

    其中类CBoardSituiton为:

    class   CBoardSituation

    {

    CList       StepList;   //每一步的列表

    char   FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];

    struct   Step   machineStep;           //机器所下的那一步

    double   value;     //该种盘面状态所得到的分数

    }

    二、评分规则

    对于下子的重要性评分,需要从六个位置来考虑当前棋局的情况,分别为:-,|,/,\,//,\\

    实际上需要考虑在这六个位置上某一方所形成的子的布局的情况,对于在还没有子的地方落子以后的当前局面的评分,主要是为了说明在这个地方下子的重要性程度,设定了一个简单的规则来表示当前棋面对机器方的分数。

    基本的规则如下:

    判断是否能成5,   如果是机器方的话给予100000分,如果是人方的话给予-100000   分;

    判断是否能成活4或者是双死4或者是死4活3,如果是机器方的话给予10000分,如果是人方的话给予-10000分;

    判断是否已成双活3,如果是机器方的话给予5000分,如果是人方的话给予-5000   分;

    判断是否成死3活3,如果是机器方的话给予1000分,如果是人方的话给予-1000   分;

    判断是否能成死4,如果是机器方的话给予500分,如果是人方的话给予-500分;

    判断是否能成单活3,如果是机器方的话给予200分,如果是人方的话给予-200分;

    判断是否已成双活2,如果是机器方的话给予100分,如果是人方的话给予-100分;

    判断是否能成死3,如果是机器方的话给予50分,如果是人方的话给予-50分;

    判断是否能成双活2,如果是机器方的话给予10分,如果是人方的话给予-10分;

    判断是否能成活2,如果是机器方的话给予5分,如果是人方的话给予-5分;

    判断是否能成死2,如果是机器方的话给予3分,如果是人方的话给予-3分。

    实际上对当前的局面按照上面的规则的顺序进行比较,如果满足某一条规则的话,就给该局面打分并保存,然后退出规则的匹配。注意这里的规则是根据一般的下棋规律的一个总结,在实际运行的时候,用户可以添加规则和对评分机制加以修正。

    三、胜负判断

    实际上,是根据当前最后一个落子的情况来判断胜负的。实际上需要从四个位置判断,以该子为出发点的水平,竖直和两条分别为   45度角和135度角的线,目的是看在这四个方向是否最后落子的一方构成连续五个的棋子,如果是的话,就表示该盘棋局已经分出胜负。具体见下面的图示:

    四、搜索算法实现描述

    注意下面的核心的算法中的变量currentBoardSituation,表示当前机器最新的盘面情况,   CountList表示第一层子节点可以选择的较好的盘面的集合。核心的算法如下:

    void   MainDealFunction()

    {

    value=-MAXINT;   //对初始根节点的value赋值

    CalSeveralGoodPlace(currentBoardSituation,CountList);

    //该函数是根据当前的盘面情况来比较得到比较好的可以考虑的几个盘面的情况,可以根据实际的得分情况选取分数比较高的几个盘面,也就是说在第一层节点选择的时候采用贪婪算法,直接找出相对分数比较高的几个形成第一层节点,目的是为了提高搜索速度和防止堆栈溢出。

    pos=CountList.GetHeadPosition();

    CBoardSituation*   pBoard;

    for(i=0;ivalue=Search(pBoard,min,value,0);

    Value=Select(value,pBoard->value,max);

    //取value和pBoard->value中大的赋给根节点

    }

    for(i=0;ivalue)

    //找出那一个得到最高分的盘面

    {

    currentBoardSituation=pBoard;

    PlayerMode=min;   //当前下子方改为人

    Break;

    }

    }

    其中对于Search函数的表示如下:实际上核心的算法是一个剪枝过程,其中在这个搜索过程中相关的四个参数为:(1)当前棋局情况;(2)当前的下子方,可以是机器(max)或者是人(min);(3)父节点的值oldValue;(4)当前的搜索深度depth。

    double   Search(CBoardSituation&

    board,int   mode,double   oldvalue,int   depth)

    {

    CList       m_DeepList;

    if(deptholdvalue))== TRUE)

    {

    if(mode==max)

    value=select(value,search(successor

    Board,min,value,depth+1),max);

    else

    value=select(value,search(successor

    Board,max,value,depth+1),min);

    }

    return   value;

    }

    else

    {

    if   (   goal(board)<>0)

    //这里goal(board)<>0表示已经可以分出胜负

    return   goal(board);

    else

    return   evlation(board);

    }

    }

    注意这里的goal(board)函数是用来判断当前盘面是否可以分出胜负,而evlation(board)是对当前的盘面从机器的角度进行打分。

    下面是Select函数的介绍,这个函数的主要目的是根据   PlayerMode情况,即是机器还是用户来返回节点的应有的值。

    double   Select(double   a,double   b,int   mode)

    {

    if(a>b   &&   mode==max)||   (a

    return   a;

    else

    return   b;

    }

    五、小结

    在Windows操作系统下,用VC++实现了这个人机对战的五子棋程序。和国内许多只是采用规则或者只是采用简单递归而没有剪枝的那些程序相比,在智力上和时间有效性上都要好于这些程序。同时所讨论的方法和设计过程为用户设计其他的游戏(如象棋和围棋等)提供了一个参考

    更多相关内容
  • 博弈树搜索算法

    2018-09-04 16:14:35
    实现人工智能博弈系统的基本思想就是博弈树搜索,本文详细介绍了几种著名的搜索算法,包括极大极小值、负极大值、alpha-beta剪枝等。
  • 基于博弈树的井字棋的实现
  • 博弈树(树的c实现)

    2015-12-22 20:26:15
    下棋属于一种博弈游戏,博弈过程可以用树(博弈树)来表示。假设游戏由两个人( A 和 B )玩,开始由某个人从根结点开始走,两个人轮流走棋,每次只能走一步, 下一步棋只能选择当前结点的孩子结点,谁先走到叶子...
  • 基于alpha-beta剪枝博弈树算法实现的一字棋游戏
  • 人工智能与信息社会 基于决策树和搜索的智能系统博弈树 陈斌北京大学gischen@ 完全信息 游戏的状态信息对所有玩家都是完全可见的 井字棋黑白棋象棋围棋 北京大学地球与空间科学学院/ 陈斌/2018 不完全信息 每个玩家...
  • 博弈树

    万次阅读 多人点赞 2019-10-13 16:28:32
    本文为个人学习博弈树的过程,非常感谢张少宏老师课上精彩的讲解! 博弈树的搜索 博弈树定义: 一类特殊的与或图 (本次讨论的博弈树都是“与或图”) 应用范围: 下棋、故障诊断、风险投资 基本搜索策略: 极小极大...

    博弈树的搜索

    博弈树定义:
    一类特殊的与或图
    (本次讨论的博弈树都是“与或图”)

    应用范围:
    下棋、故障诊断、风险投资

    基本搜索策略:
    极小极大搜索(min-max)

    优化的搜索方法:
    α-β剪枝搜索
    (剪枝)
    (搜索与生成同时进行)

    了解背景:

    (完全博弈问题)博弈问题

    特点:
    双人对弈:轮流下,一人走一步。
    信息完备:双方看到的信息一样
    零和:双方利益冲突,对一方有利则对另一方不利。一般对节点N取一个估价函数f(N),一共两类节点:
    ——叫Max的极大节点追求最大化,有选择时肯定选值最大的;
    ——叫Min的极小节点追求最小化,有选择时肯定选值最小的。

    例子1:下棋

    两位选手对垒,轮流走步。这时每一方不仅知道对方过去已经走过的棋步,而且还能估计出对方未来可能的走步。对弈的结果是一方赢(另一方则输),或者双方和局。如象棋,围棋,五子棋,…

    例子2:选包拿钱

    假设有两个钱包,每个钱包都放2张钱,第一个放了0.5元和100元,第二个放了2元和10元, Max和Min两个人是仇敌。现在Max负责挑出一个包,Min负责从Max选的包里选一张小的钱给Max。
    因为Max想让自己的钱越多越好而Min不想让Max钱多,所以Min会选一张相对最小的钱给Max。也即,Max想获得最大利益,而Min只是想承受最小的对手变强程度。在这种情况下Max应该选择包2,Min会给他2元。如果Max选择了包1 ,Min只会给他选0.5元。
    图1
    完全信息博弈抽象出任务原型:
    给出(或逐步生成)一个博弈树,求出在指定搜索深度(层数)下的最佳路径和相应估价分数。比如下象棋,Max先走一步,Min再走一步,再轮到Max走,这时Max遇到的各个局面可以估分,再倒推回去Max的第一步应该选择走哪步最佳
    基本搜索策略:极小极大搜索(min-max)
    为了提高极小极大搜索方法的速度,所以采用剪枝,最主要的是α-β剪枝

    不完全信息博弈情况:
    大部分纸牌游戏(如斗地主、拖拉机)
    大部分即时策略游戏(如红警、星际、帝国)
    ——需要探路(即信息不对等)
    ——游戏还受手速(APM)影响

    但是博弈问题常常不能简单穷举,以中国相亲为例:
    ——一盘棋平均走50步,总状态数约为10的161次方。假如一毫微秒走一步,约需10的145次方。
    ——结论:不可能穷举

    极小极大搜索方法:

    极小极大搜索方法是博弈树搜索的基本方法 。
    首先假定,有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时,表示棋局对我方有利,对对方不利。当评价函数小于0时,表示棋局对我方不利,对对方有利。
    方法过程:
    1、当轮到我方走棋时,首先按照一定的搜索深度生成出给定深度d以内的所有状态,计算所有叶节点的评价函数值。然后从d-1层节点开始逆向计算:
    2、对于我方要走的节点(用MAX标记,称为极大节点)取其子节点中的最大值为该节点的值(因为我方总是选择对我方有利的棋)。
    3、对于对方要走的节点(用MIN标记,称为极小节点)取其子节点中的最小值为该节点的值(对方总是选择对我方不利的棋)。
    4、一直到计算出根节点的值为止。获得根节点取值的那一分枝,即为所选择的最佳走步。
    图2 极小极大搜索
    因此,极小极大过程是一种假定对手每次回应都正确的情况下,如何从中找出对我方最有利的走步的搜索方法。
    值得注意的是,不管设定的搜索深度是多少层,经过一次搜索以后,只决定了我方一步棋的走法。等到对方回应一步棋之后,需要在新的棋局下重新进行搜索,来决定下一步棋如何走。

    对于静态估计函数f(x)
    一般规定有利于MAX的势态,f§取正值,有利于MIN的势态,f§取负值,势均力敌的势态,f§取0值。若f§=+∞,则表示MAX赢,若f§=-∞,则表示MIN赢。下面的讨论规定:顶节点深度d=0,MAX代表程序方,MIN代表对手方,MAX先走。
    当用端节点的静态估计函数f(p)求倒推值时,两位选手应采取不同的策略,从下往上逐层交替使用极小和极大的选值方法,故称极小极大过程。

    个人总结:
    极小极大搜索——从一个原始状态节点,根据估值函数,对后面出现的可能状态进行估值,在一定深度内通过一个路径选择方式(max层节点从子节点选择最大的值,min层节点从子节点总选择最小的值),选择出最优的路径(该路径为到达最优值所在节点路径)。

    α-β剪枝搜索过程:

    能否在搜索深度不变的情况下,利用已有的搜索信息减少生成的节点数呢?
    MIN-MAX过程是把搜索树的生成和格局估值这两个过程分开来进行,即先生成全部搜索树,然后再进行端节点静态估值和倒推值计算,这显然会导致低效率。
    实际上把生成和倒推估值结合起来进行,再根据一定的条件判定,有可能尽早修剪掉一些无用的分枝,同样可获得类似的效果,这就是α-β过程的基本思想。

    注意: α-β剪枝搜索和生成扩展子节点是同步的。其得到的最优解结果与Min-Max过程一致
    Min-Max过程和α-β剪枝搜索的结果都受生成/搜索策略顺序有关(比如选择广度优先或者深度优先,结果可能不一样)

    简单例子:

    图3 极小极大搜索方法
    由图3可知,对于min-max搜索,得到的最优路径为A1-A11。max得分为3

    图4 α-β剪枝方法
    而图4是通过α-β剪枝方法得到的,同样得到最优路径为A1-A11。max得分为3。

    例子2:

    对该搜索树进行左边深度优先α-β剪枝搜索

    图5 例子2
    左边为原搜索树,右边为α-β剪枝搜索
    ——极小值节点I的N子树被剪枝了( α剪枝)
    ——极大值节点G的L子树被剪枝了(β剪枝)

    α-β搜索方法定义:
    Max节点的下界为α,即Max确保能获得的最小得益。初始化为-inf。
    Min节点的上界为β,即Min付出的上界代价保障。初始化为+inf。
    对于节点N的估计函数值f(N),初始化α =-inf ≤ f(N) ≤ β=+inf
    若 α ≤ β则N有解。若 α > β 则N无解(为什么无解?因为对于上一层,min/max层不会选择该路径的节点了,故而可以放弃搜索),该节点N的其他未访问子树会被剪枝
    如图中节点I,从左子树DBE可以获得下界α=3,并传送到右边的极小节点I,此时I的子节点M给了个上界β=1。所以α=3> β=1,下界α大于上界β ,无解。

    在这里插入图片描述
    理解:
    极大节点N,从一个子树获得的α值和β值,可以传送给其子节点
    极大节点N 的α值只可能越改越大,否则极大节点N可以还选择原有α值
    极小节点M的β值只可能越改越小,否则极小节点M可以还选择原有β值
    从单边子节点往父节点推,极大值父节点只更改α值,极小值父节点只更改β值。

    在这里插入图片描述
    α剪枝(发生在极小层节点,如图中的节点I)
    (1)α剪枝:若任一极小值层节点的β值小于或等于它任一先辈极大值层节点的α值,即α(先辈层)≥β(后继层),则可中止该极小值层中这个MIN节点以下的搜索过程。这个MIN节点最终的倒推值就确定为这个β值。
    从一个子树获得的极大节点的α值,可以传送给该节点的其他子树,从而选择α剪枝机会(课本说法,和“先辈”节点α值比较,是和所有先辈节点比较,而不是仅仅和父节点比较)。
    从单边子节点往父节点推,极大值父节点只更改α值,极小值父节点只更改β值

    注意看极小节点I:
    极大节点A从左子树获得α值3,从而可以把α=3传播给右子树,在极小节点I点由于子节点M值为1从而可以确认β=1,此时α=3> β=1,从而I的其他节点可以被α剪枝, I点的β=1。

    在这里插入图片描述
    β剪枝(发生在极大层节点,如图中的节点G)
    (2)β剪枝:若任一极大值层节点的α值大于或等于它任一先辈极小值层节点的β值,即α(后继层)≥β(先辈层),则可以中止该极大值层中这个MAX节点以下的搜索过程。这个MAX节点的最终倒推值就确定为这个α值。
    从一个子树获得的极小节点的β值,可以传送给该节点的其他子节点,从而选择β剪枝机会(课本说法,和“先辈”节点β值比较,是和所有先辈节点比较,而不是仅仅和父节点比较)。
    从单边子节点往父节点推,极大值父节点只更改α值,极小值父节点只更改β值

    注意看极大节点G:
    极小节点C通过部分计算(A左子树和F子树)获得α=3和β=5 ,从而可以把α=3和β=5传播给极大节点G,在极大节点G点由于子节点K值为6从而可以确认α=6 ,从而G点此时α=6> β=5,从而G的其他节点可以被β剪枝,G点的α=6 。

    祭出终极例子3:
    在这里插入图片描述

    α-β搜索方法总结:

    1、α-β剪枝后选得的最好优先走步,其结果与不剪枝的MINIMAX方法所得完全相同,因而α-β过程具有较高的效率。
    2、α-β剪枝最理想的情况是,Min节点先扩展最低估值子节点,Max节点先扩展最大估值节点。(这个策略可以用于启发式α-β剪枝搜索)

    思考问题:为什么所有α-β剪枝搜索例子都是用深度优先策略?
    因为深度优先更有机会发生剪枝。

    展开全文
  • 人工智能下五子棋(基于博弈树极大极小值alpha-beta剪枝搜索算法),代码解析链接参见网址:https://blog.csdn.net/m0_38106923/article/details/93347117
  • 人工智能实验二-博弈树井字棋-实验报告:2.该文档所得收入(下载 内容 预览三)归上传者、原创者。 3.登录后可充值,立即自动返金币,充值渠道很便利 同意并开始全文预览 人工智能实验二 博弈树井...|下载前务必先预览,...
  • 通过对机器博弈主要搜索算法的深入分析和实践,提出了在博弈树一层结点中以广度优先方式,运用接力式空窗探测技术反复淘汰到只剩一个结点的新搜索方法.该方法面向应用,搜索过程易控,理论上的最小搜索极限小于极小...
  • 一篇实用的博弈树并行搜索算法论文,以中国象棋AI为例描述了基于OpenMP平台和NegaScout(PVS)算法的博弈树并行搜索算法,并以中国象棋为例做了实验。
  • 除了基于Alpha-Beta算法的博弈树并行搜索算法外,还有其他的博弈树搜索算法.现简要介绍如下.7.1SSS*算法及其并行化Alpha-Beta算法是一种基于Min-Max方法的固定深度(fixed-depth)搜索算法.说它是固定深度的搜索算法,是...

    除了基于Alpha-Beta算法的博弈树并行搜索算法外,还有其他的博弈树搜索算法.现简要介绍如下.

    7.1SSS*算法及其并行化

    Alpha-Beta算法是一种基于Min-Max方法的固定深度(fixed-depth)搜索算法.说它是固定深度的搜索算法,是因为对每个结点,它依序从左到右搜索其所有子结点.与Alpha-Beta算法相同的是,SSS*算法[19](或者其对称算法DUAL*)也基于Min-Max方法,但与前者不同的是,它使用最佳优先(best-first)策略.即,SSS*算法不以结点在博弈树中所处的位置为标准,而按照它们前途有望的(promising)程度,由高至低搜素结点.

    为了实现最佳优先策略,算法维护一个OPEN队列(OPEN list).OPEN队列的每项对应着一个结点,用的形式组织.其中n代表博弈树中的一个结点,s是一个状态标识,可能的取值是LIVE或SOLVED,h被称为merit,是一个实数值.一个使用状态空间搜索(State Space Search)概念描述的SSS*算法如下[20]:

    1. 将插入OPEN队列中.

    2. 将OPEN队列中h最大的p = 取出.由于OPEN队列是h的非降序列,所以p为队列的第一项.

    3. 如果n = root且s = SOLVED 那么p就是目标状态,此时h就是博弈树的最大最小值,否则继续.

    4. 通过执行状态空间操作Г,扩充p状态,将所有的输出状态Г(p)按序插入OPEN队列中.如果可能,清除OPEN队列中的多于状态.

    5. 跳转到2.

    操作Г的情况

    输入状态满足条件

    操作Г产生的新的状态

    不操作

    s = SOLVED

    n = ROOT

    达到最终状态,算法退出,博弈值为h

    1

    s = SOLVED

    n ≠ ROOT

    type(n) = MIN

    将插入OPEN队列中,清除OPEN队列中满足m是k的祖先的

    2

    s = SOLVED

    n ≠ ROOT

    type(n) = MAX

    next(n) = NIL

    将插入OPEN队列中

    3

    s = SOLVED

    n ≠ ROOT

    type(n) = MAX

    next(n) = NIL

    将插入OPEN队列中

    4

    s = LIVE

    first(n) = NIL

    将插在所有merit值次小的项的前面.其中f(n)是结点n的最大最小值.

    5

    s = LIVE

    first(n) ≠ NIL

    type(first(n)) = MAX

    将插在OPEN队列最前面

    6

    s = LIVE

    first(n) ≠ NIL

    type(first(n)) = MIN

    将n修改为first(n)

    执行下列操作,直到n = NIL

    1. 将插在OPEN队列最前面

    2. 将n修改为next(n)

    的状态空间操作Г

    Stockman证明了SSS*算法在某种意义上比Alpha-Beta算法好:它绝不会比Alpha-Beta搜索更多的叶结点.当两个算法搜索同一个良序的博弈树时,它们搜索的叶结点相同,但是平均来看,SSS*算法搜搜的叶结点数比Alpha-Beta算法少.虽然如此,SSS*算法存在着一些问题阻碍了它的实用性:

    1. 算法太过复杂,使人难以理解.

    2. OPEN队列占用的空间太大,其大小随着博弈树深度的增加而指数增长.

    3. 为了维护OPEN队列的有序性,其插入和删除操作花费的时间开销很大.

    在基本SSS*算法的基础上,许多改进算法也提出来,例如MT-SSS*算法[10].并行的SSS*算法也被提出来,例如HYBRID算法[21],PARSSS*算法[22]等.这里不做介绍.

    7.2ER算法及其并行化

    ER(Evaluate-Refute)算法[23]的基本思想是:在评估完一些强制性的工作(mandatorywork)之后,尝试驳斥博弈树中的其他结点.在这一点上它与MWF算法的基本思想有点类似,但是两者又有本质的不同.

    ER算法[24]将结点分为E结点(e-node)和R结点(r-node).E结点将会被完全地搜索,而R结点将会进行部分搜索,得到估值后尝试剪除,这个尝试剪枝的过程称为驳斥(refutation).E结点的所有子结点将会被搜索,而R结点只会进行较少的子结点的搜索,少到只有一个子结点被搜索.因此,E结点比R结点开销大(morecostly).

    博弈树的每个内部结点只有一个子结点是E结点,称这个结点为该父结点的E子结点.选择任意一个子结点作为E子结点都是允许的,但是为了性能的优化,选择结点n的E子结点的方法如下: ER算法搜索结点的长孙结点们(elder grandchildren),将博弈值最大的长孙结点n''的父结点n'作为n的E子结点.其中,长孙结点即为n的子结点们各自的第一个子结点(eldest child).当得到了结点n的E结点n'之后,算法首先搜索n'的所有子结点(n''除外,因为它的博弈值已经得到了).n剩下的子结点则会按序进行驳斥(refute).

    在ER算法的并行实现时,长孙结点可以被同时搜索,因为这些是强制性的工作.又由于这些长孙结点本身又是E结点,所以他们的长孙结点们又也可以递归地并行搜索.如果ER算法只在进行强制性的工作时并行完成,那么E结点的兄弟结点就需要串行地进行驳斥了.但是为了防止处理器的空闲,ER算法还引入了下面两个方法提高并行度:

    1. 并行驳斥.当E子结点n的E子结点n'已经搜索完成时,那么n''的兄弟结点可以并行地进行驳斥.

    2. 多个E子结点.当E子结点n的E子结点n'已经搜索完成时,在n的子结点中选择次佳的子结点作为n的第二个E子结点.如果n'被证明不是n的最佳子结点(即n的其他结点不能被立即驳斥),那么就用第二个E子结点对其他子结点进行剪枝.

    从某种意义上说,ER算法比Alpha-Beta算法的搜索效率低,因为它可能会错过一些深的剪枝(deep cutoff).另一方面,在ER算法上使用迭代深入和最小窗口的方法的效果如何,还需要进一步的实验测试[12].

    本文章欢迎转载,请保留原始博客链接http://blog.csdn.net/fsdev/article

    --------------------

    [1]    Valavan Manohararajah(2001). Parallel Alpha-Beta Search on SharedMemory Multiprocessors. Master’s thesis, Graduate Department of Electrical andComputer Engineering, University of Toronto, Canada.

    [2]    A. Newell and H.A. Simon (1972). Human Problem Solving.Prentice-Hall, 1972.

    [3]    Stuart Russell and Prter Norvig (1995). Artificial Intelligence, AModern Approach. Prentice-Hall, Egnlewood Cliffs, 1995.

    [4]    Knuth, D.E. and Moore, R.W. (1975). An Analysis of Alpha-Beta Pruning.Artificial Intelligence, 6:293–326.

    [5]    Hopp, Holger and Sanders, Peter (1995). Parallel Game Tree Search onSIMD Machines. IRREGULAR '95: Proceedings of the Second International Workshopon Parallel Algorithms for Irregularly Structured Problems. 349-361.

    [6]    Marsland, T.A. and Campbell, M.S. (1982). Parallel Search ofStrongly Ordered Game Trees. ACM Computing Surveys, Vol. 14, No. 4, pp.533-551. ISSN 0360-0300.

    [7]    Schaeffer J.(1989). The History Heuristic and Alpha-Beta SearchEnhancements in Practice. IEEE Transactions on Pattern Analysis and MachineIntelligence. Vol. PAMI-11, No.11, pp. 1203-1212.

    [8]    Marsland, T.A. (1986). A Review of Game-Tree Pruning. ICCA Journal,Vol. 9, No. 1, pp. 3-19. ISSN 0920-234X.

    [9]    Korf , R.E. (1985). Depth-first Iterative-deepening Search: AnOptimal Admissible Tree Search. Artificial Intelligence, 27(1), 97-109.

    [10]    Aske Plaat, Jonathan Schaeffer,Wim Pijls, and Arie de Bruin(1995). Best-First and Depth-First Minimax Searchin Practice. In Proceedings of Computing Science in the Netherlands 1995,Utrecht, the Netherlands, November 27-28, 1995, pages 182-193.

    [11]    Brockington, M. G. andSchaeffer, J. (1996). APHID Game-Tree Search. Presented at Advances in ComputerChess 8, Maastricht.

    [12]    Brockington, M.G. (1996). ATaxonomy of Parallel Game-Tree Searching Algorithms. ICCA Journal, Vol. 19, No.3, pp. 162-174.

    [13]    Baudet G. M.(1978). The Designand Analysis of Algorithms for Asynchronous Multiprocessors. Carnegie MellonUniversity, Pittsburgh, PA, Available as Tech. Rep. CMU-CS-78-116.

    [14]    Akl, S.G., Barnard, D.T. andDoran, R.J.(1982). Design Analysis and Implementation of a Parallel Tree SearchAlgorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.PAMI-4, No.2, pp. 192-203.

    [15]    Feldmann, R., Mysliwietz, P.and Monien. B (1993). Game Tree Search on a Massively Parallel System. InAdvances in Computer Chess 7, 1993. (The conference was held in June1993, butthe proceedings have not published as of August 1993.)

    [16]    Kuszmaul, B.C. (1994).Synchronized MIMD Computing. Ph.D thesis, Massachusetts Institute ofTechnology, Cambridge MA.

    [17]    NewBorn M.(1988). UnsynchronizedIteratively Deepening Parallel Alpha-Beta Search. IEEE Transactions on PatternAnalysis and Machine Intelligence, Vol. PAMI-10, No.5, pp. 687-694.

    [18]    Weill, J-C. (1996). The ABDADADistributed Minimax-Search Algorithm. ICCA Journal, Vol.19, No.1, pp. 3-16.

    [19]    Mark Brockington and JonathanSchaeffer(1996). The APHID Parallel Alpha-Beta Search Algorithm , Eighth IEEESymposium on Parallel and Distributed Processing, pp. 432-436.

    [20]    Stockman, G. C. (1979). AMinimax Algorithm Better than Alpha-Beta? Artifcial Intelligence, Vol. 12, pp.179-196.

    [21]    Aske Plaat, Jonathan Schaeffer,Wim Pijls, and Arie de Bruin (1994). SSS* = Alpha-Beta + TT. Technical Report94-17, Department of Computing Science, University of Alberta, December 1994.

    [22]    Leifker, D. B. and Kanal, L.N.(1985). A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees.In Proceedings of IJCAI-85, pp. 1044-1046.

    [23]    Subir Bhattacharya and A.Bagchi (1989).Searching game trees in parallel using SSS*. Proc IJCAI-89,International Joint Conf on Artificial Intelligence, Detroit, USA, Aug 1989, pp42-47.

    [24]    Steinberg, I. R. and Solomon,M. (1990). Searching Game Trees in Parallel. In Proccedings of the 1990International Conference on Parallel Processing (vol.3), pp. 9-17, UniversityPark, PA. Penn. State University Press.

    [25]    Jaleh Rezaie and RaphaelFinkel(1992). A comparison of some parallel game-tree search algorithms.Technical report, University of Kentucky, Department of Computer Science,Lexington, USA.

    [26]    Karp, R. M. and Zhang, Yanjun.(1989). On Parallel Evaluation of Game Trees. In Proceedings of SPAA '89, pp.409-420, New York, NY. ACM Press.

    [27]    Richard M. Karp , Yangun Zhang(1998). On parallel evaluation of game trees, Journal of the ACM (JACM), v.45n.6, p.1050-1075, Nov.

    [28]    PKU JudgeOnline, Problem 1085,Triangle War. http://acm.pku.edu.cn/JudgeOnline/problem?id=1085.

    展开全文
  • 博弈树搜索对于计算机博弈至关重要。优秀的搜索算法通过搜索较少的节点就可以获得最佳路径,从而提高计算机的博弈水平。论文以中国象棋计算机博弈作为背景,在alpha-beta基本搜索算法上,详细阐述了置换表启发算法的...
  • 第6-2课:决策树、博弈树和行为树

    千次阅读 2020-09-22 12:17:12
    在以各种“XX学习”为代表的人工智能技术普及之前,游戏里常见的角色 AI 都是各种预设的行为逻辑,比如博弈树和行为树,当然也会用到各种专家知识库。当这些预设的行为逻辑足够复杂的时候,往往会让游戏玩家觉得游戏...

    在以各种“XX学习”为代表的人工智能技术普及之前,游戏里常见的角色 AI 都是各种预设的行为逻辑,比如博弈树和行为树,当然也会用到各种专家知识库。当这些预设的行为逻辑足够复杂的时候,往往会让游戏玩家觉得游戏里的人物很“智能”。从本质上来说,这些都还不算是真正的 AI,但也能够给游戏的体验增加很多乐趣,这一课我们就来介绍三种常见的给角色预设行为逻辑的方法,分别是决策树、博弈树和行为树。

    决策树(Decision Tree)

    在介绍决策树之前,先说一下分类算法,它是机器学习领域里的基本算法之一,常见的分类算法有贝叶斯分类算法、KNN 算法、逻辑回归算法、神经网络算法等,当然,还有各种深度学习算法。决策树是一种简单但广泛使用的分类器,因此,决策树也是一种分类算法。

    决策树长什么样

    决策树易于理解,通过解释后就能知道决策树所表达的意义了。决策树的每个内部节点表示在一个属性上的测试,每个分支代表该测试的一个输出,而每个树叶结点则代表一个分类标记,所谓的分类标记其实就是分类结果,比如“Yes”或“No”。

    21c89660-01ab-11e9-b0f4-ff31f4e5691e

    图(1)相亲决策示意图

    图(1)就是一个“疑似”决策树的示意图,这是一个姑娘的相亲决策。之所以用“疑似”来形容,是因为这个决策树上的判断条件都太主观、太抽象、没有量化。什么意思呢?比如说“年轻”这个条件,多少岁算年轻,多少岁算年老呢

    展开全文
  • 博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,提出在扩展未达到规定深度节点时,...
  • 计算机博弈为人工智能提供一个实验平台,将人工智能的一些理论与方法应用于计算机博弈,可通过博弈水平的高低来检验这些理论与方法的有效性,研究计算机博弈所得到的成果也可推广至人工智能的其他领域。
  • 基于博弈树的五子棋 AI 算法及其 C++ 实现

    千次阅读 多人点赞 2020-11-27 01:19:03
    基于博弈树的五子棋 AI 算法及其 C++ 实现摘要一   五子棋的游戏规则二   五子棋对弈的算法描述2.1 博弈树搜索算法2.2 α ─ β 剪枝2.3 估价函数 摘要 五子棋是一个风靡全国的棋类...
  • 一、构建博弈树 当轮到机器落子时,程序调用主函数,树的深度n=0,代表以当前局势为整个博弈树根结点,深度为0;同时在棋盘上没有落子的地方依次调用creatNode函数,在creatNode函数内部,n首先加一,n代表当前...
  • 极大极小博弈树(Minimax Game Tree,简写为MGT)用于编写电脑之间的游戏程序,这类程序由两个游戏者轮流,每次执行一个步骤。当然,所有可能的步骤构成了一个树的结构。例如下面的图就是一个MGT,它表示了Tic-Tac-Toe...
  • 博弈树的启发式搜索

    2022-04-26 20:31:36
    博弈树(game tree)是指由于动态博弈参与者的行动有先后次序,因此可以依次将参与者的行动展开成一个树状图形。博弈树是扩展型的一种形象化表述。它能给出有限博弈的几乎所有信息。其基本构建材料包括结、枝和信息集...
  • 第四章 博弈树game tree

    千次阅读 2021-07-19 13:09:34
    博弈树 game tree、 perfect-information game (N, A, H, Z, χ, ρ, σ, u)(N,~A, ~H, ~Z,~\chi, ~\rho, ~\sigma, ~u )(N, A, H, Z, χ, ρ, σ...
  • 博弈树-BIT

    千次阅读 2020-12-16 01:41:17
    博弈树-BIT 下棋属于一种博弈游戏,博弈过程可以用树(博弈树)来表示。假设游戏由两个人( A 和 B )玩,开始由某个人从根结点开始走,两个人轮流走棋,每次只能走一步, 下一步棋只能选择当前结点的孩子结点,谁先...
  • 博弈树的搜索是人工智能领域一个重要的研究课题.许多完全信息的二人零和博弈问题都可以用博弈树搜索算法解决。 那么什么是二人零和博弈问题呢? 有一系列的博弈问题拥有以下性质[1]: 有两个对抗者:对抗者1和对抗者...
  • 博弈树 一字棋

    2013-05-24 18:15:36
    人工智能 可曾作业 非常牛逼的作业 欢迎大家参考
  • 简单博弈树算法(nim游戏)的python实现。import randomimport treelibimport systagid=0def genId():global tagidtagid+=1return str(tagid)def next(c):if(c>3):return [c-1,c-2,c-3]elif (c>2):return [c-1,c...
  • 在我们的五子棋游戏中,黑白两方轮流下子,会产生不同的棋盘局面。... 这样看就是一个又一个的树,但是在一个五子棋游戏里面博弈树的全部遍历有10的41次方个局面,所以我们基本上就是设定一个深度就不在搜索了,用一...
  • 本关任务:学习人工智能博弈算法中的 AlphaBeta 剪枝技巧,并基于 MinMax 算法编程实现如下图博弈树最优值问题的求解。 博弈树的输入形式为字符串:[A, [B, (E, 3), (F, 12), (G, 8)], [C, (H, 2), (I, 4), (J, 6)]...
  • 对于博弈类人工智能,其中一个方法就是:博弈树极大极小值alpha-beta剪枝搜索。是不是觉得这个名字很牛逼, 但经过我的详细解读, 你马上就会发现,原来不过如此。对于要实现一个会智能下五子棋的AI,要怎么去实现呢...
  • 人机博弈问题是近年来比较热点的问题,机器博弈被专家们描述为人工智能的果蝇,就是说人类对机器博弈的研究衍生了大量的研究成果,这些成果对更广泛的领域产生了重要影响。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,038
精华内容 5,615
关键字:

博弈树