我正在为标准的8×8跳棋游戏编写一个AI。游戏状态通过一个包含棋盘上棋子坐标列表的镜头来表示。我试图遵循以下伪代码实现极小极大搜索算法。

function minimax(position, depth, maximizingPlayer)   if depth == 0 or game over in position        return static evaluation of position   if maximizingPlayer         maxEval = -infinity         for each child of position              eval = minimax(child, depth-1, False)              maxEval = max(maxEval, eval)         return maxEval   else           minEval = +infinity          for each child of position              eval = minimax(child, depth-1, true)              minEval = min(minEval, eval)         return minEval

根据我的理解，在我的情况下，position将是GameState。所以在我的程序中，我希望对GameState的所有子节点再次调用minimax，每个子节点将是一个应用了移动后的GameState。最终我会达到深度0，此时我会返回一个我已经编写函数来计算的启发式值。我卡在如何遍历每一步之后的所有可能的GameState。我有一个函数可以计算从特定GameState可以进行的所有可能移动，但我卡在如何遍历所有这些移动，并对每次移动应用后的新GameState调用minimax。

回到伪代码，我知道child将是一个函数调用applyMove，它接受一个移动和当前的GameState，并返回一个新的棋子位置的GameState。每个“子节点”将是不同移动后的不同GameState。我对Haskell还比较新手，我知道我可能需要使用折叠来实现这个。但我卡在如何编写它，我找不到很多我能轻松联系到我情况的例子。任何建议/提示都将不胜感激。

移动列表看起来像这样：[[(1,2),(2,3)],[(3,6),(2,7)]]，而GameState的一个child将是应用移动后的GameState，例如

applyMove [(1,2),(2,3)] gameState。

回答：

你已经有几个函数了：

legalMoves :: Position -> [Move]applyMove :: Position -> Move -> Position

我认为你的minimax函数如果使用不同的签名会更清晰：不是通过布尔值来决定是最大化还是最小化，而是通过不同的情况来处理，而是始终尝试最大化，并通过在每一步翻转评估函数的符号来改变评估函数。

一旦你有了这个，你就不需要手动编写折叠：只需对每个合法移动进行递归调用的映射，并使用maximum将它们粘合在一起，以找到当前玩家的最佳移动。

minimax :: (Position -> Int) -> Int -> Position -> Intminimax eval 0 pos = eval posminimax eval n pos = case legalMoves pos of  [] -> eval pos  moves -> maximum . map negate        . map (minimax (negate . eval) (n - 1) . applyMove pos)        $ moves

请注意，你的规格使得无法决定哪个移动是最佳的，只能决定通过最佳移动可以获得什么分数。要找到最佳移动，你需要让minimax返回一个包含分数和达到该分数的移动的元组，或者类似的结构。