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.

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.

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

[Sven]

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 do you think SEE would go negative here? I would not assume that for a correct implementation.

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.

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.

Again, I think that a correct SEE implementation should cover most of these cases. A pawn that promotes and is not captured should count as "+MatValue[Queen]-MatValue[Pawn]". An ep capture without recapture should count as "+MatValue[Pawn]".

Regarding your last example, I'm not exactly sure what you mean. Is it possible that you mean "we capture with a rook that gets *pinned* when his pawn is removed"? For instance, do you think of a position like this one? (EDIT: considering the SEE value of 1.c4, of course.) (2nd EDIT: my example is not perfect since the white rook gets lost on c3 but maybe we can simply ignore this )

[d]8/8/1K1B4/2R5/3p4/4b3/2Pk4/2r5 w KQkq - 0 1
In this case, it is true that SEE usually does not detect the pin. But I still don't understand why you say this would result in a value of -100, it should be 0 since there is a capture and a recapture on the same square (the target square of the ep capture). Maybe you think of something different, so could you please give an example?

Sven

[Pablo Vazquez]

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 do you think SEE would go negative here? I would not assume that for a correct implementation.

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.

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.

Again, I think that a correct SEE implementation should cover most of these cases. A pawn that promotes and is not captured should count as "+MatValue[Queen]-MatValue[Pawn]". An ep capture without recapture should count as "+MatValue[Pawn]".

Regarding your last example, I'm not exactly sure what you mean. Is it possible that you mean "we capture with a rook that gets *pinned* when his pawn is removed"? For instance, do you think of a position like this one? (EDIT: considering the SEE value of 1.c4, of course.) (2nd EDIT: my example is not perfect since the white rook gets lost on c3 but maybe we can simply ignore this )

[d]8/8/1K1B4/2R5/3p4/4b3/2Pk4/2r5 w KQkq - 0 1
In this case, it is true that SEE usually does not detect the pin. But I still don't understand why you say this would result in a value of -100, it should be 0 since there is a capture and a recapture on the same square (the target square of the ep capture). Maybe you think of something different, so could you please give an example?

Sven

Hi Sven,

It would not be difficult to modify a normal SEE and make it handle ep and promotions correctly, but a lot of programs keep it simple and only consider normal captures, I guess there is a reason for this.

In the second ep example I meant something like this:

[d]1r2k3/8/8/1pP5/8/8/8/1R2K3 w - b6

A normal SEE would make the pawn capture (which would have a value of 0 when in fact we have won the enemy pawn) and then black would capture with his rook and captures would end, and it would be a SEE value of -100. If the SEE could handle ep captures, the first value would be 100, the second would be 0 and the third would be 500, and the captures would stop after the ep capture, having a SEE value of 100.

[Sven]

It would not be difficult to modify a normal SEE and make it handle ep and promotions correctly, but a lot of programs keep it simple and only consider normal captures, I guess there is a reason for this.

In the second ep example I meant something like this:

[d]1r2k3/8/8/1pP5/8/8/8/1R2K3 w - b6

A normal SEE would make the pawn capture (which would have a value of 0 when in fact we have won the enemy pawn) and then black would capture with his rook and captures would end, and it would be a SEE value of -100. If the SEE could handle ep captures, the first value would be 100, the second would be 0 and the third would be 500, and the captures would stop after the ep capture, having a SEE value of 100.

An SEE implementation that considers an ep capture but does not count the captured pawn as +100 is buggy IMO, not "normal". The same applies to promotions, I see no good reason for ignoring the promotion piece (always Queen). Your other point with the rook that attacks one more square after the ep capture is similar to cases like doubled rooks, where the capture with the first rook uncovers the attack by the second rook behind it. These cases can be handled by updating the list of attackers to the target square after each capture, adding those attackers that were hidden until that capture occurred.

Of course it is possible that many implementations are missing this detail for reasons of simplicity.

Have you had a look at the SEE implementation of Fruit 2.1? AFAIK it does not have the limitations you have mentioned. Especially it includes detection of these "hidden attacks", which might give you an idea about how to implement this within your own SEE and its data structures.

Sven

[Pablo Vazquez]

It would not be difficult to modify a normal SEE and make it handle ep and promotions correctly, but a lot of programs keep it simple and only consider normal captures, I guess there is a reason for this.

In the second ep example I meant something like this:

[d]1r2k3/8/8/1pP5/8/8/8/1R2K3 w - b6

A normal SEE would make the pawn capture (which would have a value of 0 when in fact we have won the enemy pawn) and then black would capture with his rook and captures would end, and it would be a SEE value of -100. If the SEE could handle ep captures, the first value would be 100, the second would be 0 and the third would be 500, and the captures would stop after the ep capture, having a SEE value of 100.

An SEE implementation that considers an ep capture but does not count the captured pawn as +100 is buggy IMO, not "normal". The same applies to promotions, I see no good reason for ignoring the promotion piece (always Queen). Your other point with the rook that attacks one more square after the ep capture is similar to cases like doubled rooks, where the capture with the first rook uncovers the attack by the second rook behind it. These cases can be handled by updating the list of attackers to the target square after each capture, adding those attackers that were hidden until that capture occurred.

Of course it is possible that many implementations are missing this detail for reasons of simplicity.

Have you had a look at the SEE implementation of Fruit 2.1? AFAIK it does not have the limitations you have mentioned. Especially it includes detection of these "hidden attacks", which might give you an idea about how to implement this within your own SEE and its data structures.

Sven

My SEE recognizes hidden attacks, like all the other ones out there, but still, that case is an en passant problem and you need special code in the SEE function to remove the captured pawn, so new attacks can be detected.

[Sven]

My SEE recognizes hidden attacks, like all the other ones out there, but still, that case is an en passant problem and you need special code in the SEE function to remove the captured pawn, so new attacks can be detected.

If you use SEE for possibly pruning away losing captures during qsearch only, your ep problem could be solved easily IMO since in this case an ep capture can only occur at the first ply of qsearch and therefore especially not in the middle of a capture sequence that is subject to SEE. So you only have to check for an ep capture and the possible hidden attacks that it uncovers once per qsearch move, not in the recursive part of SEE. This should not require too much special effort in your code.

Sven

[Don]

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.

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.

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

Most program (thought not all) only care about losing captures, which get sorted to a position later in the move list. The sorting order is most valuable victim first, then least valuable attacker if it's not a losing capture. But en-passant is not a losing capture so it would be sorted as if it was PxP.

There has been much discussion on this site about how to do all of this and you will get some disagreement, but if you do it this way you don't have to worry about en-passant captures, just consider them adequate captures. And your program will be slightly faster according to most program authors.

Losing captures get placed later in the list - some programs put them after all the other captures, others place them after the killers and still others put them even farther down the list.

[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

[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).

[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...