cmput 670   games graphs algorithms

winter 2014

instructor Prof Ryan Hayward

office hours   by email appointment

prerequisites   a strong background in algorithms and/or math

overview An intro to automated players and solvers for two-player graph-based board games such as Hex. As necessary, the course may cover relevant graph problems (some polynomial, some NP-hard).

course objectives/content Understand strengths and weaknesses of current automated 2-player graph-based players and solvers.


tentative schedule

Jan  7..    overview
Jan 14..    Hex, history, properties              
Jan 21..    Hex theory: virtual connections       W1 due
Jan 28..    Hex theory: inferior cells            P1 due: Y program
Feb  4..    Monte Carlo tree search               W2 due
Feb 11..    depthfirst proof number search        W3 due
            reading week
Feb 25..    TBA                                   P2 due: Y solver
Mar 4..                                           P3 due: phantom Y tournament
March 4--13       presentations
April 1--8        final presentations             reports due

final letter grade assignment cutoffs: A+95 A90 A-85 B+80 B75 B-70 C+65 C60 C-55 D+50 D45 F0

text   none ... references TBA

plagiarism before submitting any work, see understanding plagiarism

presentations on any topic or paper related to the course... see bibliographies of phd theses of Phil or Jack