Haskell Recursive Minimax Tree

Question

I'm trying to write a Tic Tac Toe program in Haskell, using the minimax algorithm. I constructed my own "Rose a" data type as follows:

data Rose a = a :> [Rose a]

This is the data type in which I want to 'store' my minimax tree. I understand how the minimax algorithm works, but can't seem to implement it in a recursive function.

minimax :: Player -> Rose Board -> Rose Int
minimax p (r :> [])   | hasWinner r == Just p              = 1  :> []
                      | hasWinner r == Just (nextPlayer p) = (-1) :> []
                      | otherwise                          = 0  :> []
minimax p (r :> rs)   = maximum(map root xs) :> xs
    where xs = map (minimax' (nextPlayer p)) rs

minimax' :: Player -> Rose Board -> Rose Int
minimax' p b@(r :> []) = minimax p b
minimax' p   (r :> rs) = minimum(map root xs) :> xs
    where xs = map (minimax p) rs

The "Player" is also a self-constructed data type, which can be of value P1 or P2. The "hasWinner" function checks if a given "Board" (data type which can hold a Tic Tac Toe board) has a winner, and returns either Maybe P1 or Maybe P2, or Nothing.

This "minimax" function I wrote is not giving me errors, but the result is not correct. Where is the flaw in my minimax implementation?

Answer 1

You aren't switching between the two players correctly. minimax' p b@(r :> []) = minimax p b is wrong. map (minimax p) rs in minimax' doesn't switch to the other player for the maximizing half.

I'd recommend writing this out explicitly for P1 (trying to maximize) and P2 (trying to minimize).

The endgame can assign the winner without caring about which player is currently playing

minimax :: Player -> Rose Board -> Rose Int
minimax p (r :> [])   | hasWinner r == Just P1 = 1    :> []
                      | hasWinner r == Just P2 = (-1) :> []
                      | otherwise              = 0    :> []

Player P1 is trying to maximize

minimax P1 (r :> rs) = maximum (map root xs) :> xs
    where xs = map (minimax (nextPlayer p)) rs

Player P2 is trying to minimize

minimax P2 (r :> rs) = minimum (map root xs) :> xs
    where xs = map (minimax (nextPlayer p)) rs