The Perils of missing sub-promotion

[hgm]

I actually had been contemplating the question of whether it's even worth it to search underpromotions in my new engine. I would recognize them and be able to deal with them no matter what I do, but I was thinking of having my engine just ignore them unless and until they're actually played. With the way I'm doing my move generator, it would require a small amount of extra work (and processing time) to get it to search them after non-capture moves instead of before them, but of course just ignoring them saves time in both move generation and the search. So is that small amount of saved time worth not seeing them when underpromotion is the best move?

Any thoughts?

I don't search under-promotions in Joker, and I have seen it already lose a couple of games because of it. In many cases it is a waste of time to search under-promotions, though. But you can be selective:

* If the best reply to promotion to Q is capture of that Q, no point in searching under-promotions. They can only be worse.
* If you can promote to Knight with check, try it!
* Under-promotion in most other cases only makes sense if there was a quick stalemate.

[nczempin]

I guess the recommended operation is to send an illegal-move message:

illegal move: { remains in check }

If that doesn't help, you can become more bold, and send a 'result' message, claiming the game:

result 0-1 { forfeit due to illegal move }

(and be sure to make it 1-0 if you are white! )

If that doesn't silence the GUI, sent him a 100KB string without linefeeds from a 100KB output buffer. That usually does the trick.

The way you're describing it, you've obviously tried it

[nczempin]

If I wanted to make a really fast engine, I would leave out the under-promotions. Everything becomes so much simpler when all promotions are to the queen:
There will never be three rooks, etc.
You don't need space in your move data structure
You don't have to search all those extra moves.

I think losing a couple of games due to it is a worthwhile tradeoff.


Eden has them, but it will never be a fast engine

[xsadar]

Thanks Gerd and HGM. I hadn't thought about conditionally generating underpromotions. That makes a lot of sense. Also, now that I think about it, always being unaware of knight promotions until they happen can cause trouble for a significant fraction of promotions as it would be easy to wander into a fork.

[bob]

I actually had been contemplating the question of whether it's even worth it to search underpromotions in my new engine. I would recognize them and be able to deal with them no matter what I do, but I was thinking of having my engine just ignore them unless and until they're actually played. With the way I'm doing my move generator, it would require a small amount of extra work (and processing time) to get it to search them after non-capture moves instead of before them, but of course just ignoring them saves time in both move generation and the search. So is that small amount of saved time worth not seeing them when underpromotion is the best move?

Any thoughts?

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

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

[bob]

I understand. I have just had the "pleasure" of watching programs that can't handle under-promotions (oh, only test positions require under-promotions so why should I worry about that now?), programs that are winning and don't know about the 50 move rule (oh, I have never seen that cause a problem so I didn't do anything about it...), programs that are winning or losing and don't handle 3-fold repetition properly and draw a won game or lose a drawn game as a result.

And then there are the time-control issues among others. It doesn't make any sense to leave _any_ hole exposed as with full-width searches, it is astounding how often a program will search a huge tree that contains the hole... I used to think that a full-width search spent most of its time trying to find ways to search into areas where my evaluation had a bug or hole. Now I know that such bugs or holes act like black holes and attract searches from all directions toward them.

[nczempin]

I understand. I have just had the "pleasure" of watching programs that can't handle under-promotions (oh, only test positions require under-promotions so why should I worry about that now?), programs that are winning and don't know about the 50 move rule (oh, I have never seen that cause a problem so I didn't do anything about it...), programs that are winning or losing and don't handle 3-fold repetition properly and draw a won game or lose a drawn game as a result.

And then there are the time-control issues among others. It doesn't make any sense to leave _any_ hole exposed as with full-width searches, it is astounding how often a program will search a huge tree that contains the hole... I used to think that a full-width search spent most of its time trying to find ways to search into areas where my evaluation had a bug or hole. Now I know that such bugs or holes act like black holes and attract searches from all directions toward them.

Losses on time with Fischer clocks should be impossible; it bugs me even more that an engine like Philemon starts with two minutes and ends with 4. Such low-hanging fruit to increase the strength!

Three-fold repetition is a biggie and should be a high priority, it will get you lots of points at the lower levels because your opponents don't have it.. Just ask umax how many games it drew in winning position against Eden

50-moves far less so. This becomes much more important when games regularly go to endgames. I don't think I've seen a game where 50-moves prevented a win from becoming a win. It is nice to see the engines ignore it when they move around pointlessly on the board in drawn positions, rather than moving that one pawn after 49 moves and having to endure all that again...

Knight promotions are even rarer, after all I started this thread because it so rarely happens in a real game (I'm not sure I agree with hgm's 1 %, actually I would think intuitively that it comes up not one, but two orders of magnitude less frequently---but I haven't looked through all Eden's games to check).

And while the Episode with the phone call is funny, I do feel that it is a random event (that we attribute too much significance to) that expected to occur given how many games Bob has seen.

But again, I think eventually every engine should play fully-legal chess

[hgm]

I can confirm the extreme importance of rep-draw recognition. Not only because it gives your engine a significant amount of Elo, but even more so because meaningful testing in the absence of it is hardly possible.

I have been stuck in the development of uMax for a long time, because none of the improvements I tried brought it more Elo than the characters they took for implementing. And then, finally, I had a good idea how to implement rep-draw detection. After tha, retrying the ideas that I had to reject before, suddenly did show them to be stroong improvements. Often they worked 5-10 times better than before. Initially the improvements just did not show up in the score, as while uMax was slowly getting the upper hand, the opponent would at some point realize that a draw was a good deal, and all those 'slow wins' ended in rep-draws anyway.

I think there are very good reasons _not_ to implement 50-move draw awareness. If engines are reluctant to make progress in a won position, there is something else wrong with them besides not counting the moves. After all, it is just a coincidence that FIDE rules include 50-move draws. If this rule had not existed, those engines would also not be able to win their won games.

You might think that 3-fold rep recognition might save you, but often this is more like painting yourself into a corner. It moves to more and more unfavorable position with (say) its King to avoid the rep-draw, until the King is so far from the action that the position really is not won anymore.

Better to program engines such that they go for progress rather than undecisively shuffle pieces around. (By a delayed-loss bonus? ) Relying on 50-move can actually backfire: I have seen many occurences where engines, being a Pawn ahead, fail to recognize that the opponent has more than a Pawn of compensation. Faced with the 50-moves ultimatum, they then sacrifice their plus-Pawn to avoid the draw. And subsequently lose the game, as the slight edge they thought to maintain after this actually was a losing disadvantage. The fact that an engine is not able to make progress in a 'won' position is in most cases due to misevaluation: it is not as won as it imagines.

Joker does not award 50-move draws to tree nodes. It does switch to a different evaluation function (putting more ephasis on advancing Pawns) after 20 reversible moves, though, when ahead. So if its normal evaluation does not see a way to make progress in 20 moves by shuffling around pieces, it switches to 'plan B', to try if aggressive Pawn pushing helps. That avoids the 50-move trap almost always.

[nczempin]

I think there are very good reasons _not_ to implement 50-move draw awareness. If engines are reluctant to make progress in a won position, there is something else wrong with them besides not counting the moves. After all, it is just a coincidence that FIDE rules include 50-move draws. If this rule had not existed, those engines would also not be able to win their won games.

You might think that 3-fold rep recognition might save you, but often this is more like painting yourself into a corner. It moves to more and more unfavorable position with (say) its King to avoid the rep-draw, until the King is so far from the action that the position really is not won anymore.

Better to program engines such that they go for progress rather than undecisively shuffle pieces around. (By a delayed-loss bonus? ) Relying on 50-move can actually backfire: I have seen many occurences where engines, being a Pawn ahead, fail to recognize that the opponent has more than a Pawn of compensation. Faced with the 50-moves ultimatum, they then sacrifice their plus-Pawn to avoid the draw. And subsequently lose the game, as the slight edge they thought to maintain after this actually was a losing disadvantage. The fact that an engine is not able to make progress in a 'won' position is in most cases due to misevaluation: it is not as won as it imagines.

Well, there is a case against shuffling around; there should always be some minor way to improve your position. But not implementing 50 moves is not a solution to this problem, but only a workaround.