Perft 9, confirmed by Sharper too...

[Albert Bertilsson]

Geschrieben von: / Posted by: Albert Bertilsson at 16 February 2003 14:23:05:

Perft 9 from initial position was confirmed by Sharper today. Calculation took about 19 to 21 hours.
/Regards Albert

[Sune Fischer]

Geschrieben von: / Posted by: Sune Fischer at 16 February 2003 14:42:29:
Als Antwort auf: / In reply to: Perft 9, confirmed by Sharper too... geschrieben von: / posted by: Albert Bertilsson at 16 February 2003 14:23:05:

Perft 9 from initial position was confirmed by Sharper today. Calculation took about 19 to 21 hours.
/Regards Albert

Congratulations that totally rules!
Welcome to a small exclusive club of perft niners
-S.

[Albert Bertilsson]

Geschrieben von: / Posted by: Albert Bertilsson at 16 February 2003 20:22:51:
Als Antwort auf: / In reply to: Re: Perft 9, confirmed by Sharper too... geschrieben von: / posted by: Sune Fischer at 16 February 2003 14:42:29:

Are you up for p10 too? As before not much point in doing this alone... come on 20 days (it's only cpu cycles).
As you and Uri have discussed, TT could become an issue since two keys can be generated from diffrent positions. I think the tests you and I have done shows that this is not much of a problem.
/Regards Albert

[Dieter Bürßner]

Geschrieben von: / Posted by: Dieter Bürßner at 16 February 2003 21:17:55:
Als Antwort auf: / In reply to: Re: Perft 9, confirmed by Sharper too... geschrieben von: / posted by: Albert Bertilsson at 16 February 2003 20:22:51:

Are you up for p10 too? As before not much point in doing this alone... come on 20 days (it's only cpu cycles).
As you and Uri have discussed, TT could become an issue since two keys can be generated from diffrent positions. I think the tests you and I have done shows that this is not much of a problem.

For a reliable new number, you should store the whole position in the hash, and after a hit in the hash key, compare the whole positions. I just tried, and Yace used 11500 seconds for perft 9 (same result) on my P4 2.53. It did not have all (but most) CPU recources. I used a very primitive depth preferred HT with only one slot per position. Possible ideas for speed ups would be, to save several depth/score pairs per position, as well as to have more than one slot in the HT per index. I used 35 bytes to store the position (32 bytes for color/piece of the 64 squares, one byte each for castling, ep and side to move). There was no wrong position in the HT for the perft 9. I stored/probed everywhere besides the last depth.
BTW. I think Chest (mate solver by Heiner Marxen) does something similar, because it won't accept some theoretical flaw in its scores.
I think a normal perft 9 without HT would need about 40 hours here. But I won't check it ...
Stephen Edwards used 15 days of CPU time on P233 for perft 9. He probably also had much less memory than todays computers.
Regards,
Dieter

[Uri Blass]

Geschrieben von: / Posted by: Uri Blass at 16 February 2003 21:36:31:
Als Antwort auf: / In reply to: Re: Perft 9, confirmed by Sharper too... geschrieben von: / posted by: Dieter Bürßner at 16 February 2003 21:17:55:

Are you up for p10 too? As before not much point in doing this alone... come on 20 days (it's only cpu cycles).
As you and Uri have discussed, TT could become an issue since two keys can be generated from diffrent positions. I think the tests you and I have done shows that this is not much of a problem.

For a reliable new number, you should store the whole position in the hash, and after a hit in the hash key, compare the whole positions. I just tried, and Yace used 11500 seconds for perft 9 (same result) on my P4 2.53.
BTW. I think Chest (mate solver by Heiner Marxen) does something similar, because it won't accept some theoretical flaw in its scores.
I think a normal perft 9 without HT would need about 40 hours here. But I won't check it ...
Stephen Edwards used 15 days of CPU time on P233 for perft 9. He probably also had much less memory than todays computers.
Regards,
Dieter

40 hours without hash mean that hash tables help you to be 144000/11500 times faster that is almost 12 times faster.

It did not have all (but most) CPU recources. I used a very primitive depth preferred HT with only one slot per position. Possible ideas for speed ups would be, to save several depth/score pairs per position, as well as to have more than one slot in the HT per index. I used 35 bytes to store the position (32 bytes for color/piece of the 64 squares, one byte each for castling, ep and side to move).
I think that you can save 8 bytes here.
there is a known simple way to store the board in 192 bits that is 24 bytes.
64 bits tell you the empty squares.
for every piece you can store the type of the piece by 4 bits so you have at most 4*32=128 additional bits.

There was no wrong position in the HT for the perft 9. I stored/probed everywhere besides the last depth.
I think that movei without hash can do it in less time.
I get 5 minutes on 1000Mhz for perft 7.
it means about than 5*900*1000/233 minutes on 233Mhz if I assume a branching factor of 30 at depth 8,9.
5*900*1000/233

[Dieter Bürßner]

Geschrieben von: / Posted by: Dieter Bürßner at 16 February 2003 21:50:01:
Als Antwort auf: / In reply to: Re: Perft 9, confirmed by Sharper too... geschrieben von: / posted by: Uri Blass at 16 February 2003 21:36:31:

It did not have all (but most) CPU recources. I used a very primitive depth preferred HT with only one slot per position. Possible ideas for speed ups would be, to save several depth/score pairs per position, as well as to have more than one slot in the HT per index. I used 35 bytes to store the position (32 bytes for color/piece of the 64 squares, one byte each for castling, ep and side to move).
I think that you can save 8 bytes here.
there is a known simple way to store the board in 192 bits that is 24 bytes.
64 bits tell you the empty squares.
for every piece you can store the type of the piece by 4 bits so you have at most 4*32=128 additional bits.

I know, it can even be done smaller with reasonable computing time, but I decided to use the easiest (coding time) method. The faster method would be: All KK positions can be coded (including castling rights) in 12 bits. A bit occupation vector for the remaining 62 squares. At most 29 additional pieces (the last piece is allways known for legal chess positions). Number from 0 to 9 for the piece/color of each piece. This means, 3 pieces need 0-999, which fit nicely into 10 bit. 29 pieces -> 98 bits. So 12+62+98=182. Plus side to move and ep.
Regards,
Dieter

[Sune Fischer]

Geschrieben von: / Posted by: Sune Fischer at 16 February 2003 23:18:11:
Als Antwort auf: / In reply to: Re: Perft 9, confirmed by Sharper too... geschrieben von: / posted by: Albert Bertilsson at 16 February 2003 20:22:51:

Are you up for p10 too? As before not much point in doing this alone... come on 20 days (it's only cpu cycles).
As you and Uri have discussed, TT could become an issue since two keys can be generated from diffrent positions. I think the tests you and I have done shows that this is not much of a problem.
/Regards Albert

Hehe, well a few days would have been fine by me, but 20 is a little long
We might need to run some experiments on the hash storing scheme, I think depth preferred can be improved, something like a two table where one is depth preferred and one is replace always.
Also I think this is a job for faster programs, yace could perhaps do it in a few days.
Yes it is not a problem if you are content being only 99% sure of the number, 20 days is after all quite a few nodes so chance of a collision increase to around 1% I think.
But if we did get the same number we could be sure it was correct
-S.