Chess

• Unfortunately, with any reasonable game, you can't see the end.
• For instance, with chess there are plausibly hundreds of possible moves.
• Here, you use an evaluation function at the leaves. With chess this includs control of areas and number of pieces.
• Deep Blue beat Kasparov using these techniques.
• It had the evaluation function in hardware (so it was fast).
• It used iterative deepening. (Start at the top, then move to the next level. So, look more moves ahead iteratively.
• It used Alpha-Beta pruning. Don't pursue paths that you know are worse than the ones you've already looked at.
• Deep blue looked 17 or 18 moves ahead.