Re: computer-go: How many bits are needed to encode an N x N Go position?

[Erik van der Werf <E.vanderWerf@xxxxxxxxxxxxx>]

It is complicated. 

For your representation, if we use a Superko rule, many positions with a
different history (and possibly a different score) can be contracted in
to one. Even if you know all the points that are at that position
illegal due to (super)ko you can not expect to identify all differences
that may occur a few moves later. These differences are caused by the
history which is not in your representation. Alternatively if you don't
use superko, some games may never end...

Erik.



Mousheng Xu wrote:
> 
> Is it that complicated? 1 position on board is either b, or w, or empty or
> ko -- 4 different values, 2 bits. 5 x 5 = 25 positions, x 2 bits = 50 bits.
> 
> Maybe I am missing something.
> 
> -- m.x.
> >From: Jean-Pierre Vesinet <jpvesinet@xxxxxxxxxxxxxxxxx>
> >Reply-To: computer-go@xxxxxxxxxxxxxxxxx
> >To: "'computer-go@xxxxxxxxxxxxxxxxx'" <computer-go@xxxxxxxxxxxxxxxxx>
> >Subject: RE: computer-go: How many bits are needed to encode an N x N Go
> >position?
> >Date: Thu, 17 Oct 2002 16:10:29 +0200
> >
> >It is difficult to further diminish in practice ceil(log2(3^(N*N))) bits (=
> >40 for N=5).
> >- Eliminating illegal positions gets you another factor 2 for N=5 (only 49%
> >of the 3^25 positions are legal).
> >- Taking into account symmetry / rotations / color reversal to avoid
> >computing several times game values that you already have does divide
> >almost
> >by 16 the useful state space with komi 0 (some positions are already
> >symmetric).
> >
> >But there is no simple function to map between this reduced number and the
> >actual board state.
> >
> >We also need 1 bit for the next player and ceil(log2(N*N)) (=5 for N=5) for
> >a ko-forbidden point (basic ko rule).
> >
> >Regards,
> >
> >Jean-Pierre Vesinet
> 
> _________________________________________________________________
> Get faster connections -- switch to MSN Internet Access!
> http://resourcecenter.msn.com/access/plans/default.asp