Comparison data of Crafty vs Rybka that I promised 2 days ag

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Dann Corbit
Posts: 10128
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Movei added to Crafty vs Rybka comaprison data

Post by Dann Corbit » Sat Jun 02, 2007 7:18 am

bob wrote:yes. In fact, crafty has commands "flip" and "flop" to do that to the current position. "evtest" takes a FEN suite and does the sanity test using those commands.

I ran all 4. all four reported a mate in 6.

the scores were +2.18 and -2.18, + when it was black to move, - when it was white to move.

So I am still not sure what this is all about since all 4 report a forced mate (the times vary because of the move ordering issue I mentioned). And the eval is correct for each position...

so where does his table of numbers come from and what do the numbers represent???
The table of numbers comes from time to mate in seconds using the chess engine to analyze the position with Arena as the API.

I guess you will get a similar effect with epdpfga

bob
Posts: 20573
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Movei added to Crafty vs Rybka comaprison data

Post by bob » Sun Jun 03, 2007 8:38 pm

Dann Corbit wrote:
bob wrote:yes. In fact, crafty has commands "flip" and "flop" to do that to the current position. "evtest" takes a FEN suite and does the sanity test using those commands.

I ran all 4. all four reported a mate in 6.

the scores were +2.18 and -2.18, + when it was black to move, - when it was white to move.

So I am still not sure what this is all about since all 4 report a forced mate (the times vary because of the move ordering issue I mentioned). And the eval is correct for each position...

so where does his table of numbers come from and what do the numbers represent???
The table of numbers comes from time to mate in seconds using the chess engine to analyze the position with Arena as the API.

I guess you will get a similar effect with epdpfga
Anything that changes the move ordering will change the size of the tree for a specific problem. For Crafty, using FirstOne() for white pieces and LastOne() for black pieces works just fine when you just flip the board so that the first rank and 8th rank are interchanged. But when you mirror the board from A-H, then there is no equivalent to FirstOne()/LastOne() that will enumerate the moves in the same order, which means the tree is going to change.

In this regard, "who cares?"

vb4
Posts: 154
Joined: Sat Mar 11, 2006 4:45 am
Location: NY

Re: Movei added to Crafty vs Rybka comaprison data

Post by vb4 » Sun Jun 03, 2007 11:28 pm

Hi Bob,

What I was curious about was the significant difference in the number of seconds it took depending on which reflection you were working on. Some of the factors were very much different certainly when I compared it to Rybka ie. For reflections Rybka's times across the 4 reflections for the entire set were almost all the same. Why does it seem that Rybka across the reflections is so consistant?

Also looking at the Slider positions one would also think that the solutions would be a bit closer in terms of solution time then what I see. Now the only stipulation I make with these "Slider" positions is that the game would have to be a proven mate in N. Anything other then that then the Sliders can not be used this way.

Anyway I thought perhaps that you may be interested in this comparison since I would have to believe that reaching a mate solution in less time would only be a benefit.

Les

Edsel Apostol
Posts: 762
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Movei added to Crafty vs Rybka comaprison data

Post by Edsel Apostol » Mon Jun 04, 2007 7:10 am

Hi Les,

Maybe Rybka is using piece lists combined with bitboard. As what Bob has said, it is true that when you flip a position, the move ordering will also change, resulting to varying time to find the solution, that is if it is a bitboard only engine.

There is also a possibility that the eval value will change even if you have no bugs in your program. This results from the SEE routine, if it uses lastOne() only for both sides, applicable only for bitboards. (I'm using SEE in my eval ). Some positions have the same rooks for example to capture on a square, but when you flipped it the other rook will be tried first in the capture sequence that might result to a different value. It is also possible that in this kind of positions the SEE is inaccurate.

I even wrote a bitboard SEE that will overcome this issue but I'm wondering if the added accuracy can compensate for the little speed loss. This kind of positions are somewhat rare, maybe one in a hundred thousand positions in my guess. I have not tested that SEE much though and on my testing, there is no significant change that I noticed.

Edsel

bob
Posts: 20573
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Movei added to Crafty vs Rybka comaprison data

Post by bob » Mon Jun 04, 2007 7:02 pm

vb4 wrote:Hi Bob,

What I was curious about was the significant difference in the number of seconds it took depending on which reflection you were working on. Some of the factors were very much different certainly when I compared it to Rybka ie. For reflections Rybka's times across the 4 reflections for the entire set were almost all the same. Why does it seem that Rybka across the reflections is so consistant?

Also looking at the Slider positions one would also think that the solutions would be a bit closer in terms of solution time then what I see. Now the only stipulation I make with these "Slider" positions is that the game would have to be a proven mate in N. Anything other then that then the Sliders can not be used this way.

Anyway I thought perhaps that you may be interested in this comparison since I would have to believe that reaching a mate solution in less time would only be a benefit.

Les
Disturb the move ordering and you greatly disturb the shape of the final tree. Add in the transposition/refutation table and move ordering becomes more significant.

For a true bitboarder, I'm not sure how this could be cured since there is no way to translate left-to-right mirroring into something that will produce the same move ordering. Many of the moves I search are simply searched in the order they are produced.

Yes the time varies a lot. But no, it is not a bug and has no specific effect on how the program plays. The only real solution would be to try to generate moves in some specific pattern regardless of how the board is set up. For example, generate moves for the pieces closest to the king, that are moving even closer to the king first. Of course, for "ties" that would still fail. And I don't see any reason, nor any acceptable (with respect to performance) way of pulling this off in a pure bitboard engine...

As far as "mate-finding time" goes, most mates are found by serendipity anyway, rather than by actual "plan". You just stumble into a move that forces mate, and how early (or late) in the move list it appears determines how long it will take to find the mate...

bob
Posts: 20573
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Movei added to Crafty vs Rybka comaprison data

Post by bob » Mon Jun 04, 2007 7:06 pm

Edsel Apostol wrote:Hi Les,

Maybe Rybka is using piece lists combined with bitboard. As what Bob has said, it is true that when you flip a position, the move ordering will also change, resulting to varying time to find the solution, that is if it is a bitboard only engine.

There is also a possibility that the eval value will change even if you have no bugs in your program. This results from the SEE routine, if it uses lastOne() only for both sides, applicable only for bitboards. (I'm using SEE in my eval ). Some positions have the same rooks for example to capture on a square, but when you flipped it the other rook will be tried first in the capture sequence that might result to a different value. It is also possible that in this kind of positions the SEE is inaccurate.

I even wrote a bitboard SEE that will overcome this issue but I'm wondering if the added accuracy can compensate for the little speed loss. This kind of positions are somewhat rare, maybe one in a hundred thousand positions in my guess. I have not tested that SEE much though and on my testing, there is no significant change that I noticed.

Edsel
I don't have this problem in my SEE. I always pick the least valuable attacking piece first when playing out the captures, regardless of where that particular piece stands on the board.

Evaluations should not change in Crafty either, as I take great pains to make sure that is true for each new version as it represents a significant bug if it happens.

But for move generation, I'm going to run into this every last time.

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Movei added to Crafty vs Rybka comaprison data

Post by Gerd Isenberg » Mon Jun 04, 2007 9:39 pm

bob wrote:
vb4 wrote:Hi Bob,

What I was curious about was the significant difference in the number of seconds it took depending on which reflection you were working on. Some of the factors were very much different certainly when I compared it to Rybka ie. For reflections Rybka's times across the 4 reflections for the entire set were almost all the same. Why does it seem that Rybka across the reflections is so consistant?

Also looking at the Slider positions one would also think that the solutions would be a bit closer in terms of solution time then what I see. Now the only stipulation I make with these "Slider" positions is that the game would have to be a proven mate in N. Anything other then that then the Sliders can not be used this way.

Anyway I thought perhaps that you may be interested in this comparison since I would have to believe that reaching a mate solution in less time would only be a benefit.

Les
Disturb the move ordering and you greatly disturb the shape of the final tree. Add in the transposition/refutation table and move ordering becomes more significant.

For a true bitboarder, I'm not sure how this could be cured since there is no way to translate left-to-right mirroring into something that will produce the same move ordering. Many of the moves I search are simply searched in the order they are produced.

Yes the time varies a lot. But no, it is not a bug and has no specific effect on how the program plays. The only real solution would be to try to generate moves in some specific pattern regardless of how the board is set up. For example, generate moves for the pieces closest to the king, that are moving even closer to the king first. Of course, for "ties" that would still fail. And I don't see any reason, nor any acceptable (with respect to performance) way of pulling this off in a pure bitboard engine...

As far as "mate-finding time" goes, most mates are found by serendipity anyway, rather than by actual "plan". You just stumble into a move that forces mate, and how early (or late) in the move list it appears determines how long it will take to find the mate...
Ok, that don't covers left-to-right mirroring, but what about to flip the complete board after each make/unmake vertically - to make side to move always the "white" side?

That takes almost one bswap for each bitboard and some trick for the hashkey. The additional advantage beside "symmetrical" search would be, that you need to generate only "white" pawn-moves, ep, promotion etc. and that you gain more hash-hits in symmetrical positions ;-)

Edsel Apostol
Posts: 762
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Movei added to Crafty vs Rybka comaprison data

Post by Edsel Apostol » Tue Jun 05, 2007 6:15 am

bob wrote:
Edsel Apostol wrote:Hi Les,

Maybe Rybka is using piece lists combined with bitboard. As what Bob has said, it is true that when you flip a position, the move ordering will also change, resulting to varying time to find the solution, that is if it is a bitboard only engine.

There is also a possibility that the eval value will change even if you have no bugs in your program. This results from the SEE routine, if it uses lastOne() only for both sides, applicable only for bitboards. (I'm using SEE in my eval ). Some positions have the same rooks for example to capture on a square, but when you flipped it the other rook will be tried first in the capture sequence that might result to a different value. It is also possible that in this kind of positions the SEE is inaccurate.

I even wrote a bitboard SEE that will overcome this issue but I'm wondering if the added accuracy can compensate for the little speed loss. This kind of positions are somewhat rare, maybe one in a hundred thousand positions in my guess. I have not tested that SEE much though and on my testing, there is no significant change that I noticed.

Edsel
I don't have this problem in my SEE. I always pick the least valuable attacking piece first when playing out the captures, regardless of where that particular piece stands on the board.

Evaluations should not change in Crafty either, as I take great pains to make sure that is true for each new version as it represents a significant bug if it happens.

But for move generation, I'm going to run into this every last time.
Hi Bob,

My SEE is somewhat similar to the SEE used in latest open source Crafty so if you had not changed that in your latest versions then the problem is there. The problem I mentioned is in positions where there are two or more same pieces as least valuable attacker.

In the position that I find in my debugging, this involves two rooks that can recapture on the SEE square, one of this rooks has a hidden attacker behind that is that of the enemy. So when you flip the position, and used only the LSB() function instead of using the MSB() for flipped positions, the sequence of capture will change. For example, instead of the rook without the hidden attacker behind is tried first, in the flipped position, the one with the hidden attacker behind will be tried first. This will result into different SEE values for flipped positions.

In my program, it uses something similar to the idea in Fruit where SEE was used to determine if a pawn is a Free Passer. This is where I discovered these positions where it failed in my Eval Symmetry test.

Another thing, in these positions, it is possible that this kind of SEE is inaccurate. It never determines which sequence of captures to consider as the best. In these positions where there are two or more Least Valuable Attackers to the SEE square, it only tried the one that was found by LSB routine first. There are cases that trying out the other Least Valuable Attackers first instead of sorting it out by the LSB only, will produce a more accurate value for the SEE.

I will try to post the positions next time as I will look it up on my debug files. I will also post the SEE trace for that position and the trace of the new SEE routine i wrote myself.

If anyone is interested, I will post the source code of the two SEE routines here.

Best Regards,
Edsel Apostol (Twisted Logic)

Dann Corbit
Posts: 10128
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Movei added to Crafty vs Rybka comaprison data

Post by Dann Corbit » Tue Jun 05, 2007 7:00 pm

Edsel Apostol wrote: {snip}
If anyone is interested, I will post the source code of the two SEE routines here.

Best Regards,
Edsel Apostol (Twisted Logic)
I am interested to see the difference and also if you have experimented to see what the difference is in eval and search, I would be interested to see your results also.

Dann Corbit
Posts: 10128
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Movei added to Crafty vs Rybka comaprison data

Post by Dann Corbit » Tue Jun 05, 2007 7:03 pm

bob wrote:
Edsel Apostol wrote:Hi Les,

Maybe Rybka is using piece lists combined with bitboard. As what Bob has said, it is true that when you flip a position, the move ordering will also change, resulting to varying time to find the solution, that is if it is a bitboard only engine.

There is also a possibility that the eval value will change even if you have no bugs in your program. This results from the SEE routine, if it uses lastOne() only for both sides, applicable only for bitboards. (I'm using SEE in my eval ). Some positions have the same rooks for example to capture on a square, but when you flipped it the other rook will be tried first in the capture sequence that might result to a different value. It is also possible that in this kind of positions the SEE is inaccurate.

I even wrote a bitboard SEE that will overcome this issue but I'm wondering if the added accuracy can compensate for the little speed loss. This kind of positions are somewhat rare, maybe one in a hundred thousand positions in my guess. I have not tested that SEE much though and on my testing, there is no significant change that I noticed.

Edsel
I don't have this problem in my SEE. I always pick the least valuable attacking piece first when playing out the captures, regardless of where that particular piece stands on the board.

Evaluations should not change in Crafty either, as I take great pains to make sure that is true for each new version as it represents a significant bug if it happens.

But for move generation, I'm going to run into this every last time.
It still seems odd that there should be such a striking difference in tree shape. After all, the pv nodes should determine the shape of the tree. Why doesn't move ordering correct the problem?

Other programs seem to be affected much less. Is it a defect due to the use of bitboards for game state? We should wonder why array type representations do not suffer from the same defect. After all, they have to choose some sort of order for generation also.

Post Reply