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

[Don Dailey <drd@xxxxxxx>]

No need to aplogize.

I am not aware if 5x5 has been solved or not, but I will say that it's
probably  possible,  certainly  not   easy,  with  todays  memory  and
hardware.  We are talking about a perfect solution.

It's one of those problems that people start thinking about just about
when the computing power makes it feasible to dream about solving.

Even though the search space is huge (huge is a term that is redefined
every couple of  years) retrograde analysis makes it  within the realm
of possibility.

The numbers have been posted, about 3^25 with further reductions based
on exploiting  sysmetries.  This is about about  200 billion positions
depending on how you count and what reduction tricks you use.  This is
already doable it terms of disk memory although it's more than most of
us have.   Most businesses have this  much and more  though and anyone
can buy this amount of space without breaking the bank if they want to
solve the problem.

Someone posted  about storing 1 bit  per position.  If the  goal is to
prove some assertion (such as first player always wins or first player
wins by 3 stones etc.) then even 1 bit is not quite enough.  You still
need another bit for workspace (it is necessary to flag positions that
have been  visited or scored.)  But  the final table could  be one bit
per position and that would give us a tidy reduction if all you needed
was 1 bit of information about each position.   

Retrograd analaysis  consists of "working backwards."   You start with
all possible go positions, find all  the legal ones that can be scored
as game  complete and keep the results  in this table.  Then  you do a
second pass, finding the remaining positions that can be scored with a
1 ply search leading to any of the already scored positions.  You keep
doing this  until you have seen  all positions in the  table.  This is
much faster than starting from the beginning of the game and doing one
giant  search.  After 50  passes of  this algorithm,  you will  have a
table of all positions.  Once you  had this table, you would have a go
program that  played perfectly from ANY  position with a  simple 1 ply
search.

There are  probably some  issues with Ko  that would require  a little
forethought.  Technically,  a position consists of more  than just the
exact board configuration and side to move because the game context is
somewhat game history dependent.

I also  suspsect that on a  fast PC with  200 gigs of disk  space, the
analysis  program  might take  many  weeks to  run,  but  it could  be
checkpointed and  done gradually.  Early  versions of the  table would
still be very useful for solving endgames.


Don





   Content-Disposition: inline
   Content-Type: text/plain; charset="iso-8859-1"
   Date: Wed, 16 Oct 2002 11:21:43 UT
   From: "Andrew Derrick Balsa" <andrebalsa@xxxxxxxxxxxxxxxxx>
   X-Epoch: 1034767308
   X-Sasl-enc: RiXqDGWPGMBPsJcOP+kJbg
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx

   Hi,

   I apologize for changing the subject, but in fact this is a follow-up
   question 
   to my previous one about the computability of 5 x 5 perfect play, from a 
   slightly different angle.

   In all the answers that were provided, I did not see any mention of a 
   theoretical obstacle. The main obstacle seems to be a practical one: the
   size 
   of the search space.

   This brings me to my present question:

   What is the minimum number of bits needed to encode a 5 x 5 Go position?
   And 
   generalizing, how many bits are needed to encode an N x N position?

   I would like to propose an answer. I am not sure it is correct (i.e. I am 
   almost sure it is incorrect!) and I would welcome the insights of others. 
   Let's add up the bits:

   First there is a term for the number of vertices, i.e. N x N. Since each 
   vertex can be empty, black or white, we also need to multiply N * N by a 
   constant, I believe this is log(3)/log(2). Am I correct here? As
   mentioned by 
   Weimin, there are the usual symmetries that reduce this search space, so
   we 
   deduct three bits (that is two bits for spacial symmetries and one bit
   for 
   the player color, am I correct?).

   We also need to encode who is to play (1 bit), and whether there is an
   active 
   ko (1 bit) and its position (log2(NxN) bits). Again, am I correct here?
   As 
   you can see, I have more doubts than answers.

   I do not believe there is any need to encode the scoring rules, so no
   bits are  
   needed for that. And I have thought about whether there is a need to
   encode 
   the number of captured stones by each side. I have reached the conclusion 
   that this is not needed, because it does not really affect how a perfect 
   player would play. I believe the perfect player will always play the same 
   best move in a given position, independent of how many stones each side
   has 
   captured. Once again, I may be wrong.

   So we have an upper bound of, for a 5 x 5 board:

   ((log(3) / log (2) ) * 25) - 3 + 2 + log2(25) = (rounding up) 44 bits

   And how many bits do we need to encode the perfect move itself ? I
   believe 
   that would be 1 bit for pass or play, plus log2(N x N) for the move
   itself. 
   For a 5 x 5 board, that is 6 bits (rounding up).

   The problem still seems within the practical limits of computability,
   IMHO.
   -- 
   Andrew D. Balsa
   andrebalsa@xxxxxxxxxxxxxxxxx

   -- 
   http://fastmail.fm/ - Consolidate POP email and Hotmail in one place