TwiddleLab / Artificial Intelligence / Search, Games and Plans
AI as Search
What you will learn
- A state is a snapshot of the puzzle, like 4 L and 3 L.
- A move takes you from one state to another. All states and moves together are the state space.
- Solving the puzzle is search: finding a path from the start to a goal state.
How the lesson goes
A 5 L jug, a 3 L jug and a tap. Can you get exactly 4 L?
No markings on the jugs. Bet first: what is the fewest number of moves?
Pour until the 5 L jug holds exactly 4 L.
Every amount you reach lights up on the map. Par is 6 moves.
Here is every state the jugs can ever be in.
You are at 5 L and 0 L. Tap every state you can reach in one move.
From 5 L and 0 L, three moves change something: fill the small jug (5,3), empty the big jug (0,0), or pour big into small, which leaves 2 L (2,3). Filling the full jug or emptying the empty one changes nothing, so those are not moves.
What you just did has names.
A state is one snapshot: how much is in each jug. A move is a line from one state to another. All states and moves together are the state space. A goal is a state you want. Search means finding a path from the start to a goal.
Draw the shortest path from 0,0 to a goal.
Tap dots one move apart. The jugs follow you. Can you do it in 6?
The path 0,0, 5,0, 2,3, 2,0, 0,2, 5,2, 4,3 uses the small jug to take away 3 L at a time: 5 minus 3 leaves 2, and topping 2 up to 5 with a 3 L jug that already holds 2 leaves 4.
New jugs: 6 L and 4 L. Which amounts can the 6 L jug end up holding?
Both jug sizes are even, so a fill, an empty or a pour always moves an even number of litres. Starting from 0 and 0, you can never reach an odd amount. The map of states simply has no odd dots, so no search can find one.
Now let the machine search the 5 L and 3 L map.
Press Spread and watch it look at the states in rings.
Next lesson: Breadth-First and Depth-First · Part of the course: Search, Games and Plans
Lessons are interactive and need JavaScript. Turn it on to play them.
