In message , johnny_t
writes
David Richerby wrote:
johnny_t wrote:
Martin Brown wrote:
johnny_t writes
Like Rybka arguably the strongest program doesn't create bishop
promotions for instance, because the program would be overall
WEAKER if it did.
That isn't necessarily the case. It fails to find solutions to
certain types of constructed chess puzzle as a result of this
decision. And I can't see that generating the bishop promotion last
rather than not at all would be that much of a performance hit.
What isn't necessarily the case? The reason that the engine would
be weaker, is that this rare case would have to be tested for with
every branch that has a pawn promotion. The time spent doing that
is time spent NOT looking at more useful things. Meaning that the
play will be weaker.

It depends on how you do it. Certainly considering bishop promotions in
the early stage of the game down completely insane pawn capture
sidelines that I would hope most modern engines would prune out on
windowing grounds would cripple performance.

But in the final stages of an endgame although it will usually be Q, R
or N that is needed, but very occasionally a B is the only answer.

It is not necessarily the case that the engine will be weaker if it
considers bishop promotions. There are two competing factors in
ignoring bishop promotions:
1. in some very rare positions, the engine might fail to find the
best
move (possibly the only winning move) because it doesn't even
consider it;
2. the rest of the search should go ever so slightly quicker, which
gives it a chance of finding a better move in nearly all positions
involving pawn promotion.
Taken in isolation, 1 makes the engine weaker and 2 makes it
stronger. But, of course, they're not taken in isolation -- both
effects occur and the question is which is the more significant. You
and Rybka's author believe that 2 is more significant than 1, which
means that ignoring the possibility of bishop promotions increases the
effective strength of the engine.
I would tend to agree with you but, without data, this is just our
supposition. It seems likely to me that disregarding bishop
promotions increases the effective strength of the engine but it isn't
*necessarily* the case.

It is a much longer, wordier version that I had compressed into the
word "rare".

But for sake of completeness we can further examine two words, weaker
and rare. And even "I believe".

First, I actually do not have a dog in this fight, the whole Rybka
issue was solely an "ad computerem" device. They are the strongest
program, they don't use all the legal moves. Trying to get an existing
engine to create a list of legal moves, while on surface seems obvious
and easy cuz aren't they "always" creating a move list in every
position. And the answer is suprisingly, most don't. They check
legality by implication, and some even ignore otherwise legal moves.

Quite a lot of the older engines did have separate move generation
stages though and the OP would be well advised to find one of them.
Preferably a simpleminded and well commented one - speed won't be
important for a single ply move generator. I'm not sure why he wants to
do it though...

Next "rare." The Bishop case is very rare. Namely because the queen
also moves diagonally. It would be very rare that a queen would not
solve the case, and the bishop would. It has been seen in puzzles, but
not in the wild (though I am nowhere near an exhaustive expert on this).

I expect it has been seen in the wild, although off hand I can't find
any. The problem for the Q promotion is that it can also move like a
rook and a standard way to get stalemate is for the opponent to create a
capture check where the additional Q mobility removes all moves for his
king.

What is also interesting, is that in certain parts of the game there
is loads and loads of possible pawn promotions and each of them would
have to be checked for bishop promotions, if you checked for such
things and it would hardly ever, especially in real life matter, and so
such things are simply pruned, by implication, from the search tree.

Some of those early promotions are pretty spurious though. Genuine pawn
promotion is relatively unusual in serious games.

By weaker... Everytime you make a decision to prune a tree for
whatever reason may mask a deeper truth that would make the program
stronger.

I suppose it really does depend on how much time would be wasted on the
bishop promotion. My instinct is that it would normally be culled after
a linear search down a single PV unless it lead somewhere interesting.

This is a truism of selective search. But you are making the
assumption that the remaining search realm will be more fruitful in the
additional depth you are allowed to search in this time frame. This
can only be determined by test. And so far Rybka has in any test
passed. As it goes forward, there will be advances in evaluation,
selectivity and speed of search. This will lead to new balances that
will hopefully lead to a stronger engine. This is true for all
engines, and computer "play" programs as well.

It would be interesting to see how much of a performance hit this small
change would be in practice. I could put a bound on it by tweaking a toy
chess engine to not generate Bishop promotions and timing it.


But for brevity, I just packaged all the above into "rare" compared to
the time lost. QED

I think you over estimate the time lost here.

Regards,
--
Martin Brown

--
Posted via a free Usenet account from http://www.teranews.com

Martin Brown wrote:

I think you over estimate the time lost here.

I haven't made any estimate. The Rybka players estimate that it is a
5-10 ELO difference as I recall. And a testing hit.

Not that big of a deal in of itself, but when you are desperately
searching for a package of tweaks that is 50-100 points its a pretty big
one to leave on the table.

In message , johnny_t
writes
Martin Brown wrote:

I think you over estimate the time lost here.

I haven't made any estimate. The Rybka players estimate that it is a
5-10 ELO difference as I recall. And a testing hit.

I am surprised they can pull that out from the noise.

Not that big of a deal in of itself, but when you are desperately
searching for a package of tweaks that is 50-100 points its a pretty
big one to leave on the table.

I was curious about the statistics though so I probed CB Big06.cbh with
the following results for P promotions in that database

=B 22 of which 3 were not immediately captured and one was critical.
=N 349 of which a fair proportion involved a fork or critical check
=R 226 of which most required not getting a queen
=Q 13168 no comment

The only =B promotion that was critical was a U14 German game.

The rest were all demonstrations by senior players that they knew the
piece would be captured on the next move. It would not have mattered
what the promotion.

So arguably if you are only interested in maximum strength the =B is
completely irrelevant (and the =R is borderline - could be generated on
the fly if =Q proves to hit problems with a forced drawing line).

Regards,
--
Martin Brown

--
Posted via a free Usenet account from http://www.teranews.com

In article ,
Martin Brown wrote:
It depends on how you do it. Certainly considering bishop promotions in
the early stage of the game down completely insane pawn capture
sidelines that I would hope most modern engines would prune out on
windowing grounds would cripple performance.

"Cripple performance"? If the promotion is of the type
where a queen would be immediately captured, then any sub-promotion
leads after one further ply to a position that should already be
in the transposition table with a value that causes an instant
beta-cutoff. If, OTOH, the queen would survive with best play,
then a bishop sub-promotion leads instantly to a position which
is approximately a rook+ worse, and will get pruned very quickly
[unless, indeed, the sub-promotion is "interesting"]. Presumably
no-one would today claim that every random move whereby [eg] an
attacked rook is left to be captured cripples performance? It
may get very short shrift, but, at least in the full-width part
of any search, *all* moves should be generated [on demand], even
those that apparently drop a rook.

[johnny_t:]
Next "rare." The Bishop case is very rare. Namely because the queen
also moves diagonally. It would be very rare that a queen would not
solve the case, and the bishop would. It has been seen in puzzles, but
not in the wild (though I am nowhere near an exhaustive expert on this).
I expect it has been seen in the wild, although off hand I can't find
any.

Tim Krabbe' listed a few in "Chess Curiosities", of which
the first is Kuppfer -- von Wulf:

8/7P/8/3P4/1p6/1k1K4/p7/8 w - - 0 1

1 h8=B! wins; 1 h8=Q? a1=Q draws.

I assume that Rybka at least *understands* B promotions?
If not, then it is going to lose a *lot* of games to engines that
know about this deficiency and promote to a B regardless of the
chessic needs, just to watch Rybka crash and burn on the "illegal"
move.

--
Andy Walker
Nottingham

Andy Walker wrote:

I assume that Rybka at least *understands* B promotions?
If not, then it is going to lose a *lot* of games to engines that
know about this deficiency and promote to a B regardless of the
chessic needs, just to watch Rybka crash and burn on the "illegal"
move.


It is an interesting theory, but I suspect what would happen is that the
hash would just become useless (no hits). And it would shorten search
for a single turn as it refills the hash with the bishop. This could
happen anytime there was a surprising (pruned) move made.

But this also brings up another point, is that it is the nature of the
UCI that the GUI is responsible for checking for move legality. That
the engine is always assumes that the position and the move was legal.

Which means that for the original poster that Arena may be a source of
code for move legality.

In message , Andy Walker
writes
In article ,
Martin Brown wrote:
It depends on how you do it. Certainly considering bishop promotions in
the early stage of the game down completely insane pawn capture
sidelines that I would hope most modern engines would prune out on
windowing grounds would cripple performance.

"Cripple performance"? If the promotion is of the type
where a queen would be immediately captured, then any sub-promotion
leads after one further ply to a position that should already be
in the transposition table with a value that causes an instant
beta-cutoff. If, OTOH, the queen would survive with best play,
then a bishop sub-promotion leads instantly to a position which
is approximately a rook+ worse, and will get pruned very quickly

I agree. That is why I find it hard to believe the alleged 5-10 ELO
point improvement claimed by Rybka fans for not generating the =B
promotion. In most circumstances =B will not waste any significant time
at all.

Some of the daft permutations in a full width search do allow PxR where
the enemy Q cannot be captured immediately. But any sensible search
strategy will never really consider them unless there is a forcing line.

[unless, indeed, the sub-promotion is "interesting"]. Presumably
no-one would today claim that every random move whereby [eg] an
attacked rook is left to be captured cripples performance? It
may get very short shrift, but, at least in the full-width part
of any search, *all* moves should be generated [on demand], even
those that apparently drop a rook.

[johnny_t:]
Next "rare." The Bishop case is very rare. Namely because the queen
also moves diagonally. It would be very rare that a queen would not
solve the case, and the bishop would. It has been seen in puzzles, but
not in the wild (though I am nowhere near an exhaustive expert on this).
I expect it has been seen in the wild, although off hand I can't find
any.

Tim Krabbe' listed a few in "Chess Curiosities", of which
the first is Kuppfer -- von Wulf:

8/7P/8/3P4/1p6/1k1K4/p7/8 w - - 0 1

1 h8=B! wins; 1 h8=Q? a1=Q draws.

I assume that Rybka at least *understands* B promotions?
If not, then it is going to lose a *lot* of games to engines that
know about this deficiency and promote to a B regardless of the
chessic needs, just to watch Rybka crash and burn on the "illegal"
move.

Here is the other one that I found in CB6 big database.
Strethoff vs Huschenbeth, U14 GER-CH 2005

8/2p5/1p3k2/1P1pR2p/3P3P/5p2/3pr1r1/2R3BK b - - 0 38

He played dxc1=B and won. dxc1=N also wins but more slowly.
=R, =Q both draw since the pending stalemate allows W to do perpetual
check... And for the record Rh2+ is the fastest win so even in this
example the =B promotion is not absolutely essential.

There is another interesting quirk though. I put this position to Rybka
2.32 and found that after manually playing dxc1=B it cannot properly
see the correct continuation line to the fastest mate whereas Fritz and
Shredder have no trouble at all. Even Crafty 19.19 groks it in under
10s.

At ply 15 it still has the brutally materialistic PV
39. Rxe2 fxe2 40. Kxg2 e1=Q Bf2 Qe4+ -16.8
It took 30 mins and a ply 17 search to resolve this position. But after
playing 39. Rxe2 it then sees the correct strongest continuation line
for black in mere seconds which goes something like
39. .... Rxe2! 40. Be3 Re1+ 41. Kh2 Bxe3 42. Kg3 f2 43. Kh3 Bf4 44.
Kg2 f1=Q#

So it seems Rybka does have an Achilles heal where promotions are
concerned. It looks like a blindness to mating opportunities (or over
zealous windowing). fxe2 is certainly good enough to win!

I miss stated the frequency of these promotions occurring before. I was
only considering Px*=B etc. The full numbers for any move P***=* are
=B 98, =R 528, =N 882, =Q 46k

So 97% of all promotions are to Q, 2% N, 1% R & 0.2% B
(and most of those =B are followed by immediate trivial capture)

Regards,
--
Martin Brown

--
Posted via a free Usenet account from http://www.teranews.com

Rybka allows Bishop promotions, but will never promote to Bishop herself.
White: King h8, pawns g7 and h7
Black King e6, Queen g3, Rook b8
White is in check and can promote to 4 different pieces.
Rook and Knight allow Qe5 checkmate
and promoting to Queen is answered by Kf6 and checkmate next move.
The only saving move is g8=B, with stalemate or exchanging everything.
Rybka will never "find" this move by White, but if you play g8=B yourself,
she will allow it and see the draw.

You extremely seldomly need the move (White's) B f2 takes g1.
Maybe some program will never consider this move, just to gain speed.
A consumer product should play by the rules. So I expect Rybka to play g8=B
in the next version.





"johnny_t" schreef in bericht
...
Andy Walker wrote:

I assume that Rybka at least *understands* B promotions?
If not, then it is going to lose a *lot* of games to engines that
know about this deficiency and promote to a B regardless of the
chessic needs, just to watch Rybka crash and burn on the "illegal"
move.


It is an interesting theory, but I suspect what would happen is that the
hash would just become useless (no hits). And it would shorten search for
a single turn as it refills the hash with the bishop. This could happen
anytime there was a surprising (pruned) move made.

But this also brings up another point, is that it is the nature of the UCI
that the GUI is responsible for checking for move legality. That the
engine is always assumes that the position and the move was legal.

Which means that for the original poster that Arena may be a source of
code for move legality.

In message , Andy Walker
writes
In article ,
Martin Brown wrote:
It depends on how you do it. Certainly considering bishop promotions in
the early stage of the game down completely insane pawn capture
sidelines that I would hope most modern engines would prune out on
windowing grounds would cripple performance.

"Cripple performance"? If the promotion is of the type
where a queen would be immediately captured, then any sub-promotion
leads after one further ply to a position that should already be
in the transposition table with a value that causes an instant
beta-cutoff. If, OTOH, the queen would survive with best play,
then a bishop sub-promotion leads instantly to a position which
is approximately a rook+ worse, and will get pruned very quickly

I agree. That is why I find it hard to believe the alleged 5-10 ELO
point improvement claimed by
Rybka fans for not generating the =B promotion. In most circumstances
=B will not waste any
significant time at all.

Some of the daft permutations in a full width search do allow PxR
where the enemy Q cannot be
captured immediately. But any sensible search strategy will never
really consider them unless there
is a forcing line.

[unless, indeed, the sub-promotion is "interesting"]. Presumably
no-one would today claim that every random move whereby [eg] an
attacked rook is left to be captured cripples performance? It
may get very short shrift, but, at least in the full-width part
of any search, *all* moves should be generated [on demand], even
those that apparently drop a rook.

[johnny_t:]
Next "rare." The Bishop case is very rare. Namely because the queen
also moves diagonally. It would be very rare that a queen would not
solve the case, and the bishop would. It has been seen in puzzles, but
not in the wild (though I am nowhere near an exhaustive expert on this).
I expect it has been seen in the wild, although off hand I can't find
any.

Tim Krabbe' listed a few in "Chess Curiosities", of which
the first is Kuppfer -- von Wulf:

8/7P/8/3P4/1p6/1k1K4/p7/8 w - - 0 1

1 h8=B! wins; 1 h8=Q? a1=Q draws.

I assume that Rybka at least *understands* B promotions?
If not, then it is going to lose a *lot* of games to engines that
know about this deficiency and promote to a B regardless of the
chessic needs, just to watch Rybka crash and burn on the "illegal"
move.

Here is the other one that I found in CB6 big database.
Strethoff vs Huschenbeth, U14 GER-CH 2005

8/2p5/1p3k2/1P1pR2p/3P3P/5p2/3pr1r1/2R3BK b - - 0 38

He played dxc1=B and won. dxc1=N also wins but more slowly.
=R, =Q both draw since the pending stalemate allows W to do perpetual
check... And for the
record Rh2+ is the fastest win so even in this example the =B
promotion is not absolutely essential.

There is another interesting quirk though. I put this position to
Rybka 2.32 and found that after
manually playing dxc1=B it cannot properly see the correct
continuation line to the fastest mate
whereas Fritz and Shredder have no trouble at all. Even Crafty 19.19
groks it in under 10s.

At ply 15 it still has the brutally materialistic PV
39. Rxe2 fxe2 40. Kxg2 e1=Q Bf2 Qe4+ -16.8
It took 30 mins and a ply 17 search to resolve this position. But
after playing 39. Rxe2 it then sees
the correct strongest continuation line for black in mere seconds
which goes something like
39. .... Rxe2! 40. Be3 Re1+ 41. Kh2 Bxe3 42. Kg3 f2 43. Kh3 Bf4 44.
Kg2 f1=Q#

So it seems Rybka does have an Achilles heal where promotions are
concerned. It looks like a
blindness to mating opportunities (or over zealous windowing). fxe2 is
certainly good enough to win!

I miss stated the frequency of these promotions occurring before. I
was only considering Px*=B etc.
The full numbers for any move P***=* are
=B 98, =R 528, =N 882, =Q 46k

So 97% of all promotions are to Q, 2% N, 1% R & 0.2% B
(and most of those =B are followed by immediate trivial capture)

Regards,
--
Martin Brown

Apologies if there are two copies of this posted (one via teranews and
one via Google - it seems both are equally unreliable - although the
advantage of teranews dropping sutff on the floor is that I get to
keep a local copy).

Wijnand Engelkes wrote:
Rybka allows Bishop promotions, but will never promote to Bishop herself.
White: King h8, pawns g7 and h7
Black King e6, Queen g3, Rook b8
White is in check and can promote to 4 different pieces.
Rook and Knight allow Qe5 checkmate
and promoting to Queen is answered by Kf6 and checkmate next move.
The only saving move is g8=B, with stalemate or exchanging everything.
Rybka will never "find" this move by White, but if you play g8=B yourself,
she will allow it and see the draw.

You extremely seldomly need the move (White's) B f2 takes g1.
Maybe some program will never consider this move, just to gain speed.
A consumer product should play by the rules. So I expect Rybka to play g8=B
in the next version.

Several things.. A properly installed Rybka WILL solve the above puzzle.
(Using 6 piece table bases).

Secondly this is clearly a puzzle, and Rybka is by no means the best
puzzle solver.

And as I read, it is not likely to make the next version. Maybe
consumers shouldn't play games that result in puzzle endings. But more
importantly you are making without realizing it, that selective search
is somehow "anti-consumer" and therefor bad. I think that is rather
bold. Just because you can find a case you construct where selective
search fails, doesn't make it, nor correct. There are many many cases
that you can probably construct if you knew the selective search pruning
rules where you can reliably beat the program, especially if you
construct single solution puzzles. None of this makes selective search
bad, or the program isn't the strongest. Clearly selective search makes
the best move most of the time, especially in non single move (real
world) cases.

Martin Brown wrote:

I agree. That is why I find it hard to believe the alleged 5-10 ELO
point improvement claimed by
Rybka fans for not generating the =B promotion. In most circumstances
=B will not waste any
significant time at all.

Not a fan, nor fanboy per se. Just using it as an example, because it
is by test, the best program by far...

And the 5-10 ELO quote doesn't come from the fan, but regurgitated from
the actual programmer and tester. But fundamentally all selective
search is a balance and you can always make a case that shows where it
is wrong. Even with selective pruning if you can simply never test for
something especially in parts of the game where the tree results in
bunches of pawn promotions, it is not that big of a stretch that the
time is not insignificant.

But importantly, I have never used the term "cripple performance", and
it is a bit of bad form to attack my premises based on the term you
used. I never ever thought it would cripple performance. What I
believe is that the performance hit would be significant compared to the
gain. Loss-gain. Risk-reward. The key balance of selective search.
Never has been always right. It is always more right than wrong. Or
don't waste time when the risks is small, when the reward is small.