Red X iconGreen tick iconYellow tick icon

    Overview

    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.

    About this paper

    Paper title Combinatorial Game Theory
    Subject Computer Science
    EFTS 0.1667
    Points 20 points
    Teaching period Not offered in 2022 (On campus)
    Domestic Tuition Fees ( NZD ) $1,371.61
    International Tuition Fees Tuition Fees for international students are elsewhere on this website.
    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

    Timetable

    Not offered in 2022

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