Re: computer-go: 5x5 Go is solved?

[Don Dailey <drd@xxxxxxx>]

I forgot to add my footnote to my previous list post:

> Subsequent  passes, will perform  1 ply  searches from  each position,
> using the scores in other entries as it's leaf node evaluator (*).


* For each build pass, you must use scores from the previous pass,
  not the current pass.

Don



   Date: Thu, 31 Oct 2002 09:37:34 -0500
   X-Authentication-Warning: bluerobin.lcs.mit.edu: drd set sender to drd@xxxxxxxxxxxxxxxxx using -f
   From: Don Dailey <drd@xxxxxxxxxxxxxxxxx>
   CC: computer-go@xxxxxxxxxxxxxxxxx
   Reply-to: drd@xxxxxxxxxxxxxxxxx


   >  (here's my understand of the problem, for what it's worth, and then a
   >   possible solution)
   >   
   >   ...


   I think your understanding is correct.   


   However, I think it's possible to store a Ko-less table.  Tell me what
   you think:

   To build  a ko-less database, the  first pass of  the database builder
   will  simply traverse  every position  and score  it  statically using
   Tromp/Taylor  or  Chinese  scores.   For  each position  there  are  2
   entries, one for white  to move and one for black to  move.  A pass is
   always a legitimate move.

   Subsequent  passes, will perform  1 ply  searches from  each position,
   using the scores in other entries as it's leaf node evaluator (*).

   Each pass of the build procedure will propogate correct values to some
   of the  table entries.  The positions  nearest the end of  the game of
   course  will   propogate  first.   When  "enough"   passes  have  been
   completed, the full table will emerge.

   Here is  the interesting part.  There  will be a few  positions in the
   table that will never get to  a stable value, they will fluctuate from
   pass  to  pass  or  perhaps   in  cycles.   These  few  positions  are
   interesting, and I  believe what they all have in  common is that they
   are dependent  on KO cycles where  BOTH players prefer  that the other
   player breaks the ko cycle.

   The interesting question is how many stable positions will emerge? For
   instance, it may  be that very few positions are  stable, or that most
   positions are stable.  If the opening position is stable, then we have
   a proof for  the opening position and know we  can navigate around any
   ko situations that exist.

   The main  point is that  all unstable positions  have to be  marked as
   invalid in the database and the  solver that uses the database will do
   a very shallow search using whatever KO rules it wants to, it only has
   to get to leaf nodes that are stable.


   Don