I'm writing a checkers AI for a standard 8*8 drafts version of the game. The state is represented as a lens with lists of Coords representing the pieces on the board. What I am trying to do is follow this pseudo code for a Min-Max search.
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
By my understanding, in my case, position would be the GameState. So in my program, I would want to call minimax again on all children of the GameState, which would each just be a GameState with a move applied to it. Eventually I would hit depth 0 in which I would return a heuristic I have made a function to calculate. Where I am stuck is how to iterate through each possible GameState after a move. I have a function that calculates all possible moves that can be made from a specific GameState, but I'm stuck on how to iterate through all those moves, calling minimax with the new GameState resulting from the application of every one of the moves.
Going back to the pseudocode, I know that child will be a function call applyMove which takes in a Move and the current GameState, and returns a GameState with the new placement of pieces. Each "child" will be a different GameState resulting from different moves. I'm pretty new to Haskell and I know I'll probably need to use a fold for this. But I'm just stuck on how to write it, and I can't find many examples that I can easily relate to my situation. Any advice/tips are greatly appreciated.
The moves list would look something like this: [[(1,2),(2,3)],[(3,6),(2,7)]] and the child of a GameState would be a GameState after the application of a move, e.g
applyMove [(1,2),(2,3)] gameState.
You have a few functions already:
legalMoves :: Position -> [Move]
applyMove :: Position -> Move -> Position
I think your minimax would be cleaner with a different signature: instead of taking a Bool to decide whether to maximize or minimize, with different cases for each, it's simpler to always try to maximize, and vary the evaluation function instead, by flipping its sign at each step.
Once you have that, you don't really need to write a fold manually: just map recursive calls over each legal move, and glue them together with maximum to find the best move for the current player.
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
Note that your specification makes it impossible to decide what move is the best, only what score you could get by making the best move. To find the best move, you'll want to make minimax return a tuple containing both the score and the move made to get there, or something of that sort.