[John.Tromp@xxxxxxxxxxxxxxxxx: Re: computer-go: How many bits are needed to encode an N x N Go position?]

[Don Dailey <drd@xxxxxxx>]

John is not getting to the go list, so I am forwarding this in his behalf.


------- Start of forwarded message -------
Date: Fri, 18 Oct 2002 14:41:25 +0200
From: John Tromp <John.Tromp@xxxxxxxxxxxxxxxxx>
To: Don Dailey <drd@xxxxxxxxxxxxxxxxx>
Subject: Re: computer-go: How many bits are needed to encode an N x N Go position?
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.2.5.1i
In-Reply-To: <200210172353.g9HNrv317710@xxxxxxxxxxxxxxxxx>; from drd@xxxxxxxxxxxxxxxxx on Thu, Oct 17, 2002 at 07:53:57PM -0400

dear Don,

I responded to the list a few times, but somehow they're not making it.
Perhaps you can relay this one for me.

> Just for  fun, there is another possible  complication.  It's possible
> that some  LEGAL positions cannot  be reached in  a real game  from an
> empty board.  I don't really know, but if that is the case, someone on
> this list  may be able  to construct an  example of a  legal positions
> that cannot be reached in a real game.

Any legal position can be reached just by playing its stones and passing
for the side with fewer stones. If you want to do it without passes, then
even the 2x2 position
 . .
 X X
is impossible to reach.

> My conclusion is  that the minimal number of  bits needed to represent
> all  positions accurately  in  N x  N go  may  be fewer  than what  is
> practical.
 
> P.S.  If someone  could come  up with  a  practical  way to  "map out"
>       illegal positions, then  it might also be possible  to throw out
>       huge classes of  positions that are legal, but  can be proved to
>       be irrelevant (for instance, easy  to "prove" it's a big win for
>       one  side or the  other.)  I'm  skeptical, but  it's an  idea to
>       think about.

For proving that white cannot live after

 . . . . .
 . . . . .
 . . X . .
 . . . . .
 . . . . .

one needn't do anything like an exhaustive search. It suffices to note that
white's 2nd move must be on one of the *s disregarding symmetry

 * * * . .
 * * * . .
 . a X b .
 . . . c .
 . . . . .

after which black can play at a. Subsequently black will take b unless white
goes there, in which case black will play c.
Black can kill white even if white is allowed to repeat any board position,
so the issue of ko can be avoided. Probably it will take a search of depth
only 10-16 more moves to check that black has secured 2 eyes while white
can no longer.

For solving arbitrary positions on 5x5, exhaustive search will be required.
Furthermore, a definite result requires use of some sort of superko rule,
which means that the whole history leading up to a position becomes
relevant, and just marking a single ko spot won't suffice. This is already
apparent in the 5x5 variations I explored at
http://www.cwi.nl/~tromp/java/go/go.html
In fact, some variations even depend on whether one uses positional or
situational superko!


I have classified the 3^25 5x5 positions as

414295148741 legal, 432993460702 illegal,
giving a probability 0.488966 of being legal.


regards,

%!PS                       %  -John Tromp (http://www.cwi.nl/~tromp/)
42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage
------- End of forwarded message -------