FYS 187-4 - Games and Computation Readings |
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 | 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 | 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, "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 | 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, TensorFlow Playground | |
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, (Zork, Lost Pig, Violet) |
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 (Your final exam will be opened at the end of class 28 and will close at the end of your final exam period.) |