Alpha Beta prune for chess always returning the first move in the list
I am writing a minimax algorithm with alpha-beta pruning for chess and cannot get the algorithm to return anything but the first move that it generates. I have been knocking my head against but cannot figure out what is going wrong. The code is a bit messy and in dire need of refactoring, but maybe you can see something that I am not.
I have verified that my evalNaive' function works as expected (very simple, just evaluate the board based on material).
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) []
EDIT:
Definitions for some of my data types:
data Coord = Coord Int Int deriving (Eq)
data Move = Move Coord Coord deriving (Eq)
data Game = Game Board Flags Color deriving (Eq)
where Flags is a list of strings telling you things like for example white's queenside rook can castle, and Color is the color of whose turn it is.
EDIT2:
Here are the results of calling alphaBeta minus maxGame $, yielding the list of tuples containing scores and the moves that got them:
(A coordinate (x,y) is the x file and y rank)
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))]
As you can see, they are all coming back as 0. Knowing that evalNaive' works, the issue is somewhere in the recursive functions.
EDIT3: Ran the same code with a depth of 5 and got this list of potential moves:
[(-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))]
so it appears that the first move it encounters is the best as far as my algorithm can tell. Am I not going deep enough into the search tree to get anything meaningful?
链接地址: http://www.djcxy.com/p/56314.html