FYS 187-4 - Games and Computation Readings |
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 |
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 | Browne et al., A Survey of Monte Carlo Tree Search Methods, section 1 through 1.1, section 3. | |
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) |
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.) |