Shall We Play A Game?
summary
Uses Ricochet Robots on a 16×16 grid to show concrete tradeoffs: state space about 976.5 billion states, branching factor 9–20, and a rule that the active robot must change direction. Implements depth‑first and breadth‑first search, then adds heuristics and precomputed stopping cells, a board‑equivalence class and data tweaks (sorted arrays faster than sets in Ruby, avoid creating needless objects). Resulting solver plays a full 17‑goal game in ~3 minutes (some random boards in ~30s).
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:56Games
- 2:40Reckless Robots
- 5:05The Problem
- 8:38Search Algorithms
- 14:30Optimization
- 19:40Profiler
- 24:47Solving Time
- 26:11AStar Algorithm
- 30:05Collision Detection
- 30:28Moving Robots
- 31:12Parallel
related talks
46mBeating Go thanks to the power of randomness
11mOm! Nom! Nash!
36mPlaying Go with Clojure
34mSolving Problems Declaratively
33mAlpha2048 - how I taught my computer to play 1024
50mOptimal control, no! Than what? (...)
18mJavaScript and Artificial Intelligence
20mAI for Gaming: How I Built a Bot to Play a Video-Game with R and Python