Coping with impossibility
It is usually impossible to solve games completely
- Connect 4 has been solved
- Checkers has not been
- we’ll see a brave attempt later
This means we cannot search entire game tree
- we have to cut off search at a certain depth
- like depth bounded depth first, lose completeness
Instead we have to estimate cost of internal nodes
Do so using a static evaluation function