COMP34120 AI and Games syllabus 2019-2020
Games have become very successful as a way of modelling the interactions of multiple agents. In this course unit we will look at the formal theory of games, which includes a discussion of what it might to find a solution to a game, and then look at how to program computers to play games, with a particular emphasis of programs that are capable of learning.
This is a 20 credit course unit that runs for the entire year. Each semester is structured as follows:
There are 12 lectures in the first six weeks of term to introduce the material, supported by handouts. In the remaining 5 weeks of terms students work, in small groups, on writing a program that implements some of the techniques taught previously. There is one exam in the May/June exam period.
The lectures are designed to support the handouts and it is expected that students read these both, in preparation for a lecture and again afterwards to ensure they have understood the material, which is quite abstract in places.
The first lecture will go into more detail regarding organizational issues and students thinking about taking this course unit are strongly encouraged to attend.
The aim of this semester is to answer the following questions.
What is a game? (Definition of game tree, pay-off function, normal form, extensive form.)
How can we describe a game plan? (Definition of strategy, representations of same.)
What does it mean to play a game well? (Definition of best-response strategy, equilibrium point and similar, discussion of the validity of these concepts, discussion of alternatives.)
How do we find good game plans? (Complexity of finding equilibrium points, minimax algorithm, alpha-beta pruning, discussion of the components of a typical game playing program via evaluation function and alpha-beta search).
What are some of the processes that can be modelled using games?
The aim of this semester is to understand the following topics.
What are Stackelberg (Leader-Follower) games? What constitutes a solution to a Stackelberg game? How can learning and optimization be used to learn good solutions? Applications to price setting and marketing will be discussed.
What is reinforcement learning and how is it applied to on-line learning? What are the important mechanisms of on-line learning? How can reinforcement learning be applied to games situations?
Feedback methodsFeedback is provided is several ways. Half of the course involves
group projects which take place in a drop-in lab where the students
can work, and get feedback on what they are doing. For each project,
each group must make a presentation, and feedback is provided
verbally. In addition, written feedback is provided.
- Assessment written exam (2 hours)
- Lectures (24 hours)
- Practical classes & workshops (26 hours)
- Analytical skills
- Group/team working
- Project management
- Oral communication
- Problem solving
On successful completion of this unit, a student will be able to:
On successful completion of semester 1 of this course unit you will be able to:
- Demonstrate knowledge of categories of games by identifying the categories of a game when given a description of that game. Categories include zero-sum/general sum, chance/no chance, hidden/perfect information, normal form/extensive form.
- Understand the different meanings of the concept of ``solving a game'' and be able to state or recognize the conditions under which a particular game can be solved.
- Demonstrate understanding of the concept of Nash equilibrium, by stating the definition, analysing whether a particular strategy profile constitutes a Nash equilibrium, and by computing Nash equilibria in simple, normal form games by hand calculation.
- Analyse a simple, normal form game to determine the Nash equilibria. At the most basic level, the students will be able to find pure strategy Nash equilibria using the MiniMax approach, dominance, and exact enumeration. At a higher standard, students will be able to calculate mixed strategy Nash equilibria in simple cases.
- Demonstrate understanding of pruning in minimax search, by hand calculation in examination.
- Work in a team of with one to three other people to produce a ``bot'' (a piece of software) which can play a particular game against the bots of the other teams in the class. Minimally, this bot (produced in any programming language) will connect with a game engine using a TCP/IP protocol, produce correct responses, and not exceed the allowed time limit. I.e. it will play a game without crashing, but not necessarily well. At a higher level, the bot will play a strong game, as measured against the other bots in the class in a tournament. At the highest level, the bot may use novel methods or be informed by literature found through independent study.
- Demonstrate understanding of the application of at least one of the possible methods which can be applied to large extensive games, by describing the approach in exam questions and implementing it in the practical described in the previous outcome.
On successful completion of semester 2 of this course unit you will be able to:
- Demonstrate knowledge and the definitions of further categories of games including: leader-follower (Stackelberg) games with perfect and imperfect information, games with discrete/continuous strategy spaces, and games in which the task is to determine the rules which cause a desired behavior from a group of self-interested agents with private information (mechanism design). You will be able to distinguish games from these categories.
- Comprehend the concept of mechanism design - the task of designing the rules and mechanism of a game to encourage the players to perform the desired behaviours. Understand the distinction between mechanism design and strategy optimization. Understand the different approaches are needed when finding the best strategies and designing the rules for a game.
- Analyse and recognise whether the game requirement is to find the best playing strategies or to design the playing rules for desired outcomes, from the description of the game.
- Distinguish, for the mechanism design of a game, the different levels of desired and achievable outcomes. Understand the solutions of some simple application mechanism design problems and their achieved best outcomes.
- Find the best strategies for simple leader-follower/Stackelberg games on continuous strategy spaces and with perfect information by applying the derivative method.
- Apply some basic learning methods to estimate a player’s reaction function in simple leader-follower/Stackelberg games with imperfect information and then find the best strategy based on the learned reaction function.
- Assemble the above skills to solve some simple application problems such as pricing gam
COMP34120 does not have a specified reading list.
Course unit materials
Links to course unit teaching materials can be found on the School of Computer Science website for current students.