MEng Software Engineering

Year of entry: 2020

Course unit details:
AI and Games

Unit code COMP34120
Credit rating 20
Unit level Level 3
Teaching period(s) Full year
Offered by Department of Computer Science
Available as a free choice unit? Yes

Overview

This course is a 50-50 mix of theory and practical development/implementation. The first project is a competition between the students to produce the best bot to play a particular
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.

Pre/co-requisites

Unit title Unit code Requirement type Description
Fundamentals of Artificial Intelligence COMP14112 Pre-Requisite Compulsory
Mathematical Techniques for Computer Science COMP11120 Pre-Requisite Compulsory
Students who are not from the School of Computer Science must have permission from both Computer Science and their home School to enrol.

Pre-requisites are waived for CM students.

Learning outcomes

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

Syllabus

Semester 1:

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?

Semester 2:

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?

Employability skills

Analytical skills
Group/team working
Innovation/creativity
Project management
Oral communication
Problem solving
Research
Other

Assessment methods

Method Weight
Written exam 40%
Written assignment (inc essay) 60%

Feedback methods

Feedback 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.

Recommended reading

COMP34120 reading list can be found on the School of Computer Science website for current students.

Study hours

Scheduled activity hours
Assessment written exam 2
Lectures 24
Practical classes & workshops 26
Independent study hours
Independent study 148

Teaching staff

Staff member Role
Jonathan Shapiro Unit coordinator

Additional notes

Course unit materials

Links to course unit teaching materials can be found on the School of Computer Science website for current students.

Return to course details