java - 推广移动搜索算法以使用递归

Question

我正在创建一个需要评估棋盘状态的简单 AI 根据定义的策略规则。游戏很像俄罗斯方 block : 您需要根据棋盘状态和 接下来的 N 个片段的顺序(N 是一个变量)。

换句话说，你必须使用 piece-queue 中的第一个 piece(就像俄罗斯方 block 有多个 “下一个”级别)。

对于向前一步，这很简单:

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，但欢迎使用任何语言或伪代码!

Answer 1

这可以很容易地修改以考虑 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(带修剪)算法？