[plt-scheme] Alpha-beta pruning
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
> >> >
> >> >
> >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20091115/108dd198/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: reversi.ss
Type: application/octet-stream
Size: 7128 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20091115/108dd198/attachment.obj>