[plt-scheme] Alpha-beta pruning

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