MEng Software Engineering
Year of entry: 2020
Course unit details:
AI and Games
|Unit level||Level 3|
|Teaching period(s)||Full year|
|Offered by||Department of Computer Science|
|Available as a free choice unit?||Yes|
game. The bots compete against each other in a tournament. The
students seem to enjoy this very much. The second project involves a game in which the students compete against the lecturers in a price-setting game. The students appreciate the industrial relevance of this project.
|Unit title||Unit code||Requirement type||Description|
|Fundamentals of Artificial Intelligence||COMP14112||Pre-Requisite||Compulsory|
|Mathematical Techniques for Computer Science||COMP11120||Pre-Requisite||Compulsory|
Pre-requisites are waived for CM students.
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
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?
- Analytical skills
- Group/team working
- Project management
- Oral communication
- Problem solving
|Written assignment (inc essay)||60%|
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.
COMP34120 reading list can be found on the School of Computer Science website for current students.
|Scheduled activity hours|
|Assessment written exam||2|
|Practical classes & workshops||26|
|Independent study hours|
|Jonathan Shapiro||Unit coordinator|
Course unit materials
Links to course unit teaching materials can be found on the School of Computer Science website for current students.