dear Robert, > The number G19 of legal games under a given go ruleset is unknown.
It will never be known since there's not enough space in the known universe to write it down. We're talking about a number with over 10^100 digits. > For positional > superko (prohibition of recreation of the same position after > completion of a move on the board), no passes, and no resignation, the > number of possible games is smaller than N^P19 The no-pass restriction makes this rather uninteresting. But actually, the same bound applies to games with passes, stated as Theorem 7 in our paper. Besides this upper bound, I can think of only two other numbers that are well defined and interesting, namely 1) the size of the smallest search tree that proves the perfect komi. and 2) same but for a full-width tree These are called the decision complexity and game tree complexity on https://en.wikipedia.org/wiki/Game_complexity#Decision_complexity It is reasonable to expect the perfect komi does not depend on games of more than 361 moves. Even with some ko fights, the ko recaptures are likely bounded by the number of unplayed points. The branching factor will be high though; let's put it at at most 200 on (geometric) average. Then we estimate the decision complexity to be upper bounded by 200^181 and the game tree complexity by 200^361. regards, -John _______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
