by Wells, David
[Hamming 1998: 649]
Go
Go is an extremely ancient oriental game much played in Japan, China and Korea. The best players in Japan, equivalent to our chess grandmasters, are well-paid professionals who earn as much as top Western golfers. Their games are followed by devoted fans and their services sought by eager businessmen for whom a high amateur grade is a status symbol.
The standard board which is 19 lines by 19 lines (smaller boards, 13 by 13 or 9 by 9, are used when teaching beginners) starts empty, and players place a single stone, either black or white, alternately, on an intersection of two lines, with the object of surrounding territory or their opponent's stones.
In Figure 2.11, the players are sketching out positions in the corners of the board: in Go, the edges are used as a defence, and in the opening the corners where you are protected by two edges are crucial.
Go has a far larger board than chess but much simpler ‘moves’. The result is another rich game that lies near the boundary of whatever the human mind can master. It might seem that Go is a ‘mathematically’ simple game because its rules are so simple, but no, the board is so large and there are so many possible moves at each turn that Go players rely even more than chess players on strategical judgement and intuition, as well as tactical calculation.
The Japanese Rules of Go This is a simple version. The official rules complete with explanatory notes are at: www.cs.cmu.edu/∼wjh/go/rules/Japanese.html on which this epitome is based.
Two players compete on a board, to see which can take more territory.
The board is a grid of 19 horizontal and 19 vertical lines forming 361 intersections. A stone can be played on any unoccupied intersection.
The board is initially empty.
The players can alternately play one move at a time, one player playing the black stones, his opponent the white stones.
After a move is completed, a group of stones belonging to one player exists as long as it has a horizontally or vertically adjacent empty point, called a ‘liberty’.
If, after a player's move, a group of his opponent's stones has no liberties, the player removes all these stones, as prisoners.
A shape in which the players can alternately capture and recapture one opposing stone is called a ‘ko’. A player whose stone has been captured in a ko cannot recapture in that ko on the next move.
A group of stones which cannot be captured by the opponent is alive. A group which can be captured is dead.
Empty points surrounded by the live stones of just one player are called ‘eye points’. Other empty points are called ‘dame’. Stones which are alive but only possess dame are said to be in ‘seki’.
Eye points surrounded by stones that are alive but not in seki are called ‘territory’, each eye point counting as one point of territory.
When a player passes his move and his opponent passes in succession, the game stops.
After agreement that the game has ended, each player removes any opposing dead stones from his territory and adds them to his prisoners.
Prisoners are then placed in the opponent's territory, and the remaining points of territory are counted. The player with more territory wins.
If both players have the same amount the game is a draw, which is called a ‘jigo’.
Like chess pieces, the pieces at Go can also take any form. When I learned to play in the 1960s good stones and boards were hard to come by in the West so we used a kind of sugared almond, painting half of them black. The shape was close to Japanese standard stones which are made of shell or slate, but the weight, colour and feel were not right, but that mattered not at all because we used them as Go stones, so they were Go stones. This also works the other way round. When John Horton Conway was inventing the Game of Life with no computer to aid him, he used Go stones on a Go board to represent the state of the ‘game’.
Figure 2.11 Opening position of Go game
Because the Go board is so large that players have to rely more on intuition and judgement than chess players, efforts by artificial intelligence enthusiasts to program computers to play Go have been disappointing.
The original game of choice for the Artificial Intelligence community was chess. In 1957, Herbert Simon, pioneer of cognitive psychology and artificial intelligence and later a winner of the Nobel prize for economics, predicted that a computer would be world chess champion within ten years. A bizarre blunder, based on the naive idea that computers would soon be able to imitate the thought processes of the human brain whose complexity Simon grossly underestimated. Forty years later, Gary Kasparov did lose a game to the computer program Deep Blue but it did not play in the style of a human player. The artificial intelligence of Deep Blue was just that – artificial – and the goal of simulating the workings of the human mind proved much further away than Simon and his colleague Alan Newell realised [Wells 2003: 159–60].
Computer analysis of Go lags even further behind and there is no prospect in the near future of a Go program beating a top professional. From 1985 to 2000 when it lapsed, a prize of $1000000 was offered by Acer Incorporated and the Ing Chang-Ki Wei-Chi Educational Foundation for the first Go program to beat a Go professional. No way! The current strongest Go Combinatorial game theory (CGT) Some games are so simple, unlike chess and Go, that they can actually be solved completely by mathematical arguments. Nim is the most famous example. Your start with several piles of stones or other objects. Players take turns to select one of the piles and take any number of the objects in it, from a single object to the whole pile. Two rules exist for deciding the winner. Either the winner is the player who does not take the last object, or the player who does.
Nim was completely ‘solved’ by Charles Bouton in 1901, meaning that he showed which player should win, given a certain set of piles to start with, and how that player should play to guarantee the win. Like the Tower of Hanoi, the solution involves binary numbers.
Nim has the important feature, shared with all the games we have presented, that the position is completely open to both players, unlike card games or poker-type games whose analysis therefore involve probabilities. The latter have been analyzed by mathematical game theory which has been applied to economic competition between firms, a nuclear arms race, the sale of licences for mobile phones operators and other more-or-less realistic scenarios.
Nim is important for another reason. In the 1930s Roland Sprague and Patrick Grundy proved independently that all impartial games – meaning that for every position of the game, the same moves are available to both players – are equivalent to some game of nim, so the variety of impartial games is less than it might seem.
The extraordinary book, Winning Ways for Your Mathematical Plays, by John Horton Conway, the inventor of the game of Life, and his colleagues Elwyn Berlekamp and Richard Guy [Berlekamp, Conway & Guy 1982/2001] showed how some very simple games which were not impartial – but not including chess and Go which are far too complex – could also be solved mathematically.
Conway was inspired in his early work on combinatorial games by the endgame at Go which, as we shall see, is much more mathematical than the rest of the game, so it is appropriate that one of the highlights of subsequent work on CGT was Mathematical Go: Chilling Gets the Last Point by Elwyn Berlekamp and David Wolfe [Berlekamp & Wolfe 1994] which reduces the final stages of any Go game to a (complex) calculation.
programs are about 10 kyu level or 10 grades below the basic amateur sho-dan level which any player is traditionally supposed to reach after playing ‘one thousand games’. So vastly better is the human brain at spotting patterns and developing intuition and a ‘feel’ for the game, than the most powerful of today's supercomputers.
However, the endgame at Go in which the board is separated into regions, often relatively small, which no longer interact, is quite another matter. Using Combinatorial Game Theory, the end game of Go can be treated as a collection of solvable sub-games. We might say that the opening and middle game of Go are less
mathematical than chess, but the endgame is much more mathematical. So, fortunately for the millions of players of chess and Go, although the ‘Fundamental Theorem of Combinatorial Game Theory’ says that,
Every game of perfect information is either unfair (one player has a winning strategy) or boring (two rational players will always bring about a draw
the qualification rational is so strict and so severe that no two real human players, however skilful, can ever be totally rational, and so chess and Go are not, after all, boring.
The games of Nine Men's Morris, Hex, chess and Go vary in complexity and subtlety, and in popularity. The hardest, chess and Go, because they offer the greatest challenge and the greatest psychological rewards in terms of beauty and elegance, are the most popular, but they are the least accessible to mathematical treatment.
What other games might be invented in the future? A game on the lines of Nine Men's Morris could be invented by any alien civilisation on a distant planet and the chess board pattern must be discovered by intelligent life elsewhere in the universe and games may be played on it, even a game modelling two opposing armies, though they are hardly likely to invent Western chess. Hex, so simple and so non-arbitrary might actually exist ‘out there’. If it does, then it is likely that players on Planet Zorg will also have decided that playing on very small boards is uninteresting and that too-large boards are unplayable, and they may well know the same proof that white ought to win – just as we expect them to have much the same mathematics that we do. They might also have analysed the game much further than we have.
It is in the nature of games that they have the potential to be more-or-less universal, one of many mysterious connections between mathematics and abstract games to which we now turn.
3 Mathematics and games: mysterious connections
There are so many connections between games and maths that it is no wonder that many mathematicians play chess or Go or Bridge, or that so many abstract game players are into mathematics.
The presence of rules or underlying assumptions, the fact that expert chess players can play games in their heads, just as most people can do at least some calculations in their heads and maybe visualise a cube sliced symmetrically into two parts; the fact that there are tactics and strategies for solving problems in chess and mathematics; the confidence that we – often but not always! – feel that our conclusions are correct, that we can prove them, and the reliance of the chess player and mathematician on patterns and structure – these shared features all point to deep underlying connections between mathematics and abstract games. Let's start with perhaps the most remarkable of all – that they can both ‘in theory’ be done in the mind.
Games and mathematics can be analysed in the head…
…provided we make allowances for limitations of memory and visualisation. Few of us have Euler's phenomenal memory. On the other hand, even first-school children are expected by their teachers to do simple sums by ‘mental arithmetic’ and all strong chess players can informally discuss a game they have just played with limited recourse to the board.
Of course, you can imagine doing many activities in your head: sports psychologists recommend that champion sportsmen mentally rehearse their next high jump or ski run as an aid to better performance but that mental action is only in imagination. Euler and Koltanowski, however, were not imagining they were mentally creating mathematics and playing chess – they really were.
There is a link here in the very language used: chess players talk of calculating possibilities and are sometimes asked, ‘How many moves ahead can you calculate?’ A player admits he made a mistake because he calculated wrongly although no arithmetic was involved: the player calculated through a tree of possibilities: ‘If I play Qe5, that threatens mate, Black can defend with Ne8, but then I can play h6…’ and so on. What a significant form of words! Why would anyone calculate the moves in a game which have nothing to do with numbers, if there were not some mysterious connection between calculating with numbers and calculating the moves of the pieces?
Can you ‘look ahead’?
Strong chess players can ‘look ahead’ in a position – tracing a complex tree of possible sequences of moves – in order to decide which move to make. Written
Three blind mathematicians Blind mathematicians are rare, but they do exist and they have reached to the very top. (Are there blind theoretical physicists or chemists?) No doubt psychologists could learn much by studying how they think. Ironically, they have been as distinguished at geometry as at algebra, partly by exploiting their sense of touch.
Nicholas Saunderson (1682–1739) was blinded by smallpox at the age of 12 but became Lucasian Professor of Mathematics at Cambridge University. He wrote a textbook, Elements of Algebra, and lectured on optics. He also invented the pin-board, much used today by primary school pupils, to create geometrical figures that he could feel with his fingers, a sort of Braille geometry.
Lev Pontryagin (1908–1988) lost his sight in an accident at the age of 14. His devoted mother read books to him, wrote his notes and even learnt to read foreign languages for his sake. At 25 he entered Moscow University, blind but able to remember all his lectures. He published his first original work at the age of 19, like Euler, and went on to become one of the great mathematicians of the twentieth century.
[O’Connor & Robertson 2006]
Bernard Morin (1931–) has been blind since the age of 6, but became a brilliant geometer who discovered how to turn a sphere inside out – yet another ironic achievement for a mathematician who can feel but not see – and what is now called Morin's surface.
out in words, which is not usually how it is thought through by the player, a very short sequence might go something like this:
‘If I play Qe4, then Black can defend by Re8, but then I play Bc3, and if he defends by Nf8 then he has no defence against Nh5, but if he plays g6 instead then I can still play Nh5 and he's helpless. So I play Qe4…’
Mathematicians may also ‘look ahead’ when examining, for example, a geometrical diagram: ‘If I draw AX parallel to BC then the triangles AXR and BYC will be similar, and so AX/BY = XR/YC. That's the right ratio but now I must link BY and YC. How can I find the ratio BY/YC?’
Chess and traditional Euclidean geometry are both highly visual, but what about algebra? Surprisingly, algebra is also highly ‘visual’. When you look at a line of algebra, you see no geometrical points and lines, no angles or areas, no surface or volume, but you do see relationships between the symbols and pattern and structure in the whole – as we shall illustrate later.
A novel kind of object
Chess pieces (or Go stones, or playing cards) are very strange objects. To highlight their strangeness, let's look at some sample objects, at how they exist and how we think about them: ‘out there’
‘in my head’
the British Museum
my conception of the British Museum
The British Museum exists ‘out there’ as a building and an institution. My idea of the British Museum depends on my personal experience: for example, have I been there? (Yes, many times.) Your idea will vary from mine. ‘out there’
‘in my head’
a wooden post
my conception of a wooden post
Wooden posts are quintessentially solid objects that also exist ‘out there’. There are millions of them in the world of different shapes and sizes. (My conception of a wooden post will also vary somewhat from yours.) You can hit someone with a wooden post but you can't hit them with the idea of a ‘wooden post’. ‘in my head’
‘out there’
the chess king
a representation of the chess king
For the chess king (let's suppose we're playing standard Western chess) the situation is reversed. The chess king exists mentally defined solely by the rules. ‘Out there’ we have millions of different representations or realisations of the chess king, actual pieces which are parts of chess sets and are used by actual play
ers. Because they are only realisations of the mental concept, they are of all shapes and sizes and made from all sorts of different materials. The one crucial feature is that they are recognised as chess kings and this recognition depends entirely on convention. Today's convention in international matches and tournaments is to use pieces of Staunton design (named after the nineteenth-century English chess master) but readers of chess books and computer players are accustomed to different conventions for representing the chess pieces. ‘in my head’
‘out there’
the number 17
assorted numerals, each representing the number 17
The concept of the number 17 was also created to be a mental object. Early man, counting as far as 17, did not find the number lurking in the forest or running across the open plains nor did he spot it in the vegetable market.
The abstract Bridges of Königsberg diagram is also a novel kind of object. It exists in physical form on paper, on a page of this book, but it crucially exists abstractly in my mind, though not in the same way as my mental picture of the view from the window of my workroom or my memory of a dream or my mental picture of an apple or a billiard table.
The problem with those mental ‘images’ is that I cannot communicate them to you clearly and unambiguously – yet I can by using very simple language communicate to you very precisely and successfully a unicursal diagram or the puzzle of the Tower of Hanoi. So we can say that my mental representation of the number 17 or of the Tower of Hanoi puzzle is not mental and private but mental and (potentially) public.