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

[Don Dailey <drd@xxxxxxx>]

Hi Jean-Pierre,

Interesting discussion!    

> With these optimisations a hashtable of less than 1 GB, resident in memory
> to completely avoid disk I/O, may be sufficient to solve 5x5 Go in a
> reasonable time.

You are  very optimistic!  I don't  believe doing a  search, even with
alpha/beta  pruning and  only 25  intersections will  solve this  in a
reasonable amount  of time.  Alpha/beta pruning does  indeed prune out
most of  the tree,  and a big  transposition table vastly  reduces the
redundant pathways  that must be  traversed.  But this is  not enough.

An  alpha  beta search  would  be  completely  dominated by  the  high
branching  factor  of the  early  part of  the  search  tree, and  the
branching factor is  about 25.  With all the  tricks of alpha/beta and
hash tables, the  branching factor will still be at  least 3, and that
gets out  of hand very quickly.   Other little tricks  and tweaks will
help, but you are well past the point of diminishing returns.

I have  a fast program  and tested this  approach a long time  ago for
small boards.   I don't have  1 GB of  memory, but my  observation was
that it took a few minutes of  search just to utilize the hash table I
did have. In other words, the hash table was not filling up so quickly
that you would  see dramatic results by throwing a  lot more memory at
it.  An infinite  size hash table would not  make the problem solvable
in a reasonable time with current hardware.

Also, hash tables are very expensive  in one sense.  The kind of table
you are refering  to requires you to store the whole  Go board in each
entry (or  at least  many bits of  checksum.)  That's  very expensive.
The scheme  I proposed makes the  position itself be the  key of "hash
table", so no  type of collision detection is  necessary and the entry
size can be just one or  2 bits, depending on how much information you
want to capture.   (You can put number  of moves to a win  or loss, 
the final results, or you can  store 1 bit representing
whether some goal was achieved.)

This  is not  a  direct  search problem  (yet.)   It needs  retrograde
analysis.  The beauty of this, is  that once you build this table, the
solution (or  score) or  every position is  readily available  for all
time.

However, and I'm not claiming otherwise, it might be the case that the
number of illegal  positions is (at least) 2  orders of magnitude more
than the  number of  legal positions.  In  this case, you  would still
have to use  retrograde analysis, but you might find  that it is still
cheaper in  terms of  memory usage to  use the  very fat entries  of a
conventional hash table.  Unfortunately, I believe retrograde analysis
requires you  to store  every legal position.   The only way  to cheat
this requirement  that I  am aware of,  is to find  "fully admissible"
heuristics that determine the result  of some subset of the positions.
These heuristics can be used in place of actual table entries.

If  you  are willing  to  cheat  even more,  you  could  thow out  the
admisibility  requirement and get  further big  savings, but  then you
have nothing to show for it except perhaps a 5 x 5 Go program that may
or may not play incredibly well (but not provably perfect.)

I have been  thinking about doing retrograde analysis with  5 x 5, but
I'm starting to think it's still  too big a problem.  In principle, we
could do it with  200 gig of disk space (I think),  but disk memory is
incredibly  slow and  this  problem wouldn't  be  very cache  friendly
either!  I think it would take several days per pass, and I don't know
how many moves are required to solve the game, which is related to the
number of passes of the algorithm  are required.  I think this is more
or less equivalent to the shortest path to all legal positions and I'm
thinking its around  50 moves because it takes up to  50 moves to fill
the board if one side constantly passes.

If anyone is  interested in this, we need to start  by reading all the
papers on what's been done so far with smaller boards and then attempt
a feasibility study.   I'm tempted to write the  program now and apply
it to 3 x 3 as a warmup exercise.


Don