Not likely as far as I am concerned. Since I moved out of infrastructure into other exciting projects, I no longer have easy access to the large clusters that I used to go up to depth 28Ajedrecista wrote:Aart, Paul... any chance of Perft(29) of English draughts
perft for 8x8 checkers
Moderators: hgm, Rebel, chrisw
-
- Posts: 819
- Joined: Fri Dec 01, 2006 10:46 pm
- Location: Mountain View, CA, USA
- Full name: Aart Bik
Re: Search space complexity of the game of nxn checkers.
-
- Posts: 89
- Joined: Mon Jun 13, 2011 12:09 pm
Re: Search space complexity of the game of nxn checkers.
In principle it is certainly possible. Perft(28) took a little under a week for me and the program could probably be made a little faster (the hash table implementation is exceptionally crude). With the low branching in checkers, 29 and 30 would be reasonable.Ajedrecista wrote:Aart, Paul... any chance of Perft(29) of English draughts?
Except I need my machine for work at the moment, so anything taking longer than a weekend isn't going to happen. Plus the hard drive with the unique position database died a while back and I lack space to regenerate them.
I was looking into getting a new machine later this year for chess/checkers/etc but my new computer fund ended up going to my dentist. :(
I'm sure I'll do them eventually, but not in the near future.
-
- Posts: 1968
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
Re: Perft for 8x8 checkers.
Hello Aart and Paul:
Thank you very much for your answers. It is good to know that Perft(29) and even Perft(30) (wow!) might have a chance in the future. I stay tuned.
Regards from Spain.
Ajedrecista.
Thank you very much for your answers. It is good to know that Perft(29) and even Perft(30) (wow!) might have a chance in the future. I stay tuned.
Regards from Spain.
Ajedrecista.
-
- Posts: 1968
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
Re: Perft for 8×8 checkers.
Hello:
I have just found that Perft(29) of 8×8 checkers was computed some months ago (On-Line Encyclopedia of Integer Sequences link) by the author of Nemesis programme (the champion of the Computer Checkers World Championship of 2002: summary of the championship). It would be good to get independent verification. Anyway, the number given is the next one:
So, Perft(29) ~ 7.63e+19. Not an easy, short task at all!
Just waiting until the verification...
Regards from Spain.
Ajedrecista.
I have just found that Perft(29) of 8×8 checkers was computed some months ago (On-Line Encyclopedia of Integer Sequences link) by the author of Nemesis programme (the champion of the Computer Checkers World Championship of 2002: summary of the championship). It would be good to get independent verification. Anyway, the number given is the next one:
Code: Select all
Perft(29) = 76,309,690,522,352,444,005
Just waiting until the verification...
Code: Select all
List of prime numbers:
https://oeis.org/A000040
https://oeis.org/A000040/a000040.txt
Perft(29) = 76,309,690,522,352,444,005 = 5 × 59 × 577 × 4093 × 150767 × 726497
Perft(29) = 76,309,690,522,352,444,005 = p(3) × p(17) × p(106) × p(564) × p(13911) × p(58525)
Ajedrecista.