Steven Skiena rapping on combinatorial search in the Algorithm Design Manual:
[Chess] has inspired many combinatorial problems of independent interest. The combinatorial explosion was first recognized with the legend that the inventor of chess demanded as payment one grain of rice for the first square of the board, and twice as much for the (i + 1)st square than the ith square. The king was astonished to learn he had to cough up 265 – 1 = 36,893,488,147,419,103,231 grains of rice. In beheading the inventor, the wise king first established pruning as a technique for dealing with combinatorial explosion.