Upper Bounds

It would be nice to have some idea how long a game could be. We ought to be able to set some bounds on this.

Initial Upper Bound 1   No game of Go $(G_{cur}, S, P_b, P_w)$ can take more than $3^{\vert V\vert}$ moves, where $V$ is the set of verticies of $G_{cur}$ .

Proof. There are $\vert V\vert$ places on the board one could play, and each at all times contains a black piece, a white piece, or no piece. There are then $3^{\vert V\vert}$ distinct configurations for a Go board. Because of the coe rule, where the board can't ever look as it looked in the past, each of these $3^{\vert V\vert}$ configurations can appear no more than once. This limits us to $3^{\vert V\vert}$ moves. $\qedsymbol$

Unfortunately, this is not a very close upper bound. The coe rule applies after Lift has run, which means that while we would have counted the first two board positions below separately, they both reduce to the third one:

Any board in which some pieces should be lifted, then, is one that we don't want to be counting towards our number of games but are, and so we are over counting the maximum number of moves by a decent margin.

Unfortunately, without running an algorithm like our isSafe function, we don't have a way to tell if a board is going to reduce in the lifting process or not. This makes it hard to have a general idea of how much of an effect these reductions will have on the total number of distinct configurations. It is unlikely³ that we would be reducing by enough to take us out of the exponential range, so our theoretical upper bound on game length is order $3^{\vert V\vert}$ and hence exponential.

This upper bound, though, is fantastically large. On a 19 by 19 board we would have the bound on the order of $3^{19\times 19}$ , or $1.74\times 10^{172}$ . Games almost never go anywhere near that long. Unless people are learning the game or trying to make it last a long time, they almost never run out of pieces. As there are $\vert V\vert$ pieces in a typical Go set, we now have an (empirical) linear bound.