[plt-scheme] Alpha-beta pruning
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
>
>