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

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

    极小极大的定义
    Minimax算法 又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)。通常以递归形式来实现。


    Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法,即一方要在可选的选项中选择将其优势最大化的选择,另一方则选择令对手优势最小化的一个,其输赢的总和为0(有点像能量守恒,就像本身两个玩家都有1点,最后输家要将他的1点给赢家,但整体上还是总共有2点)。很多棋类游戏可以采取此算法,例如tic-tac-toe。


    关于极小极大,更多的信息可参考以下文章:


    以TIC-TAC-TOE为例
    tic-tac-toe就是我们小时候玩的井字棋(我这边习惯叫“井字过三关”),不熟悉的可以参考wiki

    一般X的玩家先下。设定X玩家的最大利益为正无穷(+∞),O玩家的最大利益为负无穷(-∞),这样我们称X玩家为MAX(因为他总是追求更大的值),成O玩家为MIN(她总是追求更小的值),各自都为争取自己的最大获益而努力。

    现在,让我们站在MAX的立场来分析局势(这是必须的,应为你总不能两边倒吧,你喜欢的话也可以选择MIN)。由于MAX是先下的(习惯上X的玩家先下),于是构建出来的博弈树如下(前面两层):


     

    MAX总是会选择MIN最大获利中的最小值(对MAX最有利),同样MIN也会一样,选择对自己最有利的(即MAX有可能获得的最大值)。有点难理解,其实就是自己得不到也不给你得到这样的意思啦,抢先把对对手有利的位置抢占了。你会看出,这是不断往下深钻的,直到最底层(即叶节点)你才能网上回溯,确定那个是对你最有利的。
    具体过程会像是这么一个样子的:


     

    但实际情况下,完全遍历一颗博弈树是不现实的,因为层级的节点数是指数级递增的:
    层数   节点数
     0       1
     1       9
     2       72
     3       504
     4       3024
     5       15120
     6       60480
     7       181440
     8       362880

    完全遍历会很耗时...一般情况下需要限制深钻的层数,在达到限定的层数时就返回一个估算值(通过一个启发式的函数对当前博弈位置进行估值),这样获得的值就不是精确的了(遍历的层数越深越精确,当然和估算函数也有一定关系),但该值依然是足够帮助我们做出决策的。于是,对耗时和精确度需要做一个权衡。一般我们限定其遍历的深度为6(目前多数的象棋游戏也是这么设定的)。

    于是,我们站在MAX的角度,评估函数会是这样子的:

     

    Java代码 复制代码 收藏代码
    1. static   final   int   INFINITY = 100 ;   // 表示无穷的值   
    2. static   final   int   WIN = +INFINITY ;   // MAX的最大利益为正无穷   
    3. static   final   int   LOSE = -INFINITY ;   // MAX的最小得益(即MIN的最大得益)为负无穷   
    4. static   final   int   DOUBLE_LINK = INFINITY / 2 ;   // 如果同一行、列或对角上连续有两个,赛点   
    5. static   final   int   INPROGRESS = 1 ;   // 仍可继续下(没有胜出或和局)   
    6. static   final   int   DRAW = 0 ;   // 和局   
    7. static   final   int [][] WIN_STATUS =   {   
    8.       {   012 },   
    9.       { 345 },   
    10.       { 678 },   
    11.       { 036 },   
    12.       { 147 },   
    13.       { 258 },   
    14.       { 048 },   
    15.       { 246   }   
    16. };   
    17. /**  
    18.  * 估值函数,提供一个启发式的值,决定了游戏AI的高低  
    19.  */  
    20. public   int   gameState( char []   board )   {   
    21.        int   result = INPROGRESS;   
    22.        boolean   isFull =   true ;   
    23.          
    24.        // is game over?   
    25.        for   ( int   pos = 0; pos < 9; pos++) {   
    26.              char   chess = board[pos];   
    27.              if   ( empty   == chess) {   
    28.                   isFull =   false ;   
    29.                    break ;   
    30.             }   
    31.       }   
    32.        // is Max win/lose?   
    33.        for   ( int [] status : WIN_STATUS) {   
    34.              char   chess = board[status[0]];   
    35.              if   (chess ==   empty ) {   
    36.                    break ;   
    37.             }   
    38.              int   i = 1;   
    39.              for   (; i < status.length; i++) {   
    40.                    if   (board[status[i]] != chess) {   
    41.                          break ;   
    42.                   }   
    43.             }   
    44.              if   (i == status.length) {   
    45.                   result = chess ==   x   ? WIN : LOSE;   
    46.                    break ;   
    47.             }   
    48.       }   
    49.        if   (result != WIN & result != LOSE) {   
    50.              if   (isFull) {   
    51.                    // is draw   
    52.                   result = DRAW;   
    53.             }   else   {   
    54.                    // check double link   
    55.                    // finds[0]->'x', finds[1]->'o'   
    56.                    int [] finds =   new   int [2];   
    57.                    for   ( int [] status : WIN_STATUS) {   
    58.                          char   chess =   empty ;   
    59.                          boolean   hasEmpty =   false ;   
    60.                          int   count = 0;   
    61.                          for   ( int   i = 0; i < status.length; i++) {   
    62.                                if   (board[status[i]] ==   empty ) {   
    63.                                     hasEmpty =   true ;   
    64.                               }   else   {   
    65.                                      if   (chess ==   empty ) {   
    66.                                           chess = board[status[i]];   
    67.                                     }   
    68.                                      if   (board[status[i]] == chess) {   
    69.                                           count++;   
    70.                                     }   
    71.                               }   
    72.                         }   
    73.                          if   (hasEmpty && count > 1) {   
    74.                                if   (chess ==   x ) {   
    75.                                     finds[0]++;   
    76.                               }   else   {   
    77.                                     finds[1]++;   
    78.                               }   
    79.                         }   
    80.                   }   
    81.                    // check if two in one line   
    82.                    if   (finds[1] > 0) {   
    83.                         result = -DOUBLE_LINK;   
    84.                   }   else   if   (finds[0] > 0) {   
    85.                         result = DOUBLE_LINK;   
    86.                   }   
    87.             }   
    88.       }   
    89.        return   result;   
    90. }   
    static   final   int   INFINITY = 100 ;   // 表示无穷的值
    static   final   int   WIN = +INFINITY ;   // MAX的最大利益为正无穷
    static   final   int   LOSE = -INFINITY ;   // MAX的最小得益(即MIN的最大得益)为负无穷
    static   final   int   DOUBLE_LINK = INFINITY / 2 ;   // 如果同一行、列或对角上连续有两个,赛点
    static   final   int   INPROGRESS = 1 ;   // 仍可继续下(没有胜出或和局)
    static   final   int   DRAW = 0 ;   // 和局
    static   final   int [][] WIN_STATUS =   {
          {   0, 1, 2 },
          { 3, 4, 5 },
          { 6, 7, 8 },
          { 0, 3, 6 },
          { 1, 4, 7 },
          { 2, 5, 8 },
          { 0, 4, 8 },
          { 2, 4, 6   }
    };
    /**
     * 估值函数,提供一个启发式的值,决定了游戏AI的高低
     */
    public   int   gameState( char []   board )   {
           int   result = INPROGRESS;
           boolean   isFull =   true ;
          
           // is game over?
           for   ( int   pos = 0; pos < 9; pos++) {
                 char   chess = board[pos];
                 if   ( empty   == chess) {
                      isFull =   false ;
                       break ;
                }
          }
           // is Max win/lose?
           for   ( int [] status : WIN_STATUS) {
                 char   chess = board[status[0]];
                 if   (chess ==   empty ) {
                       break ;
                }
                 int   i = 1;
                 for   (; i < status.length; i++) {
                       if   (board[status[i]] != chess) {
                             break ;
                      }
                }
                 if   (i == status.length) {
                      result = chess ==   x   ? WIN : LOSE;
                       break ;
                }
          }
           if   (result != WIN & result != LOSE) {
                 if   (isFull) {
                       // is draw
                      result = DRAW;
                }   else   {
                       // check double link
                       // finds[0]->'x', finds[1]->'o'
                       int [] finds =   new   int [2];
                       for   ( int [] status : WIN_STATUS) {
                             char   chess =   empty ;
                             boolean   hasEmpty =   false ;
                             int   count = 0;
                             for   ( int   i = 0; i < status.length; i++) {
                                   if   (board[status[i]] ==   empty ) {
                                        hasEmpty =   true ;
                                  }   else   {
                                         if   (chess ==   empty ) {
                                              chess = board[status[i]];
                                        }
                                         if   (board[status[i]] == chess) {
                                              count++;
                                        }
                                  }
                            }
                             if   (hasEmpty && count > 1) {
                                   if   (chess ==   x ) {
                                        finds[0]++;
                                  }   else   {
                                        finds[1]++;
                                  }
                            }
                      }
                       // check if two in one line
                       if   (finds[1] > 0) {
                            result = -DOUBLE_LINK;
                      }   else   if   (finds[0] > 0) {
                            result = DOUBLE_LINK;
                      }
                }
          }
           return   result;
    } 
     

    基于这些,一个限定层数的实现是这样的:

     

    Java代码 复制代码 收藏代码
    1. /**  
    2.  * 以'x'的角度来考虑的极小极大算法  
    3.  */  
    4. public   int   minimax( char [] board,   int   depth){   
    5.        int [] bestMoves =   new   int [9];   
    6.        int   index = 0;   
    7.          
    8.        int   bestValue = - INFINITY ;   
    9.        for ( int   pos=0; pos<9; pos++){   
    10.                
    11.              if (board[pos]== empty ){   
    12.                   board[pos] =   x ;   
    13.                      
    14.                    int   value = min(board, depth);   
    15.                    if (value>bestValue){   
    16.                         bestValue = value;   
    17.                         index = 0;   
    18.                         bestMoves[index] = pos;   
    19.                   } else  
    20.                    if (value==bestValue){   
    21.                         index++;   
    22.                         bestMoves[index] = pos;   
    23.                   }   
    24.                      
    25.                   board[pos] =   empty ;   
    26.             }   
    27.                
    28.       }   
    29.          
    30.        if (index>1){   
    31.             index = ( new   Random (System. currentTimeMillis ()).nextInt()>>>1)%index;   
    32.       }   
    33.        return   bestMoves[index];   
    34.          
    35. }   
    36. /**  
    37.  * 对于'x',估值越大对其越有利  
    38.  */  
    39. public   int   max( char [] board,   int   depth){   
    40.          
    41.        int   evalValue =   gameState (board);   
    42.          
    43.        boolean   isGameOver = (evalValue== WIN   || evalValue== LOSE   || evalValue== DRAW );   
    44.        if (depth==0 || isGameOver){   
    45.              return   evalValue;   
    46.       }   
    47.          
    48.        int   bestValue = - INFINITY ;   
    49.        for ( int   pos=0; pos<9; pos++){   
    50.                
    51.              if (board[pos]== empty ){   
    52.                    // try   
    53.                   board[pos] =   x ;   
    54.                      
    55.                    //   maximixing   
    56.                   bestValue = Math. max (bestValue, min(board, depth-1));   
    57.                      
    58.                    // reset   
    59.                   board[pos] =   empty ;   
    60.             }   
    61.                
    62.       }   
    63.          
    64.        return   evalValue;   
    65.          
    66. }   
    67. /**  
    68.  * 对于'o',估值越小对其越有利  
    69.  */  
    70. public   int   min( char [] board,   int   depth){   
    71.          
    72.        int   evalValue =   gameState (board);   
    73.          
    74.        boolean   isGameOver = (evalValue== WIN   || evalValue== LOSE   || evalValue== DRAW );   
    75.        if (depth==0 || isGameOver){   
    76.              return   evalValue;   
    77.       }   
    78.          
    79.        int   bestValue = + INFINITY ;   
    80.        for ( int   pos=0; pos<9; pos++){   
    81.                
    82.              if (board[pos]== empty ){   
    83.                    // try   
    84.                   board[pos] =   o ;   
    85.                      
    86.                    //   minimixing   
    87.                   bestValue = Math.min(bestValue, max(board, depth-1));   
    88.                      
    89.                    // reset   
    90.                   board[pos] =   empty ;   
    91.             }   
    92.                
    93.       }   
    94.          
    95.        return   evalValue;   
    96.          
    97. }   
    /**
     * 以'x'的角度来考虑的极小极大算法
     */
    public   int   minimax( char [] board,   int   depth){
           int [] bestMoves =   new   int [9];
           int   index = 0;
          
           int   bestValue = - INFINITY ;
           for ( int   pos=0; pos<9; pos++){
                
                 if (board[pos]== empty ){
                      board[pos] =   x ;
                      
                       int   value = min(board, depth);
                       if (value>bestValue){
                            bestValue = value;
                            index = 0;
                            bestMoves[index] = pos;
                      } else
                       if (value==bestValue){
                            index++;
                            bestMoves[index] = pos;
                      }
                      
                      board[pos] =   empty ;
                }
                
          }
          
           if (index>1){
                index = ( new   Random (System. currentTimeMillis ()).nextInt()>>>1)%index;
          }
           return   bestMoves[index];
          
    }
    /**
     * 对于'x',估值越大对其越有利
     */
    public   int   max( char [] board,   int   depth){
          
           int   evalValue =   gameState (board);
          
           boolean   isGameOver = (evalValue== WIN   || evalValue== LOSE   || evalValue== DRAW );
           if (depth==0 || isGameOver){
                 return   evalValue;
          }
          
           int   bestValue = - INFINITY ;
           for ( int   pos=0; pos<9; pos++){
                
                 if (board[pos]== empty ){
                       // try
                      board[pos] =   x ;
                      
                       //   maximixing
                      bestValue = Math. max (bestValue, min(board, depth-1));
                      
                       // reset
                      board[pos] =   empty ;
                }
                
          }
          
           return   evalValue;
          
    }
    /**
     * 对于'o',估值越小对其越有利
     */
    public   int   min( char [] board,   int   depth){
          
           int   evalValue =   gameState (board);
          
           boolean   isGameOver = (evalValue== WIN   || evalValue== LOSE   || evalValue== DRAW );
           if (depth==0 || isGameOver){
                 return   evalValue;
          }
          
           int   bestValue = + INFINITY ;
           for ( int   pos=0; pos<9; pos++){
                
                 if (board[pos]== empty ){
                       // try
                      board[pos] =   o ;
                      
                       //   minimixing
                      bestValue = Math.min(bestValue, max(board, depth-1));
                      
                       // reset
                      board[pos] =   empty ;
                }
                
          }
          
           return   evalValue;
          
    } 
     

    Alpha-beta剪枝
    另外,通过结合Alpha-beta剪枝能进一步优化效率。Alpha-beta剪枝顾名思义就是裁剪掉一些不必要的分支,以减少遍历的节点数。实际上是通过传递两个参数alpha和beta到递归的极小极大函数中,alpha表示了MAX的最坏情况,beta表示了MIN的最坏情况,因此他们的初始值为负无穷和正无穷。在递归的过程中,在轮到MAX的回合,如果极小极大的值比alpha大,则更新alpha;在MIN的回合中,如果极小极大值比beta小,则更新beta。当alpha和beta相交时(即alpha>=beta),这时该节点的所有子节点对于MAX和MIN双方都不会带来好的获益,所以可以忽略掉(裁剪掉)以该节点为父节点的整棵子树。

    根据这一定义,可以很轻易地在上面程序的基础上进行改进:

     

    Java代码 复制代码 收藏代码
    1. /**  
    2.  * 以'x'的角度来考虑的极小极大算法  
    3.  */  
    4. public   int   minimax( char [] board,   int   depth){   
    5.        int [] bestMoves =   new   int [9];   
    6.        int   index = 0;   
    7.          
    8.        int   bestValue = - INFINITY ;   
    9.        for ( int   pos=0; pos<9; pos++){   
    10.                
    11.              if (board[pos]== empty ){   
    12.                   board[pos] =   x ;   
    13.                      
    14.                    int   value = min(board, depth, - INFINITY , + INFINITY );   
    15.                    if (value>bestValue){   
    16.                         bestValue = value;   
    17.                         index = 0;   
    18.                         bestMoves[index] = pos;   
    19.                   } else  
    20.                    if (value==bestValue){   
    21.                         index++;   
    22.                         bestMoves[index] = pos;   
    23.                   }   
    24.                      
    25.                   board[pos] =   empty ;   
    26.             }   
    27.                
    28.       }   
    29.          
    30.        if (index>1){   
    31.             index = ( new   Random (System. currentTimeMillis ()).nextInt()>>>1)%index;   
    32.       }   
    33.        return   bestMoves[index];   
    34.          
    35. }   
    36. /**  
    37.  * 对于'x',估值越大对其越有利  
    38.  */  
    39. public   int   max( char [] board,   int   depth,   int   alpha,   int   beta){   
    40.          
    41.        int   evalValue =   gameState (board);   
    42.          
    43.        boolean   isGameOver = (evalValue== WIN   || evalValue== LOSE   || evalValue== DRAW );   
    44.        if (beta<=alpha){   
    45.              return   evalValue;   
    46.       }   
    47.        if (depth==0 || isGameOver){   
    48.              return   evalValue;   
    49.       }   
    50.          
    51.        int   bestValue = - INFINITY ;   
    52.        for ( int   pos=0; pos<9; pos++){   
    53.                
    54.              if (board[pos]== empty ){   
    55.                    // try   
    56.                   board[pos] =   x ;   
    57.                      
    58.                    //   maximixing   
    59.                   bestValue = Math. max (bestValue, min(board, depth-1, Math. max (bestValue, alpha), beta));   
    60.                      
    61.                    // reset   
    62.                   board[pos] =   empty ;   
    63.             }   
    64.                
    65.       }   
    66.          
    67.        return   evalValue;   
    68.          
    69. }   
    70. /**  
    71.  * 对于'o',估值越小对其越有利  
    72.  */  
    73. public   int   min( char [] board,   int   depth,   int   alpha,   int   beta){   
    74.          
    75.        int   evalValue =   gameState (board);   
    76.          
    77.        boolean   isGameOver = (evalValue== WIN   || evalValue== LOSE   || evalValue== DRAW );   
    78.        if (alpha>=beta){   
    79.              return   evalValue;   
    80.       }   
    81.        // try   
    82.        if (depth==0 || isGameOver || alpha>=beta){   
    83.              return   evalValue;   
    84.       }   
    85.          
    86.        int   bestValue = + INFINITY ;   
    87.        for ( int   pos=0; pos<9; pos++){   
    88.                
    89.              if (board[pos]== empty ){   
    90.                    // try   
    91.                   board[pos] =   o ;   
    92.                      
    93.                    //   minimixing   
    94.                   bestValue = Math.min(bestValue, max(board, depth-1, alpha, Math.min(bestValue, beta)));   
    95.                      
    96.                    // reset   
    97.                   board[pos] =   empty ;   
    98.             }   
    99.                
    100.       }   
    101.          
    102.        return   evalValue;   
    103.          
    104. }   
    /**
     * 以'x'的角度来考虑的极小极大算法
     */
    public   int   minimax( char [] board,   int   depth){
           int [] bestMoves =   new   int [9];
           int   index = 0;
          
           int   bestValue = - INFINITY ;
           for ( int   pos=0; pos<9; pos++){
                
                 if (board[pos]== empty ){
                      board[pos] =   x ;
                      
                       int   value = min(board, depth, - INFINITY , + INFINITY );
                       if (value>bestValue){
                            bestValue = value;
                            index = 0;
                            bestMoves[index] = pos;
                      } else
                       if (value==bestValue){
                            index++;
                            bestMoves[index] = pos;
                      }
                      
                      board[pos] =   empty ;
                }
                
          }
          
           if (index>1){
                index = ( new   Random (System. currentTimeMillis ()).nextInt()>>>1)%index;
          }
           return   bestMoves[index];
          
    }
    /**
     * 对于'x',估值越大对其越有利
     */
    public   int   max( char [] board,   int   depth,   int   alpha,   int   beta){
          
           int   evalValue =   gameState (board);
          
           boolean   isGameOver = (evalValue== WIN   || evalValue== LOSE   || evalValue== DRAW );
           if (beta<=alpha){
                 return   evalValue;
          }
           if (depth==0 || isGameOver){
                 return   evalValue;
          }
          
           int   bestValue = - INFINITY ;
           for ( int   pos=0; pos<9; pos++){
                
                 if (board[pos]== empty ){
                       // try
                      board[pos] =   x ;
                      
                       //   maximixing
                      bestValue = Math. max (bestValue, min(board, depth-1, Math. max (bestValue, alpha), beta));
                      
                       // reset
                      board[pos] =   empty ;
                }
                
          }
          
           return   evalValue;
          
    }
    /**
     * 对于'o',估值越小对其越有利
     */
    public   int   min( char [] board,   int   depth,   int   alpha,   int   beta){
          
           int   evalValue =   gameState (board);
          
           boolean   isGameOver = (evalValue== WIN   || evalValue== LOSE   || evalValue== DRAW );
           if (alpha>=beta){
                 return   evalValue;
          }
           // try
           if (depth==0 || isGameOver || alpha>=beta){
                 return   evalValue;
          }
          
           int   bestValue = + INFINITY ;
           for ( int   pos=0; pos<9; pos++){
                
                 if (board[pos]== empty ){
                       // try
                      board[pos] =   o ;
                      
                       //   minimixing
                      bestValue = Math.min(bestValue, max(board, depth-1, alpha, Math.min(bestValue, beta)));
                      
                       // reset
                      board[pos] =   empty ;
                }
                
          }
          
           return   evalValue;
          
    } 
     
    *这里对极小极大算法的实现只是其中一种可行性,实际上可能会看到很多种不同的实现方式,但道理是一样的。

    使用开局库
    同时,你会发现,这样做视乎还不够,特别在一开局。我们都知道,中心的位置是最好的,但是按照我们上面的算法,第一步确实随机的...这在深度受限制的情况下就更显得重要了。于是就引申出了开局库的概念,这是我在某个讲象棋AI的网上看到的,就是给初始的棋盘设定一些格局。

    针对上面的例子,我们只要判断是否第一步棋,如果是则想办法让他选择中心的位置(4)。

    在WIKI百科中找到一幅图也能作为TIC-TAC-TOE开局库的参考:


     

    于是,估算函数会变成这样的(当然也可以在别的地方修改,只要合理):

     

    Java代码 复制代码 收藏代码
    1. //开局时,每个位置的估值   
    2. static   final   int []   INITIAL_POS_VALUE   = {   
    3.       323,   
    4.       242,   
    5.       323  
    6. };   
    7. /**  
    8.  * 估值函数,提供一个启发式的值,决定了游戏AI的高低  
    9.  */  
    10. public   int   gameState ( char []   board ) {   
    11.        int   result =   INPROGRESS ;   
    12.        boolean   isFull =   true ;   
    13.        int   sum = 0;   
    14.        int   index = 0;   
    15.        // is game over?   
    16.        for ( int   pos=0; pos<9; pos++){   
    17.              char   chess = board[pos];   
    18.              if ( empty ==chess){   
    19.                   isFull =   false ;   
    20.             } else {   
    21.                   sum += chess;   
    22.                   index = pos;   
    23.             }   
    24.       }   
    25.          
    26.        // 如果是初始状态,则使用开局库   
    27.        boolean   isInitial = (sum== x ||sum== o );   
    28.        if (isInitial){   
    29.              return   (sum== x ?1:-1)*INITIAL_POS_VALUE[index];   
    30.       }   
    31.          
    32.        // is Max win/lose?   
    33.        for ( int [] status :   WIN_STATUS ){   
    34.              char   chess = board[status[0]];   
    35.              if (chess== empty ){   
    36.                    break ;   
    37.             }   
    38.              int   i = 1;   
    39.              for (; i<status.length; i++){   
    40.                    if (board[status[i]]!=chess){   
    41.                          break ;   
    42.                   }   
    43.             }   
    44.              if (i==status.length){   
    45.                   result = chess== x   ?   WIN   :   LOSE ;   
    46.                    break ;   
    47.             }   
    48.       }   
    49.          
    50.        if (result!= WIN   & result!= LOSE ){   
    51.                
    52.              if (isFull){   
    53.                    // is draw   
    54.                   result =   DRAW ;   
    55.             } else {   
    56.                    // check double link   
    57.                    // finds[0]->'x', finds[1]->'o'   
    58.                    int [] finds =   new   int [2];   
    59.                    for ( int [] status :   WIN_STATUS ){   
    60.                          char   chess =   empty ;   
    61.                          boolean   hasEmpty =   false ;   
    62.                          int   count = 0;   
    63.                          for ( int   i=0; i<status.length; i++){   
    64.                                if (board[status[i]]== empty ){   
    65.                                     hasEmpty =   true ;   
    66.                               } else {   
    67.                                      if (chess== empty ){   
    68.                                           chess = board[status[i]];   
    69.                                     }   
    70.                                      if (board[status[i]]==chess){   
    71.                                           count++;   
    72.                                     }   
    73.                               }   
    74.                         }   
    75.                          if (hasEmpty && count>1){   
    76.                                if (chess== x ){   
    77.                                     finds[0]++;   
    78.                               } else {   
    79.                                     finds[1]++;   
    80.                               }   
    81.                         }   
    82.                   }   
    83.                      
    84.                    // check if two in one line   
    85.                    if (finds[1]>0){   
    86.                         result = - DOUBLE_LINK ;   
    87.                   } else  
    88.                    if (finds[0]>0){   
    89.                         result =   DOUBLE_LINK ;   
    90.                   }   
    91.                      
    92.             }   
    93.                
    94.       }   
    95.          
    96.        return   result;   
    97.          
    98. }   

    转载地址:http://univasity.iteye.com/blog/1170216

    展开全文
  • 极大极小值算法、α-β剪枝算法的理解

    万次阅读 多人点赞 2019-03-27 23:04:41
    定义:极大极小值算法(摘自百度百科) Minimax算法 又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)。通常以递归形式来实现。 ========================= 谈一下我的...
    1. 定义:极大极小值算法(摘自百度百科)
      Minimax算法 又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)。通常以递归形式来实现。

      =========================
      谈一下我的理解:
      刚开始看极大极小算法的时候,说实话并不是很理解。其实通俗的意思:既然是博弈,那必然要使自己的利益最大化,也就是想将自己分数得的尽可能的高,而对手是尽可能的去选取最小的,给我留下最不利的局面来选择

    2. 极大极小算法图解分析:
      在这里插入图片描述
      当然如果觉得我的图太少,可以转向这篇博客
      图解比较清晰

    3. 伪代码:

    //伪代码:A表示己方,B表示对方
    int MaxMin(int level, int curVal)
    {
        if (level == 0) return 该局面结点的估价值;
        int best;
        
        if(player == A){
            best = INT_MIN; //初始化最小值,之后才会更新取到更高分
            while(子树不空){
                int newval = MaxMin(level-1,best);
                if (newval > best)
                {
                    best = newval;
                }
            }
        }
        //player == B
        else{
            best = INT_MAX; //初始化最大值,之后才会更新取到更低的分留给对方
            while(子树不空){
                int newval = MaxMin(level-1,best);
                if (newval < best)
                {
                    best = newval;
                }
            }
        }
        return best;
    }
    

    但是我们发现最小最大值算法将所有的子树全部扫描,会很浪费时间和空间。
    所以就有了α-β剪枝算法的优化。下面谈一下我对α-β剪枝算法的理解,个人很菜,欢迎各位dalao及时指出错误~谢谢!

    二、α-β剪枝算法

    1. α-β剪枝算法的定义:(摘自百度百科)
      AlphaBeta剪枝算法是一个搜索算法旨在减少在其搜索树中,被极大极小算法评估的节点数。这是一个常用人机游戏对抗的搜索算法。它的基本思想是根据上一层已经得到的当前最优结果,决定目前的搜索是否要继续下去。

    2. 图解:
      其中α代表的是下界,β代表的是上界,即在(α,β)的范围内进行搜索
      初始值是(α,β)= (-∞,+∞)
      所以:
      (1)对手也就是player B负责更新上限,目的是使上限尽可能的小,留给 player A最不利的局面。
      (2)己方也就是player A负责更新下限,目的是使下限尽可能的大,保证最次的情况下也可以提高分数,留给自己最好的局面

      我的图解:
      在这里插入图片描述
      解释一下:对于level = 2 拥有的第一个方案,己方获利值为3,那么α=3,然后向下传递,现在选到2的,那么β = 2,目前存在α>β,则不需要再对这个节点及其子树进行遍历,因为player A根本不会在乎此方案会不会比β = 2小的数,虽然player B想去这个分支去寻找更小的数,但是player A压根不会理会,白白浪费空间,SO直接剪枝。

    有一张更详细的图解来自此篇博文
    在这里插入图片描述

    1. 伪代码:
    int AlphaBeta(int level,int CurVal)
    {
        int alpha = INT_MIN;
        int beta = INT_MAX;
        if(level == 0)  return 该局面结点的估价值;
    
        if(player == A){
            while(子树不空){
                int newval = AlphaBeta(level-1,alpha);
                if (newval > alpha){
                    alpha = newval;
                }
                if(alpha > beta)
                    return alpha;
            }
        }
        return alpha;
    
        else{
            while(子树不空){
                int newval = AlphaBeta(level-1,beta);
                if (newval < beta){
                    beta = newval;
            }
            if(alpha > beta)
                return beta;
            }
        }
        return beta;
    }
    

    参考博客:
    https://www.jianshu.com/p/3b464aeba078

    https://blog.csdn.net/u013351484/article/details/50789521#commentBox

    https://blog.csdn.net/UFv59to8/article/details/79331675

    展开全文
  • 五子棋AI算法第二篇-极大极小值搜索算法

    万次阅读 多人点赞 2016-02-02 18:17:02
    AI实现的基本思路-极大极小值搜索算法五子棋看起来有各种各样的走法,而实际上把每一步的走法展开,就是一颗巨大的博弈树。在这个树中,从根节点为0开始,奇数层表示电脑可能的走法,偶数层表示玩家可能的走法。假设...

    AI实现的基本思路-极大极小值搜索算法

    五子棋AI教程第二版发布啦,地址:https://github.com/lihongxun945/myblog/labels/%E4%BA%94%E5%AD%90%E6%A3%8BAI%E6%95%99%E7%A8%8B%E7%AC%AC%E4%BA%8C%E7%89%88

    当前这个是旧版教程,强烈建议阅读新版教程。

    五子棋看起来有各种各样的走法,而实际上把每一步的走法展开,就是一颗巨大的博弈树。在这个树中,从根节点为0开始,奇数层表示电脑可能的走法,偶数层表示玩家可能的走法。

    假设电脑先手,那么第一层就是电脑的所有可能的走法,第二层就是玩家的所有可能走法,以此类推。

    我们假设平均每一步有50种可能的走法,那么从根节点开始,往下面每一层的节点数量是上一层的 50被,假设我们进行4层思考,也就是电脑和玩家各走两步,那么这颗博弈树的最后一层的节点数为 50^4 = 625W 个。

    先不考虑这么多个节点需要多久能算出来。有了对博弈树的基本认识,我们就可以用递归来遍历这一棵树。

    那么我们如何才能知道哪一个分支的走法是最优的,我们就需要一个评估函数能对当前整个局势作出评估,返回一个分数。我们规定对电脑越有利,分数越大,对玩家越有利,分数越小,分数的起点是0。

    我们遍历这颗博弈树的时候就很明显知道该如何选择分支了:

    • 电脑走棋的层我们称为 MAX层,这一层电脑要保证自己利益最大化,那么就需要选分最高的节点。
    • 玩家走棋的层我们称为MIN层,这一层玩家要保证自己的利益最大化,那么就会选分最低的节点。

    这也就是极大极小值搜索算法的名称由来。直接盗一个图说明这个问题:

    极大极小值搜索树

    此图中甲是电脑,乙是玩家,那么在甲层的时候,总是选其中值最大的节点,乙层的时候,总是选其中最小的节点。

    而每一个节点的分数,都是由子节点决定的,因此我们对博弈树只能进行深度优先搜索而无法进行广度优先搜索。深度优先搜索用递归非常容易实现,然后主要工作其实是完成一个评估函数,这个函数需要对当前局势给出一个比较准确的评分。

    这篇博客讲的五子棋算法已经全部用JS实现并且是开源的,源码地址: https://github.com/lihongxun945/gobang ,预览地址: http://gobang.light7.cn/

    可以clone这个仓库,参考其中js目录下的源码。因为代码量不小,后面要讲的只是关键部分的代码实现,不会贴完整的代码。而且关键代码可能会省略部分实现,UI因为跟AI算法无关,也不会讲,请自行参考源码。

    我们下面来分部实现其中几个关键的部分。

    极大极小值搜索

    五子棋是一个15*15的棋盘,因为棋盘大小不会变动,所以目前来看用 15*15 的二维数组来存储,效果是最好的。

    极大极小值的搜索比较简单,就是一个DFS,直接上代码,看不懂的可以

    var maxmin = function(board, deep) {
      var best = MIN;
      var points = gen(board, deep);     //这个函数的作用是生成待选的列表,就是可以下子的空位。后面会讲这个方法。
    
      for(var i=0;i<points.length;i++) {
        var p = points[i];
        board[p[0]][p[1]] = R.com;     //尝试下一个子
        var v = min(board, deep-1);     //找最大值
        //如果跟之前的一个好,则把当前位子加入待选位子
        if(v == best) {
          bestPoints.push(p);
        }
        //找到一个更好的分,就把以前存的位子全部清除
        if(v > best) {
          best = v;
          bestPoints = [];
          bestPoints.push(p);
        }
        board[p[0]][p[1]] = R.empty;     //记得把尝试下的子移除
      }
      var result = bestPoints[Math.floor(bestPoints.length * Math.random())]; //在分数最高的几个位置中随机选择一个
      return result;
    }
    
    var min = function(board, deep) {
      var v = evaluate(board);     //重点来了,评价函数,这个函数返回的是对当前局势的估分。
      if(deep <= 0 || win(board)) {
        return v;
      }
    
      var best = MAX;
      var points = gen(board, deep);
    
      for(var i=0;i<points.length;i++) {
        var p = points[i];
        board[p[0]][p[1]] = R.hum;
        var v = max(board, deep-1);
        board[p[0]][p[1]] = R.empty;
        if(v < best ) {
          best = v;
        }
      }
      return best ;
    }
    
    var max = function(board, deep) {
      var v = evaluate(board);
      if(deep <= 0 || win(board)) {
        return v;
      }
    
      var best = MIN;
      var points = gen(board, deep);
    
      for(var i=0;i<points.length;i++) {
        var p = points[i];
        board[p[0]][p[1]] = R.com;
        var v = min(board, deep-1);
        board[p[0]][p[1]] = R.empty;
        if(v > best) {
          best = v;
        }
      }
      return best;
    }
    

    源码里面是有 Alpha Beta剪枝的,不过剪枝代码其实就几行,可以直接看源码,在 js/max-min.js 里面。

    评估函数

    在源码中 js/evaluate.js 就是评估函数,它接受一个二维数组,返回一个整型数。

    我们对五子棋的评分是简单的把棋盘上的各种连子的分值加起来得到的,对各种连子的基本评分规则如下:

    • 成五,100000
    • 活四, 10000
    • 活三 1000
    • 活二 100
    • 活一 10

    如果一侧被封死但是另一侧没有,则评分降一个档次,也就是死四和活三是相同的分

    • 死四, 1000
    • 死三 100
    • 死二 10

    score.js 中是对各种情况估值的定义。

    按照这个规则把棋盘上电脑的所有棋子打分,之和即为电脑的单方面得分 scoreComputer,然后对玩家的棋子同样打分 得到 scoreHuman

    scoreComputer - scoreHuman 即为当前局势的总分数。

    那么如何找出所有的连子呢,目前我的方式是先把二维的棋盘按照横竖撇捺四个方向变成N个一维数组,这个过程称为 flat。flat.js 是一个专门实现这个功能的模块。
    然后我们就可以对所有的一维数组进行得分计算。
    评分函数代码领比较大,请自行参考 evalute.js

    请注意,这里我们说的评估函数是对整个棋局的评估,后面讲启发式搜索的时候还会有一个启发式评估函数是对某一个位置的评估。这两个评估函数是不同的

    generator函数

    generator顾名思义,就是在每一步生成所有可以落子的点。并不是所有的空位我们又要搜索,很多位置明显不合适的我们可以直接排除。
    这个函数非常重要,是优化性能的关键。不过目前我们只做一个最简单的实现。就是把所有周围有邻居的空位认为是合适的位子。

    有邻居的定义是:想个两步以内至少有一个不为空的点即可。比如 b[7,7] 有一个子,那么 b[6,7]是他的邻居,b[5,7] 也是,但是 b[4,7] 就不是,因为相隔了三步。

    var gen = function(board, deep) {
    
      var neighbors = [];
      var nextNeighbors = [];
    
      for(var i=0;i<board.length;i++) {
        for(var j=0;j<board[i].length;j++) {
          if(board[i][j] == R.empty) {
            if(hasNeighbor(board, [i, j], 1, 1)) { //必须是有邻居的才行
                neighbors.push([i, j]);
            } else if(deep >= 2 && hasNeighbor(board, [i, j], 2, 2)) {
              nextNeighbors.push([i, j]);
            }
          }
        }
      }
      return  neighbors.concat(nextNeighbors)
    }
    

    这里做了一个简单的优化,就是按照邻居的远近做了一个排序,为什么要排序。后面讲AB剪枝的时候会讲到。排序对AB剪枝的效率起了决定性作用。

    另外一些简单的函数,没有列出,直接去看源码就行了

    下面我们将讲一个重点: Alpha Beta 剪枝算法。

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

    极大值,极小值算法

    1. 问题提出

    在中国象棋的人机对战模块的开发中,对于电脑如何选择下一步要走的棋时,首先很自然的想到要设立一个估值函数,然后暴力遍历所有可以移动的己方棋子以及每个棋子可以移动的目标位置,找到一个移动后估值函数值最大的移动方式。这里的估值函数最开始只是简单的为每颗棋子固定的设置不同的价值,然后用己方棋子价值之和减去对方棋子价值之和的最大值作为估值函数的返回值。这种方式效果很差,电脑在走的时候老是容易在原地打转,其实对比我们平常下棋就可以发现,我们在每走一步时,都会思考对方会怎么走,我们吃掉对方的一个棋子,会不会反而损失更多,总而言之,就是人会考虑多步,而我们只让电脑考虑了一步,那么就想到让电脑也考虑多步,可是要如何来实现呢?我们仔细分析一下,我们走棋(正常人下棋,不说高手)是要尽量可以吃掉对方的棋,然后让对方无法吃掉自己的棋,换句话说,就是我们选择时尽量得到最高的分,并且让对方得到尽量小的分,这就引出了极大值,极小值算法,在对方作出的所有对它自己价值大的选择中(意味着对己方价值小,或者为负)的选择中选择一个对自己价值最大的。

    2. 代码实现

    (1)需要考虑多少层
    (2)递归调用终止条件
    (3)求最大值(getMaxScore)和求最小值(getMinScore)函数中会调用getAllPossible函数,而这个函数会根据被谁调用内部会有不同的处理方式,因为求最大值相当于己方走一步棋,而求最小值相当于对方走一步棋(对于本项目,内部是根据该红棋走还是黑棋走返回对应的可能步骤)
    (4)在最顶层之上,还应该有一个函数getBestStep开始去调用getMaxScore函数,并传入初始层级(对于本项目,这个函数会返回一个表示最佳选择的step,而不是一个分数)
    (5)在本项目中,因为人走完一步后,电脑会立刻去计算它需要走的一步,如何考虑的层级较高,则会阻塞前端的渲染,解决方案为延时一点时间(使用定时器实现)再让电脑去计算(或者还可以考虑使用子线程)

    //step是代表一步棋
    int getMaxScore(int level)
    {
    	//层级为0,直接计算当前分数返回
    	if(level == 0) return calcScore();
    	vector<step*> steps;//存放所有可能的走法
    	getAllPossibleStep(steps);//获取所有可能的走法并放到steps中
    	//step * res;//保存返回值
    	int maxScore = int(1<<31);//保存最大分数
    	for(auto it = steps.begin(); it != steps.end(); it++)
    	{
    		step * cur = *it;
    		fakeMove(step);//尝试去走某一步
    		int score = getMinScore(level-1);//走完某一步后计算得分
    		unFakeMove(step);//把这一步退回来
    		if(score > maxScore)
    		{
    			maxScore = score;
    		}
    	}
    	return maxScore;
    }
    //取得最小分数函数和取得最大分数函数基本一样
    int getMinScore(int level)
    {
    	//层级为0,直接计算当前分返回
    	if(level == 0) return calcScore();
    	vector<step*> steps;//存放所有可能的走法
    	getAllPossibleStep(steps);//获取所有可能的走法并放到steps中
    	//step * res;//保存返回值
    	int minScore = int(~(1<<31));//保存最大分数
    	for(auto it = steps.begin(); it != steps.end(); it++)
    	{
    		step * cur = *it;
    		fakeMove(step);//尝试去走某一步
    		int score = getMaxScore(level-1);//走完某一步后计算得分
    		unFakeMove(step);//把这一步退回来
    		if(score < maxScore)
    		{
    			maxScore = score;
    		}
    	}
    	return minScore;
    }
    

    α-β剪枝优化

    1. 代码实现,注意和上面的代码进行比较(其实差别并不大)

    int getMaxScore(int level, int currentMin)
    {
    	//层级为0,直接计算当前分返回
    	if(level == 0) return calcScore();
    	vector<step*> steps;//存放所有可能的走法
    	getAllPossibleStep(steps);//获取所有可能的走法并放到steps中
    	//step * res;//保存返回值
    	int maxScore = int(1<<31);//保存最大分数
    	for(auto it = steps.begin(); it != steps.end(); it++)
    	{
    		step * cur = *it;
    		fakeMove(step);//尝试去走某一步
    		int score = getMinScore(level-1);//走完某一步后计算得分
    		unFakeMove(step);//把这一步退回来
    		//剪枝代码,注意等号(有没有等号对最后的选择出来的结果都是不可控的,因为处理
    		//各个情况的顺序无法控制,或者说无法确定得分相同的两种情况到底哪个好,所以
    		//使用等号反而会提高一些效率,
    		//因为我们在计算时棋子的类别并不多,这个分数很有可能相等)
    		if(score >= currentMin)
    		{
    			return score;
    		}
    		
    		if(score > maxScore)
    		{
    			maxScore = score;
    		}
    	}
    	return maxScore;
    }
    //取得最小分数函数和取得最大分数函数基本一样
    int getMinScore(int level, int currentMax)
    {
    	//层级为0,直接计算当前分返回
    	if(level == 0) return calcScore();
    	vector<step*> steps;//存放所有可能的走法
    	getAllPossibleStep(steps);//获取所有可能的走法并放到steps中
    	//step * res;//保存返回值
    	int minScore = int(~(1<<31));//保存最大分数
    	for(auto it = steps.begin(); it != steps.end(); it++)
    	{
    		step * cur = *it;
    		fakeMove(step);//尝试去走某一步
    		int score = getMaxScore(level-1);//走完某一步后计算得分
    		unFakeMove(step);//把这一步退回来
    		
    		if(score <= currentMax)
    		{
    			return socre;
    		}
    		
    		if(score < maxScore)
    		{
    			maxScore = score;
    		}
    	}
    	return minScore;
    }
    

    2. 代码分析

    相比较与未优化状态,只是多了一个参数,多了一个判断。为什么可以直接剪掉呢?
    首先,我们需要明确一点,对分数的计算是在最底那一层进行的(也就是level等与0的时候),就好比一个树的结构中的叶子节点,计算结果一层一层往上送,在送的过程中一层一层比较,未经剪枝的时候,所有的叶子节点都会被计算,然后往上送,进行比较,选出最大值或最小值继续往上送,直到递归起点,即获得所需的得分最好的走法。而剪枝剪掉的就是不必要的计算,因为这里的递归是一次到底后进行计算,然后回溯,再到底进行计算,这样的话,叶子节点的计算并没有连续进行,中间有一个回溯的过程。
    (1)在求最大值函数中调用求最小值和函数,向其中传入一个当前的最大值,在求最小值函数中,若得到下层送上来的某个分数小于传入的最大值,则可以肯定在求最小值函数中的下层递归求解过程可以被剪掉,因为求最小值函数返回的值肯定不会大于那个比传入的最大值小的值。
    (2)在求最小值函数中调用求最大值的函数,向其传入一个当前的最小值,在求最大值的函数中,若得到下层传上来的值大于传入的最小值,则可以肯定在求最大值函数中的下层递归求解过程可以被剪掉,因为要递交给上层求最小值函数一个自己的最大值,而这个最大值肯定不会小于那个比传入的最小值大的值,那么在求最小值的函数中肯定不会被使用。

    3.其他可优化点

    (1)若对当前层所有可能的情况以某种方式进行排序,使得可以更早的得到需要返回的值,那么在调用下一层时可以得到更好的剪枝效果。(具体的可以在求所有情况的函数中,遍历棋子的顺序作出调整,比如说车所有可以走的步先与兵所有可走的步放入下一步集合中,其实这个做的更细的话,应该结合估值函数来进行调整,有点像在中间层先简易的使用一下估值函数)。
    (2)对估值函数的优化,原程序中每个棋子设定固定的分值,其实在不同的局势下,棋子应该有不同的价值,对其进行调整,应该能得到更好的选择。
    (3)判断某个棋子是否可以移动到某个位置时用到的函数应该可以优化,以提高判断的效率,在获取所有可能步骤的时候,对于不同的棋子,可以确定它不能走到某个位置,那么可以直接过滤掉,而不是调用判断是否可以移动的函数,用填充的方法(而非遍历)去获取所有可能的移动步骤。

    展开全文
  • 这个评价函数应该从什么角度来写,极大值和极小值叶子节点的评价函数是不是需要评价角度不同? 如果AI方是极大者,按照极大值叶子节点评价极大者方的落子利益,值取正; 极小值叶子节点评价极小值方的落子效益,值取...
  • 极大极小值算法( Minimax algorithm) 在上文的博弈树中,如果我们令甲胜的局面值为1,乙胜的局面值为-1,而和局的值为0。当轮到甲走时,甲定会选择子节点值最大的走法:而轮到乙时,乙则会选择子节点值最小的...
  • 极小值极大值算法-井字棋

    千次阅读 2015-08-24 08:56:56
    极小值极大值算法写的井字棋: #include #include #define COM -1 #define MAN 1 #define STEP 9 #define DRAW 0 #define ROW 3 #define COL 3 #define MAX_NUM 1000; struct Move { int x; int y; }; ...
  • 由来 最近人工智能很火,经常有各种新闻,作为一个程序员多少要懂一点吧,未来万一用得着呢。...那就从最简单的五子棋游戏开始好了,用普通的规则实现一个电脑下棋的算法,姑且叫做AI算法。作为一...
  • max-min极大极小值算法就是考虑了博弈的算法。来看一个简单的例子在这个棋局中,电脑为白旗,白旗走哪一步更好呢,也许使用策略表会告诉你,应该冲4,但是冲4后,玩家就会连成4。这就是考虑了博弈之后,这一步棋就是...
  • 极小极大算法与负极大值算法

    千次阅读 2016-10-11 19:30:02
    1.极小极大算法(Minimax)  Minimax算法又名极小极大算法,是一种找出失败的最大可能性中的最小值的算法。Minimax算法常用于棋类等由两方较量的游戏和程序,这类程序由两个游戏者轮流,每次执行一个步骤。我们...
  • 从人落子开始到出现胜负...极大极小值搜索算法,来搜索(回溯)这个解空间:它假设人和电脑都是极其聪明的,他们都会选择出最优的一步。 但是搜索整棵树是不现实的,16*16!指数级,所以只回溯n步,即这个AI考虑的是N
  • 对人工智能中“极大极小值”的博弈算法的资料整理。
  • 极小极大值搜索算法MinimaxSearch 算法描述 极小极大值搜索算法,MinimaxSearch算法,是一种零和算法,是用来最小化对手的利益,最大化自己的利益的算法极小极大之搜索算法常用于棋类游戏等双方较量的游戏和程序...
  • 遗传算法求解极大值问题

    千次阅读 2018-01-01 16:20:26
    极大值问题假设有一个函数z=ysin(x)+xcos(y)z=ysin(x)+xcos(y),图形如下:这时要求这个函数在x位于[-10,10]和y位于[-10,10]之间的最大。这时想象这是个地形图,且这个地区无规律的放置很多人,有的在谷底,有的...
  • 先参考学习如下博文: ...参考图书《PC游戏编程(人机博弈)》极大极小值法深度搜索(dfs)伪代码/** 1。 p 为棋盘 2。 d 为规定的搜素最大深度,比如d层红方,d-1层为黑方,d-2层为红方
  • 1、非极大值抑制算法提出的目的  在目标检测中,为了消除多余的检测框,找到最佳的物体检测的位置。   2、 非极大值抑制(Non-Maximum Suppresion, NMS) 什么是非极大值抑制  非极大值抑制(Non-...
  • C语言实现极小极大搜索算法五子棋

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

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

    千次阅读 2018-07-26 11:49:30
    极大极小值搜索设计五子棋 源代码可在这里下载 摘要: 设计一个五子棋对战AI,使用极大极小值搜索,并使用α-β剪枝减少复杂度。采用启发式函数对整个棋局形式进行评估,并作为极大极小值搜索的依据。 一...
  • 极大极小算法原理

    2019-03-25 17:41:20
    算法的搜索策略是考虑双方若干步之后,从可能的步中选择相对较好的走发来走。 以MAX表示程序方,MIN表示对手方,P表示局势...(1) 轮到MIN走时,MAX应考虑最坏的情况,也即f(p)取极小的情况 (2) 轮到MAX走...
  • 极大极小搜索算法 minimax search

    千次阅读 2019-10-21 13:11:56
    对于node I,会选择的node M,node I的更新为0。再考虑第三层,单数层是我方行动。node F会选择I,J中值更的J,更新为5,G会选择K,L中值更的L,更新为8。依次一层层向上类推,可以得到最终结果为: ...
  • 极小极大算法 (The Minimax Algorithm)

    万次阅读 热门讨论 2014-04-04 11:01:13
    极小极大算法 (The Minimax Algorithm)[说明] 本文基于&lt;&lt;CS 161 Recitation Notes - The Minimax Algorithm&gt;&gt;, 本文中的图片均来源于此笔记。极小极大算法常用于二人博弈游戏,目的...
  • 极大极小算法和AlphaBeta剪枝算法学习总结

    万次阅读 多人点赞 2018-07-09 09:46:52
    1.极小极大算法 2.<<CS 161 Recitation Notes - The Minimax Algorithm>> 3.《PC游戏编程-人机博弈》-作者陈其,王小春 本文目录: 直观图解 伪代码 习题实战 适用范围:极小极大算法常用于零和...
  • 极小极大算法(The minimax algorithm)前面部分描述的技术适用于简单,完全可解决的游戏,如Nim(因为其所有的情况也不算大)。然而,随着游戏变得越来越复杂,很快就无法检查每一个可能的结果。例如,如果你试图...
  • 各位牛,朋友好,目前小白接触了一个问题,非常棘手,还望指导。 问题描述如下:我现在绘制了一个波形,并没有准确的函数去描述这个波形,但是却有着这个函数的横纵坐标每个点,现在想取得纵坐标最小的点(也就是...
  • 极大极小算法以及Alpha_beta剪枝 # python3 # author :李先生 # time :2018.10.28 # email :2452871021@qq.com class TicTacToe(object): ''' 井字棋游戏: player:当前落子玩家,-1代表AI,1代表人类 board:...
  • %% 初始化种群计算适应度 % 初始化种群 for i=1:sizepop %随机产生一个种群 individuals.chrom(i,:)=Code(lenchrom,bound); x=individuals.chrom(i,:); %计算适应度 individuals.fitness(i)=fun(x); %染色体...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 201,132
精华内容 80,452
关键字:

极大极小值算法