Not logged inRybka Chess Community Forum
Up Topic Rybka Support & Discussion / Rybka Discussion / Bishop underpromotion
1 2 Previous Next  
- - By Nelson Hernandez (Gold) [us] Date 2007-05-20 22:57
This topic was beat to death on another thread, and there's little left to say, but I did want to follow up on some comments Larry made about games where the lack of bishop underpromotion making a difference might be "one in a million".

Turns out he was probably generous.  I pored through my database and checked every game with a bishop underpromotion that actually happened going back through 2005.  That's quite a large number of games.  I could not find one instance among engine games where promoting to queen or making an alternative move that did not result in a promotion would have resulted in a different ending outcome.  I did find several games where promotion to bishop shortened the number of moves to mate.  The biggest improvement I ran across was five moves.  I also found instances where an engine was clueless and would have been clearly better off promoting to queen.  (These were all weak engines that were mate-challenged.)

Of course that is not to say the situations never happen.  It's just that they are extremely rare.  If anybody can find such a game among their engine vs. engine games I'd love to see it.

All this said, I've changed my mind from the earlier thread.  In terms of maximizing ELO, it is clear that keeping bishop promotion out of the code is the right thing to do.  But this is one of those very rare instances where I'd rather see the engine lose a fraction of one ELO point in exchange for handling this sort of chess problem correctly.  Trade brute force for a bit of rococo elegance, that's what I am saying.
Parent - - By Kapaun (****) [de] Date 2007-05-20 23:22
Why not making it optional? A button in the settings... One button more shouldn't be such a hassle.
Parent - By grolich (***) Date 2007-05-20 23:45
I can't really speak for Vas, but he said on another thread that what's stopping him is mostly related to the fact that even supporting this small feature will make Rybka's code even more monstrously complex than it already is... has to do with the fact that with adding the bishop promotion issue, He can no longer encode a move as an EASY straightforward 16 bit value, and will have to do some flag encoding tricks... Considering the size of codebase such programs can reach (This time I'm speaking as a programmer), I think that for this reason, we, that is, the Rybka user community, should actually advocate delaying this feature (EVEN as a side button...) for the foreseeable future. For Rybka's development sake.
After it has matured a bit, and the code will not need to undergo that many changes, if enough users will still want it, sure, why not?
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-05-21 10:05
Let me give you an analogy. Do you have at home a dart gun specially made for shooting African Elephants?

You could make all sorts of arguments:

1) You can definitely construct scenarios where the gun is useful, even necessary. What if the traveling circus passed by your house and the elephant truck derails?
2) All these scenarios are probably quite rare. We can discuss whether it's 1/1,000,000 or 1/1,000,000,000.
3) On the other hand, this dart gun might cost only $200 or so and I'm sure you can afford it and have some space in your basement for it.

I think, in the final analysis, you'd conclude that you just don't want to make your life more complicated by getting this gun.

Vas
Parent - By Nelson Hernandez (Gold) [us] Date 2007-05-21 12:22
How can I answer that?  What a funny analogy!
Parent - - By fhub (**) Date 2007-05-21 14:20

>Let me give you an analogy. Do you have at home a dart gun specially made for shooting African Elephants?


Sorry Vas, but that´s really nonsense!

Bishop underpromotion IS a valid chess move, and so it SHOULD be considered - like all other valid moves.
With the same argument you could omit e.p. captures, castlings, 50 move rule ...

And one more point:
What´s really SO complicated in bishop underpromotion?
If a promotion is possible, Rybkas move generator provides 3 possible moves - could you please tell me, where´s the problem when it would provide all 4 possible moves instead?
Parent - By Uri Blass (*****) [il] Date 2007-05-21 14:32
This is not nonsense.
ep captures is not something that is relevant only in one of million games.

The problem is not in the generator but in memorizing the move so you can take it back later.
Vas used 2 bits for memorizing queen rook knight or no promotion when with bishop promotion 2 bits are not enough.
 
Uri
Parent - By Vasik Rajlich (Silver) [hu] Date 2007-05-23 06:48
Note that Rybka does accept bishop underpromotions. She just won't suggest them as best moves.

Vas
Parent - - By h1a8 (***) [us] Date 2007-05-24 01:33
You must understand that rybka will lose chess strength if Vas adds that option.
1. The time it takes calculating variations for a non-needed bishop promotion will cost rybka millions of positions that she could have been analyzing for the continuation after the needed queen (or knight) promotion.
2. More bugs can be introduced (with the option on or off). This is probably why Vas is trying to get rid of all the clutter (less clutter leads to less bugs and easier bug cleaning leads to more time spent in improving search instead of bug cleaning).
3. The time it takes putting this in could be used to do more important stuff (like get rid of bugs[improve code], work on mp efficiency, improve search, and work on pocket pc version).

So ask yourself this: "Would I rather see Rybka play somewhat less stronger with more bugs but analyzes bishop promotions?"
If yes, then you have a point (a minority one).

note: 1. is not quite a valid reason since this can be offered as a option that can be turned off. But still it would lead to problems 2. and 3.
And forget 1/1000000 or even elephant chances; I guarantee you that you will never ever see a position in rybka's or your games where a bishop promotion is the best move.
That is to say, why would Rybka even play to a position where a bishop promotion is the only move that wins.

P.S. Just because some of my reasons are faulty doesn't mean the whole argument is not valid. All it takes is for one of my points to hold up (2. and 3. are good enough). So argue against them all (and not a select few).
Parent - - By Kapaun (****) [de] Date 2007-05-24 09:32
Now, come on, if it's that difficult to program a chess engine without bugs, why programming a chess engine at all? The position "Yes, we are making a computer version of this strategy game, but there is a difficult move which could lead to extra bugs, and it's rare anyway, so we just skip it" is certainly not a valid one. As a project manager of such a game I would not have accepted it.

I understand Vas' position when he is saying that including the move would result in Rybka being a tiny little bit weaker, but I also understand people who want a "complete" chess engine, even if they will never see a situation where they need it. And anyway there are different purposes to use a chess engine for - if you are creating or solving chess problems, for instance, then you will see a few of these situations for sure.

And I certainly don't understand why a simple option in the settings would hurt anyone...
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-05-25 07:15
Of course, there are two valid viewpoints here (as with most things). It's not quite correct to call this a bug. Rybka just doesn't like bishop underpromotions - she will have a (very strong) tendency to undervalue them.

Vas
Parent - - By Kapaun (****) [de] Date 2007-05-25 07:32
How far would this dislike go? Would she be able to find a bishop underpromotion if it's the (best) winning move? And what about if it's the only one?
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-05-25 07:54
Very far - she will never 'choose' a bishop underpromotion :)

Vas
Parent - - By Felix Kling (Gold) [de] Date 2007-05-25 08:07
I think the handling of underpromotions can be improved. The underpromotion to a rook or bishop only happens, if the underpromotion to a queen leads to a stalemate. So Rybka should first look at the underpromotion to the queen and if this line is a draw because of a stalemate, she should look at rook and bishop. That would save a lot of useless calculation time.
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-05-27 07:23
That's an interesting theory, I'll think about it a little bit.

At the very least, it's not always trivial to recognize the stalemate. For example:

6k1/1R6/2p3p1/1pPpp1Pp/7P/7K/6p1/8 b - - 0 7


Vas
Parent - By Felix Kling (Gold) [de] Date 2007-05-27 09:28 Edited 2007-05-27 09:30
OK, I like Uri's suggestion.
It would be more precise to look for an stalemate somewhere in the tree and not only in the best line.
Parent - - By Felix Kling (Gold) [de] Date 2007-06-10 14:09
Little change: My idea is only true if the stronger side needs a underpromotion, but I now have an example where the weaker side needs it, so you should look if the queen promotion leads to a stalemate/draw or a mate/bad position and then look for the underpromotion:

2K5/2Pnk1P1/PP6/8/2b5/2n5/8/8 w - - 0 0


Solution:

1. a7 Ba6+ 2. b7 Ne4 3. g8=N+ Ke8 4. Nf6+ Nexf6 5. a8=B

PS: Btw.: This study is by J. Rusinek, I found it today on www.chesvibes.com
Parent - By Vasik Rajlich (Silver) [hu] Date 2007-06-11 13:34
Felix,

this is getting too complex :)

During 99.99% of searches, you don't know how the queen promotion did - you only know that it failed low (ie. didn't work).

Basically, a bishop or rook underpromotion can work regardless of whether you are looking for an advantage or to minimize a disadvantage.

Vas
Parent - - By Uri Blass (*****) [il] Date 2007-05-27 08:16
No

underpromotion to a rook can be better than promotion to a queen inspite of the fact that there is no stalemate in the correct line after promotion to a queen

5r2/4P3/8/8/6rp/7k/3PPK2/4R3 w - - 0 1


When rybka analyzes exf8=Q it will not see a draw score because the main line after this move is Rf4+ Kg1 Rxf8 but it is clear that exf8=R is better.

Note that I do not know if exf8=Q is a draw or win for white but it is clear that there are cases of drawn position after promotion to a queen when rybka will see advantage for the side that promoted.

You can suggest to consider rook underpromotion or bishop underpromotion only in case that rybka saw some line that leads to stalemate in the tree after queen promotion.

Uri
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-05-29 06:40
Yes, I see. The 'main line' doesn't need to end in stalemate or even a repetition.

I wonder about two things:

1) Is it sound to only do rook and bishop underpromotions when beta > 0?

2) Is it sound to only do rook and bishop underpromotions when some branch of the full (alpha-beta) search of the queen promotion ends in stalemate within X moves? If yes, what is X?

Maybe #1 is the way to go, since it's not overly complex.

Vas
Parent - - By Uri Blass (*****) [il] Date 2007-06-04 04:00 Edited 2007-06-04 04:13
If queen promotion leads to small advantage for the promoter then it is clear that it is not sound not to consider rook or bishop promotion(I showed example)

If queen promotion leads to no advantage for the promoter then I think that it is also not sound not to consider rook or bishop underpromotion because it is possible that the opponent cannot prevent stalemate after under promotion and can prevent stalemate after promotion to queen(stalemate can be achieved by 2 ways and here I think about stalemate when the promoter cannot move).

I am even not sure if not having stalemate after queen promotion is enough not to consider underpromotion because it may be that only bishop promotion save the promoter by stalemate and queen promotion is losing because the side that promotes to queen has no stalemate.

Note that this is only theoretical thing and I will try to find if there is a study when underpromotion to rook is the only way to draw(same for underprootion to bishop).

I do not see way to prove that it is impossible
Uri

Parent - - By Debaser (***) Date 2007-06-04 08:54
Underpromotion to a rook (d8R) is the only way to draw here, acording to rybka And Lazard, 1935

8/3P4/3b4/8/8/1p2k2p/1Pp4P/2K5 w - - 0 7


And a8B is the only way to draw according to Troitzky

1n4b1/PP6/6p1/4p1p1/p5P1/3p2PK/3P4/7k w - - 0 7
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-06-05 09:55
Very nice, that settles it. Sorry, Felix :) Actually, it was an interesting idea.

Vas
Parent - By Vasik Rajlich (Silver) [hu] Date 2007-06-05 09:57
Actually, on second thought, since these are really obscure cases, a big reduction for underpromotions to rooks or bishops when beta > 0 may still be a nice (although tiny) gain.

Vas
Parent - - By Felix Kling (Gold) [de] Date 2007-06-11 17:52 Edited 2007-06-11 17:56
I discovered those posts today, yesterday I realised that it's a bit trickier :)
What we can say as a conclusion is that an underpromotion to rook/bishop needs a stalemate. If the board is full of pieces which can move there won't be a underpromotion.
The problem with the latest examples is that the stalemate can happen some moves after the underpromotion, but as a human I can see quite quickly when the unerpromotion could be a move-
I will think about it, there has to be a way to use this fact better...

a big reduction is good, a formula that would allow to ignore them would be better :)
Parent - - By Felix Kling (Gold) [de] Date 2007-06-11 18:12
New idea:

We look if after the promotion (to a queen) both sides have more than two pieces which can make moves.
If yes we don't look at the underpromotions to rook/bishop.
If no we look at it.

It may be possible to create a position where this rule doesn't work, I'm thinking about it, if anyone can create such a position please post it.
Parent - - By Felix Kling (Gold) [de] Date 2007-06-11 21:35
OK, I created it :)

5q2/4P2r/8/6rp/7k/4P3/4P1PP/4RKR1 w - - 0 1


So additional to the rule with the two pieces, if the main line leads to a stalemate look for underpromotions to bishop/rook .

I wonder if it's possible to create a position where both rules combined lead to a wrong decision.

Anyway, I guess it's already good, maybe this is true for 99,99% of those underpromotions (but maybe I'm making wrong conclusions again :) )
Parent - By Vasik Rajlich (Silver) [hu] Date 2007-06-13 10:27
In practice, I think the following two restrictions make sense:

1) Only trying underpromotions to rooks or bishops when we are looking for an advantage (ie. beta > 0) seems like a good restriction.
2) Only trying underpromotions to rooks or bishops when there are X pieces or less on the board. X can be 5 or so, it's easy to collect data about it.

Checking for the queen promotion leading to stalemate is more complex. Complex is only good when it helps a lot, which is unlikely to be the case here.

Anyway - all of this will be revisited later on.

Vas
Parent - By grolich (***) Date 2007-05-26 18:17
so is the elephant scenario - completely feasible... :)

the chances of a bishop underpromotion being the best move in a real game are negligible (Larry's guess is 1 in a million chance of that move being the best in a position, while my guess is more pessimistic than that, about 1 in 5 million at least).

Unless you're not talking about actual play but rather about problem / endgame compositions.
Of course, for the sake of these, it is not only a useful feature, it is an absolute must.

Now for the serious part - what's so complicated about bishop underpromotions?
After all, if it were very simple to implement, this whole argument would be futile. Vas would just do it...
so what part of bishop underpromotions is complicated enough to warrant the dart gun analogy?

Well, Obviously, Vas does not like to repeat himself (a great quality, and one which I do not yet possess...), but he has mentioned it in another post:

it makes the move encoding a lot more complicated and therefore Rybka's code a lot more difficult to handle, thus seriously slowing down and hampering development.

Why? right now (as I understand it from Vas's previous post), each move is easily encoded as a 16 bit value:
6 bits for origin square, 6 for destination square, 1 for en passant, 1 for castling, and 2 for promotion. The 2 promotion bits can only represent 4 options... and since the move encoding is for ANY move, not just promotions, one of the options is "no promotion", leaving only three options for promotion. Knight promotions are the best in quite a lot of cases actually... So for the time being, bishops were taken out.

Of course, there are solutions to this, but they entail a certain cost to the complexity of the code.
Even adding that as an option for composition solvers will still entail that cost.

Hope it DOES get added in the 3.x series sometimes, when more important issues have been dealt with.
Parent - - By Nelson Hernandez (Gold) [us] Date 2007-05-21 15:29
I have to reply, though...

1.  No, I don't have a dart gun for African elephants, but I do have one for spearing fish.
2.  Getting this $200 anti-elephant dart gun would be no less implausible and incomparably cheaper than spending thousands of dollars on computer hardware and devoting thousands of hours of unpaid labor to playing chess against other people who have spent similar amounts of money and time.
3.  As with Rybka 2.4, where can I get this dart gun?

On a serious note, you should include bishop underpromotion strictly because it's extremely cool to see such a super-unusual move played with purpose and effect.  I know, I know, you and Rybka are already so cool that if you were any cooler we'd all suffer from acute hypothermia.
Parent - By Cubeman (**) [nz] Date 2007-05-22 00:11
Just my 10 cents worth,Vas I can live without Bishop under promotion.But there are some positions in actual games between humans that have required Bishop under promotion to win the game.But these are extremly rare.Look on Tim Krabbes chess curiosities website and you will find some.
Parent - - By vroger007 (**) [be] Date 2007-05-22 00:58
I also definitely vote for implementing bishop underpromotion, whether now (2.3.x) or later (3.x)
Roger
Parent - - By Roland Rösler (****) [de] Date 2007-05-22 01:31
Buy Fritz!
Parent - By Kapaun (****) [de] Date 2007-05-22 05:24
Fritz? I would consider if it were UCI.
By the way, I would consider other CB engines, too, if they were UCI...
Parent - By vroger007 (**) [be] Date 2007-05-22 17:56
i have 4 or 5 fritzes, 2 or 3 shredders, 2 hiarcs's, junior9, chessmaster...
so far I am most pleased with rybka for its much more correct and trustable analysis... but still I feel I paid for a version including b.underprom., even if it were only for 100% complete egtb access or 100% complete analysis output... which is what I personally want, and want to pay for... allow me?
Parent - By Kapaun (****) [de] Date 2007-05-22 05:27
I guess I will have to second that. Even if it would mean a little ELO loss. I mean there are anyway always some bugs which could be blamed for it... ;->
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-05-23 06:51
A dart gun for spearing fish is like rook underpromotions, so it seems that we agree about everything :)

In all seriousness, I will revisit this later. There is a good argument for having an engine which, when given infinite time, will solve everything. What I don't like to do is just "add toppings" left and right.

Vas
Parent - - By davidwhite (***) Date 2007-05-24 00:00
Vas,
          I strongly urge you to red-flag this deficiency and assign it a prominent position in your Things To Do...LAST list!
Regards,
David
Parent - - By Roland Rösler (****) [de] Date 2007-05-24 02:10
Let us call this the VLTDL (very last to do list).
Parent - - By davidwhite (***) Date 2007-05-24 04:01
Roland,
               LOL!!!
               You're right...that's where Vas should file this red herring...the VLTDL.
Parent - By Vasik Rajlich (Silver) [hu] Date 2007-05-25 07:16
Simply 'a bit lower on the to-do list' is in practice good enough :)

Vas
Parent - - By vroger007 (**) [be] Date 2007-05-26 16:44
a quote from another 2.3.2 thread from you, Vas:
"If you don't do bishop underpromotions, then moves fit easily into 16 bits. 6 bits from origin square, 6 bits for target square, 1 bit for castling flag, 1 bit for en passant, 2 bits for no underpromotion, underpromotion to queen, rook or knight. With bishop underpromotions, you have to start conglomerating the flags. No big problem, but for what benefit?"

->  *under* promotion to queen??? :-)
Now in all seriousness, I still definitely want the engine to be 100% complete regarding legal moves, because as you already know I'm not in the first place interested in playing games or ELO strength, but in as-correct-as-possible analysis of games (and later also in "engines that are good teachers")!

Now, a mathematical-boolean-and-chess-logical conclusion, hopefully the trigger that will make you decide to implement bishop underpromotion once and for all :-)
I can see the reasons for using two bits about the promotion cases, but given the fact that any pawn which reaches the 8th (or 1st) rank  MUST  promote (it can never stay a pawn), two bits is precisely enough to cover everything: (I leave the order up to you):
00 -> promote to knight
01 -> bishop
10 -> rook
11 -> queen
!!!!!!!!!!!!!!!!!!!!!!!
I hope this opens everyones sleepy eyes ;-)
Best regards, hope to meet you in Amsterdam!
Roger
Parent - - By grolich (***) Date 2007-05-26 18:13
You missed the fact that NO underpromotion is one of the values.
You MUST have it, despite the fact that a pawn that reaches that rank can not remain a pawn, because the move encoding is done for EVERY move, not just for promotion moves.

Not using "no underpromotion" as one of the options is a bit trickier than it sounds, because it has a serious cost attached to it.
In order to do that, you have to check for a couple conditions each time you see a move:

if (pawn moved AND rank = 8/1) it is a promotion - read the promotion bits values
else it isn't - ignore them.

Rather than just obtaining all the information you need through a simple bit mask.
this should have quite a serious cost I believe, since those masking operations are done many times on each move.
Parent - By noctiferus (***) [it] Date 2007-05-26 18:18
You were faster than me: with this encoding, one has to check the pawn position.
Parent - - By vroger007 (**) [be] Date 2007-05-26 18:50 Edited 2007-05-26 19:05
I'm not convinced :-)  When will you *set* the promotion bits?  When you reach the back rank!
When do you know you reach the backrank? ....  right! ;-)

Edited: you can use an equally simple bitmask on the 6 destinationfield bits to check for backrank.
Of course I don't know rybka's internals but I think it's just very few extra bit-ops with little cost.
If one uses '00' as 'no promotion' it looks to me like the 2 promotion bits are not only used for
promotion, but also for determining pawn position (not yet on backrank) and that info is available
in the other 6 bits.
Parent - - By Vasik Rajlich (Silver) [hu] Date 2007-05-27 07:28
Roger,

I certainly didn't mean to claim that handling bishop underpromotions is some tremendous technical achievement :)

It's just that, in general, simpler is better. Things are messy enough as they are.

I don't see this as an issue regarding having a full analysis tool. You'll never analyze positions like this. There is however something to be said for having an engine which will find every search-based solution, given enough time. This just might save all the bishop-promotion lovers out there :)

Vas
Parent - - By grolich (***) Date 2007-05-27 09:33
"You'll never analyze positions like this"

Although I definitely agree on the overall rank in the "todo list" of the bishop underpromotion issue (very low right now),
On this one, I have to disagree... Because many people do use Rybka for testing compositions (both their own and others).

Despite the fact that composers who use normal engines for this have probably never heard of specialized tools such as "Freezer", I've known quite a few who do use engines for this purpose.

So, for the sake of a happy Rybka user base, I hope a fix for the bishop underpromotion issue will be fixed somewhere in the 3.x series.
Parent - By Uri Blass (*****) [il] Date 2007-05-27 12:08
I think that for composers it may be more important to add null move verification in rybka so rybka will always be able to solve mate problems.

Uri
Parent - By Vasik Rajlich (Silver) [hu] Date 2007-05-29 06:42
Yes, true.

Another issue is not showing the bishop underpromotion in multi-PV mode in cases where all promotions wins. This could be a bit of a head-scratcher.

Vas
Parent - - By Dr.X (Gold) Date 2007-05-24 01:48
Well! Let's look at that analogy and place it into another context.

The Pygmies believed that whatever animal they saw from a distance that was in fact the actual size of that animal. The closer they came to the animal the animal  was thought then to grow in stature. Their first experience of being in an automobile horrified them, since the animal grew so fast that it was perceived as bearing down upon them.

So, perhaps for, Nelson, who is looking at the issue from a distance-had no idea how huge of an issue it truly was until Vas- brought Nelson up close to the issues at hand.

Sidserious
Up Topic Rybka Support & Discussion / Rybka Discussion / Bishop underpromotion
1 2 Previous Next  

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill