7

In the minimax algorithm, chess engines do a depth-first search as far as they can calculate ahead, and then evaluate all these final positions. Then, using these evaluations they work backwards one move at a time and assign values to the previous positions. Eventually they reach the current, starting position and give it an evaluation value.

However, how would minimax chess engines evaluate a final position if it was in the middle of some exchange? For example, take the following:

  1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Bxc6

Let's say an engine's depth capacity was 7 ply (a move from either player), and it reached this position as one of the final positions in its calculations from the start of the game. It wouldn't be able to calculate further (and see Black could play 4...dxc6) and would have to evaluate this position now. To me, it seems it would have to assign this final position a +3 advantage for White, but I know that chess engines have a way around this.

My question is, how do chess engines get around this scenario?

12

A good chess engine won't stop after a predetermined number of moves, but will keep looking until the position is "quiescent", which roughly speaking means that there are no pending captures or checks. See Quiescence Search in chessprogramming wikispaces for a more detailed explanation.

4

@itub is absolutely right. Generally, computer chess engine don't stop until the position is clear at least in terms of material captures. When you ask an engine to search for depth=10, it doesn't actually mean it searches variations up to depth=10.

Quiescence Search is important for minimizing horizon effect.

  • It may be worthwhile to note that in most positions the number of possible captures and checks will be rather limited, and the number of available moves will be rather limited in most cases where the king is in check. An engine which is supposed to work up to depth 6 might search while a depth counter is less than 96, and increase that counter by 16 after a non-check-non-capture, by 1 after a capture, and by N if a move involves a check and there have been N such moves in the current line. Pretty simple, and I think that's how a lot of 1980s chess programs work. – supercat Apr 23 '18 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.