我正在创建一个简单的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步棋呢？我不是递归专家，感谢任何帮助！

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

回答：

这可以很容易地修改以考虑到N步棋，无论是递归还是迭代方式。

bestMove = function(Board board, piece piece, int lookAhead){ possibleMoves = getPossibleMoves(board, piece) bestMove = null bestScore = -INFINITY boardCp = clone(board)      for (move in possibleMoves) {    /* 只是原始代码 */     if(lookAhead <= 1) {         tempBoard = applyMove(boardCp, move)         if (tempBoard.score > bestScore)         {             bestMove = move             bestScore = tempBoard.score          }         boardCp = undoMove(tempBoard, move)     }     /* 递归，可以改成循环 */     else {        tempBoard = applyMove(boardCp, move)                // 应用        move2 = bestMove(tempBoard, piece, lookAhead-1)     // 深入并获取最佳移动         boardCp = undoMove(tempBoard, move)                 // (1) 检查它实际有多好        tempBoard = applyMove(boardCp, move2)        if (tempBoard.score > bestScore)         {             bestMove = move2             bestScore = tempBoard.score          }        boardCp = undoMove(tempBoard, move2)                // 通常我会重构这两个if-else路径并重用一些代码     }  }return bestMove}    

如果函数可以返回两个值，那么(1)将不是必要的 – 你需要移动和它的得分。

顺便问一下，你有阅读过关于极小极大、alfa-beta（带剪枝）算法的资料吗？