Lecture notes and other supporting materials from a module given by me for the Mathematics Department of Nottingham University from 1986 to 2007, inclusive. Supplied as is, with no warranty as to their continued correctness! Use as you see fit, but please achnowledge this site if you publish or publicise this material.
Coursework will be set from a booklet which will be available early in the module, and which will contain a wide variety of relevant questions. I normally ask for three sets of coursework to be handed in, usually towards the middle of this term [this is later than I would like, but the first chunk of the module is rather bookworky, and not really fit for interesting coursework!], two or three weeks after that, and towards the end of term. Occasionally I've managed to slip in a fourth. Model solutions to most questions will be distributed as the module progresses. Not all the questions in the booklet will be formally set for solution; this should not prevent you from attempting them -- they form a valuable adjunct to the lectures.
Objectives: By the end of the module, students will be able to construct and analyse game trees and discuss the problems with this analysis and their resolution; to describe numbers as games; and to analyse positions in both familiar and unfamiliar games.
Key skills: The analysis of conflict situations; investigative skills in new situations; and the use of the Web as a teaching and learning resource.
After a short introductory section, the module proper starts with a practical investigation into computer chess. [No significant knowledge of either chess or computing is required. You know more than enough about chess if you know `the moves', and about computing if you attended the first-year module. The reason for dealing with chess rather than any other game is that considerably more effort and research has been expended in this area; but the theory is common to virtually every game.] We look at tree-searching: the standard marking algorithm, alpha-beta pruning, windowing, and so on. We then look at various problems and their resolutions: the horizon effect, quiescence, transpositions and cycles, and the `killer' heuristic and its relatives.
We then turn to the mathematical theory. We explore the connexion between numbers and games, firstly in general [finite] games, then in impartial games, where the same moves are available to both sides. The Sprague-Grundy theory of such games shows that they can be reduced to `Nim', motivating the study of Nim-addition and minimal excludents. Games such as `Kayles' and `Hackenbush' are used to illustrate the reduction. Some partisan games will also be explored.
Finally, there will be a collection of special topics. Currently this comprises (a) `Dots-and-Boxes', as an example of how to investigate games that are nearly but not quite amenable to theory; (b) `Solitaire', as an example of how to apply the ideas of game theory to quite different areas; (c) matrix games, as examples of games that are not related to numbers in this way; and (d) evolutionary games. Other topics may be added if time permits.
Please note: This is not `the' module text, in any sense that by reading it you will suddenly become enlightened about the content of this module. In previous years, there has been an unseemly and unnecessary scramble for copies just before the exam, which has overwhelmed the resources of the Library and its short-loan collection. BCG should be read at leisure and for pleasure, not in a mad dash.A much more mathematical treatment of the theory is given in On Numbers and Games, J. H. Conway (Academic Press, 1976, or Peters, 2000); that too now has a shiny new edition, but you need a microscope to find important changes. In addition, Berlekamp has expanded the `Boxes' section of BCG into a book, The Dots and Boxes Games, (Peters, 2000). The Mathematics of Games, J. D. Beasley (Oxford, 1989) covers some of the same ground as this module [and also some other topics] in an introductory way.
For a survey of computer chess, see Computers, Chess and Cognition, ed. A. Marsland and J. Schaeffer (Springer, 1990). Sadly, we still await an accessible textbook on this material. A reasonable source for matrix games and related topics is Game Theory, A. J. Jones (Ellis Horwood, 1980); or try Games, Theory and Applications, L. C. Thomas (Dover, 2003); but there is plenty of choice of books under QA269 in the library.
There are two other sources of information [besides the textbooks mentioned above, and any other private reading which you may (and are encouraged to!) do] which you should use in conjunction with lecture notes. One is the set of solutions to the examples [which will be made available as the module progresses]. Please try the examples, and read the solutions. Remember, we're talking about games, so you can play most of the examples and see who wins; doing this with a modest side-stake when appropriate will give added point!
The other is, of course, the Web, both in general and in particular. This document is at URL
http://cuboid.me.uk/anw/G13GAMand will, from time to time, be extended with references to other pages containing useful information. I shall try to make sure that there are pages giving more detailed notes about topics that have caused problems in the past, and I'll let you know as such pages are added.
These pages are intended to supplement lectures, and, for example, to give extended explanations in detail that would be tedious in lectures. They are not in themselves part of the module.
These are the lecture notes taken by Hermione Peters [to whom many thanks] for session 2001-02; they are provided `as is' as a help to students. There is no guarantee that exactly the same topics will occur in precisely the same order in any other session!
- Introduction
- Game trees and computer chess
- Alpha-beta pruning
- Games and numbers
- Domination and reversibility
- Simplicity and temperature
- Nim
- Sprague-Grundy Theory
- Octal games
- Impartial hackenbush
- Boxes
- Solitaire
- Matrix games
- Evolutionary games
- [end]
ANW