Perft

Discussion about development of draughts in the time of computer and Internet.
Post Reply
Rein Halbersma
Posts: 1635
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Perft

Post by Rein Halbersma » Sat Aug 26, 2017 10:40

BertTuyt wrote:A weekend in Holland.
Full bulk counting, but should still be a little beter :D

Code: Select all

Perft(11)       N = 1665861398     7.35 sec.    KN/sec = 226647
Perft(9)        N = 1216917193     3.95 sec.    KN/sec = 308080
Perft(15)       N = 346184885      2.38 sec.    KN/sec = 145455
Bert
What are your machine specs, Bert?

My latest results: Ubuntu Linux 16.04 in a VirtualBox on Windows 10 @3.6 GHz, gcc 7.2 PGO build

Code: Select all

info depth 11 leafs   1665861398 time   6849 243227 knps
info depth  9 leafs   1216917193 time   3490 348687 knps
info depth 15 leafs    346184885 time   2486 139254 knps
2 out of 3 are fastest, the final position doesn't respond to PGO at all

BertTuyt
Posts: 1344
Joined: Wed Sep 01, 2004 19:42

Re: Perft

Post by BertTuyt » Sat Aug 26, 2017 11:39

Rein, 8 core Intel, 4 GHz.

Attached the source, so all may use, or propose improvements.

Bert
Attachments
CMoveGen128.zip
(3.31 KiB) Downloaded 123 times

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

Re: Perft

Post by Rein Halbersma » Sat Aug 26, 2017 11:45

BertTuyt wrote:Rein, 8 core Intel, 4 GHz.

Attached the source, so all may use, or propose improvements.

Bert
I noticed that Harm, Ed, and you use these ray masks for king jumps. It took me a long time to fully understand how they work, but they are very clever! However, because the ray masks are of constant length and shifted per origin square, they interact with the ghost squares in a tricky way. I managed to improve (well, On My Machine TM) this by making a table of square-specific jump detection masks. This allows some early "cut-offs" in my capture routine. I'll write something longer about it when I have some more time.

Another thing that I do differently is king move generation: I use what the chess programming wiki calls the Classical Approach In One Run, which is 5 table lookups XOR-ed together, and then a single bit-serialization for each king origin square.

On my TODO list is generalizing my capture routine to generate both moves, GUI moves with path info as well as successor positions from the same routine.

My source is here: https://github.com/rhalbersma/dctl/tree ... ons/detail (warning, template-heavy code!). Feel free to ask anything.

BertTuyt
Posts: 1344
Joined: Wed Sep 01, 2004 19:42

Re: Perft

Post by BertTuyt » Sat Aug 26, 2017 11:57

I noticed that Harm, Ed, and you use these ray masks for king jumps

Rein, I implemented the ray mask while studying the Moby Dam code from Harm.
I thought this was a very clever approach, and therefore also implemented this.
So all credits to him.

Bert

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

Re: Perft

Post by Rein Halbersma » Sat Aug 26, 2017 11:59

BertTuyt wrote:I noticed that Harm, Ed, and you use these ray masks for king jumps

Rein, I implemented the ray mask while studying the Moby Dam code from Harm.
I thought this was a very clever approach, and therefore also implemented this.
So all credits to him.

Bert
Yes, Harm's program is a great piece of work. It reads very easily, compiles fast and its perft is fastest of all.

BertTuyt
Posts: 1344
Joined: Wed Sep 01, 2004 19:42

Re: Perft

Post by BertTuyt » Sat Aug 26, 2017 14:00

Rein, now doing a Verify for 13P DB.
When observing the task manager I didnt see the 4.0 GHz speed.
But the 3.5 GHz - 3.6 GHz (which seems to me the Turbo Speed).
So I might need to rerun the Perft(), when the Verify has finished.

In the past I had the feeling that Windows 10 changed Power Balance Plan Settings, after an update.
Or things in the BIOS are modified, will have a look at it.

Bert

BertTuyt
Posts: 1344
Joined: Wed Sep 01, 2004 19:42

Re: Perft

Post by BertTuyt » Sat Aug 26, 2017 23:17

With PGO and 4 GHz .

Code: Select all

pos XW XB 20 20
Perft(1)        N = 9      0.00 sec.    KN/sec = 0
Perft(2)        N = 81     0.00 sec.    KN/sec = 0
Perft(3)        N = 658    0.00 sec.    KN/sec = 0
Perft(4)        N = 4265           0.00 sec.    KN/sec = 0
Perft(5)        N = 27117          0.00 sec.    KN/sec = 0
Perft(6)        N = 167140         0.00 sec.    KN/sec = 0
Perft(7)        N = 1049442        0.00 sec.    KN/sec = 0
Perft(8)        N = 6483961        0.02 sec.    KN/sec = 324198
Perft(9)        N = 41022423       0.15 sec.    KN/sec = 273482
Perft(10)       N = 258895763      1.08 sec.    KN/sec = 239718
Perft(11)       N = 1665861398     6.16 sec.    KN/sec = 270432
pos XW XB 17 2
Perft(1)        N = 14     0.00 sec.    KN/sec = 0
Perft(2)        N = 55     0.00 sec.    KN/sec = 0
Perft(3)        N = 1168           0.00 sec.    KN/sec = 0
Perft(4)        N = 5432           0.00 sec.    KN/sec = 0
Perft(5)        N = 87195          0.00 sec.    KN/sec = 0
Perft(6)        N = 629010         0.00 sec.    KN/sec = 0
Perft(7)        N = 9041010        0.02 sec.    KN/sec = 452050
Perft(8)        N = 86724219       0.24 sec.    KN/sec = 361350
Perft(9)        N = 1216917193     3.83 sec.    KN/sec = 317732
pos XW XB 10 10
Perft(1)        N = 6      0.00 sec.    KN/sec = 0
Perft(2)        N = 12     0.00 sec.    KN/sec = 0
Perft(3)        N = 30     0.00 sec.    KN/sec = 0
Perft(4)        N = 73     0.00 sec.    KN/sec = 0
Perft(5)        N = 215    0.00 sec.    KN/sec = 0
Perft(6)        N = 590    0.00 sec.    KN/sec = 0
Perft(7)        N = 1944           0.00 sec.    KN/sec = 0
Perft(8)        N = 6269           0.00 sec.    KN/sec = 0
Perft(9)        N = 22369          0.00 sec.    KN/sec = 0
Perft(10)       N = 88050          0.00 sec.    KN/sec = 0
Perft(11)       N = 377436         0.00 sec.    KN/sec = 0
Perft(12)       N = 1910989        0.01 sec.    KN/sec = 191098
Perft(13)       N = 9872645        0.07 sec.    KN/sec = 141037
Perft(14)       N = 58360286       0.40 sec.    KN/sec = 145900
Perft(15)       N = 346184885      2.24 sec.    KN/sec = 154546
Press any key to continue . . .
Bert

BertTuyt
Posts: 1344
Joined: Wed Sep 01, 2004 19:42

Re: Perft

Post by BertTuyt » Sun Sep 22, 2019 11:16

Herewith a recent Perft test.
Processor is the Intel Core i7-8700K, during the test the speed was around 4.5 GHz.

Code: Select all

pos XW XB 20 20
Perft(1)        N = 9      0.00 sec.    KN/sec = 0
Perft(2)        N = 81     0.00 sec.    KN/sec = 0
Perft(3)        N = 658    0.00 sec.    KN/sec = 0
Perft(4)        N = 4265           0.00 sec.    KN/sec = 0
Perft(5)        N = 27117          0.00 sec.    KN/sec = 0
Perft(6)        N = 167140         0.00 sec.    KN/sec = 0
Perft(7)        N = 1049442        0.00 sec.    KN/sec = 0
Perft(8)        N = 6483961        0.02 sec.    KN/sec = 324198
Perft(9)        N = 41022423       0.14 sec.    KN/sec = 293017
Perft(10)       N = 258895763      0.96 sec.    KN/sec = 269683
Perft(11)       N = 1665861398     5.53 sec.    KN/sec = 301240
pos XW XB 17 2
Perft(1)        N = 14     0.00 sec.    KN/sec = 0
Perft(2)        N = 55     0.00 sec.    KN/sec = 0
Perft(3)        N = 1168           0.00 sec.    KN/sec = 0
Perft(4)        N = 5432           0.00 sec.    KN/sec = 0
Perft(5)        N = 87195          0.00 sec.    KN/sec = 0
Perft(6)        N = 629010         0.00 sec.    KN/sec = 0
Perft(7)        N = 9041010        0.02 sec.    KN/sec = 452050
Perft(8)        N = 86724219       0.20 sec.    KN/sec = 433621
Perft(9)        N = 1216917193     3.28 sec.    KN/sec = 371011
pos XW XB 10 10
Perft(1)        N = 6      0.00 sec.    KN/sec = 0
Perft(2)        N = 12     0.00 sec.    KN/sec = 0
Perft(3)        N = 30     0.00 sec.    KN/sec = 0
Perft(4)        N = 73     0.00 sec.    KN/sec = 0
Perft(5)        N = 215    0.00 sec.    KN/sec = 0
Perft(6)        N = 590    0.00 sec.    KN/sec = 0
Perft(7)        N = 1944           0.00 sec.    KN/sec = 0
Perft(8)        N = 6269           0.00 sec.    KN/sec = 0
Perft(9)        N = 22369          0.00 sec.    KN/sec = 0
Perft(10)       N = 88050          0.00 sec.    KN/sec = 0
Perft(11)       N = 377436         0.00 sec.    KN/sec = 0
Perft(12)       N = 1910989        0.01 sec.    KN/sec = 191098
Perft(13)       N = 9872645        0.06 sec.    KN/sec = 164544
Perft(14)       N = 58360286       0.34 sec.    KN/sec = 171647
Perft(15)       N = 346184885      1.91 sec.    KN/sec = 181248
Bert

BertTuyt
Posts: 1344
Joined: Wed Sep 01, 2004 19:42

Re: Perft

Post by BertTuyt » Sun Sep 22, 2019 11:47

Also interesting to see what timings were in 2008 when Ed started this post.
Respectively around 55s, 30s, and 17s, so close to a factor of 10 slower.
These tests were without bulk counting, but anyway, at that time we were proud on this speed :D
Further optimization is most likely a goal in itself (but still fun), as the MoveGenerate (these days) is so fast, that it has a minor impact on program playing strength.

As my PC has water cooling, I could increase the Turbo Boost to 5 GHZ (for 1 core), which yield a further 10% speed increase in theory, but that is for another time...

Bert

Post Reply