Potentially Trapped Pieces

[JVMerlino]

Greetings,

I know that it's relatively easy to determine some kinds of trapped pieces, such as a bishop on h7 with enemy pawns on g6 and f7. However, my engine has come across a few positions in which a piece can be trapped if an escape route is not created immediately.

Here are two examples:

[D]r4r2/p1q1n1kp/2n1ppp1/8/3P2N1/3BPP2/2Q2P1P/R3K2R w KQ - 0 19

In this one, h3 or h4 are required immediately, otherwise the knight on g4 will be trapped with h5. It's not really a question of mobility, as the knight currently has three squares to move to.

[D]r4rk1/1p2ppbp/pq1p2p1/3P4/1nP3n1/2N2N2/PP2QPPP/R1B2RK1 b - - 0 18

This is similar in appearance, but even more difficult for my engine to solve. The move required is a5, or else the b4-knight (which now has five squares to move to) is lost with a3. This position also has more potential exchanges/captures that can really extend the search.

Myrddin now solves the first position in less than two seconds, but the second one still takes 54 seconds (on a P4-3.0).

So, my question (finally). Is it worth it to try to find this kind of potentially trapped piece in the static eval, checking every escape square to see if it is being attacked (sounds expensive to me), or should search improvements be enough to handle most cases?

Many thanks in advance,
jm

[bob]

Greetings,

I know that it's relatively easy to determine some kinds of trapped pieces, such as a bishop on h7 with enemy pawns on g6 and f7. However, my engine has come across a few positions in which a piece can be trapped if an escape route is not created immediately.

Here are two examples:

[D]r4r2/p1q1n1kp/2n1ppp1/8/3P2N1/3BPP2/2Q2P1P/R3K2R w KQ - 0 19

In this one, h3 or h4 are required immediately, otherwise the knight on g4 will be trapped with h5. It's not really a question of mobility, as the knight currently has three squares to move to.

[D]r4rk1/1p2ppbp/pq1p2p1/3P4/1nP3n1/2N2N2/PP2QPPP/R1B2RK1 b - - 0 18

This is similar in appearance, but even more difficult for my engine to solve. The move required is a5, or else the b4-knight (which now has five squares to move to) is lost with a3. This position also has more potential exchanges/captures that can really extend the search.

Myrddin now solves the first position in less than two seconds, but the second one still takes 54 seconds (on a P4-3.0).

So, my question (finally). Is it worth it to try to find this kind of potentially trapped piece in the static eval, checking every escape square to see if it is being attacked (sounds expensive to me), or should search improvements be enough to handle most cases?

Many thanks in advance,
jm

This looks like a search issue, not an evaluation issue. In the second position, it takes Crafty 8 plies to see this. In a fraction of a second. The first is even quicker. The key is the delaying moves the opponent can make once the piece is threatened and has nowhere to go. I can't imagine why this would take almost a minute to spot...

[JVMerlino]

This looks like a search issue, not an evaluation issue. In the second position, it takes Crafty 8 plies to see this. In a fraction of a second. The first is even quicker. The key is the delaying moves the opponent can make once the piece is threatened and has nowhere to go. I can't imagine why this would take almost a minute to spot...

For the second position, the fail happens in less than four seconds, but (perhaps somewhat due to poor move ordering?) it takes 50 seconds to resolve:

Code: Select all

 1   571      7        82 b6f2 f1f2 g4f2 e2f2 g7c3 b2c3
 1   -25      7       130 g7c3 b2c3
 2   -25      7       368 g7c3 b2c3
 3    15      7      1679 g7c3
 3    14      9      7017 f8c8 c1d2 g4e5 b2c3
 4    17     17     31625 f8c8 c1d2 g7f6 f3g5
 5    57     45    120026 f8c8 c1d2 g7f6 a2a3 b4c2 d2c3
 5    31     62    178927 f8e8 a2a3 b6a5 c1d2 b4c2 d2c3
 5    28    100    284842 g7f6 a2a3 b6a5 c1d2 b4c2
 5    21    135    415400 a8c8 a2a3 b6a5 c1d2 b4c2 d2c3
 6    22    214    697672 a8c8 a2a3 b6a5 c1d2 g7c3 d2c3
 7    62    379   1263945 a8c8
 7   160   1831   6151999 a8c8 a2a3 g7c3 b2c3 b4d5 c4d5 c8c3 e2e7
 7   148   2404   8069465 a8a7 a2a3 g7c3 b2c3 b4c6 d5c6 b7c6
 7   128   4803  17524200 g7d4 f3d4 b6d4 e2e7 d4e5 e7e5 g4e5
 7    78   5456  19661045 a6a5 a2a3 b4a6 e2e7 g7c3 b2c3 f8e8
 8    78   7723  25146094 a6a5 a2a3 b4a6 e2e7 g7c3 b2c3 f8e8

jm

[bob]

This looks like a search issue, not an evaluation issue. In the second position, it takes Crafty 8 plies to see this. In a fraction of a second. The first is even quicker. The key is the delaying moves the opponent can make once the piece is threatened and has nowhere to go. I can't imagine why this would take almost a minute to spot...

For the second position, the fail happens in less than four seconds, but (perhaps somewhat due to poor move ordering?) it takes 50 seconds to resolve:

Code: Select all

 1   571      7        82 b6f2 f1f2 g4f2 e2f2 g7c3 b2c3
 1   -25      7       130 g7c3 b2c3
 2   -25      7       368 g7c3 b2c3
 3    15      7      1679 g7c3
 3    14      9      7017 f8c8 c1d2 g4e5 b2c3
 4    17     17     31625 f8c8 c1d2 g7f6 f3g5
 5    57     45    120026 f8c8 c1d2 g7f6 a2a3 b4c2 d2c3
 5    31     62    178927 f8e8 a2a3 b6a5 c1d2 b4c2 d2c3
 5    28    100    284842 g7f6 a2a3 b6a5 c1d2 b4c2
 5    21    135    415400 a8c8 a2a3 b6a5 c1d2 b4c2 d2c3
 6    22    214    697672 a8c8 a2a3 b6a5 c1d2 g7c3 d2c3
 7    62    379   1263945 a8c8
 7   160   1831   6151999 a8c8 a2a3 g7c3 b2c3 b4d5 c4d5 c8c3 e2e7
 7   148   2404   8069465 a8a7 a2a3 g7c3 b2c3 b4c6 d5c6 b7c6
 7   128   4803  17524200 g7d4 f3d4 b6d4 e2e7 d4e5 e7e5 g4e5
 7    78   5456  19661045 a6a5 a2a3 b4a6 e2e7 g7c3 b2c3 f8e8
 8    78   7723  25146094 a6a5 a2a3 b4a6 e2e7 g7c3 b2c3 f8e8

jm

I'm assuming no null-move search yet? That's about the only reason I could think of where a 7 ply search would take that long...

[JVMerlino]

This looks like a search issue, not an evaluation issue. In the second position, it takes Crafty 8 plies to see this. In a fraction of a second. The first is even quicker. The key is the delaying moves the opponent can make once the piece is threatened and has nowhere to go. I can't imagine why this would take almost a minute to spot...

For the second position, the fail happens in less than four seconds, but (perhaps somewhat due to poor move ordering?) it takes 50 seconds to resolve:

Code: Select all

 1   571      7        82 b6f2 f1f2 g4f2 e2f2 g7c3 b2c3
 1   -25      7       130 g7c3 b2c3
 2   -25      7       368 g7c3 b2c3
 3    15      7      1679 g7c3
 3    14      9      7017 f8c8 c1d2 g4e5 b2c3
 4    17     17     31625 f8c8 c1d2 g7f6 f3g5
 5    57     45    120026 f8c8 c1d2 g7f6 a2a3 b4c2 d2c3
 5    31     62    178927 f8e8 a2a3 b6a5 c1d2 b4c2 d2c3
 5    28    100    284842 g7f6 a2a3 b6a5 c1d2 b4c2
 5    21    135    415400 a8c8 a2a3 b6a5 c1d2 b4c2 d2c3
 6    22    214    697672 a8c8 a2a3 b6a5 c1d2 g7c3 d2c3
 7    62    379   1263945 a8c8
 7   160   1831   6151999 a8c8 a2a3 g7c3 b2c3 b4d5 c4d5 c8c3 e2e7
 7   148   2404   8069465 a8a7 a2a3 g7c3 b2c3 b4c6 d5c6 b7c6
 7   128   4803  17524200 g7d4 f3d4 b6d4 e2e7 d4e5 e7e5 g4e5
 7    78   5456  19661045 a6a5 a2a3 b4a6 e2e7 g7c3 b2c3 f8e8
 8    78   7723  25146094 a6a5 a2a3 b4a6 e2e7 g7c3 b2c3 f8e8

jm

I'm assuming no null-move search yet? That's about the only reason I could think of where a 7 ply search would take that long...

If only it were that simple. Null move is implemented. Without null move it takes 73 seconds. <sigh>

jm

[MattieShoes]

This looks like a search issue, not an evaluation issue. In the second position, it takes Crafty 8 plies to see this. In a fraction of a second. The first is even quicker. The key is the delaying moves the opponent can make once the piece is threatened and has nowhere to go. I can't imagine why this would take almost a minute to spot...

For the second position, the fail happens in less than four seconds, but (perhaps somewhat due to poor move ordering?) it takes 50 seconds to resolve:

Code: Select all

 1   571      7        82 b6f2 f1f2 g4f2 e2f2 g7c3 b2c3
 1   -25      7       130 g7c3 b2c3
 2   -25      7       368 g7c3 b2c3
 3    15      7      1679 g7c3
 3    14      9      7017 f8c8 c1d2 g4e5 b2c3
 4    17     17     31625 f8c8 c1d2 g7f6 f3g5
 5    57     45    120026 f8c8 c1d2 g7f6 a2a3 b4c2 d2c3
 5    31     62    178927 f8e8 a2a3 b6a5 c1d2 b4c2 d2c3
 5    28    100    284842 g7f6 a2a3 b6a5 c1d2 b4c2
 5    21    135    415400 a8c8 a2a3 b6a5 c1d2 b4c2 d2c3
 6    22    214    697672 a8c8 a2a3 b6a5 c1d2 g7c3 d2c3
 7    62    379   1263945 a8c8
 7   160   1831   6151999 a8c8 a2a3 g7c3 b2c3 b4d5 c4d5 c8c3 e2e7
 7   148   2404   8069465 a8a7 a2a3 g7c3 b2c3 b4c6 d5c6 b7c6
 7   128   4803  17524200 g7d4 f3d4 b6d4 e2e7 d4e5 e7e5 g4e5
 7    78   5456  19661045 a6a5 a2a3 b4a6 e2e7 g7c3 b2c3 f8e8
 8    78   7723  25146094 a6a5 a2a3 b4a6 e2e7 g7c3 b2c3 f8e8

jm

I'm assuming no null-move search yet? That's about the only reason I could think of where a 7 ply search would take that long...

If only it were that simple. Null move is implemented. Without null move it takes 73 seconds. <sigh>

jm

My engine is nowhere near as fast as crafty but still finds a5 on ply 7 in just a few seconds. Do you have move ordering at all? It makes an enormous difference

[JVMerlino]

I'm assuming no null-move search yet? That's about the only reason I could think of where a 7 ply search would take that long...

If only it were that simple. Null move is implemented. Without null move it takes 73 seconds. <sigh>

jm

My engine is nowhere near as fast as crafty but still finds a5 on ply 7 in just a few seconds. Do you have move ordering at all? It makes an enormous difference

Yep, move ordering is there: PV moves, then hash moves, captures (MVV/LVA) and checks. Killer moves and history heuristic are there also.

But this did give me an idea which I am looking into. Currently, I am only sorting the move scores for the first handful of moves (depending on the total number of moves), and not bothering to sort the rest. This did slow some positions down (primarily positions that fail low, of course) but gave me an overall improvement for general gameplay due to the speed increase.

Hmmmm.....

jm

[JVMerlino]

I'm assuming no null-move search yet? That's about the only reason I could think of where a 7 ply search would take that long...

If only it were that simple. Null move is implemented. Without null move it takes 73 seconds. <sigh>

jm

My engine is nowhere near as fast as crafty but still finds a5 on ply 7 in just a few seconds. Do you have move ordering at all? It makes an enormous difference

Yep, move ordering is there: PV moves, then hash moves, captures (MVV/LVA) and checks. Killer moves and history heuristic are there also.

But this did give me an idea which I am looking into. Currently, I am only sorting the move scores for the first handful of moves (depending on the total number of moves), and not bothering to sort the rest. This did slow some positions down (primarily positions that fail low, of course) but gave me an overall improvement for general gameplay due to the speed increase.

Hmmmm.....

jm

p.s. Checking the move ordering scores, at depth 7 the move a5 is ordered 28th out of 45 moves.

jm

[CRoberson]

I'm assuming no null-move search yet? That's about the only reason I could think of where a 7 ply search would take that long...

If only it were that simple. Null move is implemented. Without null move it takes 73 seconds. <sigh>

jm

My engine is nowhere near as fast as crafty but still finds a5 on ply 7 in just a few seconds. Do you have move ordering at all? It makes an enormous difference

Yep, move ordering is there: PV moves, then hash moves, captures (MVV/LVA) and checks. Killer moves and history heuristic are there also.

But this did give me an idea which I am looking into. Currently, I am only sorting the move scores for the first handful of moves (depending on the total number of moves), and not bothering to sort the rest. This did slow some positions down (primarily positions that fail low, of course) but gave me an overall improvement for general gameplay due to the speed increase.

Hmmmm.....

jm

Telepath found it in 7 ply and searched 898,513 nodes compared
to your 19.6 million nodes. Given that you have Null move working,
maybe you have a bug in transposition tables. Also, are you using
LMR?

Your move ordering is different from mine. I don't use hashmoves
or checks. Could you possibly be ordering some of the history
moves before the killers?

[JVMerlino]

I'm assuming no null-move search yet? That's about the only reason I could think of where a 7 ply search would take that long...

If only it were that simple. Null move is implemented. Without null move it takes 73 seconds. <sigh>

jm

My engine is nowhere near as fast as crafty but still finds a5 on ply 7 in just a few seconds. Do you have move ordering at all? It makes an enormous difference

Yep, move ordering is there: PV moves, then hash moves, captures (MVV/LVA) and checks. Killer moves and history heuristic are there also.

But this did give me an idea which I am looking into. Currently, I am only sorting the move scores for the first handful of moves (depending on the total number of moves), and not bothering to sort the rest. This did slow some positions down (primarily positions that fail low, of course) but gave me an overall improvement for general gameplay due to the speed increase.

Hmmmm.....

jm

Telepath found it in 7 ply and searched 898,513 nodes compared
to your 19.6 million nodes. Given that you have Null move working,
maybe you have a bug in transposition tables. Also, are you using
LMR?

Your move ordering is different from mine. I don't use hashmoves
or checks. Could you possibly be ordering some of the history
moves before the killers?

Yes, I am using LMR.

Turning off hash tables takes 90 seconds and just over 30 million nodes.

Here are the hash stats upon reaching the correct answer:
Hash Saves = 894539
Failed Saves (stale data) = 150425
Hash Probes = 5117049
Hash Hits = 351165
Hash Returns = 89798
Hash Zeroes (probes of positions with no hash data) = 4562136

I have no idea if this is remotely decent performance or not.

And, no, history moves (with no other modifiers) will never be scored higher than a killer move.

jm