From: mark@hpcvxmsr.cv.hp.com (Mark Rowe)
Subject: Re: complexity of go
Reply-To: mark@.cv.hp.com
Organization: UDT-CV (ITO)
Date: Thu, 10 Sep 1992 16:33:04 GMT

In article <1992Sep9.202419.1432@hpcvusn.cv.hp.com>, mark@hpcvxmsr.cv.hp.com (Mark Rowe) writes:
>In article <95620@bu.edu>, rohm@bucrf17.bu.edu (Ryan Rohm) writes:
>> To order of magnitude I propose that the total number of go positions is 
>> not too different from 3**(n*n), where n is the side-length of the board. 
>> That is, each spot on the board can be White, Black, or empty, and the 
>> constraints of being able to reach such a position do not change the estimate
>> substantially (so exponent could be n^2 or n^2 - c*n, hardly matters).
>> 
>> (Because players can `pass out` the game at any point, any legal position
>> is a possible final position, however illogical).
> 
> You are probably being much too liberal in numbering the go positions.
> Since any combination that has stones with 0 liberties is not a legal
> position, these must be eliminated.  I haven't looked at this closely,
> but I believe it to be a very significant number (even when we are
> talking orders of magnitude).

I have given this some more thought since posting the above response and
have concluded that the odds of any randomly generated position on a 19x19
board of being a legal position is less than 1 in 20.  My argument here is
not very rigorous; however consider the chance of a random configuration
having no dead stones.  If we only consider single stone death (as opposed
to groups of more than one stone) and we consider every stone to have four
liberties (not true for corners and sides) then we will arrive at a number
that is conservative at best and may greatly understate the probability of
a legal position; however, even with these constraints the chance of a
random position being legal is only 1 in 20 (computed as follows):

The chance that there is a dead stone at any given position is equal
to the chance that there is a stone at that position (2/3) times the
chance that each of the four adjacent positions has a stone of the
opposite color (1/3)^4.  This works out to (2/3)*(1/81)=.0082 and thus
the chance that the position is not dead is 1-.0082 or .9918.  With
361 positions on the board, the chance that all of them are not dead
is .9918^361=.0506

Thus even with these conservative constraints 19 out of 20 randomly
generated positions will be illegal.  It would not be difficult to
factor in accurate considerations of side and corner stones.  It
would be somewhat more difficult to accurately factor in dead pairs,
triples, etc.  (any takers) However, the above calculation should be
sufficient to show that randomly produced board states are not likely
to be legal.

BTW, I agree with Eric Hoffman's contention that the number of possible
positions on the Go board (legal or otherwise) is a very poor criterion
for measuring complexity of the game, and though I do believe that the
complexity will increase as the board size increases, I do not believe
this to be any simple relationship (linear, logarithmic, exponential, or
otherwise).

Mark Rowe             email: mark@hpcvlx.cv.hp.com
Hewlett Packard       voice: (503) 750-3246
Corvallis, OR         FAX:   (503) 750-3788