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

[Jean-Pierre Vesinet <jpvesinet@xxxxxxxxxx>]

Reducing the number of bits to encode a position is desirable in order to
save as much space as possible in a hashtable, but it should not be done at
the expense of the ease of mapping the value to the position.

> 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.

In a legal game every legal position is reachable. Now what is a real game?
If you count only games that are needed in order to compute perfect play,
many legal lines of play will be pruned out during search, because the
position is statically evaluable as a win for one side.

> 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.

Not putting these into the hashtable is the solution. When there is a fast
way to compute the game theoretic value of a position (or rather a situation
= position + next player + ko point), there is no need to store it in the
hashtable. Several classes of situations have this property. These
situations:
- are statically evalualuable as a win for one side (not difficult to code,
but not very fast),
- already have a symmetric / rotated / color-reversed situation in the
table,
- can be evaluated with a search of less than MaxN nodes (MaxN = 100 for
example). All MaxN nodes are situations already stored in the table.

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. 

Jean-Pierre