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 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 |