I don't honestly know what people claim TDD does. But where the requirements are clearly specified (albeit changing) and problem space isn't well understood it has its uses.

The example given is one TDD is kinda one of worst case scenarios for it. If for example the goal was to write a novel game that is popular with some audience Norvigs analytical approach would falter. TDD wouldn't fare much better but I believe it would be better than purely analytical problem. I however have little doubts Norvig would adapt to the challenge.

Do note that by TDD I consider only red-green-refactor methodology on clearly specified parts and adding tests on encountered bugs. Rest I consider fluff.

Summary: Tests and test first design is a tool. It can't be used for everything.