The following is an implementation of zero-window search (alpha-beta pruning
with a minimal window) for searching trees with integer leaves, and a driver
function for finding the minimax value. I admit to a number of false starts
before I got the logic right, but I attribute this to my obtuseness.
I think this qualifies as beautiful.
(defun zw (tree max alpha)
(if (numberp tree)
(eq max (>= tree alpha))
(loop for child in tree
thereis (not (zw child (not max) alpha)))))
(defun mtdf-zw (tree max guess)
(if (eq max (zw tree max guess))
(loop for v from (1+ guess)
while (eq max (zw tree max v))
finally return (1- v))
(loop for v downfrom (1- guess)
until (eq max (zw tree max v))
finally return v)))
Jim Bushnell
Jim Bushnell wrote:
> The following is an implementation of zero-window search (alpha-beta pruning
> with a minimal window) for searching trees with integer leaves, and a driver
> function for finding the minimax value. I admit to a number of false starts
> before I got the logic right, but I attribute this to my obtuseness.
>
> I think this qualifies as beautiful.
>
> (defun zw (tree max alpha)
> (if (numberp tree)
> (eq max (>= tree alpha))
> (loop for child in tree
> thereis (not (zw child (not max) alpha)))))
>
> (defun mtdf-zw (tree max guess)
> (if (eq max (zw tree max guess))
> (loop for v from (1+ guess)
> while (eq max (zw tree max v))
> finally return (1- v))
> (loop for v downfrom (1- guess)
> until (eq max (zw tree max v))
> finally return v)))
Don't you need a transposition table? Otherwise you're going
to be expanding the same nodes over and over again. ISTR
that the "M" in "MTD-F" stands for "memory"...
However: yes, it's very elegant. :-)
--
Gareth McCaughan
.sig under construc
"Gareth McCaughan" <················@pobox.com> wrote in message
···················@g.mccaughan.ntlworld.com...
> Jim Bushnell wrote:
>
> > The following is an implementation of zero-window search (alpha-beta
pruning
> > with a minimal window) for searching trees with integer leaves, and a
driver
> > function for finding the minimax value. I admit to a number of false
starts
> > before I got the logic right, but I attribute this to my obtuseness.
> >
> > I think this qualifies as beautiful.
> >
> > (defun zw (tree max alpha)
> > (if (numberp tree)
> > (eq max (>= tree alpha))
> > (loop for child in tree
> > thereis (not (zw child (not max) alpha)))))
> >
> > (defun mtdf-zw (tree max guess)
> > (if (eq max (zw tree max guess))
> > (loop for v from (1+ guess)
> > while (eq max (zw tree max v))
> > finally return (1- v))
> > (loop for v downfrom (1- guess)
> > until (eq max (zw tree max v))
> > finally return v)))
>
> Don't you need a transposition table? Otherwise you're going
> to be expanding the same nodes over and over again. ISTR
> that the "M" in "MTD-F" stands for "memory"...
>
> However: yes, it's very elegant. :-)
>
> --
> Gareth McCaughan
> .sig under construc
When the "tree" is really a tree, transposition tables don't buy anything
except for the evaluation of the leaves (in the code above, the leaves are
just integers, so evaluation of the leaves is minimal cost).
Most game "trees" are really directed acyclic graphs, and for these
transposition tables are essential.
Jim Bushnell
Jim Bushnell wrote:
>>> The following is an implementation of zero-window search
...
>> Don't you need a transposition table? Otherwise you're going
>> to be expanding the same nodes over and over again. ISTR
>> that the "M" in "MTD-F" stands for "memory"...
...
> When the "tree" is really a tree, transposition tables don't buy anything
> except for the evaluation of the leaves (in the code above, the leaves are
> just integers, so evaluation of the leaves is minimal cost).
>
> Most game "trees" are really directed acyclic graphs, and for these
> transposition tables are essential.
Indeed. I was assuming that the only reason for the formulation
in terms of nested lists was to avoid unnecessary clutter...
--
Gareth McCaughan
.sig under construc
"Jim Bushnell" <···········@comcast.net> writes:
> "Gareth McCaughan" <················@pobox.com> wrote in message
> ···················@g.mccaughan.ntlworld.com...
> > Jim Bushnell wrote:
> >
> > > I think this qualifies as beautiful.
It does, but I'm afraid you will find that it will be hard to keep it
beautiful when you start adding all the tricks and optimizations you
need if you want to create a competitive game-playing program.
I am the author of one of the strongest MTD(f)-based chess programs,
and the search code is big, complicated and ugly. The search in
itself is about 1000 lines of C code (the whole program is around
10,000 lines), and I'm afraid it wouldn't be much shorter in Lisp.
> > Don't you need a transposition table? Otherwise you're going
> > to be expanding the same nodes over and over again. ISTR
> > that the "M" in "MTD-F" stands for "memory"...
Yes. MTD(f) stands for "Memory-enhanced Test Driver with first guess
f".
> When the "tree" is really a tree, transposition tables don't buy anything
> except for the evaluation of the leaves (in the code above, the leaves are
> just integers, so evaluation of the leaves is minimal cost).
When using MTD, a transposition table buys you *a lot*, even if you
search a true tree. The whole point of MTD is that most of the
re-searches (especially those which fail high) are extremely cheap
because the many bounds found in previous searches enable you to make
a lot of transposition table cutoffs. Without a transposition table
(or some other data structure which allow you to store the upper and
lower bounds for all nodes in memory), a MTD(f) search is nowhere near
as efficient as a traditional alpha-beta search.
--
Tord Romstad
"Jim Bushnell" <···········@comcast.net> writes:
> The following is an implementation of zero-window search (alpha-beta pruning
> with a minimal window) for searching trees with integer leaves, and a driver
> function for finding the minimax value. I admit to a number of false starts
> before I got the logic right, but I attribute this to my obtuseness.
>
> I think this qualifies as beautiful.
>
> (defun zw (tree max alpha)
> (if (numberp tree)
> (eq max (>= tree alpha))
> (loop for child in tree
> thereis (not (zw child (not max) alpha)))))
>
> (defun mtdf-zw (tree max guess)
> (if (eq max (zw tree max guess))
> (loop for v from (1+ guess)
> while (eq max (zw tree max v))
> finally return (1- v))
> (loop for v downfrom (1- guess)
> until (eq max (zw tree max v))
> finally return v)))
I'm not a fan of loop, but the non-loop version is nice, too.
(defun zw (tree max alpha)
(if (numberp tree)
(eq max (>= tree alpha))
(notevery (lambda (child)
(zw child (not max) alpha))
tree)))
(defun mtdf-zw (tree max guess)
(if (eq max (zw tree max guess))
(do ((v (1+ guess) (1+ v)))
((not (eq max (zw tree max v))) (1- v)))
(do ((v (1- guess) (1- v)))
((eq max (zw tree max v)) v))))
I was hacking some game code a few months back and I didn't like the
way the iteration was duplicated in both the positive and negative
sense. Rather than do negamax, though, I passed in the min or max
function itself:
(defun minimax (tree min max)
(cond ((numberp tree) tree)
((null (cdr tree)) (minimax (car tree) max min))
(t (funcall max (minimax (car tree) max min)
(minimax (cdr tree) min max)))))
(defvar *test-tree* '((((3 1) (4 1)) ((5 9) (2 6)))
(((2 7) (1 8)) ((2 8) (1 8)))))
(minimax test-tree #'max #'min) => 6
(minimax test-tree #'min #'max) => 2
If we extend MAX and MIN to allow NIL values:
(defun my-max (left right)
(if (and right (< left right))
right
left))
(defun my-min (left right)
(if (and right (> left right))
right
left))
(defun minimax (tree min max)
(if (consp tree)
(funcall max (minimax (car tree) max min)
(minimax (cdr tree) min max))
tree))
The problem with this method is that it is a bit tricky to add
alpha-beta pruning because you need relational operations that depend
on whether you are minimizing or maximizing. You *could* test the
identity of the function:
(if (eq max #'max)
(> a b)
(<= a b))
but that was unaesthetic. I did it like this:
(defun m>= (max left right)
(= (funcall max left right) left))
(defun m<= (max left right)
(= (funcall max left right) right))
(defun m> (max left right)
(not (m<= max left right)))
(defun m< (max left right)
(not (m>= max left right)))
Now we can add alphabeta pruning:
(defun alphabeta (tree min max lower upper)
(if (numberp tree)
tree
(let ((this-branch (alphabeta (car tree) max min upper lower)))
(if (or (null (cdr tree))
(m>= max this-branch upper))
this-branch
(funcall max this-branch
(alphabeta (cdr tree)
min max
(funcall max this-branch lower) upper))))))
It isn't quite as pretty, though.
--
~jrm
Jim Bushnell wrote:
> The following is an implementation of zero-window search (alpha-beta pruning
> with a minimal window) for searching trees with integer leaves, and a driver
> function for finding the minimax value. I admit to a number of false starts
> before I got the logic right, but I attribute this to my obtuseness.
>
> I think this qualifies as beautiful.
>
> (defun zw (tree max alpha)
> (if (numberp tree)
> (eq max (>= tree alpha))
> (loop for child in tree
> thereis (not (zw child (not max) alpha)))))
Isn't the
thereis (not (zw child (not max) alpha)
equivalent to
never (zw child (not max) alpha)
?
Just nitpicking.
marco
"Marco Antoniotti" <·······@cs.nyu.edu> wrote in message
·······················@typhoon.nyu.edu...
>
>
> Jim Bushnell wrote:
>
> > The following is an implementation of zero-window search (alpha-beta
pruning
> > with a minimal window) for searching trees with integer leaves, and a
driver
> > function for finding the minimax value. I admit to a number of false
starts
> > before I got the logic right, but I attribute this to my obtuseness.
> >
> > I think this qualifies as beautiful.
> >
> > (defun zw (tree max alpha)
> > (if (numberp tree)
> > (eq max (>= tree alpha))
> > (loop for child in tree
> > thereis (not (zw child (not max) alpha)))))
>
> Isn't the
>
> thereis (not (zw child (not max) alpha)
>
> equivalent to
>
> never (zw child (not max) alpha)
>
> ?
>
> Just nitpicking.
>
> marco
>
I made the same error at first.
thereis (not (zw child (not max) alpha) returns t if any zw call returns nil
and nil if all return t
while
never (zw child (not max) alpha) returns nil if any zw call returns nil and
t if all return nil, so the sense is reversed. This could be fixed by
wrapping a not around the entire loop.
Jim Bushnell
Jim Bushnell wrote:
> "Marco Antoniotti" <·······@cs.nyu.edu> wrote in message
> ·······················@typhoon.nyu.edu...
>>>
>>>I think this qualifies as beautiful.
>>>
>>>(defun zw (tree max alpha)
>>> (if (numberp tree)
>>> (eq max (>= tree alpha))
>>> (loop for child in tree
>>> thereis (not (zw child (not max) alpha)))))
>>
>>Isn't the
>>
>>thereis (not (zw child (not max) alpha)
>>
>>equivalent to
>>
>>never (zw child (not max) alpha)
>>
>>?
>>
>>Just nitpicking.
>>
>>marco
>>
>
>
> I made the same error at first.
>
> thereis (not (zw child (not max) alpha) returns t if any zw call returns nil
> and nil if all return t
>
> while
>
> never (zw child (not max) alpha) returns nil if any zw call returns nil and
> t if all return nil, so the sense is reversed. This could be fixed by
> wrapping a not around the entire loop.
>
Ok. Understood.
Marco