perft for 8x8 checkers (depth 27)

[AartBik]

With the new improvements in place, it would almost be a waste not to go deeper with my perft for checkers computation. Therefore, I computed perft(27) from the initial position of 8x8 checkers. Below you see the perft breakdown per move, called "divide". As stated before, these numbers were computed on a cluster of machines, further optimized with a "hard collision"-free transposition table as well as bulk counting. The move generator does not eliminate duplicate captures.

Code: Select all

 move                 divide(27)
-------------------------------
 12-16    =  516399283859880203
 11-16    =  519502096014967805
 11-15    =  476666239516455180
 10-15    =  468705060101275533
 10-14    =  400425747281243848
  9-14   =  486493422418651579
  9-13   =  631652334435528457 
-------------------------------
perft(27) = 3499844183628002605

The implementation is "fault tolerant" against machine failures. Nevertheless, since I saw a few of these recoveries in this particular run, I may rerun this depth soon to verify the results pedantically.

[Rein Halbersma]

With the new improvements in place, it would almost be a waste not to go deeper with my perft for checkers computation. Therefore, I computed perft(27) from the initial position of 8x8 checkers. Below you see the perft breakdown per move, called "divide". As stated before, these numbers were computed on a cluster of machines, further optimized with a "hard collision"-free transposition table as well as bulk counting. The move generator does not eliminate duplicate captures.

Code: Select all

 perft(27) = 3499844183628002605

The implementation is "fault tolerant" against machine failures. Nevertheless, since I saw a few of these recoveries in this particular run, I may rerun this depth soon to verify the results pedantically.

Awesome, Aart! When are you going to do 10x10?

[AartBik]

Awesome, Aart! When are you going to do 10x10?

Thanks Rein! And who knows? I really like board game engines!

[murraycash]

Aart, Wow, these numbers are so big I had to look them up to see how they are named. So that is 3 quintillion and counting!
I do hope to be able to verify this, I think it is just within my grasp. I will post back when I am an old man!

[AartBik]

Aart, Wow, these numbers are so big I had to look them up to see how they are named. So that is 3 quintillion and counting! I do hope to be able to verify this, I think it is just within my grasp. I will post back when I am an old man!

Thanks Murray. Perhaps one more, just to make sure we run out of 64-bit space?

[Rein Halbersma]

Aart, Wow, these numbers are so big I had to look them up to see how they are named. So that is 3 quintillion and counting! I do hope to be able to verify this, I think it is just within my grasp. I will post back when I am an old man!

Thanks Murray. Perhaps one more, just to make sure we run out of 64-bit space?

You need 2 more to actually overflow 64-bits because if the branching factor stays the same (~4.66) then perft(28) will weigh in at 1.63e+19 which is still within 2^64 = 1.84e+19.

[Rein Halbersma]

Aart, Wow, these numbers are so big I had to look them up to see how they are named. So that is 3 quintillion and counting!
I do hope to be able to verify this, I think it is just within my grasp. I will post back when I am an old man!

If Moore's law can go on until you are retired, then you might have the same computing resources that Aart has right now

[AartBik]

You need 2 more to actually overflow 64-bits because if the branching factor stays the same (~4.66) then perft(28) will weigh in at 1.63e+19 which is still within 2^64 = 1.84e+19.

Well, that is what I meant . One more, i.e. perft(28), and then we can claim we ran out of 64-bit space to go further! Of course, there are ways around that also.....

[ibid]

Code: Select all

 move                 divide(27)
-------------------------------
 12-16    =  516399283859880203
 11-16    =  519502096014967805
 11-15    =  476666239516455180
 10-15    =  468705060101275533
 10-14    =  400425747281243848
  9-14   =  486493422418651579
  9-13   =  631652334435528457 
-------------------------------
perft(27) = 3499844183628002605

Code: Select all

thread  0 -- block    0 -- time    141 -- perft 4887271141477779
thread  2 -- block    2 -- time    148 -- perft 13567985195298713
thread  1 -- block    1 -- time    150 -- perft 8859582627418271
thread  3 -- block    3 -- time    154 -- perft 6984856907105633
thread  4 -- block    4 -- time    163 -- perft 5868683701151800
thread  5 -- block    5 -- time    170 -- perft 4728148773749011
thread  2 -- block    7 -- time    298 -- perft 7311700995592627
...
thread  0 -- block 5070 -- time 155893 -- perft 4295146303614
thread  3 -- block 5074 -- time 155898 -- perft 467736054753
thread  1 -- block 5072 -- time 155906 -- perft 1453143682121
thread  5 -- block 5071 -- time 155913 -- perft 3123703922871
thread  4 -- block 5073 -- time 156009 -- perft 4340343451235
3499844183628002605 positions.  156009 seconds.  done.

perft 27 confirmed... I've just started 28, I am guessing 9 days or so.
perft 28 will be my last, I want my machine back. :)

-paul

[AartBik]

perft 27 confirmed... I've just started 28, I am guessing 9 days or so.
perft 28 will be my last, I want my machine back.
-paul

Thanks Paul! Extremely kind of you to take the time verifying this!