Skip to main navigation Skip to search Skip to main content

The probabilistic method meets go

    Research output: Contribution to journal › Article › Research › peer-review

    Abstract

    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 ×N square lattice graph, we show that, with q = cN−α and c and α constant, as N → ∞ the limiting probability of legality is 0, exp(−2c5), and 1 ac-cording as α < 2/5, α = 2/5 and α > 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ős-Rényi model 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.

    Original languageEnglish
    Pages (from-to)1121-1148
    Number of pages28
    JournalJournal of the Korean Mathematical Society
    Volume54
    Issue number4
    Publication statusPublished - 2017

    Keywords

    • Baduk
    • Game
    • Go
    • Go polynomial
    • Legal position
    • Probabilistic method
    • Ran-dom position
    • Random graph
    • Square lattice graph
    • Wéiqí

    Cite this