Static Exchange Evaluation...

[Steve Maughan]

Hi All - I'm grappling with SEE at the moment. Here's a post which discuss some of the issues. Some may find interesting:

http://www.chessprogramming.net/compute ... -in-chess/

Best,

Steve

[hgm]

OK, so you are doing in fact a null-window alpha-beta search.

Note that one of the tests you do is actually superfluous (except perhaps on the first ply): if you do futility pruning (return if SEE value + trophy value < thresholds, step 8) there is no way you can later stand pat (step 13).

In my experience X-rays involving pieces of different color ('foe backing') almost always give completely non-sensical results. Because an enemy piece blocked by your piece can always capture the latter by an oof-square capture (and often the reverse is true as well), which is beyond the scope of SEE, but almost always the best line.

E.g. in your second example,, suppose there was an extra white Q on a2:

[d]2k5/8/8/3pRrRr/8/8/Q7/2K5 w

It looks like the SEE on d5 for RxP is now good, and gains you a Pawn. But in reality RxP will of course lose you a Rook on g5.

I found that deep exchanges are rare, and when they occur the side effects (pins, overloads) accumulate so rapidly that their result almost never is meaningful. The only thing that SEE does with any accuracy is detect if the primary victim is unprotected (at least, if you take the trouble screening the first recapture for legality), or, if it is protected, whether capturing it is 'obviously losing' SEE-wise (protector + victim < attacker). Even detetermining whether it is protected is hopelessly inaccurate, as you will miss soft-pinning and overloading of the protector. So if you find it is unprotected, then fine. But anything else is so hopelessly inaccurate that it is basically an 'unknown' result.

For that reason in my recent engines I abandoned SEE, and switched to BLIND.

[Gerd Isenberg]

For that reason in my recent engines I abandoned SEE, and switched to BLIND.

What is BLIND?

[Uri Blass]

I know that you did not choose the example and it is based on Steve Maughan's link but
I think that the example is not a good example because I see no reason even to search capturing the pawn when Re5xf5 wins a rook(after you add the queen it may lose the queen after Ra1+ and Ra2+ but there is still Rg5xf5 that wins the queen when the rook e5 can defend after
Ra1+ Kd2 Ra2+ Re2)

[Steve Maughan]

Hi H.G.,

OK, so you are doing in fact a null-window alpha-beta search.

Indeed. Which makes sense to me.

I found that deep exchanges are rare, and when they occur the side effects (pins, overloads) accumulate so rapidly that their result almost never is meaningful. (...)

I agree. It's just a matter of creating something which works most of the time.

There is another weakness with my approach. The routine takes the first available piece of a given value to work with. However the other piece may give a different result. For example:

[d]1K1k4/8/5n2/3p4/8/1BN2B2/6b1/7b w - -

In this crazy position, Nxd5 wins a pawn if the SEE evaluates Bb3xd5. If Bf3xd5 is evaluated the other discovered bishops come into play. As you rightly say these positions are extremely rare and somewhat contrived.

For that reason in my recent engines I abandoned SEE, and switched to BLIND.

What's BLIND?

Best,

Steve

[hgm]

BLIND stands for 'Better, or Lower If Not Defended'. Meaning you initially only try those captures from the MVV/LVA ordering that are Low x High or Equal x Equal, and High x Low only if the victim is completely unprotected. Other captures are postponed (grouped with the bad captures, or pruned alltogether). Sometimes I define a third group of 'dubious captures', where Low x protected High has victim + protector >= attacker, and there is a second attacker. These could conceivably still lead to some gain (while if victim + protector < attacker the defender will simply stand pat after you capture with the second attacker). This requires you to figure out what the protector is, though, and often there is no big loss when you make QS figure that out, rather than having dedicated code for it. Since it does not occur that frequently.

[Gerd Isenberg]

BLIND stands for 'Better, or Lower If Not Defended'. Meaning you initially only try those captures from the MVV/LVA ordering that are Low x High or Equal x Equal, and High x Low only if the victim is completely unprotected. Other captures are postponed (grouped with the bad captures, or pruned alltogether). Sometimes I define a third group of 'dubious captures', where Low x protected High has victim + protector >= attacker, and there is a second attacker. These could conceivably still lead to some gain (while if victim + protector < attacker the defender will simply stand pat after you capture with the second attacker). This requires you to figure out what the protector is, though, and often there is no big loss when you make QS figure that out, rather than having dedicated code for it. Since it does not occur that frequently.

Aha, so a kind of "visually handicapped" SEE with very early termination

[hgm]

Exactly!

And a sort of three-state result, good, bad or unclear (ugly?).

[Don]

BLIND stands for 'Better, or Lower If Not Defended'. Meaning you initially only try those captures from the MVV/LVA ordering that are Low x High or Equal x Equal, and High x Low only if the victim is completely unprotected. Other captures are postponed (grouped with the bad captures, or pruned alltogether). Sometimes I define a third group of 'dubious captures', where Low x protected High has victim + protector >= attacker, and there is a second attacker. These could conceivably still lead to some gain (while if victim + protector < attacker the defender will simply stand pat after you capture with the second attacker). This requires you to figure out what the protector is, though, and often there is no big loss when you make QS figure that out, rather than having dedicated code for it. Since it does not occur that frequently.

Is there a definite measurable performance gain in terms of CPU time for this? Probably the majority of SEE cases terminate very quickly too.

Don

[Gerd Isenberg]

I know that you did not choose the example and it is based on Steve Maughan's link but
I think that the example is not a good example because I see no reason even to search capturing the pawn when Re5xf5 wins a rook(after you add the queen it may lose the queen after Ra1+ and Ra2+ but there is still Rg5xf5 that wins the queen when the rook e5 can defend after
Ra1+ Kd2 Ra2+ Re2)

Assuming this is only a detail of a real position to demonstrate that particular exchange. When it is about to decide on RxP the "winning" RxRs were already tried, but obviously didn't fail high for some reason. RxP may also consider if P is a passed pawn or not.