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

[Erik van der Werf <E.vanderWerf@xxxxxxxxxxxxx>]

As robert jasiek pointed out these numbers for storing the complete
state space are quite meaningless if we don't specify the rules. The
rules determine what information needs to be stored...

An alternative is to guess the length of the game, and the average
effective branching factor and use these numbers to estimate the
game-tree complexity. 

For example if we need to look ahead 28 ply on a 5x5 board with an
average effective branching factor of 3 solving the game requires
searching roughly 3^28 = 2,3 x 10^13 positions. At a speed of about 10^6
nps this takes about 265 days.

So yes, 5x5 can be solved.

Erik.



Second ones we know the rules 

Andrew Derrick Balsa wrote:
> 
> 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