The MiniMax algorithm has an exponential running time. If we want to fi nd the exact best move, we might have to wait forever. How can we get an approximate best move in a given time?

The MiniMax algorithm has an exponential running time. If we want to fi nd the exact best move, we might have to wait forever. How can we get an approximate best move in a given time?

Search the full game tree, make the best move and wait for a reply, search the full gametree, make the best move, wait for a reply... repeat until game over.

Searching to a cut$-$off and applying utility functions on terminal $($game$-$over$)$ states.

Do a depth$-$limited search with evaluation functions for intermediate nodes.

Do a depth$-$first search down to the terminal nodes and calculate minimax values simultaneously.