[computer-go] Re: Scalability

[Don Dailey <drd@xxxxxxx>]

I think Don Beal (a computer chess researcher) once defined moves that
should be included in a quies search as moves which didn't change the
resulting static evaluation by more than some margin.    

This seems like an intelligent definition because it is tied directly
to the evaluator.  Different evaluation functions would have different
ideas of which moves are quiet.  In chess, any capture is clearly a
non-quiet move by this definition for almost any chess program.   

So you have a simple domain specific rule in chess, which automatically
applies to almost any reasonable evaluation function.

But how to do this in GO?  You could use a evaluation function
directly, using Don Beal's definition but I'm not sure it would work.
One of the things that makes capture searches work in chess is the
happy coincidence that captures are extremely self limiting.

>From your email, it occured to me that YOUR quiecence search could
simply be:  Add 1 ply to the leaf if the move resulting in the leaf
position increased the score by some margin.


- Don






   Date: Tue, 18 Jan 2005 14:46:48 +0100

   > -----Original Message-----
   > From: Don Dailey [mailto:drd@xxxxxxxxxxxxxxxxx]

   > But in each case, I got very chess-like improvements for increasing
   > the number of nodes searched.  I did most of these runs on 9x9 boards
   > but did one verify with a 19x19 board.  In short, any evaluation
   seemed to
   > scale.

   I can confirm that go scales with increasing search depth with a complex
   evaluation function as well.

   I did some experiment this summer using my 19x19 evaluation function on
   9x9 with traditional alfabeta search. I used 9x9 because the evaluation
   function seemed to be fast enough in order to search up to ply 6
   (playing games overnight). I tested different search depths against
   gnugo 3.4 and there was some clear scaling with increasing search depth.
   With my evaluation function there was a strong effect of odd/even search
   depth. With odd depth the program would play unreasonable moves (because
   it could always play some unreasonable attack as the last move). I did
   some attempts at implementing quiescence search to the program with some
   partial success. But Q-search is very hard to do in go (at least when
   you only spend a few hours on writing the code). If one want to have a
   very complex evaluation function as I do it might pay off to first think
   about the "Q-search problem" when designing the evaluation function.
   Since my evaluation function tries to accurately judge the stability of
   groups statically then any move causing a position where a groups safety
   is affected should be handled by a Q-search.

   So at least in principle traditional chess techniques work in go but
   since you only can search 2 ply with a complex evaluation function all
   the cool chess stuff such as null moves and transposition tables has no
   impact.

   --
   Magnus Persson
   Center for Adaptive Behavior and Cognition
   Tel: +49-(30)-82406-350
   Cell phone: +49 163 6639868


_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/