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

[stefanmertin@xxxxxxxxxxx (Stefan Mertin)]

Don Dailey wrote:
> Hi Jean-Pierre,
> Interesting discussion!    

indeed!

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

Yes, that would correspond a lot more to my idea of a "solved" 5x5 GO:
a huge database with all the possible positions (3^25 for 5x5),
in which only for the relevant (legal) positions
an information is stored 
e.g. 1 byte = 2 (W or B to play next) * 4 bits (final result:
     0 = net yet computed
     1 = -7 or worse for Black
     ...
     8 = jigo
     ...
     15= +7 or better for Black)

I even would think, that we may easily get rid of the whole 
awfully difficult KO-complex! We just only store positions WITHOUT
any KO-forbidden points! I think we just donīt need them in our database:
We only handle with the KO-problems in the games that occur.
After every KO comes a move that makes a position without a KO-forbidden
point! If this position is stored in our database with a correct result,
what do we need else...

BUT... How long would a program take to fill in all the values for
every position = for every move
that may occur in rational games?

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

sic!  :-)

> I'm tempted to write the  program now and apply
> it to 3 x 3 as a warmup exercise.>
> Don

Perhaps 
   3 x 5 (3^15 =    14.348.907),
   4 x 4 (3^16 =    43.346.721) or even
   4 x 5 (3^20 = 3.486.784.401)
should allready be possible with todays hardware!?


Stefan