That Go Has a Winner

Go is finite, so for any starting board

we can build a tree of all possible configurations. This tree would have the empty board as root, all intermediate boards as internal nodes, and finished games as leaves. A board is put in as a child of another board if you can get from one to the other in one move. Note that a board configuration can show up multiple times in the tree, but never twice in any downward path from the root node to a leaf.⁴ Call this the move tree for

We can then say that player

can force a win on board

if no matter what the other player,

, does,

will always have choices that will result in winning the game.

Proof. Given an initial board

, construct the move tree. We can declare the forcible winner of a node where it is person

's turn to be

if the forcible winner of at least one child node is

and

otherwise. Nodes that have no children are leaves and represent finished games, so there we simply have the forced winner of that node be the winner of the finished game represented by that node.

This recursively defined forced winnerness will propagate up the tree until we know who wins every node, including the root node. The winner of the root node, player , can then force a win by always choosing the moves represented by transitions to child nodes that are marked with as their winner, and due to our definition of the forced winner of a node, there will always be at least one such transition and accompanying move. $\qedsymbol$

For a simple board we might actually be able to calculate the forced winner this way, by building the tree and recursing over it. This tree has a branching rate of around $\frac{1}{2}\vert V\vert$ , however, as you can play in almost any open space and there are lots of open spaces. Additionally, we have a depth on the order of $3^{\vert V\vert}$ . This gives a tree with around $(\frac{1}{2}\vert V\vert)^{3^{\vert V\vert}}$ nodes. In the standard board $\vert V\vert$ is

, so we're talking about an unmanageably large tree, of size $(\frac{1}{2} \times 19 \times 19)^{3^{19\times 19}}$ . I tried to find a scientific notation representation for this, to get an idea of its size, but this number is so tremendously huge that I was not able to calculate it on a computer.