I am currently working on the question about writing a tic-tac-toe
playing game that uses minimax search to choose moves for the computer
by using alpha-beta pruning. Though i have an idea of how the algorithm
for this program will be, but i have difficulty of translating the
algorithm into common lisp. Could anybody give me some ideas on how to
do that? bcoz im a lisp beginner, not familiar with lisp yet. and
Thankx in advance!!!
the algorithm is as following:
function alphabeta(s, n, a, b):
;; recursively score a state s using evaluation
;; function f and an n-ply state space graph
if n=0 or s is a terminal node then {
if win position for machine then return ++
else if loss position for machine then return --
else if draw position then return()
else return f(s)}
else{ let bestscore = if program's move then a else b
for each successor state s' of s do{
let v = alphabeta(s', n-1, a, b)
if program's move then{
bestscore = max(v, bestscore)
a = bestscore
if a>= b then {
bestscore = b
prune any more successors of s}
}
else { bestscore = min(v, bestscore)
b = bestscore
if a >= b then{
bestscore = a
prune any more successors of s}
}
}
return bestscore}
In article <·················@hotmail.com>,
Mike Chu <······@hotmail.com> wrote:
>I am currently working on the question about writing a tic-tac-toe
>playing game that uses minimax search to choose moves for the computer
>by using alpha-beta pruning. Though i have an idea of how the algorithm
>for this program will be, but i have difficulty of translating the
>algorithm into common lisp. Could anybody give me some ideas on how to
>do that? bcoz im a lisp beginner, not familiar with lisp yet. and
It's been a while since I looked at the book, but I expect that Peter
Norvig's book "Paradigms of Artificial Intelligence using Lisp" would have
a chapter on this, with examples.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.