The Perils of missing sub-promotion

[xsadar]

I see no reason to omit them. Null-move makes them go quickly, and often the hash table cuts the trees off since any promotion gets ripped off the board instantly...

I think once your engine reaches a certain strength, it really should play proper chess. However, if you are starting out, you can get a long way without them.

As I said, I am not eating my own dog food here, as Eden had them from very early on, perhaps even the first release
( I wanted it to follow the path of a human beginner, and those I would tell about underpromotions but then say "you'll usually want to promote to a queen, so don't worry about it". Games at low levels are not lost because there is a fork from a sub-promoted pawn.)

I still have the inefficient "Move" class that included the "promotedPiece".

But especially for a program like uMax, it will not be possible to increase the Elo/character by adding them.

But why leave them out if having them is an improvement. It's not like they're difficult to implement. The point of my question was are they an improvement or a waste of time. That's processing time of course, not programming time, as I've probably spent more time discussing them on this forum than what it takes to implement them. In fact, I had already implemented them before I asked the question, but I was considering removing them completely (just from the search of course) or changing where they were in my move ordering. I think I'll do neither, although I may have it only generate rook and bishop promotions if queen promotion results in a draw. Knight promotions really need to be searched unless the queen promotion results in a capture, in which case the knight promotion should result in a hash cut anyway.
uMax of course has very different goals than most of us, so in HGM's case he may not want to implement them for that engine.

[nczempin]

The answer is yes. I have seen multiple programs lose tournament games due to this trivially fixable oversight. The most amusing was a program "LaChex" at an ACM event where we had a long discussion about this and Burton Wendroff left going back to his home in Los Alamos (the event was in Albuquerque) and since he didn't do underpromotions, he told Tony Warnock as he left "if this is ever a problem, call me". Before Burton got back to Los Alamos (about 80 miles or so away) Tony called him on his cell phone and said "OK, it's a problem. We just lost the game we were winning because we overlooked a knight fork that led to a forced mate, even though we were a queen+ ahead". By the next round lachex was doing underpromotions...

I see no reason to omit them. Null-move makes them go quickly, and often the hash table cuts the trees off since any promotion gets ripped off the board instantly...

Thanks for your input Bob. You make a very good point about hash cuts. Also, I had realized after seeing the other responses that knight promotions really do need to be searched or the engine will likely stumble into a few too many unnecessary knight forks.
Searching bishop and rook promotions however doesn't seem necessary to me most of the time, but would be useful if a queen promotion returns a draw score. It would be trivial to generate them only in that case. Do you know of any other case where I would need to search them?

I am aware of only one position type where you need to promote to the rook to avoid a stalemate. When I implemented subpromotions way back when, I tried to find test cases for all of them. AFAIR, I was not able to create a test case where you needed to promote to a bishop. Does anyone have one?

[nczempin]

I see no reason to omit them. Null-move makes them go quickly, and often the hash table cuts the trees off since any promotion gets ripped off the board instantly...

I think once your engine reaches a certain strength, it really should play proper chess. However, if you are starting out, you can get a long way without them.

As I said, I am not eating my own dog food here, as Eden had them from very early on, perhaps even the first release
( I wanted it to follow the path of a human beginner, and those I would tell about underpromotions but then say "you'll usually want to promote to a queen, so don't worry about it". Games at low levels are not lost because there is a fork from a sub-promoted pawn.)

I still have the inefficient "Move" class that included the "promotedPiece".

But especially for a program like uMax, it will not be possible to increase the Elo/character by adding them.

But why leave them out if having them is an improvement. It's not like they're difficult to implement. The point of my question was are they an improvement or a waste of time. That's processing time of course, not programming time, as I've probably spent more time discussing them on this forum than what it takes to implement them. In fact, I had already implemented them before I asked the question, but I was considering removing them completely (just from the search of course) or changing where they were in my move ordering. I think I'll do neither, although I may have it only generate rook and bishop promotions if queen promotion results in a draw. Knight promotions really need to be searched unless the queen promotion results in a capture, in which case the knight promotion should result in a hash cut anyway.
uMax of course has very different goals than most of us, so in HGM's case he may not want to implement them for that engine.

WHy leave them out? "Make the common case fast". You do not get them for free. Bob has made a few valid points that they will disappear quickly, but quickly is not the same as zero time
You have extra moves to generate, your move struct needs extra information to hold the piece type (when you do queens only, all pawn moves to the back rank are queen promotions, so there is no need to store that redundant information. It can add up.

However, I have not done any measurements on this. Presumably the effect either way would be more prevalent at endgames. Not sure if 20,000 games of the 80 positions would show a significance either way. Perhaps there are some good endgame suites one could use.

And coding them does not take zero characters. While this goal is driven to the extreme with uMax, in general (other things being equal) it is better to have less code for a given task; the fastest, most reliable and easiest to maintain lines of code are those that aren't there (now where have I read that recently )

[nczempin]

Incidentally, I just encountered another thing that immature engines, and perhaps some of the stronger ones, like to leave out: Recognition of insufficient material. Both in the "hard" way as well as as a bound, so you can say (like a human would) "if I swap all those pieces the maximum my opponent can get is a draw"

[Uri Blass]

There was a discussion about it in the israeli forum

There was a question to find a position with minimal number of pieces when underpromotion to bishop is the only drawing move

[D]r6K/6PP/4k1q1/8/8/8/8/8 w - - 0 1

There was a question to find a position with 5 pieces when underpromotion to bishop is the only winning move and here is the solution.

[D]8/8/8/8/8/7k/3n1p2/6BK b - - 0 1

Another example from a game between humans

[D]8/8/8/8/K7/4N3/kp6/4b3 w - - 0 1

White played Nd1
black played the only winning move(underpromotion to bishop) but practically failed to win the game.

[nczempin]

There was a discussion about it in the israeli forum

There was a question to find a position with minimal number of pieces when underpromotion to bishop is the only drawing move

[D]r6K/6PP/4k1q1/8/8/8/8/8 w - - 0 1

There was a question to find a position with 5 pieces when underpromotion to bishop is the only winning move and here is the solution.

[D]8/8/8/8/8/7k/3n1p2/6BK b - - 0 1

Another example from a game between humans

[D]8/8/8/8/K7/4N3/kp6/4b3 w - - 0 1

White played Nd1
black played the only winning move(underpromotion to bishop) but practically failed to win the game.

Ah, nice, thanks! I'll add those to my test suite.

[xsadar]

I generate underpromotion conditionally after unmaking the queen promotion without cutoff. If the promoted queen got captured (best reply), I don't generate them at all, because one can at least capture the underpromoted piece as well with same score. Otherwise, I generate knight-promotion and if queen-promotion returns stalemate score, even bishop- and rook-promotions. Seems to cover most issues

Are there counter examples where the above heuristic fails?

Looks like Uri had one. He posted this in another branch of the discussion.

There was a question to find a position with minimal number of pieces when underpromotion to bishop is the only drawing move

[D]r6K/6PP/4k1q1/8/8/8/8/8 w - - 0 1

Because you only search bishop and rook promotions when queen promotion leads to a draw, you only see g8=Q+ where black mates in 2 (Kf6 Qxa8 Qg7#), but white can get a draw by g8=B+ since all king moves for black are now stalemates and Rxg8+ also leads to a draw.

Positions like this are probably extremely rare, but it probably wouldn't hurt to also search bishop and rook promotions when queen promotions result in the promoting player being mated. In fact, now that I think about it, you definitely would want to search them in that case. If a player is getting mated, you would want to consider all possible moves for that player. I'm still not sure that covers every situation where bishop or rook promotion's the best move but it should probably be sufficient.

[xsadar]

I see no reason to omit them. Null-move makes them go quickly, and often the hash table cuts the trees off since any promotion gets ripped off the board instantly...

I think once your engine reaches a certain strength, it really should play proper chess. However, if you are starting out, you can get a long way without them.

As I said, I am not eating my own dog food here, as Eden had them from very early on, perhaps even the first release
( I wanted it to follow the path of a human beginner, and those I would tell about underpromotions but then say "you'll usually want to promote to a queen, so don't worry about it". Games at low levels are not lost because there is a fork from a sub-promoted pawn.)

I still have the inefficient "Move" class that included the "promotedPiece".

But especially for a program like uMax, it will not be possible to increase the Elo/character by adding them.

But why leave them out if having them is an improvement. It's not like they're difficult to implement. The point of my question was are they an improvement or a waste of time. That's processing time of course, not programming time, as I've probably spent more time discussing them on this forum than what it takes to implement them. In fact, I had already implemented them before I asked the question, but I was considering removing them completely (just from the search of course) or changing where they were in my move ordering. I think I'll do neither, although I may have it only generate rook and bishop promotions if queen promotion results in a draw. Knight promotions really need to be searched unless the queen promotion results in a capture, in which case the knight promotion should result in a hash cut anyway.
uMax of course has very different goals than most of us, so in HGM's case he may not want to implement them for that engine.

WHy leave them out? "Make the common case fast". You do not get them for free. Bob has made a few valid points that they will disappear quickly, but quickly is not the same as zero time
You have extra moves to generate, your move struct needs extra information to hold the piece type (when you do queens only, all pawn moves to the back rank are queen promotions, so there is no need to store that redundant information. It can add up.

However, I have not done any measurements on this. Presumably the effect either way would be more prevalent at endgames. Not sure if 20,000 games of the 80 positions would show a significance either way. Perhaps there are some good endgame suites one could use.

And coding them does not take zero characters. While this goal is driven to the extreme with uMax, in general (other things being equal) it is better to have less code for a given task; the fastest, most reliable and easiest to maintain lines of code are those that aren't there (now where have I read that recently )

Sorry I thought you were implying that having underpromotions made the engine better. My question, "Why leave them out . . . ?" applied only to that case (as I indicated in the question itself). After reading people's comments and thinking about it, I think it probably is worth it to search them (for me at least), but like you, I haven't tested it.

My rational is based on the idea that knight promotions if not seen in advance can be dangerous due to forks. Also, while they don't take zero time overall, they do take zero time (at least for me) when there are no promotions to search (the common case), so I only need to consider how it affects performance for positions where promotions are legal, because that's the only place there's a tradeoff. Adding knight promotion in my Move generator, because it can be done along with the queen promotions, requires just two additional statements: Move.PromTo = KNIGHT; MoveList[nMoves++] = Move; Searching knight promotions will result in a hash cut-off if capturing a queen promotion is the best move. If capture is not the best move, there's the potential for a fork. As for rook and bishop promotions, they will probably only be generated and searched if queen promotion forces the promoting player into a draw or a mate, in which case it can only help my ELO even if by a miniscule amount. Storing the extra information in my move struct is not a problem either as those 3 bits would be wasted otherwise.

[Gerd Isenberg]

I generate underpromotion conditionally after unmaking the queen promotion without cutoff. If the promoted queen got captured (best reply), I don't generate them at all, because one can at least capture the underpromoted piece as well with same score. Otherwise, I generate knight-promotion and if queen-promotion returns stalemate score, even bishop- and rook-promotions. Seems to cover most issues

Are there counter examples where the above heuristic fails?

Looks like Uri had one. He posted this in another branch of the discussion.

[D]r6K/6PP/4k1q1/8/8/8/8/8 w - - 0 1

Thanks Mike and Uri for pointing that out - very nice position. The ability of the pinned queen to move in zugzwang is deadly here.
At least my program is able to solve it at the root

Yes, i think if queen promotion is less or equal to draw - without capturing the queen as best reply - one may try all minor promotions as well.

Gerd

[xsadar]

Incidentally, I just encountered another thing that immature engines, and perhaps some of the stronger ones, like to leave out: Recognition of insufficient material. Both in the "hard" way as well as as a bound, so you can say (like a human would) "if I swap all those pieces the maximum my opponent can get is a draw"

I can't imagine a reason to leave out recognition for insufficient material. It's simple enough to do for most cases and fairly common. The rare case of having multiple bishops on the same color could be an exception, which technically isn't insufficient material but still a dead position. I've noticed that most engines don't seem to recognize that specific case, but they may not have even realized such a case existed, and it's probably not too important anyway.