As every college student knows, being lazy is on occasion a remarkably effective way to get work done. What we mean, of course, is that some work just goes away if you wait long enough. In this chapter, we’ll show how these virtues of laziness carry over to the world of computation.
Dice of Doom is fun, but the board is a little small. Try setting the board size so you get a 3×3 board and run the game. Did you notice that the generation of the game tree seems to just hang? It hangs because the time it takes to process the number of possible moves for a 3×3 board is massive compared to the time it takes for a 2×2 board. But think about it: do we really need to consider all possible moves at each step? ...