精华内容
下载资源
问答
  • 极小化极大算法

    万次阅读 2016-08-05 18:08:54
    极小化极大(minimax)算法顾名思义,就是让最大得情况最小,这里的最大一般是指最差的情况,比如游戏中最不利的情况。 该算法需要满足零和博弈,初略的解释就是若有两个玩家进行游戏,如果其中一方得到利益那么另...

    此博客是我对之前学习的minimax算法的个人总结,毕竟有一段时间没实际使用此算法了,需要巩固一下。除了我下文标注的引用以外其他内容都是原创的,如果需要转载请注明出处,谢谢。


    基本算法思想

    极小化极大(minimax)算法顾名思义,就是让最大得情况最小,这里的最大一般是指最差的情况,比如游戏中最不利的情况。

    该算法需要满足零和博弈,初略的解释就是若有两个玩家进行游戏,如果其中一方得到利益那么另一方就会失去利益,游戏利益的总和为0(某些情况下为常数)。

    因此,零和的约束条件也使得该算法在很多游戏中图体现出很好的效果,比如大多数的棋类游戏。

    其实说白了,这个算法就是一个树形结构的递归算法,每个节点的孩子和父节点都是对方玩家,所有的节点被分为极大值(我方)节点和极小值(对方)节点

    算法思想参考维基的伪代码:

    function minimax(node, depth)
        if node is a terminal node or depth = 0
            return the heuristic value of node
        if the adversary is to play at node
            let α := +foreach child of node
                α := min(α, minimax(child, depth-1))
        else {we are to play at node}
            let α := -foreach child of node
                α := max(α, minimax(child, depth-1))
        return α

    上述代码depth是最多预测层数限制,函数递归有两个出口,一是到达层数限制即depth 为 0,二是已经递归到叶子节点,在游戏中体现为“死棋“或者有一方已经确定胜利获失败。

    下面的两个迭代过程需要进行玩家判断,因为我们需要最小话敌方的优势(最大化我方优势),所以对应敌方的当前步,需要返回找到的min;我方的当前步,需要返回找到的max。

    与此同时,迭代本身体现在我们假设对方也做出了在我们已经考虑到的范围内(同样想到了这层策略)的最佳判断,因为游戏通常是双方交替进行的,所以通常在实际编程中我们还要给minimax方法中添加一个确认当前玩家身份的参数,如果只有两个玩家布朗型可能是一个较好的选择。

    每次的迭代,都可以认为是向上一层的预测,当然,因为minimax的算法是树形结构,不断地向下拓展该树会导致计算量的倍数增加(多少倍取决于所剩可选的当前支孩子节点的数量)。但是有可能会出现一种情况,当函数递归到一定层数(计算量达到一定数值后),所剩可选分支已经很少(很多已经到达叶子节点),可继续递归的子节点数量也相应减少,反而高层级的预测计算量并不大。当然通常情况是在还没到达这个极值之前,计算机已经无法在可以接受的时间内进行玩这些计算了,比如围棋。


    alpha-beta 剪枝

    每个节点都有其α β两个值,α记录当前最大值,β记录当前最小值。所有层级的α默认值为负无穷,β默认值为正无穷。




    这里右边正方形节点出现了α >= β的情况,也就是说当前节点我们找到的(部分)最小值已经不大于父节点的最大值判断。因为父节点是极大值节点,当前节点是极小值节点,所以我们如果我们继续遍历剩下的孩子节点,找到的β只可能比当前小,所以从父节点的角度来看,当前已经没有继续遍历的需要,所以我们应该减掉剩下的孩子节点,也就是途中的右下圆形节点,直接更新父节点(上方圆节点),但是如果这不是二叉树结构,还有别的方形节点未访问,仍需继续访问完再更新,但是这种情况下的当前方形节点的圆型子节点就没有必要继续访问了(无论有多少)。


    还有一种相反的情况是上过程的方形和圆形节点全部替换,如果在圆形节点出现α >= β的情况,可以减掉剩下的枝(跳过所有剩下未访问的子节点)


    关于建模问题

    实话说数学建模一直是我的弱点,之前研究机器学习的内容理解还好,但是一旦要实际问题建模我就开始头疼。所以这里我不准备用数学语言做很复杂的描述,而是举几个简单的例子,以说明minimax算法的建模特点为目的,不深究其数学细节。

    五子棋例子

    五子棋游戏是最适合用minimax算饭进行ai设计的棋类游戏之一,也是很多教程用来教学的案例。五子棋游戏的minimax结构每个节点代表在对应棋格下一子,其所有的子节点是剩下所有空的棋格。当然第一步的棋子最好人为设定走法,因为如果计算的话计算量太大而且没有意义。

    对局势判断其实只有一下两个因素的排列组合

          1. 我方棋子目前有多少子相连 A[1,2,3,4,5]

          2. 相连子两边空位有几个 B[0,1,2]

    分别看这两组很数据,逻辑明显,越大越好

    结合起来假设D[B][A]为决策,当B > 0时,A越大越好

    在实际AI设计时,应考虑到优先级最高的是直接赢得比赛,因此可以在当有D[B][4] (B > 0)出现时应该直接选择赢得比赛而不是去防守

    所以,需要区分D为表示己方的Dx(加分)和表示对手的Dy(扣分),而且保证Dx[][5] > -Dy[][5]

    而当B = 0的情况下,除非A = 5,其他情况对于双方是没有区别的,所以都应该是不加分不减分

    当然还有一些其他有趣的细节可以优化这个AI的判断,这些就有待以后慢慢补充了



    展开全文
  • 极小化极大算法与负极大值算法

    千次阅读 2016-10-11 19:30:02
    1.极小化极大算法(Minimax)  Minimax算法又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法。Minimax算法常用于棋类等由两方较量的游戏和程序,这类程序由两个游戏者轮流,每次执行一个步骤。我们...

    1.极小化极大算法(Minimax)

         Minimax算法又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法。Minimax算法常用于棋类等由两方较量的游戏和程序,这类程序由两个游戏者轮流,每次执行一个步骤。我们众所周知的五子棋、象棋等都属于这类程序,所以说Minimax算法是基于搜索的博弈算法的基础。该算法是一种零总和算法,即一方要在可选的选项中选择将其优势最大化的选择,而另一方则选择令对手优势最小化的方法。

     

         我们知道,常用的博弈算法都是基于搜索的博弈算法,所有可能的下棋步骤构成一个树的结构,以Tic-tac-toe(中文称为井字棋,即两人轮流在井字棋盘的方格内划×或〇,谁先将划过的三个方格成一直线或对角线为胜)游戏为例,下面一幅图表示了Tic-tac-toe游戏的前两步所有可能的步骤.

         上图中第0层为空棋盘,第1层是×方所有可能的步骤,第2层是〇方所有可能的步骤。在第1层,×方需要选择使其优势最大的选择,而在第2层,〇方则需要选择使×方优势最小即己方优势最大的选择。

     

         Minimax的含义就是极小化对手的最大利益,在上图中,在第2层〇方一定会选择使自己优势最大的选择,而对于×方需要做的就是选择〇方最大选择中的极小值。

     

    Minimax是一种深度优先搜索,其用伪代码表示如下:

    1. function minimax(node, depth)  
    2. if node is a terminal node or depth = 0  
    3.     return the heuristic value of node  
    4. if the adversary is to play at node  
    5.     let α := +∞  
    6.     foreach child of node  
    7.         α := min(α, minimax(child, depth-1))  
    8. else {we are to play at node}  
    9.     let α := -∞  
    10.     foreach child of node  
    11.         α := max(α, minimax(child, depth-1))  
    12. return α。  

     

    2.负极大值算法(Negamax)

    负极大值算法是极小化极大算法的一个变体,其基本原理是基于下面的公式:

                                      max (a,b) = - min ( - a, - b)

        即在几个节点中选择得分最小的节点相当于将这些节点的得分乘以-1然后取得分最大的节点。这样Negamax算法就将每一步递归过程都统一了起来,每一次递归都选取最大值。

    下面是Negamax算法的伪代码:

    1. function negamax(node, depth)  
    2. if node is a terminal node or depth = 0  
    3.     return the heuristic value of node  
    4.  let best := -∞  
    5.  foreach child of node  
    6.      best := max(α, -negamax(child, depth-1))  
    7. return best  

     

    3.两种的区别

         我们把电脑方的价值总和叫做CpValue,对手方价值总和叫做OpValue,那么一个局面的估值Value就是电脑方和对手方的价值差。表达如下式:Value=CpValue - OpValue。这个Value也就是最终返回给搜索引擎的估值。在基本的极小极大搜索的过程里估值的取得是和上式完全契合的,即无论任何时候取估值均由固定一方的值减去另一方的值。

     

    而在负极大值形式的搜索中,
    1.对于电脑方走棋所形成的局面,如果该节点是叶节点,则估值是CpValue - OpValue;如果该节点有父节点,则父节点必然是对手方走棋的局面,它是取极大值极点,我们希望取OpValue - CpValue中的最大的子节点。
    2.对于对手方走棋所形成的局面,如果该节点是叶节点,则估值是OpValue - CpValue;如果该节点有父节点,则必然是电脑方走棋的局面,它是取极小值节点,我们希望取CpValue - OpValue中最大的子节点。
    这样我们就理解了在负极大值算法中的那个负号啦。


    负极大值算法:一个局面对红方的优势为X,那么对于黑方的优势就是-X;一个局面对红方的优势为-X,对黑方的优势就是X。在负极大值搜索算法中,没有了极小点,只有极大点。需要注意的是,局面对一方的优势转化为另一方的优势时需要加负号。局面估计区间是一个关于0点对称的区间:

    [-MaxValue,MaxValue].需要注意的是,为了能使负极大值搜索算法得到正确的评价,必须修改局面评估函数的返回值,原来在极大极小搜索算法中始终返回的是红方的优势,现在要改为当前走棋方的优势。

    负极大值搜索算法: 

    输入:搜索深度

    输出:节点的最佳走法,及对应的最佳估值

    函数形式:int negaMaxSearch(int depth)

     

    初始化最优值best=负无穷大                //都是极大点

    如果depth小于等于0

           调用评估函数,并将结果赋给value

           返回value值

     

    否则

          生成当前所有合法的走法

          对于每一步走法

                执行走法

                value= -negaMaxSearch(depth-1)             //注意函数之前有负号

                撤销走法

                如果 value> best

                        best=value

                        如果  depth == Max_Depth

                                bestMove=mv

    返回best                                                                 //返回某个搜索分支的最优评估值

     

     

    评估函数的算法:

     

    输入:棋局

    输出:局面对当前走方的优势

     rValue:红方的优势总和

    bValue:黑方的优势总和

    分别进行评估,具体问题具体设计,获得rValue和bValue的值

     

    如果当前局面是红方走棋

         return rValue-bValue;

    否则

         return bValue-rValue;



    两种算法估值函数的实现方法:

        如果我们把红方的价值总和叫做RedValue,黑方价值总和叫做BlackValue,那么一个局面的估值Value就是红方和黑方的价值差。表达式如下式:

                   Value = RedValue-BlackValue

        这个Value也就是最终返回给搜索引擎的估值。在基本的极大极小搜索的过程里估值的取得是和上式完全契合的,即无论任何时候取估值均由固定的一方减去另一方的值。而在负极大极小值搜素中,如果被估值节点是取极小值点时取的估值RedValue-BlackValue,则被估值节点取极大值节点时取得估值应是BlcakValue-RedValue.



    展开全文
  • 极小化极大算法及Alpha-beta剪枝

    千次阅读 2018-01-16 00:38:58
    极小化极大算法是一个深度优先的搜索算法,树形结构递归,一般在棋类等两方较量的游戏和程序中运用较多,如tic-tac-toe 它需要满足零总和博弈,比如在一场棋类比赛中,我方得分,对方失分,总分值永远为0或者某一...

    初学者的个人笔记,不足之处还请指正,谢谢


    极小化极大算法(minimax) L'algorithm minimax

    极小化极大算法是一个深度优先的搜索算法,树形结构递归,一般在棋类等两方较量的游戏和程序中运用较多,如tic-tac-toe

    它需要满足零总和博弈,比如在一场棋类比赛中,我方得分,对方失分,总分值永远为0或者某一常数

    因此,我们为了获胜,即需要最大化我方利益(Max),最小化对方利益(Min)

    伪代码如下(来自Wikipedia):

    function minimax(node, depth)
        if node is a terminal node or depth = 0
            return the heuristic value of node
        if the adversary is to play at node
            let α := +foreach child of node
                α := min(α, minimax(child, depth-1))
        else {we are to play at node}
            let α := -foreach child of node
                α := max(α, minimax(child, depth-1))
        return α

    第一个if伪代码块指出了函数递归的两个出口,一是depth=0即到达了层数顶点,游戏结束,二是递归到了某一节点,程序无法再进行,或者已经有一方获胜。

    第二个if伪代码块指出,当处于对方节点时,取最小值

    否则else 位于我方节点时,取最大值

    由于minimax算法是一个树形结构,所以总共需要计算n的x次方个结果,对于棋盘比较大的游戏来说,计算量成几何倍数增长,于是我们需要用到Alpha-beta剪枝,来优化这个算法


    Alpha-beta剪枝 L'algorithme Alpha-beta

    根据上文提到的,alpha-beta剪枝实际上就是minimax的升级版本

    将minimax的搜索树,剪裁掉无意义无需搜索的枝干以提升搜索效率,减少工作量

    伪代码如下(来自Wikipedia):

    01 function alphabeta(node, depth, α, β, maximizingPlayer) // node = 节点,depth = 深度,maximizingPlayer = 大分玩家
    02      if depth = 0 or node是终端节点
    03          return 节点的启发值
    04      if maximizingPlayer
    05          v := -∞
    06          for 每个子节点
    07              v := max(v, alphabeta(child, depth - 1, α, β, FALSE)) // child = 子节点
    08              α := max(α, v)
    09              if β ≤ α
    10                  break // β裁剪
    11          return v
    12      else
    13          v := ∞
    14          for each 每个子节点
    15              v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
    16              β := min(β, v)
    17              if β ≤ α
    18                  break // α裁剪
    19          return v
    

    由于我们的每一步都是为了预测上一层的走向,每一层自己为(max)α ,对手为(min)β
    当树形结构到达 α >= β 的时候,无论接下来的子节点为几,都会小于等于β,因为子节点为对手取最小值min
    而自己要取的是max,所以无论接下来出现的是几都不重要了
    至此,我们就可以将右侧的树枝精减掉,不需要再耗费时间去计算

    后续会补充python代码及手画推导








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

    极小化极大算法(The minimax algorithm)

    前面部分描述的技术适用于简单,完全可解决的游戏,如Nim(因为其所有的情况也不算大)。然而,随着游戏变得越来越复杂,很快就无法检查每一个可能的结果。例如,如果你试图通过一切可能的棋牌游戏,即使以现代电脑的速度,这个过程可能需要数十亿年的时间。 然而,不管怎样,尽管有这个限制,电脑在国际象棋方面仍然非常擅长。1997年,IBM的“深蓝色”(Deep Blue)超级计算机当时击败了世界冠军Garry Kasparov。 Deep Blue未不是通过对所有可能的游戏进行详尽的分析而获胜, 它反而只是针对有限数量的分析,以与人类完全相同的方式前进。
    即使对于在计算上不可行的游戏,但是每一个动作都是在一个可能的动作序列中进行操作,来自Nim游戏的有利位置和不利位置的递归概念仍然派上用场。虽然可能无法确定一个肯定胜利的举动,但是在任何位置上的最佳举动是让对手处于最糟糕的位置。这个策略,其中包括找出让对手处于最差可能的最佳状态的位置(也就是说,这个时候你处于劣势,你要做的是最小化对手赢的机会) - 被称为极小化极大算法,因为目标是找到最小化对手赢的最大机会的动作。所以我们可以总结一下这个算法的基本特点:
    - 在任何位置上的最佳举动是让对手处于最糟糕的位置。
    - 当你处于劣势,你要做的是最小化对手赢的机会
    - 你的目的是找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)

    怕我自己解释的不够规范,我引用一段原文:

    Although it may not be possible to identify a move as surefire winner, it is still true that the best move in any position is the one that leaves your opponent in the worst position. Similarly, the worst position is the one that offers the weakest best move. This strategy—which consists of finding the position that leaves your opponent with the worst possible best move—is called the minimax algorithm because the goal is to find the move that minimizes your opponent’s maximum opportunity.

    游戏树(Game trees)

    可视化最小化策略的操作的最佳方法是考虑在游戏中可能的未来移动,从而形成每轮转动的分支图。这种分支结构,这种图表被称为游戏树。初始状态由游戏树顶部的点表示。例如,假设存在来自这个位置的三个可能的移动,则会有三条线从当前状态向下发展到表示这些移动结果的三个新状态,如下图所示:

    从这些新位置,您的对手也有选择权。 如果每个位置再次有三个选择,下一代的游戏树如下所示:

    你在初始位置选择哪一个? 显然,你的目标是取得最好的结果。不幸的是,你只能控制一半的游戏(因为这是双人游戏)。如果你能够选择对手的举动以及自己的选择,那么您可以选择两次左右的路径,使你处于最佳位置(意味着你这个时候要考虑对手的选择)。考虑到你的对手也在努力争取,你最好的选择是选择一个最终的举动,让你的对手尽可能减少的获胜的机会。

    对位置和动作进行评估(Rating positions and moves)

    为了弄清楚你应该如何进行,添加一些定量数据的有助于我们分析。如果你为每个可能的移动分配数字分数,则决定某个特定动作是否比某些替代方法更好。数值越高越好。例如,得分为+ 7的举动胜过评级为-4的动作。除了评估每个可能的移动之外,对游戏中的每个位置分配类似的数字评级是都是有意义的。 因此,一个位置可能具有+9的等级,因此比具有+2分的位置更好。
    从移动的玩家的角度来看,这两个位置和动作都是对应评估的。此外,评估系统被设计为在0左右对称,因为在玩家移动得分为+9的位置上,从对手的角度来看,得分为-9。 对评级数字的这种解释就是认为,对于一个玩家来说,一个对一个玩家有利的位置对于另一个玩家而言是不好的,就像Nim游戏一样。更重要的是,以这种方式定义评估系统,可以很容易地表达行动和位置的分数之间的关系。 任何举动的评级只有在对手评估时才会对得分位置的评级负数。类似地,任何位置的评级可以被定义为其最佳移动的评级。
    为了使这个讨论更具体,它有助于考虑一个简单的例子。假设你已经看到了游戏中的两个步骤,包括你的一个举动和对手可能的回应。在计算机科学中,单个玩家的单一动作被称为ply,以避免与移动(move)和回合(turn)相关的歧义,这有时意味着两个玩家都有机会玩。 如果你在双层分析结束时评价位置,则游戏树可能如下所示:

    因为这棵树底部的位置是你在树的顶部移动将会产生其他位置,这些位置的评级数字从你的角度分配。 如果考虑到这些潜在位置的评级,你应该从原始位置中做出什么动作?
    为了方便理解,你可以说你负责选第二行的三个点,而第三行是第二行所产生的所有情况的评估
    乍一看,你可能会被中心分支包含导致+9的路径所吸引,这对你来说是一个很好的结果。不幸的是,中心分支提供了如此美好的结果这一点并不是很重要。如果你的对手玩得很合理,你就没有办法可以达到+9的位置。即使,假设你选择了中心分支。给定可用的选项,你的对手将选择最左侧的分支,如以下游戏树中的彩色路径所示:

    从你的角度来说你的初始选择让你有可能处于一个评级为-5这样的位置。但是如果你选择最右边的分支,你会做得更好,因为你的对手最好的策略只是让你处于-2级的位置而已。

    如前面所述,当从对手的角度进行评估时,移动评级是对对方所得到的位置的评级的负数。游戏树的突出显示行中的最后一个移动的对手的评级为+2,因为它导致了我处于-2级的位置。负号表示角色的转变。 所以说,对我的对手不利的位置的移动对我有好处,反之亦然。 每个位置的评级只是其提供的最佳举措的评级。因此,在游戏树中突出显示的路径上的位置和移动的评分如下所示:

    起始位置的等级为-2。虽然这个立场是不太理想的,但假如你的对手正在合理地运营,那么对于你而言,比其他可能的结果更好。
    极小化极大算法的任何实现都要比较移动的等级以确定最佳的运动。因此,将每个移动的评级存储在相应的Move对象中是很方便的。实现此目标的最简单方法是向Move类添加一个称为评级的新实例变量,以使Nim游戏的定义现在如下所示:

    class Move {
        int nTaken;
        int rating;
        friend class SimpleNim;
    };

    这一篇先讲原理,等晚上再把具体的实现补上,我理解这段也需要点时间的。

    展开全文
  • Minimax极小化极大算法

    2021-05-19 16:03:52
    转载:Minimax算法及实例分析
  • tic-tac-toe Minimax(极小化极大算法

    千次阅读 2012-12-10 22:16:14
    说起人工智能,说起博弈论,不得不说的一个经典的游戏tic-tac-toe,围棋,五子棋,六子棋都可用此法测试 public void minmax(int chess[][], int depth, int Alpha, int Beta)//找最大 { int best=-1000, tempt...
  • 极小化极大算法是基于决策树和搜索的智能系统中的典型算法,可用于指导井字棋、黑白棋、五子棋等经典完全信息零和博弈。虽在学生时代学习过极小化极大算法,但时过境迁,思量该算法的来龙去脉已然如雾里探花水中望月...
  • 算法思想-极大化极小

    2021-02-06 10:52:42
    算法思想-极大化极小 简单来说就是假如答案要求的是最大解,我们可以从反面考虑,考虑最小的反面,就是最大的正面,这种方法叫极大化极小。尤其在博弈论中最为常见。 问题 LeetCode 1423 此题我们可以从n-k个剩余...
  • 这是一个全新的系列--隔三岔五聊算法。这个系列充满不确定性,什么时间更新全靠自己的心情,今天的文章也有能是最后一篇,内容...Minimax算法又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法。Mi...
  • 极大极小算法简介

    2019-09-26 13:21:30
    Minimax算法 又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)。通常以递归形式来实现。 Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法,即...
  • 极大极小算法

    万次阅读 2013-08-24 18:32:30
    Minimax算法 又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)。通常以递归形式来实现。 Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法,...
  • 极大极小算法、α-β剪枝算法的理解

    万次阅读 多人点赞 2019-03-27 23:04:41
    Minimax算法 又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)。通常以递归形式来实现。 ========================= 谈一下我的理解: 刚开始看极大极小算法的时候,说...
  • Minimax算法又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法。Minimax算法常用于棋类等由两方较量的游戏和程序,这类程序由两个游戏者轮流,每次执行一个步骤。我们众所周知的五子棋、象棋等都...
  • 极小极大算法

    2016-11-24 14:35:09
    极小极大算法常用于二人博弈游戏,目的是寻找最优的方案使得自己能够利益最大。基本思想就是假设自己(A)足够聪明,总是能选择最有利于自己的方案,而对手(B)同样足够聪明,总会选择最不利A的方案。 ...
  • 针对一类非线性l-1模极小化问题目标函数非光滑的特点给求解带来的困难,利用差分进化算法并结合极大熵函数法给出了解决此类问题的一种有效算法。利用极大熵函数将l-1模极小化问题转化为一个光滑函数的无约束最优化...
  • 目录 一、问题描述 二、算法描述 三、评估函数 ...(一)极小化极大算法: 极小化极大搜索是一种在有限的深度范围内搜索博弈树的求解方法,程序代表AI方MAX节点,目的是打败玩家,基本原理...
  • 本文为个人手记,是对设计各种【极小化极大算法类型博弈游戏】的设计思路的一个白话总结。 开始自言自语 由于象棋的步数比较多,走法也比较多,所以无法把所有走法都枚举。 只能在给定的棋局里面,遍历可能的走法,...
  • 极小极大值搜索算法,MinimaxSearch算法,是一种零和算法,是用来最小对手的利益,最大自己的利益的算法极小极大之搜索算法常用于棋类游戏等双方较量的游戏和程序,算是一种电脑AI算法。 该算法是一种总零和...
  • 极小极大算法 (The Minimax Algorithm)

    万次阅读 热门讨论 2014-04-04 11:01:13
    极小极大算法 (The Minimax Algorithm...极小极大算法常用于二人博弈游戏,目的是寻找最优的方案使得自己能够利益最大。基本思想就是假设自己(A)足够聪明,总是能选择最有利于自己的方案,而对手(B)同样足够聪...
  • 算法设计——极大极小搜索

    千次阅读 2010-08-13 22:42:00
    极大极小搜索策略一般都是使用在一些博弈类的游戏之中:这样策略本质上使用的是深度搜索策略,所以一般可以使用递归的方法来实现。在搜索过程中,对本方有利的搜索点上应该取极大值,而对本方不利的搜索点上应该取...
  • 利用MAF模型的基本思想,探讨了一种串扰时延最大化算法,并且利用被修改的FAN算法,生成测试矢量。对于一条敏化通路,利用被修改的FAN算法适当地激活相应的攻击线和受害线,使电路在最恶劣情况下引起最大通路时延,...
  • 5.极小极大化搜索与α-β剪枝:编程实现人机“三子棋”小游戏并对算法过程进行动态展示。三子棋的游戏规则是只要将己方的三个棋子连成一条线则游戏获胜,如果对方连线成功,则游戏失败,若均连线失败则游戏平局。 ...
  • 改进算法在原目标函数中引入中心极大化约束项来调控簇间分离度,从而避免算法出现一致性聚类结果。利用磷虾群算法对基于新目标函数的KFCM算法进行优化,使算法不再依赖初始聚类中心,提高算法的稳定性。基于距离最大...
  • 改进算法在原目标函数中引入中心极大化约束项来调控簇间分离度,从而避免算法出现一致性聚类结果。利用磷虾群算法对基于新目标函数的KFCM算法进行优化,使算法不再依赖初始聚类中心,提高算法的稳定性。基于距离最大...
  • 极小化极大:回溯+剪枝 先来说极小极大算法主要应用于什么样的游戏: 1. 零和游戏(Zero-sum Game):意思就是你死我活,一方的胜利代表另一方的失败,比如,象棋,五子棋等。 2. 完全信息(Perfect Information)...
  • 已给m个定义在n维欧几里德空间的函数,在这m个函数中求r个最大值函数和的最小值,其中1≤r≤ m。...该问题转化为只包含最大值函数max{0,t}的非光滑问题,对该非光滑问题提出一种具有全局收敛的二阶光滑化算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 803
精华内容 321
关键字:

极小化极大算法