[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
>> >
>> >
>
>