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

[Don Dailey <drd@xxxxxxx>]

Woops, while working on drafts of  this email, I left out a qualifying
statement.  So this:

>  After 50  passes of  this algorithm,  you will  have a
>  table of all positions.

Should have been this:

  After 50  passes of  this algorithm,  you will  have a table of all
  positions that are within 50 moves away from the end of the game.

Don




   Date: Wed, 16 Oct 2002 08:41:18 -0400
   X-Authentication-Warning: bluerobin.lcs.mit.edu: drd set sender to drd@xxxxxxxxxxxxxxxxx using -f
   From: Don Dailey <drd@xxxxxxxxxxxxxxxxx>
   CC: computer-go@xxxxxxxxxxxxxxxxx
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx


   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