TwiddleLab / Courses / Artificial Intelligence

Search, Games and Plans

Search, game trees and plans: the AI that thinks ahead instead of learning.

Intermediate · 11 lessons · Free, no account needed

Best after: How a Neural Network Thinks

Start the course

Lessons

1. AI as Search (5 min): A state is a snapshot of the puzzle, like 4 L and 3 L.
2. Breadth-First and Depth-First (7 min): A search keeps a waiting list of squares it has found but not checked yet.
3. Heuristics: A* Finds the Way (7 min): A heuristic is a quick guess of the distance left, like steps to the star if there were no walls.
4. Game Trees (6 min): A game tree shows every way a game can go: the position at the top (the root), each move a branch, each finished game an ending (a leaf).
5. Minimax (7 min): Give every ending a score: +1 if you win, -1 if you lose, 0 for a draw.
6. Scoring Positions: Evaluation Functions (7 min): Big games can't be searched to the end, so the search stops at a depth limit.
7. Alpha-Beta: Skip What Doesn't Matter (7 min): Alpha-beta pruning searches the tree like minimax, left to right, and skips any branch that can't beat what is already guaranteed.
8. Monte Carlo: Play Random Games (7 min): A random playout (rollout) finishes the game with random moves for both sides.
9. Planning: From Goal to Steps (7 min): Every action has preconditions (what must be true first) and effects (what it makes true).
10. Constraint Puzzles (7 min): A constraint problem has variables (clubs, cells, countries), each with a domain of allowed values, and constraints between them.
11. Project: Pathfinder Robot (8 min): Breadth-first finds the path with the fewest squares, but checks many squares on the way.

Lessons are interactive and need JavaScript. Turn it on to play them.