通过递归折叠实现minimax

Question

我正在为游戏的标准8 * 8草稿版本编写跳棋AI。该状态被表示为一个镜头，带有代表列表板上零件的坐标列表。我想做的是遵循此伪代码进行Min-Max搜索。

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。因此，在我的程序中，我想minimax再次调用的所有子元素，每个子GameState元素都只是一个GameState，并对其应用了一个招式。最终，我将达到深度0，在该深度中，我将返回一个启发式函数，该函数已进行计算。我受困的地方是如何在移动后迭代每个可能的GameState。我有一个函数可以计算特定GameState可以进行的所有可能动作，但是我仍然坚持如何遍历所有这些动作，并使用每个动作的应用产生的新GameState调用minimax。

回到伪代码，我知道这child将是一个函数调用applyMove，该函数 接受Move和当前的GameState，并返回带有新棋子位置的GameState。每个“孩子”将因不同的举动而成为不同的GameState。我对Haskell来说还很陌生，我知道我可能需要为此使用折叠。但是我只是坚持如何编写它，我找不到很多可以轻松地与自己的情况相关的示例。任何建议/提示将不胜感激。

这些举措名单将是这个样子：[[(1,2),(2,3)],[(3,6),(2,7)]]和child的GameState将是一招，如应用后的游戏状态

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

Answer 1

您已经有一些功能：

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

我认为您minimax可以使用不同的签名来变得更清洁：与其用布尔来决定是最大化还是最小化（每种情况都有不同的用例），总要尝试最大化并更改评估函数（通过将符号翻转到每一步。

一旦有了，您就不需要手动编写弃牌：只需map对每个合法举动进行递归调用，然后将它们粘合在一起，maximum以找到当前玩家的最佳举动。

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

请注意，您的规格使您无法决定什么动作是最好的，而只能决定通过做出最好的动作可以获得的分数。为了找到最好的举动，您需要minimax返回一个包含分数和达到该点的举动的元组，或类似的东西。