[plt-scheme] Alpha-beta pruning

From: Shriram Krishnamurthi (sk at cs.brown.edu)
Date: Sun Nov 15 13:38:29 EST 2009

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

Posted on the users mailing list.