Re: On Game Space Size

[Antti Huima <huima@xxxxxx>]

On Fri, 30 Apr 1999, Robert Jasiek wrote:

> Henrik Rydberg wrote:
> > Several people have during the last week or so been interested
> > in the question of how many legal states there are in Go space.
> > I guess the answer has been around for a long time, even.
> 
> If history is considered, then the used ko rules might
> influence the number of reachable positions / situations.
> However, if passes are part of the rules, then the following
> holds:
> 
> Proposition:
> If a position can be legally reached, then it can be reached by a 
> move-sequence without any removal.
> 
> Proof:
> Assume P is a position that can be legally reached. Now we can
> construct a move-sequence without any removal that creates P:
> Let black occupy the black intersections of P while white passes, (*)
> then let white occupy the white intersections of P while black passes.
> During this any white stone has and keeps a liberty since it also has a
> liberty in P; no black string is removed for the same reason. QED.
> 
> Corollary:
> An additional pass creates remaining situations for the same positions.
> 
> Note:
> Hence the set of legal situations is independent from ko rules.

Obviously, if the concept of `situation' does not include the ko-banned
intersections.

Otherwise there are more `situations' than there are `positions'. For
state-space search, one must consider `situations' whose number varies
depending on the ko-rule, although perhaps not significanty (mostly when
there are multiple ko's on the board).

-- 
Antti Huima
SSH Communications Security Oy