通过递归折叠实现极小极大

Question

我正在为游戏的标准 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，在其中我会 return 一个启发式算法，我已经制作了一个函数来计算。我被卡住的地方是如何在移动后遍历每个可能的 GameState。我有一个函数可以计算可以从特定 GameState 做出的所有可能动作，但我一直在研究如何遍历所有这些动作，用应用每一个动作产生的新 GameState 调用 minimax。

回到伪代码，我知道 child 将是一个函数调用 applyMove，它接受一个 Move 和当前的 GameState，returns 一个 GameState 和新的件的放置。每个 "child" 都将是不同动作产生的不同 GameState。我是 Haskell 的新手，我知道我可能需要为此使用折叠。但是我只是停留在如何写它上，我找不到很多可以很容易地与我的情况联系起来的例子。非常感谢任何 advice/tips。

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

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

Answer 1

您已经拥有了一些功能：

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

我认为你的 minimax 使用不同的签名会更清晰：与其使用 Bool 来决定是最大化还是最小化，对于每种情况都有不同的情况，总是尝试最大化和变化更简单取而代之的是评估函数，通过在每一步翻转它的符号。

一旦你有了它，你真的不需要手动编写折叠：只需 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 return 一个元组，其中包含分数和到达那里所采取的着法，或类似的东西。

通过递归折叠实现极小极大

Implementing minimax by recursively folding

haskell

artificial-intelligence

fold

minimax