TwiddleLab / Artificial Intelligence / Search, Games and Plans
Heuristics: A* Finds the Way
What you will learn
- A heuristic is a quick guess of the distance left, like steps to the star if there were no walls.
- A* gives every waiting square a score f = g + h: steps so far plus the guess, and takes the lowest.
- With a guess that never says farther than the truth, A* still finds the shortest path, and checks far fewer squares.
- Trust the guess too much and the search gets faster but the path gets longer.
How the lesson goes
Breadth-first checked 63 squares to cross this maze. The robot knows where the star is. How many will a smarter search check?
Give the robot a sense of direction. Fill in the missing guesses.
A guess is the number of steps to the star if there were no walls: squares across plus squares up or down.
The guess ignores walls, so it is just the distance on the grid: |dx| + |dy|. It is quick to compute and never says farther than the real walk.
Now each waiting square gets a score: steps so far plus the guess.
f = g + h. The search always takes the card with the lowest f. Step, or Play.
This search has a famous name.
The guess is a heuristic. The search that takes the lowest f = g + h is A* (say "A star"). It is how game characters and map apps find paths.
A* is paused. Tap the square it checks next.
Each yellow card shows g + h. Lowest total wins. A tie? Either one is fine.
What if the robot trusts its guess more? Find the best w.
f = g + w x h. Find the w that checks the fewest squares and still finds the shortest path.
At w = 0 the guess is ignored and A* behaves like breadth-first. At w = 1 it is plain A*, which keeps the shortest path. Bigger w trusts the guess more than the steps already walked: the robot rushes toward the star, checks fewer squares, and can miss the shortest way.
Two ways to guess the distance. Run both and pick the better guess.
Squares across plus up or down, or a straight line (Pythagoras: the square root of dx² + dy²). The robot can only move along the grid.
Both guesses never say farther than the real walk, so both keep the shortest path. But a grid robot can't walk diagonally, so the straight line always guesses too low. The squares count is closer to the truth, and a closer guess means less wasted checking.
One guess is wrong, and A* missed the shortest path. Find it.
Tap a grey guess to test it against a real count.
The gap square is only 7 squares from the star on the grid, but its guess said 12. A* believed it, gave the gap a high score and went round the bottom instead. A* keeps the shortest path only if no guess says farther than the truth.
Race the machine: you are A*.
Each turn tap the yellow square with the lowest g + h. Two lives. Can you match the machine?
Previous lesson: Breadth-First and Depth-First · Next lesson: Game Trees · Part of the course: Search, Games and Plans
Lessons are interactive and need JavaScript. Turn it on to play them.
