Re: computer-go: Alpha-Beta Search

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

Hi people,

Nullmove  is based on certain domain  specific assumptions that may or
may not apply to GO.  Since I am  very new at the  game, I don't claim
to know  whether it would work   for go, but  I think  it  might.  The
"assumption"  null move makes  is that  it  is ALWAYS (or very  nearly
always) better to  be on the move.   Or put another  way,  it is NEVER
good to  "pass."  How valid is this  assumption in GO?  In chess, it's
not  always correct,   but correct  enough  of the  time  to  be  very
effective.  But enough of the time must mean "nearly always."

Another aspect to null   move, that  may be  a  factor is   the actual
validity of the "null move test."  The null move test is a "null move"
followed by a reduced depth search.   The assumption is that this test
will  return a lower  bound that is  very UNLIKELY  to disagree with a
full  width   search   of this particular   subtree.   The   null move
assumption could very well be correct, and yet it's still possible the
"null   move test"    methodology  is  not.   Do  you   understand the
difference?  The point is that it's a question of resource management.
Does a null move followed by a reduced  depth search, save enough time
and   simultaneously provide a reliable    lower bound to the  current
context of  the search?   I would NEVER  make  this assumption but  we
should try  hard to get an  answer.  My best guess  is  that NULL MOVE
should work pretty well in GO, but I don't  claim to have any evidence
of this yet.  I haven't tried it!

By  the way, someone in  a previous email said you  need 3  ply to use
Alpha-beta.  This is not correct, you can get lot's  of cutoffs in a 2
ply search using alpha beta.
 

- Don

 

> At 09:31 AM 11/17/99 -0800, you wrote:
> > In my opininion we should be looking at Proof Number based searching.
> >
> >* I've one powerful weapon in my arsenal after learning alpha-beta
> >search. Now what is Proof Number?
> 
> skip that question and ask: what is nullmove. and get back to
> my previous email.
> 
> I feel that nullmove solved the selectivity problem in alfabeta.
> Searching all those unnecessary branches with alfabeta now is
> solved by nullmove.
> 
> >* Thanks.
> >-- Mousheng Xu
> 
> Vincent Diepeveen
> diep@xxxxxxxxxxxxxxxxx