Shortcuts: Course notes · Test yourself · Exams · Slides · Content
I have written a short piece on why to choose (or not to choose) COMP30191.
Games are not only something people take part in to pass the time in a pleasant way; they have also become a widely-used model in a variety of disciplines. Even in areas which typically do not lend themselves to traditional mathematical modelling, such as economics, biology and the social sciences, they have had somewhat surprising successes, and the use of game models has led to entire sub-disciplines being created, such as `traditional game theory' in economics (most books with Game Theory in the title will fit into that area) or `evolutionary game theory' in biology.
Computers are widely used in this kind of modelling, either to `solve' games, that is to find an optimal strategy, or to simulate playing (often many) such games as a way of exploring the predictions a given game model will make. Additionally, game models can be applied to model computer systems--for example, machines competing for slots on a network to transmit data.
In this course I will give an overview into methods for `solving games' as well as give examples for how games are used to model various scenarios. I would like to stress here that this course will require dealing with abstract entities; if you hated the theoretical or mathematical components of modules you have taken in the past this may not be a good choice for you. It should also be emphasized that this course has nothing whatsoever to do with computer games. More details regarding the are given below.
This course is taught in a non-traditional way. There is a full set of notes with exercises for the course, and the expectation is that every student will each week work through a set number of pages. This activity is supported by weekly sessions that serve two purposes:
|
When Week 1 Weeks 1-5, 7-12 Weeks A (3, 5, 8, 10) Week 12 |
What Introduction Question sessions Examples classes Assessment |
Where Mo 4.00pm in 1.4 Mo 4.00pm in 1.4 We 9.00am in LF15 We 10.00am in LF15 We 9.00am in LF15 We 10.00am in LF15 |
Who All All Surnames ending A-L Surnames ending M-Z Surnames ending A-L Surnames ending M-Z |
Some frequently asked questions (and their answers) regarding the course.
The course notes cover the part of the material that is fairly mathematical. Everything that is in the notes is examinable, but there is material that will be covered by the exam that is not in the notes (see above). I appreciate any feedback on the course in general as well as on the material handed out. For this purpose please email me at A.Schalk at cs.manchester.ac.uk.
Please do not print the notes as they appear here. You will get copies in the first week of term. Also note that the rooms given in the notes are incorrect! The ones given above, and on the official timetable, are the ones you should adhere to.
gzipped postscript, postscript, pdf version.
Here is a timetable regarding the set material for each week. It is important to work through the material in the week given in order not to fall behind. Bear in mind that there are no labs associated with this course. In the second year, students learn a lot during the labs - in the third year, they need to have more initiative!
|
Week Theme Pages |
1 Games 1-15 |
2 Strategies 13-22 |
3 Equilibria 23-33 |
4 Non 0-sum 34-42 |
5 Mixed strats 42-48 |
6 Solving games 48-59 |
|
Week Theme Pages |
7 Game models 60--75 |
8 Evolution I 76--88 |
9 Evolution II 88--97 |
10 Medium game 98--110 |
11 Large games 111--130 |
12 Catch-up |
To give you a chance to test your understanding I have produced some tests. We may make use of these in the question sessions - I'm not sure about that yet.
|
postscript Test 1 Test 2 Test 3 Test 4 |
pdf Test 1 Test 2 Test 3 Test 4 |
There is no book which will cover the entire course, which is somewhat innovative in its conception. There are references at the end of each section of the lecture notes.
Question 1. As in previous years, this consists of me giving you a description of a zero-sum game and asking you to draw the game tree, determine all strategies for both players, give the matrix for the game and determine its equilibrium points. This is a good question if you have practiced the techniques required, and usually very popular.
Question 2. As in previous years, this consists of asking you to solve (find equilibrium points for) various games given in normal form. This is another good question if you have practiced the techniques required, and has always been the most popular question.
Question 3. This is the wild card question. I feel free to do anything I like with that one. It's not for the faint of heart, and you should only tackle it if you're sure you can solve it.
Question 4. This covers the material on game-playing programs, and how they work.
Question 5. This covers the material on game models and evolutionary game theory
Note that the course was taught as CS3192 and CS3191 in the past. The University has decided only to provide access to exam papers from the past three years. There used to be a legacy server that provided papers from pre-2005/6, but this has now been taken out of commission. Here are direct links to my papers from 2005/2006, 2006/2007, and 2007/2008.
The material for this course has been slightly reduced over time. So if you find part of an exam question which uses concepts that have not been covered just ignore it.
Lecturers are now asked to give feedback on exam performance. This allows students to find out what happened in previous exams. This is my 2002/2003 feedback, my 2003/2004 feedback, my 2004/2005 feedback, my 2005/2006 feedback, my 2006/2007 feedback, and my 2007/2008 feedback.
The electronic slides I have used in lectures in the past are available here. The pdf version is the one I used in the lectures, containing all the step-by-step overlays. The ps versions are printer-friendly: They produce all the overlays for a slide on a page, cutting down the number of pages that have to be printed. I'm not sure how useful these would be without lectures.
If you use `lpr -o number-up=2' or `lpr -o number-up=4 -o number-up-layout=btlr' on departmental machines under Linux then you can print them 2 or 4 slides on a page. No printed copy of the slides will be handed out.
|
pdf version Introduction Small games Medium games Large games Game models Games and evolution |
gzipped postscript Introduction Small games Medium games Large games Game models Games and evolution |
postscript Introduction Small games Medium games Large games Game models Games and evolution |
There are also slides I used to explain the unassessed exercises.
|
Covering Exercises 1-5 Exercises 6-11 Exercises 12-17 Exercises 20-24 |
pdf Slides First Collection Second Collection Third Collection Fourth Collection |
gzipped ps Slides First Collection Second Collection Third Collection Fourth Collection |
ps Slides First Collection Second Collection Third Collection Fourth Collection |
Official Syllabus for COMP30191, Theory of Games and Game Models.
A game is given by a set of rules describing the allowed actions by one or more players in a given position. In particular such rules fix whose turn it is at any given moment, and what moves they may choose to play. Typically games can be described using a so-called game tree. Here a node is a given position, and it is precisely one player who is allowed to make any move in that position (there are ways of getting around games where players make their moves at the same time, such as Scissors, Stone, Paper). For each alternative such move, there is a branch leading to a new position. The game is over when nobody can move. Often the outcome of a game is given by describing some kind of pay-off that takes place as the game ends, that is at the leaves of the tree.
How we tackle a game is largely dependent on its size.
Small games can be described in a particularly simple fashion: Given a player of such a game, we can view all the positions when it would be that player's turn, and make a decision how to move should that position arise in a play of the game. This defines a strategy for the player in question. We can now list all the strategies available for each player, and assume that as the game starts, every player commits to one of his or her available strategies. Calculating where such a game ends is then a mechanical process in which the players do no longer have any part. If there are just two players then the description of such a game amounts to describing a matrix (or table) which tells us about the pay-off that will occur given a strategy for each player.At first sight, this has nothing to do with how games are played - indeed, it seems to be a rather boring game where our only move consists in choosing a strategy, and then have somebody calculate what final result that gets us! However, this is the method traditionally used for `solving games', that is, for finding optimal strategies for all players. However, this way of proceeding is viable only for games so small that for the most part, they are not interesting to play. (Games following this pattern which are played `in the real world' often consist of one move per player only, such as the above mentioned Scissors, Stone, Paper, or games where each player chooses a number, and the pay-off is then determined by some relation between the two numbers.) However, such games turn out to be very useful in modelling certain decision processes, which is why their analysis is of interest. And such games can become even more interesting when one models a situation by assuming that a great number of such simple games are played in some environment--this is how, for example, --> --the stock market can be modelled.
Medium games are ones which are too large to be submitted to the above treatment, but which we can still hope to explore fully with the use of a computer program. What is of interest here is an intelligent choice of exploring the game tree to find the best move in a given situation, without having to store the entire game tree at any given time. The methods used here are popular as search techniques in Artificial Intelligence.
Large games are those which do not yield to the methods typically employed for medium games. Examples of these are games such as Chess and Go. Here finding the best move in a given position by exploring the game tree is hopeless because we can never hope to do so fully. In this course we will look at the principles underlying all competitive game-playing programs for games such as Chess or Checkers.
Game models have done a lot to increase the interest in games since there are now useful applications in a number of fields. We will look at some of these, in particular in the social sciences and in biology. As part of that we will look at what happens if the same game is repeated, which typically makes even small games much more interesting. Modelling social interaction, or the evolution of certain behaviours depends on the idea that the issue in question is something that occurs many times, so there are consequences beyond a single game from the choices that were made in playing it. We will look at ways of drawing lessons from this taken from evolutionary game theory.
Games are categorized according to a number of criteria, but we will not have the time to cover all of the options listed here.
Full information. Games of full information are those where at each stage, both sides know precisely what the state of the game is, there are no hidden components. Examples for this are games such as Chess, Go, Noughts and Crosses, Checkers. Many games played for entertainment do have a component of information that is hidden from all but one player (typically card players only know the cards they hold themselves). We will look at both versions.
Chance. Many games, typically those played with card or dice, contain elements of chance. The rolling of the dice, or the dealing of the cards are chance experiments. We will consider such games, but on a level where we don't require more knowledge regarding combinatorics than the level that is taught at A-level maths, or the maths courses you have taken in your first year.
Cooperation. The usual assumption when considering games is that each player is trying to play for him- or herself, for example maximizing the number of points to be gained. In real life, people often form coalitions to improve what the can get out of a given situation. Again, allowing for this makes an analysis much more complicated. We will not consider games where the players are allowed to cooperate.
Skill. There is no good way, really, of handling games of skill such as darts, or most of computer games of the 'shoot 'em up' type. That requires some way of modelling players' skills, and that turns out to be difficult in itself. We will therefore not treat these games at all.