Journal of the
Korean Mathematical Society JKMS

Go is an ancient game of great complexity and has a huge following in East Asia. It is also very rich mathematically, and can be played on any graph, although it is usually played on a square lattice. As with any game, one of the most fundamental problems is to determine the number of legal positions, or the probability that a random position is legal. A random Go position is generated using a model previously studied by the author, with each vertex being independently Black, White or Uncoloured with probabilities $q,q,1-2q$ respectively. In this paper we consider the probability of legality for two scenarios. Firstly, for an $N\times N$ square lattice graph, we show that, with $q=cN^{-\alpha}$ and $c$ and $\alpha$ constant, as $N\rightarrow\infty$ the limiting probability of legality is 0, $\exp(-2c^5)$, and 1 according as $\alpha<2/5$, $\alpha=2/5$ and $\alpha>2/5$ respectively. On the way, we investigate the behaviour of the number of captured chains (or chromons). Secondly, for a random graph on $n$ vertices with edge probability $p$ generated according to the classical Gilbert-Erd\H{o}s-R\'enyi model $\mathcal{G}(n;p)$, we classify the main situations according to their asymptotic almost sure legality or illegality. Our results draw on a variety of probabilistic and enumerative methods including linearity of expectation, second moment method, factorial moments, polyomino enumeration, giant components in random graphs, and typicality of random structures. We conclude with suggestions for further work.

Keywords: probabilistic method, square lattice graph, random graph, random position, legal position, game, Go, W\'eiq\'\i, Baduk, Go polynomial

MSC numbers: 05C80, 05C57, 05C15, 05C30, 60C05, 91A46