[computer-go] Re: Scalability

[Don Dailey <drd@xxxxxxx>]

>  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.

Yes, it seems so.  But I'm not even sure what the term "quiescence
search" really means in Go.  It is really an ambigious term to
describe a kind of "selectivity done just before leaf nodes."

Here is my (take with a grain of salt) analysis and definition of
quiescence search might be:

In chess it's clearly understood to be (mostly) a playout of captures
after what would normally be considered a leaf node.  But it's
combined with this strange concept of "stand pat", where each side has
the option to simply stop and accept the current static evaluator or
try to do better by playing a capture.  So it's a strange kind of
search pasted on to the end of a normal search.

So I think I would make the generality that a quiesence search is any
tree expansion technique designed to quickly get to a position where a
global evaluation function can do a better job.  I'm thinking local
life and death tactics also have nothing to do with a proper
quiescence search, it's really part of a static evaluation which
happens to have a search component and doesn't drive the global board
to a quiet position.

In GO, it can't work just like a chess Q-search.  First of all, what
kind of move would be the equivalent of the capture move?  The capture
of a group or chain?  There is not that much point in playing out
"capture sequences" in go, they mostly don't exist as complicated
interactions like in chess.  You don't "capture a group" and then need
a search to see if it can be recaptured (although this can happen, it
doesn't seem like it should be the driving goal behind an expensive
quies search in Go.)

You could of course look for trivial ladders and consider atari AND
capture moves, but this is ridiculously expensive and doesn't have the
self limiting characteristics of captures in chess unless you focus on
them one at a time (which Go programs do.)  The equivalent in chess
might be like looking at all captures and threats of captures and even
in chess that is prohibitive.

A quiescence search in GO COULD be a limited set of moves which get
expanded very late in the tree to aid a global evaluator (which may or 
may not happen to have it's own localized searches) to return more 
accurate scores.    

Are some of you guys using such a search in your GO programs?  I'm not
talking about the highly localized life/death searches which isn't in
the spirit of giving a quiet board.

- 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/