prof hayward     cmput 670:games.graphs.algorithms     winter 2014


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). Prerequisites: a strong background in algorithms and/or math.


Understand strengths and weaknesses of current automated 2-player graph-based players and solvers.

  • 60% 6 assignments – 3 written, 3 programming – (15% penalty/day late, to maximum of 2 days)

  • 10% 1 25-minute research paper presentation

  • 30% project (14% content, 8% report, 8% 20-minute presentation)

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

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..    PNS, DFPNS, 1+eps trick               W2 due
Feb 11..    10x10, scalable parallel DFPNS        W3 due
                 reading week
Feb 25..    monte carlo tree search
Mar 4..     MCTS
Mar 11-13   TBA          presentations: IL BH
Mar 18-20   pres: A TY         TBA
Mar 27      Y tourney round 1                     P2 due
Apr   8     Y tourney round 2                     P3 due Y program report
Apr  11     1100-1300 final presentations         final reports due
lecture refs