在Haskell中应用带有折叠的递归函数

Question

我正在为游戏的标准8 * 8草稿版本编写跳棋AI。

type AiMove = GameState -> Move

data MoveType = Human | AI AiMove

type Coord = (Int, Int)
type Move = [Coord]

data Status = Red | Black | GameOver 
  deriving (Show, Eq)


data GameState =
  GameState { _blackPieces :: [Coord]
            , _redPieces :: [Coord]
            , _blackKings :: [Coord]
            , _redKings :: [Coord]
            , _status :: Status
            , _message :: String}
              deriving (Show, Eq)

makeLenses ''GameState


initialGameState :: GameState
initialGameState =
  GameState { _blackPieces = blackInit
            , _redPieces = redInit
            , _blackKings = []
            , _redKings = []
            , _status = Red
            , _message = ""} 

以上是我正在使用的所有数据类型。该状态被表示为一个镜头，带有代表列表板上零件的坐标列表。我要尝试的是遵循此伪代码进行最小-最大搜索。

   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在应用移动后将成为GameState，例如

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

我正在为游戏的标准8 * 8草稿版本编写跳棋AI。 AiMove = GameState->移动数据MoveType = Human | AI AiMove类型Coord =（Int，Int）类型Move = [Coord] data ...

Answer 1

您已经有一些功能：