Solving Ricochet Robots
summary
Solves Ricochet Robots (16 by6 grid, five robots) by treating robot positions plus current goal as the state, using breadth‑first search with optimizations to find optimal solutions. State space is about 9,765 billion positions with a branching factor of 9–20. Key engineering: pre-computed stopping cells, a board state equivalence class that ignores irrelevant robot colors, skip generating no‑move states, and check successors before enqueueing — cutting states considered by nearly 3× and solving a 17‑turn game in about 30 seconds.
AI-written summary · about
chapters (20)
- 0:00Intro
- 1:25Why Graphs, Trees & Algorithms?
- 2:02What is Ricochet Robots?
- 3:35Characterizing the Problem
- 4:14Representing the Board
- 4:59Representing Robot Movement
- 5:49Search Algorithms
- 7:32Depth-First Search: Cycles
- 9:48Breadth-First Search
- 12:18Heuristic: Move Active Robot First
- 14:25Do Things Faster: Precompute stopping cells
- 16:30Do Things Faster: Sorted Array vs Set
- 17:07Do Things Faster Use Object Identity Instead of Deep Equality
- 17:42Demo
- 18:53Future Ideas: Better Algorithms
- 19:06A* Algorithm
- 20:53Work Backwards
- 21:11Future Ideas: Better Heuristics
- 21:56Future Ideas: More Optimizations
- 22:28Acknowledgements
related talks
28mMake It Fast: Simultaneous AI Actions in Gears Tactics
33mKarp Plays a Game
21mBalancing Player Experience Without Players At Supercell: Case mo.co
48mMachine Learning for Boardgame AI in Race for the Galaxy
25mReal Algebraic Geometry in Computational Game Theory
06mUnderstanding Player Patterns by Combining Knowledge-Based Data Abstraction with Interactive ...
59mGame AI 4N00bz
17mPlay Magnus