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

["Mousheng Xu" <moushengxu@xxxxxxxxxxx>]

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