Re: computer-go: Re: Nullmove

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

I think everyone is missing the point  of null move selectivity.  I am
familiar  with the technique of analyzing  individual groups of stones
with  2  searches, one  from  whites point  of  view  and another from
blacks.  This is a powerful technique to  quickly determine if a group
is in critical danger for instance.  But this is not really "null move
pruning", which is something  different.  Null move pruning  is simply
another kind  of simple bounds  test and in  this context shouldn't be
viewed as anything  magic.  The  power of it  in chess  is that it  is
cheap (because of a reduction factor), it  is trivial to implement and
on top of this it is quite accurate as a bounds test.  It is in no way
the same as just doing two searches from the same position to the same
depth (or until some kind of termination.)  In my chess program I have
substituted "cheap  null move  bounds   testing" with other kinds   of
bounds testing with  good results, I view them  as a being pretty much
the  same  things,  only  implemented   differently.  All   good chess
programs use some kind of bounds testing but not necessarily NULL MOVE
PRUNING.  Rebel is an example of this.

But after  considering the nature  of  GO (to the   extent that my own
limited understand can take me)  I may be inclined  to agree with what
Dave is saying.   "Ignore this  threat at your  peril"  is exactly the
point, and since  I  believe GO to  be  closer to chess  endgames than
middlegames  with (relatively) few direct   threats and many long term
threats  looming (or "threats of  threats") the required reduced depth
search to make the test cheap may not do the job.

However, I really would like to hear some reports from people who have
actually tried  it.  I'm not sure the  nature of many GO programs lend
themselves very well to null  move pruning.  Probably you should start
with a basic full width search capable of doing at least 3 ply or more
and I'm not sure many programs are written this way, my own isn't.

Presumably,  a program  like this  would have a  good enough evaluator
that had some  abilities to  make  positional judgements  and  measure
degree's of threats.   If this is the  case, then an evaluator that is
reasonably  good might  work  well with  NULL MOVE  SELECTIVITY and is
worth a shot.  Really, the  point is that it's  fine to talk about it,
but I  am  not too eager  to  draw  a conclusion  in  either direction
without having a lot of experience with it.  Is there someone here who
does?

Most people think of null  move  selectivity as a tactical  technique,
but this  notion is in error  too.  Humans tend  to think  in terms of
tactics when thinking about algorithms like this, but NULL MOVE has no
problem discriminating between a tactical threat and a tiny positional
threat.  It   measures  threats of  ANY  magnitude.  It  is  better at
measuring  direct threats than  long  term threats, it doesn't  matter
what the magnitude of the threat is.

Based on Daves inuitions I am inclined to believe that it may not work
very well for GO.  Still, it should be explored, or has it already?

I  want to  avoid the trap  that I  think  happened in computer chess.
Common wisdom  dictated  a lot of  false  steps in computer  chess.  A
typical example is  that most people  thought a lot  about the problem
and decided  that computer chess  would require an extremely selective
highly intelligent deep searcher.  Those people  might still be right,
and yet sudden progress was made when people started relying on highly
optimized full width searching,  because they didn't initially realize
that  it  was  more important  to  be accurate  than  deep.  Once they
learned this  lesson they figured out  how to do  conservative pruning
later.  In a nutshell,  I think we should all  be skeptical of our own
intuitions, not to  ignore them but to take  them with a grain of salt
and let them gently guide us.  


- Don




> I agree with Dave:
> 
> At 02:01 PM 11/18/99 -0800, you wrote:
> >
> >
> >I think nullmove, while valid, is not all that useful for Go.  
> >The problem is that nullmove is useful only if it can give
> >a strong signal "ignore this threat at your peril".  This works
> >well for chess, where the refutation for most stupid moves is that
> >a piece gets captured.
> >
> >In Go, there is no strong signal in almost all cases, so nullmove
> >is not going to produce much useful information.
> >
> >In my problem solver, the standard way to run a problem is to run
> >it twice, once with "black moves first" and then with "white moves 
> >first".   Running black-first, then feeding the result of
> >that search into the white-first search, is roughly equivalent to nullmove.
> >
> >The upshot is that searching black-moves-frist first takes just as 
> >long as searching white-moves-first, and even when run to completion,
> >doesn't usually change the effort required to run the white search.
> >
> >There certainly is a space where nullmove-type tricks are useful, but
> >it's not a dramatic improvement.  The real problem is weak evaluators.