perft for 8x8 checkers (depth 28)

Discussion about development of draughts in the time of computer and Internet.
Post Reply
AartBik
Posts: 103
Joined: Wed Mar 11, 2009 01:30
Location: Mountain View
Contact:

perft for 8x8 checkers (depth 28)

Post by AartBik » Mon Sep 24, 2012 22:52

My quest for deeper perft numbers for 8x8 checkers using has reached depth 28. Below you see the perft(28) breakdown per move, called "divide". As stated before, the numbers were computed on a cluster of machines, optimized with a "hard collision"-free transposition table as well as bulk counting. The move generator does not eliminate duplicate captures. At this point, the limits of 64-bit unsigned integers have been reached. Although there are obvious ways around these restrictions, this seems a very good time to give this (by now probably insane) project a rest (although I may do some re-computations to get more confidence in the higher depth numbers; third party confirmation always welcome!).

Code: Select all

divide(28)
12-16 = 2400708339858199191
11-16 = 2431386196712611878
11-15 = 2231787529331259810
10-15 = 2186446356811761737
10-14 = 1872427919495823777
 9-14 = 2285893686261887442
 9-13 = 2969067990365356900
--------------------------- +
       16377718018836900735   = perft(28)

AartBik
Posts: 103
Joined: Wed Mar 11, 2009 01:30
Location: Mountain View
Contact:

Re: perft for 8x8 checkers (depth 28)

Post by AartBik » Tue Sep 25, 2012 00:47

Paul Byrne kindly verified perft(24), perft(25), and perft(26), and will work on confirming the others too. Murray Cash kindly verified perft(23) and perft(24) in earlier postings in this forum and will try to confirm higher depths too. Thanks all for your interest in this project!

Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: perft for 8x8 checkers (depth 28)

Post by Rein Halbersma » Tue Sep 25, 2012 08:29

AartBik wrote:Paul Byrne kindly verified perft(24), perft(25), and perft(26), and will work on confirming the others too. Murray Cash kindly verified perft(23) and perft(24) in earlier postings in this forum and will try to confirm higher depths too. Thanks all for your interest in this project!
Hi Aart,

Congrats once more! Looking at your divide stats on your website, I noticed some interesting patterns. E.g. there is a small alternating effect in the branching factor of some initial moves, and the relative subtree sizes also show quite a bit of variation.

Rein

ibid
Posts: 5
Joined: Tue Sep 25, 2012 22:59
Real name: Paul Byrne

Re: perft for 8x8 checkers (depth 28)

Post by ibid » Tue Oct 02, 2012 11:19

Code: Select all

-2069026054872650881 positions.  543939 seconds.
Also known as 16377718018836900735 for those who can use printf properly. :) Perft 28 confirmed.

-paul

AartBik
Posts: 103
Joined: Wed Mar 11, 2009 01:30
Location: Mountain View
Contact:

Re: perft for 8x8 checkers (depth 28)

Post by AartBik » Wed Oct 03, 2012 02:32

ibid wrote:

Code: Select all

-2069026054872650881 positions.  543939 seconds.
Also known as 16377718018836900735 for those who can use printf properly. :) Perft 28 confirmed.
:-)

Thanks for taking the time to verify this number Paul. Highly appreciated!

Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: perft for 8x8 checkers (depth 28)

Post by Rein Halbersma » Tue May 28, 2024 09:28

Apparently @murraycash computed perft(29) in November 2020: https://oeis.org/A133046
Anyone up for the task of confirming that number?

Post Reply