[plt-scheme] Alpha-beta pruning

From: Hari Prashanth K R (krhari at ccs.neu.edu)
Date: Mon Nov 16 10:52:56 EST 2009

Well, then the simplest way to get the solution right and to debug your code would be to come up with examples and turn them into test cases(for each function if required)... I this way when a test fails you will know where the problem is and one can easily help you there... Without that it would be difficult I suppose... It might take you a little more time to come up with test cases than to just start coding but the practice would definitely help you in a long run... And if you have comments in the code, it would help people to understand your code and also its a better practice...

----- Original Message -----
From: "Shriram Krishnamurthi" <sk at cs.brown.edu>
To: "G G" <shaoron at gmail.com>
Cc: "PLT Scheme" <plt-scheme at list.cs.brown.edu>
Sent: Monday, November 16, 2009 8:05:56 AM GMT -05:00 US/Canada Eastern
Subject: Re: [plt-scheme] Alpha-beta pruning

You clearly have some type confusion, given that the algorithm on
paper and the algorithm in your program have different type
representations.  Without any form of documentation of this, it's not
surprising that you can't find the mismatch.  Can you at least
determine the mapping of the types in the algorithm to the types in
your program?

On Sun, Nov 15, 2009 at 11:02 PM, G G <shaoron at gmail.com> wrote:
> Well I guess yes.
>
> On Sun, Nov 15, 2009 at 9:38 PM, Shriram Krishnamurthi <sk at cs.brown.edu>
> wrote:
>>
>> Does your course prof not require you to write ANY data definitions,
>> templates, etc.?  You're allowed to turn in ONLY code and they give
>> you a full grade?
>>
>> Shriram
>>
>> On Sun, Nov 15, 2009 at 11:01 AM, G G <shaoron at gmail.com> wrote:
>> > Well I can attach the full .ss file here
>> >
>> > On Sun, Nov 15, 2009 at 4:48 PM, Shriram Krishnamurthi <sk at cs.brown.edu>
>> > wrote:
>> >>
>> >> I assume G forgot to reply to the list, so I'm taking the liberty of
>> >> replying there.
>> >>
>> >> I'll point out that this code still has no data definitions, examples
>> >> of data, test cases, etc.
>> >>
>> >> S.
>> >>
>> >> On Sat, Nov 14, 2009 at 11:25 PM, G G <shaoron at gmail.com> wrote:
>> >> > This is the orignal Minimax that I am trying to add Alpha-beta on
>> >> >
>> >> >
>> >> > (define minimax
>> >> >   (lambda (b player moves max-depth heuristic-function)
>> >> >     (define max/min
>> >> >       (lambda (player)
>> >> >         (if (eq? player 'W) max min)))
>> >> >     (define minimax-move
>> >> >       (lambda (b player max-depth move)
>> >> >         (minimax/depth
>> >> >           (apply-move b player move)
>> >> >           (opponent player)
>> >> >           (- max-depth 1))))
>> >> >     (define minimax/depth
>> >> >       (lambda (b player max-depth)
>> >> >         (if (= max-depth 0)
>> >> >             (heuristic-function b)
>> >> >             (let ([moves (possible-moves b player)])
>> >> >               (if (null? moves)
>> >> >                   (minimax/depth b (opponent player) (- max-depth 1))
>> >> >                   (let ([scores
>> >> >                          (map (lambda (move)
>> >> >                                 (minimax-move b player max-depth
>> >> > move))
>> >> >                               moves)])
>> >> >                     (apply (max/min player) scores)))))))
>> >> >     (let ([scores
>> >> >            (map (lambda (move) (minimax-move b player max-depth
>> >> > move))
>> >> >                 moves)])
>> >> >       (let ([best (apply (max/min player) scores)])
>> >> >         (let loop ([moves moves] [scores scores])
>> >> >           (if (= (car scores) best)
>> >> >               (car moves)
>> >> >               (loop (cdr moves) (cdr scores))))))))
>> >> >
>> >> >
>> >> > And I used the algorithm but i didnt know how to do these
>> >> >
>> >> > S ← Successors(n)
>> >> >
>> >> > best ← −∞
>> >> >> for all ni ∈ S do
>> >> >>   v ← −αβ(ni, d − 1, −β, −max(α, best))
>> >> >
>> >> >
>> >> > Thanks a lot,
>> >> > G
>> >> >
>> >> > On Sat, Nov 14, 2009 at 9:36 PM, Shriram Krishnamurthi
>> >> > <sk at cs.brown.edu>
>> >> > wrote:
>> >> >>
>> >> >> Sure, we'd be happy to help.  Where are your data definitions,
>> >> >> examples of data, and test cases?
>> >> >>
>> >> >> Shriram
>> >> >>
>> >> >> On Sat, Nov 14, 2009 at 12:00 PM, G G <shaoron at gmail.com> wrote:
>> >> >> > I am trying to implement the alpha beta pruning but with no luck
>> >> >> > can
>> >> >> > anyone
>> >> >> > help me with how it works I am trying to use this Algorithm
>> >> >> >
>> >> >> > αβ(n, d, α, β)
>> >> >> > S ← Successors(n)
>> >> >> > if d ≤ 0 ∨ S ≡ ∅ then
>> >> >> > return f(n)
>> >> >> > best ← −∞
>> >> >> > for all ni ∈ S do
>> >> >> >   v ← −αβ(ni, d − 1, −β, −max(α, best))
>> >> >> >    if    v > best    then
>> >> >> >     best ← v if    best ≥ β    then
>> >> >> >       return best
>> >> >> > return best
>> >> >> >
>> >> >> >
>> >> >> > Best regards,
>> >> >> > G
>> >> >> >
>> >> >> > _________________________________________________
>> >> >> >  For list-related administrative tasks:
>> >> >> >  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>> >> >> >
>> >> >> >
>> >> >
>> >> >
>> >
>> >
>> > _________________________________________________
>> >  For list-related administrative tasks:
>> >  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>> >
>> >
>
>
_________________________________________________
  For list-related administrative tasks:
  http://list.cs.brown.edu/mailman/listinfo/plt-scheme


Posted on the users mailing list.