通过递归折叠实现极小化极大算法

Question

通过递归折叠实现极小化极大算法

haskellartificial-intelligencefoldminimax

3

我正在为标准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，它接受一个移动和当前GameState，并返回一个具有新位置的状态。每个“child”将是不同的GameState，是由不同的移动产生的。我对Haskell很陌生，我知道我可能需要使用fold。但我不知道如何编写它，并且很难找到与我的情况相符的示例。非常感谢任何建议或提示。

移动列表将类似于[[(1,2),(2,3)],[(3,6),(2,7)]]，GameState的child将是应用移动后的GameState，例如：applyMove [(1,2),(2,3)] gameState。

- MDS18

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amalloy · Accepted Answer

你已经有了几个函数：

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

我认为你的minimax函数在签名方面可以更简洁：不要使用布尔值来决定是最大化还是最小化，而是始终尝试最大化，并在每一步翻转评估函数的符号以实现最小化。

有了这个之后，你就不需要手动编写fold函数了：只需对每个合法的移动进行递归调用，并通过使用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返回一个包含得分和落子方式的元组，或类似的东西。