Shall We Play A Game?
summary
A Ruby solver for Ricochet Robots tackles a 16×16 board with 976.5 billion possible states using DFS, BFS and A; practical tricks include moving the active robot first, early goal detection when generating successors, precomputing per-cell stop positions, collapsing robot-color permutations into equivalence classes, reducing object churn, and using a C-backed priority queue (fast_containers) plus profiling with RubyProf. Those changes cut explored states by roughly threefold and turn runtimes to about 3 min 7 s* for a full 17-disc game, sometimes down to 30s.
AI-written summary · about
chapters (13)
- 0:00Start
- 0:39Computers Playing Games
- 2:25Game Playing
- 7:04Robot Movement
- 7:28Trees
- 8:43Depth-First Search
- 10:23Cycles
- 11:36Not a Tree
- 12:10Complications
- 13:55Breadth-First Search
- 18:51Do Less Things: Check for Solutions at Generation Time
- 26:41Best-First Search
- 30:23A* Algorithm
