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

objectives

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

grading

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

plagiarism

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

code

hexgui for hex (and y)

newer benzene improved vc engine, mohex patterns, spdfpn

mopyhex kenny's python hex player

kenny's rex solver mohex:dfpn; ignore all other code

kenny's fuego works with kenny's benzene on his mac

kenny's morat hex122cleaned branch has Hex 122 player

references

assignments