cmput 670   games graphs algorithms

winter 2012  M W 900-1020   CSC B43

instructor Prof Ryan Hayward

office hours Athabasca 301   MW 11-12 or by email appointment

prerequisites   a strong background in algorithms and/or math

overview This course covers the evolution of automated players and solvers for two-player graph-based board games such as Hex, (the classic 2-player connection game created by Piet Hein in 1942 and independently John Nash in 1949), starting with Claude Shannon's analogue machines and ending with current state-of-the-art players. As necessary, the course covers relevant graph problems (some polynomial, some NP-hard). The course ends with a survey of relevant open problems.

course objectives/content Understand the evolution of Hex algorithms in the context of the evolution of ideas in theoretical computing science. Understand weaknesses of current state-of-the-art automated Hex players and solvers.


final letter grade assignment as per UofA marking and grading guidelines, final grades will be assigned as a combination of a UofA illustrative sample 600 level graduate course distribution (A+ A A- B+ B B- C+ C C- D+ D F resp.% 15 15 15 17 16 10 7 2 1 0 1 1) together with absolute cutpoints reflecting the instructor's view of the UofA graduate course descriptors: A* excellent, B/B+ good, C+/B- satisfactory, F-C fail

text   none ... references TBA

presentations on any topic or paper related to the course... see bibliographies of phd theses of Phil or Jack ... one presentation should be on a theoretical topic