SEE and en passant

[Pablo Vazquez]

Hi,

When using SEE to discard losing captures in the quiescence search, there is a little problem with en passant captures: suppose you capture en passant and the other side takes the pawn. Its an equal capture but it would have a SEE value of -100 so it would not be searched.

Why is that? First, we normally only use SEE on captures, and not on the pawn push that enables the EP capture. There's no reason why you can't have the first move in the SEE sequence as an EP capture. You are capturing a pawn. yes the target square is empty, but surely you can find a way to figure out that you are capturing a pawn that is not really there???

Also, using SEE in move ordering has some inaccuracies besides the usual hanging pieces after a SEE sequence (because of pinned and overloaded pieces) for example: a pawn promotes and it doesn't get captured: that's has a value of 0 when in fact it is much higher, or we make an en passant capture and the enemy doesn't capture, or he captures and we capture with a rook that gets discovered when his pawn is removed. The first one would have a SEE value of 0 and the second one -100 (since the rook attack goes unnoticed in SEE) when in fact it is a winning capture in both cases.

That's why it is called SEE, rather than PSEE (Perfect Static Exchange Evaluation). Yes it has errors. Whatever you do in the q-search already if fraught with errors. Do you really think the best move in most positions is a c apture rather than a quiet move? Yet the q-search looks mostly at captures.

But these last cases only give inaccurate move ordering, I'm more concerned in how to solve the first case, in which we would discard a non losing capture.

Regards

Well, I specifically looked at crafty after I made my SEE function and thought about this problem. Suppose you apply Swap() to an ep capture, in line 41 you have:

attacked_piece = p_values[PcOnSq(target) + 6]; /* 0 for an empty square, which is the case in an ep capture */

and in line 51

swap_list[0] = attacked_piece;

So after making the ep cap, you have a score of 0 instead of 100 (or 1 in your case).

I'm not sure who changed that. The captured piece is actually encoded in the move, and that is what should be used. I'll check and fix if that is broken in the current version...

Yes, but you can't know that, since Swap() only receives the from and to squares, in fact that is how it has always been done in Crafty, hasn't it?

[bob]

Hi,

When using SEE to discard losing captures in the quiescence search, there is a little problem with en passant captures: suppose you capture en passant and the other side takes the pawn. Its an equal capture but it would have a SEE value of -100 so it would not be searched.

Why is that? First, we normally only use SEE on captures, and not on the pawn push that enables the EP capture. There's no reason why you can't have the first move in the SEE sequence as an EP capture. You are capturing a pawn. yes the target square is empty, but surely you can find a way to figure out that you are capturing a pawn that is not really there???

Also, using SEE in move ordering has some inaccuracies besides the usual hanging pieces after a SEE sequence (because of pinned and overloaded pieces) for example: a pawn promotes and it doesn't get captured: that's has a value of 0 when in fact it is much higher, or we make an en passant capture and the enemy doesn't capture, or he captures and we capture with a rook that gets discovered when his pawn is removed. The first one would have a SEE value of 0 and the second one -100 (since the rook attack goes unnoticed in SEE) when in fact it is a winning capture in both cases.

That's why it is called SEE, rather than PSEE (Perfect Static Exchange Evaluation). Yes it has errors. Whatever you do in the q-search already if fraught with errors. Do you really think the best move in most positions is a c apture rather than a quiet move? Yet the q-search looks mostly at captures.

But these last cases only give inaccurate move ordering, I'm more concerned in how to solve the first case, in which we would discard a non losing capture.

Regards

Well, I specifically looked at crafty after I made my SEE function and thought about this problem. Suppose you apply Swap() to an ep capture, in line 41 you have:

attacked_piece = p_values[PcOnSq(target) + 6]; /* 0 for an empty square, which is the case in an ep capture */

and in line 51

swap_list[0] = attacked_piece;

So after making the ep cap, you have a score of 0 instead of 100 (or 1 in your case).

I'm not sure who changed that. The captured piece is actually encoded in the move, and that is what should be used. I'll check and fix if that is broken in the current version...

Yes, but you can't know that, since Swap() only receives the from and to squares, in fact that is how it has always been done in Crafty, hasn't it?

No. I recently changed this a bit but lost the change on my end. However, after I fixed it, I ran several tests. Essentially this makes no difference. For one test:
n=23115757 n=23117464, where the first is the original total nodes, the second is after the change we were discussing. Really is irrelevant.

[brianr]

Recently I have been redoing Tinker's SEE (it finally works better now with version 7.47), and have a very simple suggestion:

Do not discard any pawn captures/promotions; just try them all without bothering with a SEE score.

How can a pawn capture can ever be losing, and at worst not even (under SEE)?

Of course, capture move ordering is a separate topic. And, every program reacts to changes in its own way
(for example, checks in q-search, using the history heuristic, etc), so testing may result in some surprises.

[BubbaTough]

Do not discard any pawn captures/promotions; just try them all without bothering with a SEE score.

How can a pawn capture can ever be losing, and at worst not even (under SEE)?

Hi Brian,

When I tried a superset of this (don't do SEE when capturing a piece >= the capturer) it did not seem to help (in fact it hurt results slightly) assumably due to move ordering in the Q search. Has your finding been different?

-Sam

[Pablo Vazquez]

Recently I have been redoing Tinker's SEE (it finally works better now with version 7.47), and have a very simple suggestion:

Do not discard any pawn captures/promotions; just try them all without bothering with a SEE score.

How can a pawn capture can ever be losing, and at worst not even (under SEE)?

Of course, capture move ordering is a separate topic. And, every program reacts to changes in its own way
(for example, checks in q-search, using the history heuristic, etc), so testing may result in some surprises.

A pawn capture (including en passant) can never be losing, but a normal pawn promotion (not a capture one) can lose the pawn.

[bob]

Do not discard any pawn captures/promotions; just try them all without bothering with a SEE score.

How can a pawn capture can ever be losing, and at worst not even (under SEE)?

Hi Brian,

When I tried a superset of this (don't do SEE when capturing a piece >= the capturer) it did not seem to help (in fact it hurt results slightly) assumably due to move ordering in the Q search. Has your finding been different?

-Sam

I suspect he doesn't use that score for ordering, just for inclusion/exclusion. Most are using MVV/LVA to order the captures that pass the inclusion / exclusion test, so the above is just an efficiency issue for me. No reason to use Swap() to evaluate a capture if it is pxanything, as it can't possibly be a SEE loser. And since we don't need the SEE score if we know it doesn't lose material, it passes the inclusion test and we resort to MVV/LVA which doesn't change at all so long as you don't exclude moves you would have previously included.

I found that his test simply made crafty slightly faster, no change in total nodes searched whatsoever.

[BubbaTough]

Do not discard any pawn captures/promotions; just try them all without bothering with a SEE score.

How can a pawn capture can ever be losing, and at worst not even (under SEE)?

Hi Brian,

When I tried a superset of this (don't do SEE when capturing a piece >= the capturer) it did not seem to help (in fact it hurt results slightly) assumably due to move ordering in the Q search. Has your finding been different?

-Sam

I suspect he doesn't use that score for ordering, just for inclusion/exclusion. Most are using MVV/LVA to order the captures that pass the inclusion / exclusion test, so the above is just an efficiency issue for me. No reason to use Swap() to evaluate a capture if it is pxanything, as it can't possibly be a SEE loser. And since we don't need the SEE score if we know it doesn't lose material, it passes the inclusion test and we resort to MVV/LVA which doesn't change at all so long as you don't exclude moves you would have previously included.

I found that his test simply made crafty slightly faster, no change in total nodes searched whatsoever.

Ahh. It is unintuitive to me that MVV/LVA is better than see order. It seems to me if you are going to go through the bother of doing SEE, you might as well use the superior information. Alas, intuition is not always right. If you are going to skip SEE for pawn captures, why not skip SEE for the superset of cases I described: capturer <= captured. I suspect it will very minorly speed up your very minor crafty speedup .

-Sam

[bob]

Do not discard any pawn captures/promotions; just try them all without bothering with a SEE score.

How can a pawn capture can ever be losing, and at worst not even (under SEE)?

Hi Brian,

When I tried a superset of this (don't do SEE when capturing a piece >= the capturer) it did not seem to help (in fact it hurt results slightly) assumably due to move ordering in the Q search. Has your finding been different?

-Sam

I suspect he doesn't use that score for ordering, just for inclusion/exclusion. Most are using MVV/LVA to order the captures that pass the inclusion / exclusion test, so the above is just an efficiency issue for me. No reason to use Swap() to evaluate a capture if it is pxanything, as it can't possibly be a SEE loser. And since we don't need the SEE score if we know it doesn't lose material, it passes the inclusion test and we resort to MVV/LVA which doesn't change at all so long as you don't exclude moves you would have previously included.

I found that his test simply made crafty slightly faster, no change in total nodes searched whatsoever.

Ahh. It is unintuitive to me that MVV/LVA is better than see order. It seems to me if you are going to go through the bother of doing SEE, you might as well use the superior information. Alas, intuition is not always right. If you are going to skip SEE for pawn captures, why not skip SEE for the superset of cases I described: capturer <= captured. I suspect it will very minorly speed up your very minor crafty speedup .

-Sam

I've tested every option there is here. The idea is that you want to (a) exclude moves that are no good. Some moves can be included easily. RxQ will always be playable, for example. So the obvious ones are included in the list first. Then the less obvious (QxR) need SEE to see if the attacked piece is adequately defended so that the capture appears unplayable. Once you get past that, MVV/LVA order actually reduces the size of the tree. Apparently because you remove heavy pieces first which reduces the size of the subsequent tree...

I have always skipped SEE for the case you mentioned. Just not the == case for some odd reason. Now MxM is included without SEE if the value of the two M's are the same (RR, QQ BB NN PP or BN/NB).

[brianr]

Ahh. It is unintuitive to me that MVV/LVA is better than see order. It seems to me if you are going to go through the bother of doing SEE, you might as well use the superior information. Alas, intuition is not always right. If you are going to skip SEE for pawn captures, why not skip SEE for the superset of cases I described: capturer <= captured. I suspect it will very minorly speed up your very minor crafty speedup .
-Sam

Yes, I use MVV/LVA for move ordering, not SEE, since SEE is relatively expensive (compared to just do all pawns, or V >= A tests).

My hunch is that there are relatively few captures to begin with, and most do not need SEE since they are either pawn moves or the attacker is less valuable than the victim, so there are relatively few SEE situations.

Yes, SEE for move ordering should be better than MVV/LVA, but perhaps the cost of doing unnecessary SEEs is greater than the move ordering benefit (at least in the q-search).

Note that in Tinker's "ecosystem", SEE is only used in q-search. I have tried using SEE and postponing "poor" captures in the full width search, but it is always worse for Tinker, which just does all captures in fulll width search in MVV/LVA order.

Incidentally, Tinker does unlimited q-search captures, and for some "early" plys away from leaf levels or when in check last move (ply-2), it also does moves to empty squares near the side to move's king in the q-search. Curiously, using SEE on these "empty" capture moves was much worse also, another counter intuitive situation.

[bob]

Ahh. It is unintuitive to me that MVV/LVA is better than see order. It seems to me if you are going to go through the bother of doing SEE, you might as well use the superior information. Alas, intuition is not always right. If you are going to skip SEE for pawn captures, why not skip SEE for the superset of cases I described: capturer <= captured. I suspect it will very minorly speed up your very minor crafty speedup .
-Sam

Yes, I use MVV/LVA for move ordering, not SEE, since SEE is relatively expensive (compared to just do all pawns, or V >= A tests).

My hunch is that there are relatively few captures to begin with, and most do not need SEE since they are either pawn moves or the attacker is less valuable than the victim, so there are relatively few SEE situations.

Yes, SEE for move ordering should be better than MVV/LVA, but perhaps the cost of doing unnecessary SEEs is greater than the move ordering benefit (at least in the q-search).

Note that in Tinker's "ecosystem", SEE is only used in q-search. I have tried using SEE and postponing "poor" captures in the full width search, but it is always worse for Tinker, which just does all captures in fulll width search in MVV/LVA order.

Incidentally, Tinker does unlimited q-search captures, and for some "early" plys away from leaf levels or when in check last move (ply-2), it also does moves to empty squares near the side to move's king in the q-search. Curiously, using SEE on these "empty" capture moves was much worse also, another counter intuitive situation.

Let me add one bit of clarification to my comments. MVV/LVA without any SEE at all is definitely worse than just using SEE. The MVV/LVA benefit shows up when applied to moves that have been pre-screened so that you do not look at losing captures early in the search. Just pure MVV/LVA is on the order of 10% worse than pure SEE, in terms of tree size. If you can get your SEE fast enough, you win. Else you lose or break-even. But if you screen the moves and then search in MVV/LVA order, it is a definite win.