FYS 187-4 - Games and Computation Syllabus

This syllabus is not a contract. Rather, it is a first approximation of course topics as planned at the beginning of the course. I reserve the right to improve upon it as we progress.

• What is a game?  Definitions, Overview of game history, Decisions separating true games (e.g. Pig) from game-like activities (e.g. Chutes and Ladders, Lotteries).
• How do we categorize games?  Broad categorization by central actions (e.g. sports, communication, logic, risk assessment, information hiding/discernment).
• Why does game representation matter? Lessons from the mutilated checkerboard problem and magic square tic-tac-toe
• Combinatorial games
  • What is a game tree? Puzzles as single-player games, States, Actions, Goals/Rewards, State spaces, cyclic/acyclic graphs, computation tractability, static (a.k.a. heuristic) evaluation
  • How do computers solve puzzles?
  • What is a two-player game tree?
  • How do computers solve two-player game trees?  Minimax versus Negamax, alpha-beta pruning
  • Nim – how to win with binary numbers
  • Chomp – game graph, dynamic programming
• Games of Chance
  • Chance nodes and basic probability axioms
  • Pig – hold at 20 turn Monte Carlo simulation, dynamic programming
  • Pig – competing strategies
  • Hog endgame analysis – algebra versus value iteration approaches
  • Reinforcement learning – Approach N (simplified Blackjack)
• Games of Imperfect Information
  • Games: Rock, Paper, Scissors; Minimum Unique Fingers
  • Normal form versus extensive form representations
  • Information sets
  • Mixed strategies
  • Regret-based learning, regret-matching
• Optional topics if time permits:
  • Simple video game programming in Scratch/PyGame
  • Interactive Fiction: the intersection of creative writing and computer games