coming soon
homework is study guide only: you do not hand it in
I recommend that you study, and compare answers, in groups
each homework will be posted 1 week before the quiz
week 1 2 3 (wk 4 2021 notes)
week 4 (lec 08 hackenbush) 5 (CF II) 6 (shallow games, CF depth 2)
week 7 (sg)
week 8 (impartial: applying nim, sg thms, e.g. nim, chop, cram, pick-up bricks)
week 9 (partizan: dyadic)
week 10 (0-sum matrix games)
week 11 (dyadic)
week 12 (konane go-problems)
week 13 presentations (ugrad attendance optional)
closed book, no devices
will cover all lectures, homework and quizzes
as a representative example of what kinds of questions you might expect, here is the most recent final exam (I do not give answers). course content changes from year to year: content corresponding to some of these questions might not be covered this year. 2019
this course is about two kinds of game theory:
classical game theory (a.k.a. economic game theory), as developed by Von Neumann, Gayle, Shipley, Nash et al
combinatorial game theory, as developed by Berlekamp, Conway, Guy, Nowakowski, et al. developed cgt.
course follows text by DeVos and Kent
UAlberta students can access text here
course covers some of these topics
combinatorial games
normal-play games
impartial games,
hackenbush and partizan games
zero-sum matrix games
von neumann's minimax theorem
general games
nash equilibrium
cooperation
n-player games
preferences and society
who is welcome?
anyone interested in classic game theory and/or combinatorial game theory
is this course cross-listed?
sometimes as ugrad CMPUT 497-B2
prereqs?
CMPUT 175 (or equiv), any of CMPUT 272, MATH 222, PHIL 220, and any CMPUT/MATH/PHIL 3xx
labs or seminars?
no
what is this course about?
we will follow Game Theory: A Playful Introduction by DeVos and Kent,
available as a pdf from UAlberta library
cgt, a.k.a. board game math,
applies to 2-player alternate turn perfect-information
deterministic games, especially those where the loser is whoever
cannot make a legal move
wikipedia (read
1st para)
is there math in this course?
yes, and proofs.
is there computing in this course?
possibly
is this relevant to computing?
yes, game-bots use search and
knowledge, this course covers knowledge common to many 2-player games,
e.g. some Go end-game solvers use CGT,
some imperfect-info game solvers use classic GT
calendar description?
(3-0-0) CMPUT 497-B2 / 670
an introduction to classic game theory and to combinatorial game theory
CGT course content?
other CGT sources Intro to Combinatorial Game Theory (Haff/Garner),
Lessons in Play (Nowakowski et al.)
algorithmic course content? CMPUT 355: games, puzzles, algorithms and other sources on simple game players/solvers
project (670 only)
comb'l games
hex etc
luke's python mcts-hex
benzene(MoHex 2.0) Nicolas patterns branch neurobenzene install tips
jakub's improved vcs, mohex patterns, spdfpn
mopyhex kenny's python hex player
kenny's fuego for kenny's osx-benzene
timo ewalds’ morat hex havannah gomoku pentago rex y
rex kenny's rex solver mohex:dfpn (ignore all other code)
hex 122 kenny's morat branc:hex122cleaned Hex 122 player
bridgit thiessen
reverse hex mcts bot
dark hex umpire old sourceforge
go
chris's c++ small-board go solver
netbots: leela0 torch-elf 10cent-phoenixGo
game-diagram drawing software
An Introduction to Combinatorial Game Theory by L R Haff and W J Garner (ugrad level)
order from lulu.com (not amazon) to get the most recent edition
Len Haff is an emeritus professor of mathematics at UC San Diego. He is also an enthusiastic Go player who became interested in Combinatorial Game Theory long ago. He's been teaching a course on combinatorial game theory for many years. Will Garner is his former student, who joined him in teaching CGT for several years. Like Lessons in Play, by Albert, Nowakowski, and Wolfe, An Introduction to Combinatorial Game Theory by Haff & Garner is a textbook for an undergraduate course. It addresses the transition from lower division (freshman & sophomore) collegiate mathematics to upper division, with increased emphasis on rigorous proofs. I think everyone who teaches an undergraduate course on CGT should take a close look at it. – Elwyn Berlekamp
Lessons in Play by M Albert, R Nowakowski, D Wolfe (ugrad level)
Combinatorial games are games of pure strategy involving two players, with perfect information and no element of chance. Starting from the very basics of gameplay and strategy, the authors cover a wide range of topics, from game algebra to special classes of games. Classic techniques are introduced and applied in novel ways to analyze both old and new games, several appearing for the first time in this book.
Game Theory: A Playful Introduction by Matt Devos and Deborah A Kent (ugrad level)
This book offers a gentle introduction to the mathematics of both sides of game theory: combinatorial and classical. The combination allows for a dynamic and rich tour of the subject united by a common theme of strategic reasoning. The first four chapters develop combinatorial game theory, beginning with an introduction to game trees and mathematical induction, then investigating the games of Nim and Hackenbush. The analysis of these games concludes with the cornerstones of the Sprague-Grundy Theorem and the Simplicity Principle. The last eight chapters of the book offer a scenic journey through the mathematical highlights of classical game theory. This contains a thorough treatment of zero-sum games and the von Neumann Minimax Theorem, as well as a student-friendly development and proof of the Nash Equilibrium Theorem. The Folk Theorem, Arrow's voting paradox, evolutionary biology, cake cutting, and other engaging auxiliary topics also appear. The book is designed as a textbook for an undergraduate mathematics class. With ample material and limited dependencies between the chapters, the book is adaptable to a variety of situations and a range of audiences. Instructors, students, and independent readers alike will appreciate the flexibility in content choices as well as the generous sets of exercises at various levels.
Combinatorial Game Theory by Aaron N Siegel (expert level)
For those wishing to know about combinatorial games in depth this is the book to read. … Aaron Siegel is currently the strongest researcher in the field and has been involved with many of the central developments. In this book, he has brought them together. Moreover, he includes asides and details that explain how and why certain directions were taken; important insights from an expert. … He has kept the tone of the book light and infused it with history, anecdotes, and important observations making it an entertaining as well as an educational read. – Richard Nowakowski, MAA Reviews
2024 lectures will not be recorded