I was reading the Chess articles on this website (http://www.gamedev.net/reference/programming/features/chess1/) and there was something a didn't understand: "This is the idea behind iterative deepening: begin by searching all moves arising from the position to depth 2, use the scores to reorder the moves, search again to depth 3, reorder, etc., until you have reached the appropriate depth. " - (http://www.gamedev.net/reference/programming/features/chess4/page5.asp) What I don't understand is this: if the computer has a queen sacrifice that will inevitably lead to checkmate, it will be rejected at depth 2 since the evaluation function won't be able to see the checkmate. All it will see is that the computer is down materail and that is, obviously not good. So it's cut off. What would be a good solution? Thanks

You might want to reread http://www.gamedev.net/reference/programming/features/chess4/page2.asp and http://www.gamedev.net/reference/programming/features/chess4/page3.asp

The idea behind that move reordering is to make the alpha-beta pruning work better. The search goes much faster if you try the best move first because you can then cut off all the moves that lead to worse outcomes, if your ordering is wrong all it does is slow down the search.

There's also quiescence search which tries to avoid problems like that at the end of the search, by only using the static evaluation when the position is 'quiet'. See http://www.gamedev.net/reference/programming/features/chess5/page2.asp

Quote:Original post by moteutsch
What I don't understand is this: if the computer has a queen sacrifice that will inevitably lead to checkmate, it will be rejected at depth 2 since the evaluation function won't be able to see the checkmate. All it will see is that the computer is down materail and that is, obviously not good. So it's cut off.

What would be a good solution?

Obviously not. You don't cut anything off. At depth 2 that move won't look too promising, so chances are that your heuristics won't make it one of the first moves to explore at depth 3, but it will still be there and it will be found as the best if depth 3 is enough to see the benefits of the sacrifice.

The two main advantages of iterative deepening are:
(1) The hash table will be full of good suggestions for which move to try first at many nodes (which speeds alpha-beta enormously).
(2) It provides a natural place to implement time control.