When humans chess players evaluate a sequence of moves they often mentally “swap off” the pieces at the end of a variation. For example if a proficient chess player took a quick look at the following position they would see Nxd5 wins a pawn:
Black can recapture with his knight but white would recapture again to win the piece. Effectively the player has resolved the sequence of captures on one square to see if the initial capture is winning or not. This type of logic is invaluable to humans and to chess engines.
In computer chess this type of routine is the “Static Exchange Evaluation” or “SEE” for short. It’s used in many different places in a chess engine. One of the most common uses is to prune losing captures in the quiescent search.
You would think such a simple “swap-off” procedure would be relatively easy to code. In my experience it’s not as simple as it seems at first! Tricky little situations add to the complexity. Is Rxd5 winning, losing or drawing?
All those discovered attacks on d5 need to be handled correctly. You also need to be able to handle the “stand-pat” condition, where one side can take but chooses not to as they would subsequently lose material.
In my previous engine (Monarch) I was never happy with the performance of the Static Exchange Evaluation. It built a list of attacking pieces and tried to resolve a score. It seemed to work but was really quite slow and I’m not convinced it was bug free. I’m determined the SEE routine in Maverick should be more robust.
In most cases the SEE function only needs to figure out if the move loses material. This simplification can save a lot of time. I Googled previous discussion about Static Exchange Evaluation on the various forums. Some people try to resolve the to a specific value using mini-max while other have an alpha-beta routine. I decided to be somewhat different and introduce a “threshold” parameter. The routine would return true if the move was equal-to, or better-than, the threshold parameter, and false if less than the threshold.
Here’s the logic in pseudo code first. “Side-to-move” is the same side as the initial SEE move being evaluated. Opponent is the opposite side:
- Generate all of the attacks and x-ray attacks on the target square for both sides
- The “see_value” is set to the value of the initially captured piece
- The “trophy_value” is set to the value of the piece making the initial capture
- Find the least valuable opponent’s piece which is attacking the target square (and is not blocked)
- Reduce the see_value by the trophy_value i.e. see_value = see_value – trophy_value
- Set the trophy_value equal to the value of the piece found in step 4
- If see_value >= threshold then return TRUE (i.e. the side to_move can stand pat and still have a score which reaches the threshold)
- If see_value + trophy_value < threshold then return FALSE (i.e. even if the side to move captures the new piece on offer, they will not reach the threshold)
- Find the least valuable piece for the side-to-move which is attacking the target square (and is not blocked)
- Increase the see_value by the trophy_value i.e. see_value = see_value + trophy_value
- Set the trophy_value equal to the value of the piece found in step 9
- If see_value – trophy_value >= threshold then return TRUE (i.e. even of the opponent captures the new piece on offer, they will not each the threshold)
- If see_value < threshold then return FALSE (i.e. the opponent can stand-pat and the score is less than the threshold).
- While each side has potential captures go to Step 4.
There are a few other wrinkles such as what to do when one side runs out of moves but I’m sure you can figure these out. I’ve also added some simple initial tests to see if an early decision can be make (e.g. can the piece be taken by a pawn?), without the need to generate all of the attacks.
Having tested the routine it seems to be quite efficient (certainly better than the SEE routine in Monarch).