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

["Andrew Derrick Balsa" <andrebalsa@xxxxxxxxxxxxxxxxxx>]

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