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

[Don Dailey <drd@xxxxxxx>]

Yes, it is that complicated.  The  subject is how many bits are needed
to encode  an N x N  Go position.  You  are suggesting a way  that has
a few more bits than needed.

> Maybe I am missing something.

There are 2 issues you are  not addressing.  One is that rotations and
reflections of the  board can save a few  bits of representation.  The
other is that many positions  are illegal.  It's wasteful to represent
those positions.

Jean-Pierre correctly  observed that trying  to map out  those illegal
positions  is tricky.   Building a  mapping  table is  easy, but  more
expensive than just using the unmapped representation!  Another way is
computationally  expensive.    Compute  the  index  on   the  fly,  by
enumerating  and   testing  the  whole  space.   This   of  course  is
ridiculously expensive,  but tells  you how to  compute the  bit space
needed.  Simply walk every configuration and count the number of legal
positions.  You also need to account for all rotations and reflections
(no point in counting positions multiple times.)

I hope  I've convinced you that  it is more complicated  than it might
seem at first.

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.

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.

Don


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.




   X-Originating-IP: [149.2.141.4]
   From: "Mousheng Xu" <moushengxu@xxxxxxxxxxxxxxxxx>
   Date: Thu, 17 Oct 2002 09:47:44 -0700
   Content-Type: text/plain; format=flowed
   X-OriginalArrivalTime: 17 Oct 2002 16:47:44.0910 (UTC) FILETIME=[EAAB52E0:01C275FC]
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx

   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