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?