Underpromotion?

[ethanara]

http://www.chessgames.com/perl/chessgame?gid=1497426
in this game nakamura wins over rybka in blitz and underpromote quite a few bishops
Couldnt he just promote to queen?

[hgm]

I found a funny case of how not considering under-promotion can cost you points,in a game between Spartacus and Joker yesterday:

[d]1b6/8/8/8/8/8/3k2Kp/8 w

I couldn't believe my eyes when I saw Spartacus play Kf2? here! First I expected a horrific bug,but later I realize it counted on a1=Q being a stalemate, and simply playing Kg2 after any other move.Funny thing was that it got away with it, because Joker does not know any under-promotion either, and had no problem rejecting a1=Q because of the stalemate. So they went on,and the Kf2? move was repeated several times with the Bishop in various locations, before the 50-move rule finally ended the game. Any under-promotion would have been winning!

The lesson is that if you don't implement under-promotion, you cannot reliably draw KBPK!

[michiguel]

I found a funny case of how not considering under-promotion can cost you points,in a game between Spartacus and Joker yesterday:

[d]1b6/8/8/8/8/8/3k2Kp/8 w

I couldn't believe my eyes when I saw Spartacus play Kf2? here! First I expected a horrific bug,but later I realize it counted on a1=Q being a stalemate, and simply playing Kg2 after any other move.Funny thing was that it got away with it, because Joker does not know any under-promotion either, and had no problem rejecting a1=Q because of the stalemate. So they went on,and the Kf2? move was repeated several times with the Bishop in various locations, before the 50-move rule finally ended the game. Any under-promotion would have been winning!

The lesson is that if you don't implement under-promotion, you cannot reliably draw KBPK!

Beautiful example!

Miguel

[bob]

I found a funny case of how not considering under-promotion can cost you points,in a game between Spartacus and Joker yesterday:

[d]1b6/8/8/8/8/8/3k2Kp/8 w

I couldn't believe my eyes when I saw Spartacus play Kf2? here! First I expected a horrific bug,but later I realize it counted on a1=Q being a stalemate, and simply playing Kg2 after any other move.Funny thing was that it got away with it, because Joker does not know any under-promotion either, and had no problem rejecting a1=Q because of the stalemate. So they went on,and the Kf2? move was repeated several times with the Bishop in various locations, before the 50-move rule finally ended the game. Any under-promotion would have been winning!

The lesson is that if you don't implement under-promotion, you cannot reliably draw KBPK!

Beautiful example!

Miguel

I was at an ACM converence (1992 I think) in Albuquerque NM. Lachex (wendroff/warnock) was playing in a game and we (several of the authors) had been discussing and arguing this point back and forth for quite a while. Burt (Wendroff) did not do under-promotions in Lachex while several of the others did. He finally said "OK, when I see this cause a problem, I'll add it." This was a 2-round day (at 40/2hrs so the games were long) and he left about midnight driving back up to Los Alamos where he lived (about 90 miles). Within half an hour after he left, this same sort of position came up and Lachex lost when it should have won. Tony (Warnock) waited until Burt got home and called him and said "OK, time to add under-promotions." Burt asked "why?" He replied "because we just lost a game because of it." And he dutifully added it that night.

These unusual things often happen at the worst possible time. I don't think under-promotions add enough overhead to measure with a good hash table implementation employed... If a8=Q fails, a8=B ought to fail exactly the same way and result in a hash hit.

[hgm]

Well, my reasons for initially not implementing under-promotion in Spartacus was not search overhead, but lack of codes in the move encoding. The latter was two bytes (from-square + to-square), and the number of promotions could be very large. (Each side can have 30 different promotion squares on a 10x10 board, and could promote to any of 6 piece types, so even making the encoding side-specific would require 180 codes.)

I finally solved that by not encoding (toSquare, promoPiece) pairs, but (stepVector, promoPiece) in stead. Promoting pawns have only 3 different possible step vectors, no matter how many promotion squares there are. So I now only need 18 codes per side for the promotion, and there are enough off-board squares available on my 0x88-like board to accomodate those codes as to-square encoding,and still have enough left for castlings and e.p. captures.

[Don]

I found a funny case of how not considering under-promotion can cost you points,in a game between Spartacus and Joker yesterday:

[d]1b6/8/8/8/8/8/3k2Kp/8 w

I couldn't believe my eyes when I saw Spartacus play Kf2? here! First I expected a horrific bug,but later I realize it counted on a1=Q being a stalemate, and simply playing Kg2 after any other move.Funny thing was that it got away with it, because Joker does not know any under-promotion either, and had no problem rejecting a1=Q because of the stalemate. So they went on,and the Kf2? move was repeated several times with the Bishop in various locations, before the 50-move rule finally ended the game. Any under-promotion would have been winning!

The lesson is that if you don't implement under-promotion, you cannot reliably draw KBPK!

I think you mean h1=Q, not a1=Q

There are many exceptions but in the grand scheme of things they are incredibly rare. Allowing knight underpromotions solves 99% of the already rare cases.

The important issue to me is scalability. This is a position that a program would never play correctly even given the lifetime of the universe to compute. So if your program does not handle rook and bishop promotions, the affect on it's strength might be tiny now, however if computers were 1000 ELO stronger this might actually start to become a serous oversight - one of the few things that your program misses.

The solution for this is not to throw out underpromotions but to reduce them significantly. For example you could forward prune them if the depth is less than (say) 10 ply, otherwise reduce them by several ply. Like any other reduction or pruning algorithm in modern programs it's all about the risk reward trade-off. How much ELO are you willing to give up to see something that is very rare? How much ELO will you gain to compensate?

I think Komodo's algorithm is to only consider knight promotions if they give check and I think all under-promotions are considered at the root. In this example Komodo would catch it because the knight promotion is a check even though it happens at the root. And yes, you can find positions if you look hard enough that will fool Komodo so I will probably at some point fix this to be more scaleable.

[Uri Blass]

It will improve decrease the strength of the program since these promotions will make the tree larger. You know with 99.999 percent certainty that a queen promotion is better than a bishop or rook promotion and this is more reliable than just about any other selective rule you can have in your program.

Don, you need to get some sleep!

What he did will by removing promotions will improve the strength of the program.

I am not convinced. I tried this a while back and found zero change. I think because of hashing where if d8=Q is no good, d8=R is a transposition once the rook is removed, ditto for B.

I am working on a draw score test, when that is finished, I'll run this again because it was trivial to do...

I think that removing rook and bishop under promotion has to be a small improvement because not always you can capture the promoted piece and even if you can capture it then not generating the rook underpromotion and the bishop under promotion save time in the move generator.

It is possible that the improvement is only 1 elo or 0.5 elo but common sense suggest that there is an improvement by not having rook and bishop promotions in the move generator(of course you need to accept rook and bishop underpromotion of the opponent but it is possible to do it even without having rook and bishop promotions in the move generator).

Most authors do not care only about playing strength so they have all underpromotions in the move generator.

[Don]

It will improve decrease the strength of the program since these promotions will make the tree larger. You know with 99.999 percent certainty that a queen promotion is better than a bishop or rook promotion and this is more reliable than just about any other selective rule you can have in your program.

Don, you need to get some sleep!

What he did will by removing promotions will improve the strength of the program.

I am not convinced. I tried this a while back and found zero change. I think because of hashing where if d8=Q is no good, d8=R is a transposition once the rook is removed, ditto for B.

I am working on a draw score test, when that is finished, I'll run this again because it was trivial to do...

I think that removing rook and bishop under promotion has to be a small improvement because not always you can capture the promoted piece and even if you can capture it then not generating the rook underpromotion and the bishop under promotion save time in the move generator.

It is possible that the improvement is only 1 elo or 0.5 elo but common sense suggest that there is an improvement by not having rook and bishop promotions in the move generator(of course you need to accept rook and bishop underpromotion of the opponent but it is possible to do it even without having rook and bishop promotions in the move generator).

Most authors do not care only about playing strength so they have all underpromotions in the move generator.

If you have under-promotions, it adds overhead. Not very much, but a little and on occasion the line is expanded thus making the tree larger. So it has to be an ELO gain to justify if you are only interested in playing strength. The ELO gain is almost surely less than 0.1 ELO and that is not enough to make up for the small slowdown. So as a program ELO improvement it's not justified.

However, there are other considerations too. "Improving" the program has a lot to do with things other than raw ELO. Playing style, usability, etc. Even not knowing that an endgame is a draw - doesn't affect the ELO noticeably, but affects peoples feelings towards the program. So I plan to put all under-promotion back in Komodo. It will be heavily reduced, but it will be there. It will probably make the program 1/2 ELO weaker - but I can live with that

[hgm]

You could make it an engine option: try underpromotions None / N / N+R / All

[Don]

You could make it an engine option: try underpromotions None / N / N+R / All

Yet another test?