Loading slide

The Summer Everything Seemed Possible

  1. 01The Summer Everything Seemed Possible
  2. 02The summer of the big bet
  3. 03The word they invented
  4. 04The Logic Theorist
  5. 05What the program was actually doing
  6. 06Memory Card
  7. 07Intelligence as search
  8. 08See it for yourself
  9. 09Where search breaks down
  10. 10The size of the problem
  11. 11Just the shape
  12. 12The optimism trap
  13. 13What they got right
  14. 14Reinforce your understanding
  15. 15Question: Logic Theorist
  16. 16Question: The greedy trap
  17. 17Question: The hidden scale
  18. 18Quiz: answer
  19. 19The door was open
  20. 20Want to go deeper?
9 / 19
BackNext

Where search breaks down

That rule you just used has a name. It is called greedy: at every step, take whatever looks closest to the goal right now.

In the first maze, greedy worked. In the second, it walked you straight into the trap. The exit was sitting right there, just past a wall, and the only way around was to head off in the wrong direction first. Greedy never does that. It cannot bring itself to step away from the goal, even when stepping away is the only path that reaches it.

That is the catch hiding inside search. Following the closest-looking option is a fine instinct until the right answer asks you to move away from it first.

And real problems are full of moments like that. The winning move often looks, at the time, exactly like a wrong one.

Did you know?

The simple search of the 1950s could never make a move like this. But fast forward to 2016. A program called AlphaGo played the ancient board game Go against Lee Sedol, one of the best players in the world. On its 37th move, it placed a stone in a spot almost no human would have chosen, and the experts watching called it a mistake.
It was not a mistake. It was the move that won the game. And AlphaGo did not find it by searching harder. It searched less, but it had also learned, from millions of games, a feel for which strange-looking moves were worth a second look. That mix, a little search and a lot of learned intuition, is where this whole story is heading.
Citations(2)↓
  1. 1. nature.com
  2. 2. deepmind.com