国际象棋的Alpha Beta修剪总是返回列表中的第一步
我正在写一个用于国际象棋的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则是它的轮回颜色。
EDIT2：
这里是调用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的作用，这个问题就在递归函数中。
编辑3：使用相同的代码，深度为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))]
所以看起来它所遇到的第一个移动是我的算法可以识别的最好的。 我是否深入搜索树以获取任何有意义的东西？
链接地址: http://www.djcxy.com/p/56313.html上一篇: Alpha Beta prune for chess always returning the first move in the list