Adversarial Search

• Minimax is a good algorithm, but Tic-Tac-Toe isn't a game one plays very often because it always ends in a draw.
• There are a lot of other games, and computers play many of them quite well.
• Probably the best example is chess.
• Minimax would work if you could unfold the whole game tree.
• How big is it?
• So, you need a good evaluation function. What does that look like?
• The further the agent can look ahead the better.
• There is a time limit, so you can also use iterative deepening.
• Finally, you can use alpha beta pruning. The idea is that if you're minimizing, if you find a number larger than the current smallest expansion, don't continue with that. (With maximimizing you don't expand smaller ones.)
• This does require the evaluation function to be right. Otherwise it's just a good heuristic.
• However, the basic idea is that you don't have to expand the whole tree.
• Moreover, you want to keep it around for the next move and continue processing while the opponent is thinking.
• Deep blue beat Kasporov with 17-18 look-ahead just using these techniques.