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

[Don Dailey <drd@xxxxxxx>]

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





   Date: Thu, 31 Oct 2002 12:13:58 +0900
   From: Darren Cook <darren@xxxxxxxxxxxxxxxxx>
   Content-Type: text/plain; charset="US-ASCII"
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx

   > why do you need to take account of all this awfully complicated
   > ko - stuff in your tablebases?

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

   Imagine you've a position ('A') that you've explored exhaustively and
   found it to be a 3pt win for black. Imagine there is a position B
   somewhere in the follow-up. There were no super-ko problems
   based on the game moves up to position A (i.e. B hadn't already appeared).

   So you store A=3 in your table.

   Now you come to A via another sequence of moves. You want to use value 3
   for this position and not have to search the follow-ups.

   But position B has already appeared prior to reaching A this time. So
   that value of '3' is invalid, and you need to search.

   So the problem is knowing when you're allowed to use the value in your
   table, and when you can't.

   One idea would be to store the list of optimum moves, along with the value.
   So when you want to use a match from the table, you quickly play out the
   unbranching sequence to make sure no super ko complaints, and if none
   then you accept the value.

   However I'm not sure that is reasonable - white might have played a
   different branch to exploit the fact that black can't move into position
   B.

   I'm sure you can exploit the nature of ko somehow here - e.g. as a first
   step store the maximum and minimum number of stones on the board in all
   positions that were looked at to justify the value of position A.

   If the minimum number is greater than the number of stones in any of the
   positions leading up to A, then the table value can be used. If not, you
   have to search. 

   I suspect tracking and storing min/max number of stones will not have
   that great an impact on performance.

   Darren