0

我正在创建一个简单的 AI，它需要根据定义的策略规则评估董事会状态。游戏很像俄罗斯方块：你需要根据棋盘状态和下 N 个棋子的顺序（N 是一个变量）来决定当前的最佳移动。

换句话说，您必须使用片段队列中的第一块（例如具有多个“下一个”级别的俄罗斯方块）。

对于单步前进，这非常简单：

bestMove = function(Board board, piece piece)
{
     possibleMoves = getPossibleMoves(board, piece)
     bestMove = null
     bestScore = -INFINITY
     boardCp = clone(board)     

     for (move in possibleMoves)
     {
         tempBoard = applyMove(boardCp, move)
         if (tempBoard.score > bestScore)
         {
             bestMove = move
             bestScore = tempBoard.score
         }
         boardCp = undoMove(tempBoard, move)
     }

    return move
}

现在，我如何将这个算法推广到 N 个前进？我不是递归专家，所以感谢您的帮助！

PS：我使用的是 Java，但欢迎使用任何语言或伪代码！

4

4 回答 4

4

这可以很容易地修改以将 N 步提前考虑在内。以递归或迭代方式。

bestMove = function(Board board, piece piece, int lookAhead)
{
 possibleMoves = getPossibleMoves(board, piece)
 bestMove = null
 bestScore = -INFINITY
 boardCp = clone(board)     

 for (move in possibleMoves)
 {
    /* just the original code */
     if(lookAhead <= 1) {
         tempBoard = applyMove(boardCp, move)
         if (tempBoard.score > bestScore)
         {
             bestMove = move
             bestScore = tempBoard.score
          }
         boardCp = undoMove(tempBoard, move)
     }

     /* recursion, can be changed to a loop */
     else {
        tempBoard = applyMove(boardCp, move)                // apply
        move2 = bestMove(tempBoard, piece, lookAhead-1)     // dive and get best 
        boardCp = undoMove(tempBoard, move)                 // (1) check how good it actually is
        tempBoard = applyMove(boardCp, move2)
        if (tempBoard.score > bestScore)
         {
             bestMove = move2
             bestScore = tempBoard.score
          }
        boardCp = undoMove(tempBoard, move2)                // generaly I'd refactor both if-else paths and reuse some code
     }
  }

return bestMove
}

如果你可以从一个函数返回 2 个值，那么(1)就没有必要了——你需要移动和它的分数。

顺便提一句。您是否阅读过有关 min-max、alfa-beta（带有修剪）算法的信息？

于 2013-02-19T18:57:41.307 回答
1

纯递归算法。不知道你的下一个作品是如何组织的，所以在这里我使用了一个队列来假设。克隆不是最有效的，所以有点取决于你的数据结构。 

 function getBestPossibleScore(Board board, Queue<piece>nextPieces){
         if (nextPieces.isEmpty())
             return board.score;
         piece = piece.pop();
         possibleMoves = getPossibleMoves(board, piece)   

         bestScore = -INFINITY
         boardCp = clone(board)     

         for (move in possibleMoves)
         {
             tempBoard = applyMove(boardCp, move)
             curentScore = getBestPossibleScore(tempBoard,nextPieces.clone());
             if (currentScore > bestScore)
             {            
                 bestScore = currentScore
              }
             boardCp = undoMove(tempBoard, move)
          }

        return board.score+bestScore;
    }
     function getBestMove(Board board, Queue<piece> nextPieces)
        {

         piece = piece.pop();
         possibleMoves = getPossibleMoves(board, piece)   
         bestMove=null;
         bestScore = -INFINITY
         boardCp = clone(board)     

         for (move in possibleMoves)
         {
             tempBoard = applyMove(boardCp, move)
             currentScore = getBestPossibleScore(tempBoard,nextPieces.clone());
             if (currentScore > bestScore)
             {            
                 bestScore = currentScore
                 bestMove=move;
              }
             boardCp = undoMove(tempBoard, move)
          }

        return bestMove
        }
于 2013-02-19T19:17:23.897 回答
0

我帮不了你，但我可以向你推荐这个MinMax 算法，这是我在我的 AI 大学课程中使用的。

伪代码，如果有用的话：

function integer minimax(node, depth)
  if node is a terminal node or depth <= 0:
    return the heuristic value of node
  α = -∞
  for child in node:       # evaluation is identical for both players 
    α = max(α, -minimax(child, depth-1))
  return α

该算法资产对手尽其所能（基于评估函数）

于 2013-02-19T19:09:50.470 回答
0

对此采取伪代码方法。我的第一选择始终是带有 alpha beta pruning 的 minimax，因为它是解决与您类似的问题的常用且经过验证的方法。

但如果你想做一些不同的事情。

List moves = new list()
Best board = current board    

While (queue is not empty){
    grab the next item in the queue.
    Implement your algorithm.
    add the move to the move list.
    update the best board
}

不是最好的但非常简单的方法，然后为您提供基于队列的移动列表。您只需将棋盘状态从前一个最佳棋盘转移到算法棋盘元素中，然后将队列中的下一个棋盘状态转移到算法的片段参数中。

于 2013-02-19T19:38:00.703 回答