[Haskell-beginners] Problem with minimax with alpha beta pruning
Maxim Frolov
maxim.frolov.07 at gmail.com
Mon Dec 21 16:00:51 UTC 2020
Hi All,
I am new to Haskell and got stuck while experimenting with minimax algorithm (tic-tac-toe game). Just for learning I am trying to avoid external modules and use only the standard Prelude library.
Here is the code snippet:
type Pos = (Int,Int)
-- Players are O (minimizing) and X (maximizing), B is for the draw (blank), I and J are used for -INF and +INF respectively
data Player = I | O | B | X | J
deriving (Eq, Ord, Show)
type Grid = [(Pos,Player)]
data Tree a = Node a [Tree a]
deriving Show
minimax :: Player -> Player -> Tree Grid -> Tree (Grid, Player)
minimax _ _ (Node g [])
| wins X g = Node (g,X) []
| wins O g = Node (g,O) []
| otherwise = Node (g,B) []
minimax a b (Node g ts)
| turn g == X =
let ts' = [minimax alpha b t | t <- ts, alpha < b]
ps = [p | Node (_,p) _ <- ts']
alpha = maximum (a:ps)
in Node (g, alpha) ts'
| turn g == O =
let ts' = [minimax a beta t | t <- ts, a < beta]
ps = [p | Node (_,p) _ <- ts']
beta = minimum (b:ps)
in Node (g, beta) ts'
The function call is like:
minimax I J tree
It looks like I got a recursion loop. Could someone advise how to approach the problem?
Thank you,
Max
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20201221/df961fe7/attachment.html>
More information about the Beginners
mailing list