1

我正在为国际象棋编写一个带有 alpha-beta 修剪的 minimax 算法，除了它生成的第一步之外，无法让算法返回任何内容。我一直在敲我的头，但无法弄清楚出了什么问题。代码有点乱，急需重构，但也许你能看到我没有看到的东西。

我已经验证了我的 evalNaive' 函数按预期工作（非常简单，只需根据材料评估板）。

alphaBeta :: Game -> Move
alphaBeta g = maxGame $ map (\mv -> (abMinNode 4 (-100) 100 (move g mv), mv)) (nextMoves g)
        where maxGame = snd . foldr foldingF (-100, Move (Coord 1 1) (Coord 1 1))
              foldingF x y = if fst x < fst y then y else x

abMaxNode :: Int -> Int -> Int -> Maybe Game -> Int
abMaxNode 0 a b (Just (Game brd _ trn)) = evalNaive' brd trn
abMaxNode d a b (Just g) = abMaxHelper d (-100) a b g $ nextMoves g

abMaxHelper :: Int -> Int -> Int -> Int -> Game -> [Move] -> Int
abMaxHelper d v a b g [] = v
abMaxHelper d v a b g (x:xs)
        | b <= newA = v
        | otherwise = abMaxHelper d newV newA b g xs
                where newV = max v (abMinNode (d - 1) a b (move g x))
                      newA = max a newV

abMinNode :: Int -> Int -> Int -> Maybe Game -> Int
abMinNode 0 a b (Just (Game brd _ trn)) = evalNaive' brd trn
abMinNode d a b (Just g) = abMinHelper d 100 a b g $ nextMoves g 

abMinHelper :: Int -> Int -> Int -> Int -> Game -> [Move] -> Int
abMinHelper d v a b g [] = v
abMinHelper d v a b g (x:xs)
        | newB <= a = v
        | otherwise = abMinHelper d newV a newB g xs
                where newV = min v (abMaxNode (d - 1) a b (move g x))
                      newB = min b newV


nextMoves :: Game -> [Move]
nextMoves g = filterLegal $ concatMap (possibleMoves g) allSpaces
        where filterLegal = foldr (\cur lst -> case move g cur of
                Nothing -> lst
                _ -> cur:lst) []

编辑：

我的一些数据类型的定义：

data Coord = Coord Int Int deriving (Eq)
data Move = Move Coord Coord deriving (Eq)
data Game = Game Board Flags Color deriving (Eq)

其中 Flags 是一个字符串列表，告诉你一些事情，例如白色的后翼车可以城堡，而 Color 是轮到谁的颜色。

编辑2：

下面是调用 alphaBeta 减去 maxGame $ 的结果，产生包含分数的元组列表和获得分数的移动：

（坐标 (x,y) 是 x 文件和 y 等级）

Just [(0,(1,7) => (1,6)),
      (0,(1,7) => (1,5)),
      (0,(2,7) => (2,6)),
      (0,(2,7) => (2,5)),
      (0,(2,8) => (1,6)),
      (0,(2,8) => (3,6)),
      (0,(3,7) => (3,6)),
      (0,(3,7) => (3,5)),
      (0,(4,7) => (4,6)),
      (0,(4,7) => (4,5)),
      (0,(5,7) => (5,6)),
      (0,(5,7) => (5,5)),
      (0,(6,7) => (6,6)),
      (0,(6,7) => (6,5)),
      (0,(7,7) => (7,6)),
      (0,(7,7) => (7,5)),
      (0,(7,8) => (6,6)),
      (0,(7,8) => (8,6)),
      (0,(8,7) => (8,6)),
      (0,(8,7) => (8,5))]

如您所见，它们都返回为 0。知道 evalNaive' 有效，问题出在递归函数的某个地方。

EDIT3：以 5 的深度运行相同的代码并获得以下潜在动作列表：

[(-1,(1,7) => (1,6)),
(-1,(1,7) => (1,5)),
(-1,(2,7) => (2,6)),
(-3,(2,7) => (2,5)),
(-3,(2,8) => (1,6)),
(-1,(2,8) => (3,6)),
(-1,(3,7) => (3,6)),
(-3,(3,7) => (3,5)),
(-1,(4,7) => (4,6)),
(-2,(4,7) => (4,5)),
(-1,(5,7) => (5,6)),
(-1,(5,7) => (5,5)),
(-1,(6,7) => (6,6)),
(-2,(6,7) => (6,5)),
(-1,(7,7) => (7,6)),
(-3,(7,7) => (7,5)),
(-1,(7,8) => (6,6)),
(-1,(7,8) => (8,6)),
(-1,(8,7) => (8,6)),
(-1,(8,7) => (8,5))]

因此，就我的算法而言，它遇到的第一步似乎是最好的。我是否没有深入到搜索树中以获得任何有意义的东西？

4

0 回答 0