Given the nets of 4 cubes with the faces coloured in 4 colours, build a tower so that on each vertical wall no colour is repeated, that is all 4 colours appear.
A connected graph is a graph in which we can get from any vertex to any other by travelling along the edges. A tree is a connected graph with no closed circuits (or loops. Prove that every tree has exactly one more vertex than it has edges.
Label the joints and legs of these graph theory caterpillars so that the vertex sums are all equal.
Published May 2002,February 2011.
Note that further discussion concerning Go can be found in the articles Two eyes and Seki in Go and Going First.
Amongst board games from around the world that are played seriously, Go is something a bit special. Known also as weiqi (way-chee) in Chinese, and baduk (bah-dook) in Korean, it has a recorded history of 2500 years and has been played just about the same way all through that period. It is a game of surrounding the opponent and walling off your own areas.
You might have thought that by now everyone would have agreed on the precise rules. In fact there are a few variants, and the relationships between them can be confusing. Not that this has much effect on the play of the game; but it does open up a field for the use of mathematical concepts in clarifying what is happening.
This article will go over the use of the idea of connectedness in networks, in two different ways, to bring into focus the basics of the game, namely capture and territory. Go is played on grids: the standard board is a 19x19 grid of 361 intersections, called 'points'. Pieces are placed one by one on the points, and are not then moved. If captured they are taken off. The first thing is to
understand the capture rule. One advantage of being a bit more mathematical in appoach is that it reveals how to play Go on all sorts of networks - a road map of Milton Keynes has been quite successfully used.
Go is a game for two players, Black and White, who place 'stones' (the traditional name for pieces, which would originally have been pebbles) on the grid serving as a board, alternately occupying points with a single stone of their own colour. Usually you start with the board empty; but if handicaps are given one player begins with several stones already in place. The supply of stones is
assumed to be enough so that neither player runs out of their colour. Black always goes first
The position after a few plays on a small grid might look like this:
up to this point in the game there has been no chance to capture. After Black and White have added the stones with triangles on them, we would get this:
in which Black has a chance to capture the white stone at the centre point. That happens like this:
Black places the stone that completely surrounds the central white stone, and then removes it from the board.
The rule for capture of a single stone is therefore expressed like this: when a player places a stone that causes an enemy stone to be surrounded on four sides (in the centre of the board), that stone is taken off. This rule extends to edge stones that become surrounded on three sides:
and corner stones surrounded on two sides:
That's not all, of course. To make for an interesting game you must allow for captures of larger units. That is usually explained by saying that you can capture any solidly-connected chain of enemy stones by filling in the final adjacent empty point, like this:
here four white stones are captured by Black.
To say this more carefully: the relation of being connected applies first to adjacent points of the grid, considered as a network, which are occupied by stones of the same colour. And then one introduces the concept of a chain as all stones of a single colour that one reaches by starting at a stone on the board, and working outwards through neighbouring connected stones, and their connected
neighbours, until all stones are included that connect 'along the lines' to the initial one. For example:
the chain including the triangle-marked white stone is recognised in three steps.
These chains may be large or just an isolated stone; they may also have very varied shapes (as many as there are polyominoes, you could say, which is enough for anyone). The advantage for talking about chains for the rules of Go is that capture can be explained simply. Each chain on the board will have at least one empty point adjacent to it: such points are called its 'liberties'. A chain is
captured when the opponent fills in its final liberty. There is never a chain without a liberty on the board at the end of a turn - positions with libertyless chains cannot occur as a result of legal play.
The basis of the Go capturing rule has recently been used in a board game about gangsters taking over a city divided into blocks, like New York. When a gang takes all the blocks surrounding a region, it takes that too.
The connection idea can also be used to clarify a much more thorny question: surrounding territory. During the game players try to wall off parts of the board as their own: the final score depends on such territory. One way to recognise 'my' territory is like this: if my opponent plays inside it, I'll be able to capture all such invading stones in due course. How does this reconcile with the
more intuitive idea that a walled-off area has an 'inside' and an 'outside'? This is something that often causes problems to novice players.
One way to deal with this issue is to use the connection idea in a way that is perhaps not so familiar, but mathematically no deeper. In computer science it is called 'flooding'. It is more attractive to think of red and blue pieces rather than black and white stones, perhaps. Imagine that red pieces can flood out red water, and blue pieces blue water. The water can run anywhere along channels
between empty points, but is blocked by occupied points.
These diagrams of flooding from one marked stone will give the idea:
the points marked A are flooded in one step, the points B from the points A, and so on.
Then you don't need any notion of 'inside' and 'outside' or 'surrounding' to explain territory in Go. A point is undisputed territory for White in a given board position if it can be reached by flooding from a white stone, but from no black stone; andvice versa for undisputed territory for Black. This is a pretty good systematic definition, not needing any intuitive input, as you'd expect from
the computing point of view. It makes comprehensible an idea about 'connecting through vacant areas', which many people find off-putting on first encounter.
It isn't how Go players normally think about it. Territories are fortress-like areas of the board that are off-limits to intruders, and the proposed idea of territory only works when all mopping-up operations have been concluded. Also territory is only counted at the end of the game. Games of Go finish when both players are happy that there is nothing more worthwhile to do, and all those
mopping-up moves would prolong matters (experienced players nearly always take them as read).
Therefore this approach has something a bit different to offer. Not many people play Go on a board that is a grid drawn on a torus or Moebius band, or worry about three-dimensional Go rules. But, using the ideas introduced here, this will all be found to make perfectly good sense.
Go is an excellent model for the idea of a 'turf war', and its definition can based on what are ultimately simple concepts of striking clarity.
For a more conventional introduction to Go try the L-plate link at the British Go Association site . The world of international Go is very well covered by Gobase .
David Parlett's The Oxford History of Board Games(OUP 1999) is a good general source.