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