I'm trying to write a small LISP program that uses alpha-beta pruning. The
input to the program is a a list
eg:'((3 4)(2 9 6)) which represents a tree
* max
/ \
* * min
/ \ / | \
3 4 2 9 6 max
The program needs to process the input using the alpha-beta rules and
eventually return the number that would maximize the value for the player at
the top of the tree. In this case it would be 3.
I'm having a hard time figuring out the recursion and would appreciate any
suggestions!
Thanks,
Brian Cummins
···········@tamu.edu
Norvig describes and gives an implementation in his book Paradigms of AI
Programming.
Andrew
In article <············@news.tamu.edu>,
"Brian" <···········@tamu.edu> wrote:
> I'm trying to write a small LISP program that uses alpha-beta pruning.
The
> input to the program is a a list
> eg:'((3 4)(2 9 6)) which represents a tree
> * max
> / \
> * * min
> / \ / | \
> 3 4 2 9 6 max
> The program needs to process the input using the alpha-beta rules and
> eventually return the number that would maximize the value for the
player at
> the top of the tree. In this case it would be 3.
>
> I'm having a hard time figuring out the recursion and would appreciate
any
> suggestions!
>
> Thanks,
> Brian Cummins
> ···········@tamu.edu
>
>
Sent via Deja.com http://www.deja.com/
Before you buy.
"Brian" <···········@tamu.edu> writes:
> I'm trying to write a small LISP program that uses alpha-beta pruning. The
> input to the program is a a list
> eg:'((3 4)(2 9 6)) which represents a tree
> * max
> / \
> * * min
> / \ / | \
> 3 4 2 9 6 max
> The program needs to process the input using the alpha-beta rules and
> eventually return the number that would maximize the value for the player at
> the top of the tree. In this case it would be 3.
>
> I'm having a hard time figuring out the recursion and would appreciate any
> suggestions!
For starters, forget about Lisp code and visualize how YOU, a person
would go about solving the problem. It might help to figure this out
using the graphical tree structure.
Pay close attention to what you do at each stage. This allows you to
understand the underlying problem -- a prerequisite to writing the code
for solving it.
Once you have a grasp of the problem, design functions to handle parts
of the problem: For example, how do you compute the value for a min-ply
of the tree? For a max-ply? Start simply by considering the case of
just having numbers -- then generalize it to having either numbers or
additional tree structure. It is at the point where you introduce the
code to handle additional tree structure that recursion comes in.
Once you have the fundamental pieces, you can go about assembling them
into a complete solution.
The only tricky part of this assignment is that instead of having a
direct recursion and always doing the same thing on subparts of the
problem, you have to alternate what you do at each level.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
Brian Cummins wrote:
> I'm trying to write a small LISP program that uses alpha-beta pruning. The
> input to the program is a a list
> eg:'((3 4)(2 9 6)) which represents a tree
> * max
> / \
> * * min
> / \ / | \
> 3 4 2 9 6 max
> The program needs to process the input using the alpha-beta rules and
> eventually return the number that would maximize the value for the player at
> the top of the tree. In this case it would be 3.
>
> I'm having a hard time figuring out the recursion and would appreciate any
> suggestions!
1. This sounds like homework -- if it is, you could try asking
your teacher / professor / TA / supervisor / tutor / whatever.
2. You need one of three things.
- Not one but two mutually recursive procedures,
one for doing min-nodes and one for doing max-nodes.
- A single procedure that does, say, max-nodes,
and a way of making it do min-nodes too. (Hint:
max(a,b,c) = -min(-a,-b,-c).)
- A single procedure that checks whose move it is
and either maximises or minimises.
The first is most straightforward. The second will
produce the smallest program. The third is easiest for
explanatory purposes.
If this doesn't help, why don't you show us what you've tried?
It's a bit hard to diagnose a problem just stated as "I'm having
a hard time figuring out the recursion"...
--
Gareth McCaughan ················@pobox.com
sig under construction
Gareth wrote:
> ...if it is, you could try asking your ... TA...whatever.
TA? Is that Transactional Analysis? if so I think suggesting psychological help is
going a bit far, even if he is having a hard time...
Cheers,
;) will
William Deakin <········@pindar.com> wrote:
+---------------
| Gareth wrote:
| > ...if it is, you could try asking your ... TA...whatever.
|
| TA? Is that Transactional Analysis? if so I think suggesting
| psychological help is going a bit far, even if he is having a hard time...
+---------------
Well, given that the full context was:
...you could try asking
your teacher / professor / TA / supervisor / tutor / whatever...
I'd assume that "TA" == Teaching Assistant. Is that term unfamiliar to you?
-Rob
-----
Rob Warnock, 41L-955 ····@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. PP-ASEL-IA
Mountain View, CA 94043