Time+Place: Tuesday 12/01/2016 14:30 Room 337-8 Taub Bld. Title: The probabilistic method meets the game of Go Speaker: Graham Farr - COLLOQUIUM LECTURE http://www.csse.monash.edu.au/~gfarr/ Affiliation: Faculty of I.T., Monash University, Clayton, Victoria, Australia Host: Johann Makowsky

Abstract:

The game of Go --- known as Go or Igo in Japan, Weiqi in China and Baduk in
Korea --- is one of the oldest and deepest board games in the world, and has
a huge following in east Asia.

Traditionally, the game involves placing black and white stones on the
vertices of a square grid, usually with 19*19 vertices. But it can in fact
be played on any graph G.  A position is an assignment of colours from the
set {Black, White} to some subset of V(G).  So each vertex is Black, White
or Uncoloured. A legal position is one in which each monochromatic
component is adjacent to some uncoloured vertex.  (A monochromatic component,
or chromon, is a component of the subgraph induced by the vertices of a
specific colour.)

Among the most basic questions that can be asked about any game are:
*  How many legal positions are there?
*  What is the probability that a random arrangement of game elements
(stones/pieces/...)
on the board gives a legal position?
The author introduced Go polynomials to study these questions for Go
(Farr, 2003).  Let q \in [0,1/2] be a probability. Suppose each vertex is,
randomly and independently, coloured Black with probability q, White
with probability q, and is left uncoloured with probability 1-2q.
Then Go(G;q) is the probability that the resulting random position
is a legal one.  The author found links to the chromatic polynomial and
proved that it is #P-hard to compute.

In this talk, we apply probabilistic methods to study the asymptotic
behaviour of Go(G;q) when G is an n*n square grid, and also when
G \in G(n;p) is a Gilbert-Erdos-Renyi random graph with edge probability p.

References:
G E Farr, The Go polynomials of a graph, Theoretical Computer Science 306
(2003) 1--18.
G E Farr and J Schmidt, On the number of Go positions on lattice graphs,
Information Processing Letters 105 (2008) 124--130.

Short Bio:
Graham Farr is a Professor in the Faculty of Information Technology
at Monash University, Australia, and Co-Convenor of the Discrete
Mathematics Research Group.  He did his BSc(Hons) in Pure
Mathematics at the same university before completing a D.Phil. in
Mathematics from the University of Oxford.  His interests include
graph theory, enumeration (especially Tutte-Whitney polynomials),
algorithms, complexity, information theory and computer history.
Since 2008 he has led Computer History Tours of Melbourne.  In 2011
he received the Vice-Chancellor's Award for Excellence in

Refreshments will be served from 14:15
Lecture starts at 14:30