Accessibility Skip to Global Navigation Skip to Local Navigation Skip to Content Skip to Search Skip to Site Map Menu

COSC411 Combinatorial Game Theory

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
Paper code COSC411
Subject Computer Science
EFTS 0.1667
Points 20 points
Teaching period Not offered in 2019
Domestic Tuition Fees (NZD) $1,307.76
International Tuition Fees (NZD) $5,517.77

^ Top of page

Eligibility
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.
Contact
Computer Science Adviser
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.

Assessment:

  • Three assignments 10%, 10% and 20%
  • Final exam 60%
Teaching Arrangements
One 2-hour lecture per week.
Textbooks
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

^ Top of page

Timetable

Not offered in 2019

Location
Dunedin
Teaching method
This paper is taught On Campus
Learning management system
None