Games on Graphs
Two-player games where positions are graph nodes. You analyze winning strategies using backward induction.
Lessons
1. Intro
(The goal)
2. Positions as States
(Graph as game board)
3. Winning vs Losing Positions
(The simple solution)
4. Terminal Positions
(Where games end)
5. Backward Induction on DAGs
(Reverse topological solve)
6. Why DAGs Are Simple
(No cycles, no draws)
7. Quiz: Winning and Losing Positions
Knowledge check
8. Games with Cycles
(Draws from cycles)
9. Classifying with Cycles
(Win, lose, or draw)
10. Implementation Pattern
(Minimax BFS pattern)
11. Quiz: Backward Induction
Knowledge check
12. Problem - Cat and Mouse (Part 1)
(Problem setup)
13. Problem - Cat and Mouse (Part 2)
(State space modeling)
14. Problem - Cat and Mouse (Part 3)
(Terminal state marking)
15. Problem - Cat and Mouse (Part 4)
(BFS propagation)
16. Problem - Cat and Mouse (Part 5)
(Degree array technique)
17. Problem - Cat and Mouse (Part 6)
(Drawing states)
18. Problem - Cat and Mouse (Part 7)
(Time and space cost)
19. Problem - Cat and Mouse (Part 8)
(Data structures needed)
20. Problem - Cat and Mouse (Part 9)
(Turn logic details)
21. Problem - Cat and Mouse (Part 10)
(Edge cases)
22. Problem - Cat and Mouse (Part 11)
(Common pitfalls)
23. Problem - Cat and Mouse (Part 12)
(Problem summary)
24. Two-Player vs Single-Player
(Key differences)
25. Nim-Like Games on Graphs
(Sprague-Grundy theory)
26. Computing Grundy Numbers
(MEX computation)
27. When to Use Grundy
(Combined games via XOR)
28. Quiz: Sprague-Grundy Values
Knowledge check
29. Pursuit-Evasion Games
(Pursuer vs evader)
30. Cops and Robbers on Trees
(Single cop captures)
31. Cops and Robbers on General Graphs
(Cop number of graphs)
32. Problem - Coin Game on DAG (Part 1)
(Problem setup)
33. Problem - Coin Game on DAG (Part 2)
(Losing position rule)
34. Problem - Coin Game on DAG (Part 3)
(Reverse topo processing)
35. Problem - Coin Game on DAG (Part 4)
(Linear time solution)
36. Problem - Coin Game on DAG (Part 5)
(Finding winning moves)
37. Problem - Coin Game on DAG (Part 6)
(Multi-coin variants)
38. Move Ordering Strategies
(Pruning heuristics)
39. Distance to Win
(BFS from terminals)
40. Minimax on Graphs
Alternating maximization an...
41. Alpha-Beta Pruning
(Skipping irrelevant branches)
42. Quiz: Minimax on Graphs
Knowledge check
43. Memoization for Graph Games
(Avoiding recomputation)
44. Problem - Game on Tree (Part 1)
(Introduction)
45. Problem - Game on Tree (Part 2)
(Minimax on tree structure)
46. Problem - Game on Tree (Part 3)
(Implementation)
47. Problem - Game on Tree (Part 4)
(What you learned)
48. Infinite Games
(Games that never end)
49. Draw Detection Strategies
Identifying non-terminating...
50. Quiz: Draw Detection in Cyclic Games
Knowledge check
51. Bipartite Game Graphs
(Player positions alternate)
52. Applications in AI
(Game-playing algorithms)
53. Applications in Network Security
(Attacker vs defender games)
54. Applications in Robotics
Path planning with adversaries
55. Stochastic Games
(Adding randomness to games)
56. Complexity of Game Analysis
(Runtime considerations)
57. When to Use Game Theory
(Problem recognition patterns)
58. Common Mistakes
(What to avoid)
59. Quiz: Game State Representation
Knowledge check
60. Debugging Game Code
(Verification strategies)
61. Extensions and Variants
(Beyond basic games)
62. Section Recap
(What you learned)