FYS 187-4 - Games and Computation
Readings

Unless otherwise noted, all readings are from the course text.  Each reading assignment should be completed before the class on the date indicated.  These readings are subject to change; check here for updates.  If a reading assigned in class does not match the reading assignment here, the reading assigned in class supersedes.  
Class Month Day Topic Readings (parenthesized
readings are optional)
1 August 28 Introduction; Game Definitions; Classifying Combinatorial, Chance, and Strategic Games Course Information Page, Syllabus, Wikipedia definitions of "game"
2   30 Game Representations for Human and Computer Reasoning Why Games?, Overview of Three Game Types
3 September 4 Combinatorial Games: Game trees, states, actions, goals/rewards, state spaces, cyclic/acyclic graphs, puzzles, minimax/negamax Russell & Norvig 5.1-5.2, Wikipedia article on Minimax (Combinatorial Games section), Bruce Rosen's Minimax algorithm example, animation of Minimax algorithm, Chomp game tree/graph, Breakthrough rules (and Wikipedia article)
4 6 Beyond Minimax: zero-sum games, minimax reasoning with the Centipede game, uncertainty of minimax values, 3-player games Kingmaker Scenario, Kingmaking, Centipede Game, Russell & Norvig 5.8
5   11 Limiting Minimax: Heuristic/Static Evaluation Functions Evaluation Function, Chess Point Values (skim), Kalah (understand rules), (Further readings - reference link, not reading assignment)
6   13 Optimizing Minimax: Alpha-Beta Pruning Russell & Norvig 5.3, Bruce Rosen's worked example, Pieter Abbeel's YouTube demonstration, Move Ordering (skim top)
7   18 Monte Carlo simulation, random/strategic playouts, n-Armed Bandit problem, exploration-exploitation problem Multi-armed bandit problem, MCTS Exploration and Exploitation
8   20 Monte Carlo Tree Search Monte Carlo Tree Search, Browne et al., A Survey of Monte Carlo Tree Search Methods, section 1 through 1.1, section 3., (Monte Carlo Tree Search Java Tutorial)
9   25 Card Magic, Nim and Binary Numbers Binary Number System, Nim article pp. 142-144 (emailed)
10   27 Toads & Frogs, Towers of Hanoi, and Computational Complexity Big-O Notation Summary (pp. 1-3, up to but not including "Related notations" section); Data Structures and Algorithms, section 1.4; (Toads and Frogs Game); Toads and Frogs Puzzle; Towers of Hanoi Puzzle; bring game bags (1st half of class alphabetically)
11 October 2 Games of Chance and Pig, Overview of Java Programming Fundamentals, Monte Carlo Simulation References (not assigned reading): Think Java: How to Think Like a Computer Scientist, CS 111 Java Summary
12   4 Games of Chance and Pig, Overview of Java Programming Fundamentals (cont.)  
13   11 Probabilities, Chance "Player", Expectiminimax, Expectimax; Take-home Exam 1 Axioms of Probability, Russell & Norvig 5.5
14 16 The Mathematics and Computation of Optimal Pig Play, Value Iteration Pig PowerPoint Presentation
15   18 Reinforcement Learning: Bellman's Optimality Equations Bellman's Optimality Equations
16   23 Dynamic Programming with Acyclic Games of Chance: Approach N  
17   25 Monte Carlo Reinforcement Learning: Exploring Starts Monte Carlo Control, (Chapter slides)
18   30 Monte Carlo Reinforcement Learning: UCB1, epsilon-Greedy, Donald Mitchie's MENACE On-Policy Monte Carlo Control, Implementation of Donald Michie's MENACE, "A Matchbox Game-Learning Machine" (Chapter 8 from Martin Gardner's "The Unexpected Hanging and other Mathematical Diversions"); bring game bags (2nd half of class alphabetically)
19 November 1 Solving Abstracted Games: Poker Squares Poker Squares rules/play grid, Learning and Using Hand Abstraction Values for Parameterized Poker Squares, (slides)
20   6 Neural Networks and Perceptron Learning Neural Network slides, TensorFlow Playground
21   8 Data Mining and k-Means Clustering OnMyPhd k-Means Clustering page, k-Means Clustering slides, Iris classification data Weka lab
22   13 Game Theory Basics, Nash Equilibrium, Pure and Mixed Strategies GameTheory101.com "The Basics" videos #1-#7
23   15 Mixed Strategy Payoffs, Strong/Weak Dominance, Number of Equilibria GameTheory101.com "The Basics" videos #8-#14
24   20 Correlated Equilibria Wikipedia Correlated Equilibrium introduction and example, (optional: Kevin Leyton-Brown slides 26-34 on Correlated Equilibrium, sections 3.4.5 and 4.6 from Shoham and Layton-Brown, Multiagent Systems, GNU Linear Programming Kit Reference Manual appendices C (CPLEX LP Format) and D (glpsol usage))
25   27 Regret, Regret Matching, Extensive Form Games An Introduction to Counterfactual Regret Minimization, Sections 1 - 2.3, Wikipedia extensive-form game article, (optional: Hart and Mas-Colell. A Simple Adaptive Procedure Leading to Correlated Equilibrium, paper sections 1-2, slides 21-70)
26   29 Counterfactual Regret Minimization An Introduction to Counterfactual Regret Minimization, Sections 3 - 3.3, slides, Wikipedia Kuhn Poker article
27 December 4 Course Evaluations, Interactive Fiction Introduction A Brief Introduction to Interactive Fiction, (Zork, Lost Pig, Violet), IF Cheat Sheet, Interactive Fiction Introduction
28   6 Interactive Fiction Programming Inform7 Introductory Screencast, Brass Lantern Inform7 Tutorial (updated text), Brandon Felger Wikibooks Inform7 Tutorial (updated text), Reiser's Inform7 Cheat Sheet
Final     Final Exam Final Exam Times (Your final exam will be opened at the end of class 28 and will close at the end of your final exam period.)