Loading slide
There is a way around a greedy trap. Instead of always grabbing the closest-looking step, you check every possible path and pick the one that actually reaches the goal. Look far enough ahead and no trap can fool you.
That maze was small. A handful of squares, few enough to check every route by hand. So why not always do that?
Because most problems are not small. Take chess. To play it perfectly, you would check every way the game could go. The number of possible chess games is larger than the number of atoms in the observable universe. Count every atom in every star and every grain of dust across all of space, and you still fall hopelessly short.
No machine can check a list that long. Not the fastest one ever built, not in the lifetime of the universe. The maze was the easy case. Real problems are this one, and chess is one of the tidy ones.
So search is squeezed from both sides. The greedy shortcut walks into traps, and checking everything is impossible. The early researchers had built things that genuinely worked and assumed the rest was a matter of time and faster computers. That assumption is the story of the next few slides, and of why it fell apart.