Problem with minimax with alpha beta pruning

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Problem with minimax with alpha beta pruning

Maxim Frolov
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



_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Problem with minimax with alpha beta pruning

Kim-Ee Yeoh
Administrator
Hi Maxim,

The scope of this question falls outside this beginners list, which tends toward questions about haskell syntax (see other active thread).

You will typically find more response on the haskell-cafe list, which you might want to resend your query to.

On Mon, Dec 21, 2020 at 11:01 PM Maxim Frolov <[hidden email]> wrote:
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


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
--
-- Kim-Ee

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Problem with minimax with alpha beta pruning

Maxim Frolov
Got it. Thank you Kim-Ee!
On 22 Dec 2020, 08:28 +0000, Kim-Ee Yeoh <[hidden email]>, wrote:
Hi Maxim,

The scope of this question falls outside this beginners list, which tends toward questions about haskell syntax (see other active thread).

You will typically find more response on the haskell-cafe list, which you might want to resend your query to.

On Mon, Dec 21, 2020 at 11:01 PM Maxim Frolov <[hidden email]> wrote:
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


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
--
-- Kim-Ee
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners