The theory of games of perfect information between two players without random elements, and algorithms for determining how to play them well.
The overall aim is to provide students with an introduction to the theory of combinatorial games and the algorithms that allow computer players to play such games well.
|Paper title||Combinatorial Game Theory|
|Teaching period||Not offered in 2020|
|Domestic Tuition Fees (NZD)||$1,333.93|
|International Tuition Fees (NZD)||$5,793.66|
- There are no formal prerequisites for the 400-level papers, but prior knowledge is assumed. Admission to these papers is restricted not only by numbers, but by satisfactory grades in 300-level COSC papers.
- Computer Science Adviser
- More information link
- View more information for COSC 411
- Teaching staff
To be confirmed
- Paper Structure
Roughly the first half of the paper will be devoted to the theory of combinatorial games using the framework developed by Berlekamp, Conway and Guy in Winning Ways. This material will be delivered through lectures and also student explorations and investigations using the software package CGSuite. The first piece of assessment will require students to demonstrate their familiarity with these ideas by analysis of interesting positions in a particular game.
The second half of the paper will be devoted to algorithms for playing games, beginning with alpha-beta search and its refinements (transposition tables, history heuristic and others). Recent progress in the development of evaluation functions for game positions (using logistic methods, or Monte Carlo approaches) will be surveyed. The second piece of assessment will require students to explore the development of a game playing agent for a specific combinatorial game, combining the heuristics of this part of the course with exact analysis where feasible.
- Three assignments 10%, 10% and 20%
- Final exam 60%
- Teaching Arrangements
- One 2-hour lecture per week.
- The course text book can be downloaded from the paper's website.
- Course outline
- View the course outline for COSC 411
- Graduate Attributes Emphasised
- Communication, Critical thinking, Self-motivation, Teamwork.
View more information about Otago's graduate attributes.
- Learning Outcomes
- An understanding of the nature of combinatorial games
- An understanding of the theoretical backdrop which allows for the analysis of combinatorial games
- The ability to assess the structure of a simple game within that theory
- Understanding the most significant types of artificial agents for playing games
- Understanding of the principal search techniques in game tree search
- The ability to implement one or more of such techniques