FYS 187-4 - Games and Computation

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
reading are optional)
1 August 29 Introduction; Game Definitions; Classifying Combinatorial, Chance, and Strategic Games Course Information Page, Syllabus, Wikipedia definitions of "game"
2   31 Game Representations for Human and Computer Reasoning Why Games?, Overview of Three Game Types
3 September 5 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
4 7 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   12 Limiting Minimax: Heuristic/Static Evaluation Functions Evaluation Function, Chess Point Values (skim), Kalah (understand rules), (Further readings - reference link, not reading assignment)
6   14 Optimizing Minimax: Alpha-Beta Pruning Russell & Norvig 5.3, Bruce Rosen's worked example, Pieter Abbeel's YouTube demonstration, Move Ordering (skim top)
7   19 Monte Carlo simulation, random/strategic playouts, n-Armed Bandit problem, exploration-exploitation problem Multi-armed bandit problem, MCTS Exploration and Exploitation
8   21 Monte Carlo Tree Search Browne et al., A Survey of Monte Carlo Tree Search Methods, section 1 through 1.1, section 3.
9   26 Card Magic, Nim and Binary Numbers Binary Number System, Nim article pp. 142-144 (emailed)
10   28 Frogs, Toads, 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; Towers of Hanoi Puzzle
11 October 3 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   5 Games of Chance and Pig, Overview of Java Programming Fundamentals (cont.)  
13   12 Probabilities, Chance "Player", Expectiminimax, Expectimax; Take-home Exam 1 Axioms of Probability, Russell & Norvig 5.5
14 17 The Mathematics and Computation of Optimal Pig Play, Value Iteration Pig PowerPoint Presentation
15   19 Reinforcement Learning: Bellman's Optimality Equations Bellman's Optimality Equations
16   24 Dynamic Programming with Acyclic Games of Chance: Approach N  
17   26 Monte Carlo Reinforcement Learning: Exploring Starts Monte Carlo Control,  (Chapter slides)
18   31 Monte Carlo Reinforcement Learning: UCB1, epsilon-Greedy, Donald Mitchie's MENACE On-Policy Monte Carlo Control, Implementation of Donald Michie's MENACE, Martin Gardner chapter 8 (matchbox-learning material) - distributed via email
19 November 2 Solving Abstracted Games: Poker Squares Poker Squares rules/play grid, Learning and Using Hand Abstraction Values for Parameterized Poker Squares, (slides)
20   7 Neural Networks and Perceptron Learning Neural Network slides
21   9 Data Mining and k-Means Clustering OnMyPhd k-Means Clustering page, k-Means Clustering slides, Iris classification data Weka lab
22   14 Game Theory Basics, Nash Equilibrium, Pure and Mixed Strategies GameTheory101.com "The Basics" videos #1-#7
23   16 Mixed Strategy Payoffs, Strong/Weak Dominance, Number of Equilibria GameTheory101.com "The Basics" videos #8-#14
24   21 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   28 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   30 Counterfactual Regret Minimization An Introduction to Counterfactual Regret Minimization, Sections 3 - 3.3, slides, Wikipedia Kuhn Poker article
27 December 5 Course Evaluations, Interactive Fiction Introduction A Brief Introduction to Interactive Fiction
28   7 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   11 Final Exam 8:30-11:30AM Final Exam Times