Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Problem with minimax with alpha beta pruning (Maxim Frolov)
2. Lambda expression currying (Lawrence Bottorff)
3. Re: Lambda expression currying (Francesco Ariis)
4. Re: Problem with minimax with alpha beta pruning (Kim-Ee Yeoh)
----------------------------------------------------------------------
Message: 1
Date: Mon, 21 Dec 2020 16:00:51 +0000
From: Maxim Frolov <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Problem with minimax with alpha beta
pruning
Message-ID: <1da56b08-a73f-407e-881f-6de8c82df5ca@Spark>
Content-Type: text/plain; charset="utf-8"
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-0001.html>
------------------------------
Message: 2
Date: Mon, 21 Dec 2020 23:59:57 -0600
From: Lawrence Bottorff <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] Lambda expression currying
Message-ID:
<cafahfsv0hqs80c+81dacgcepeh10vrzb_vjdzwzyp9sf5u9...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Here's something from *Learn You... *
Lambdas are normally surrounded by parentheses unless we mean for them to
extend all the way to the right. Here's something interesting: due to the
way functions are curried by default, these two are equivalent:
addThree :: (Num a) => a -> a -> a -> a
addThree x y z = x + y + z
addThree :: (Num a) => a -> a -> a -> a
addThree = \x -> \y -> \z -> x + y + z
If we define a function like this, it's obvious why the type declaration is
what it is. There are three ->'s in both the type declaration and the
equation. But of course, the first way to write functions is far more
readable, the second one is pretty much a gimmick to illustrate currying.
So with the lambda version how exactly is the currying taking place? I
understand something like this
doubleDouble x = (\x -> x*2) (2 * x)
So with beta reduction we have (2*x)*2, then plug in the argument.
And with this
overwrite x = (\x -> (\x -> (\x -> x) 4) 3) 2
which gives (\x -> (\x -> 4) 3) 2
(\x -> 4) 2
4
But how is the beta reduction happening with addThree?
BTW, I flunked lambda calculus in Kindergarten.
LB
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20201221/17f9cc87/attachment-0001.html>
------------------------------
Message: 3
Date: Tue, 22 Dec 2020 07:54:46 +0100
From: Francesco Ariis <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Lambda expression currying
Message-ID: <20201222065446.GA20111@extensa>
Content-Type: text/plain; charset=utf-8
Hello Lawrence,
Il 21 dicembre 2020 alle 23:59 Lawrence Bottorff ha scritto:
> addThree :: (Num a) => a -> a -> a -> a
> addThree = \x -> \y -> \z -> x + y + z
> […]
>
> But how is the beta reduction happening with addThree?
Should be:
addThree = (\x -> \y -> \z -> x + y + z) 1 2 3
= (\y -> \z -> 1 + y + z) 2 3 beta
= (\z -> 1 + 2 + z) 3 beta
= 1 + 2 + 3 beta
= …
Does that make sense?
—F
------------------------------
Message: 4
Date: Tue, 22 Dec 2020 15:27:11 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Problem with minimax with alpha beta
pruning
Message-ID:
<capy+zdtzsbrn0ehm2yfixe2pfeaks6yzsfygw-ylspxbyh1...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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 <[email protected]>
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
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
--
-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20201222/d18ae15e/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 149, Issue 16
******************************************
