Perft

Discussion about development of draughts in the time of computer and Internet.
Post Reply
Rein Halbersma
Posts: 1666
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: 1435
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 201 times

Rein Halbersma
Posts: 1666
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: 1435
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: 1666
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: 1435
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: 1435
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: 1435
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: 1435
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

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

Re: Perft

Post by BertTuyt » Fri Apr 03, 2020 01:54

Perft is addictive.
With the same processor the Intel Core i7-8700K, and frequency 4.5 GHZ, another test.
This time the perft for the initial position has really improved, others almost the same.

Code: Select all

Perft 1.
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 = 27117
perft(6)        N = 167140         0.00 sec.    KN/sec = 0
perft(7)        N = 1049442        0.00 sec.    KN/sec = 262360
perft(8)        N = 6483961        0.02 sec.    KN/sec = 324198
perft(9)        N = 41022423       0.13 sec.    KN/sec = 328179
perft(10)       N = 258895763      0.78 sec.    KN/sec = 332770
perft(11)       N = 1665861398     4.80 sec.    KN/sec = 347126

Perft 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 = 5432
perft(5)        N = 87195          0.00 sec.    KN/sec = 0
perft(6)        N = 629010         0.00 sec.    KN/sec = 314505
perft(7)        N = 9041010        0.02 sec.    KN/sec = 376708
perft(8)        N = 86724219       0.22 sec.    KN/sec = 403368
perft(9)        N = 1216917193     3.22 sec.    KN/sec = 378042

Perft 3.
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 = 88050
perft(11)       N = 377436         0.00 sec.    KN/sec = 125812
perft(12)       N = 1910989        0.01 sec.    KN/sec = 146999
perft(13)       N = 9872645        0.06 sec.    KN/sec = 167332
perft(14)       N = 58360286       0.33 sec.    KN/sec = 179019
perft(15)       N = 346184885      1.86 sec.    KN/sec = 185721


Attached the movegen source.

Bert
Attachments
movegen.zip
(3 KiB) Downloaded 48 times

Joost Buijs
Posts: 325
Joined: Wed May 04, 2016 11:45
Real name: Joost Buijs

Re: Perft

Post by Joost Buijs » Sat Apr 04, 2020 18:28

It was not my intention to post here anymore, but your perft numbers are amazing and you clearly beat the old perft numbers I've got back in 2017 with my move generator based on magics.

I just ran perft() on my old Broadwell i7-6950X at 4.4 GHz. At the second position I'm still a little bit better, but on the other two you clearly beat me. A small difference is that I update hash and game-stage which is not really necessary for perft, but still your numbers are amazing.

Code: Select all

> perft

    m  m  m  m  m
  m  m  m  m  m
    m  m  m  m  m
  m  m  m  m  m
    -  -  -  -  -
  -  -  -  -  -
    M  M  M  M  M
  M  M  M  M  M
    M  M  M  M  M
  M  M  M  M  M

perft( 1)  nodes            9  time   0.0000  nps  29250000
perft( 2)  nodes           81  time   0.0000  nps  12535714
perft( 3)  nodes          658  time   0.0000  nps 285133333
perft( 4)  nodes         4265  time   0.0000  nps 243179825
perft( 5)  nodes        27117  time   0.0001  nps 226701608
perft( 6)  nodes       167140  time   0.0008  nps 221580665
perft( 7)  nodes      1049442  time   0.0048  nps 217681394
perft( 8)  nodes      6483961  time   0.0295  nps 219927187
perft( 9)  nodes     41022423  time   0.1889  nps 217157508
perft(10)  nodes    258895763  time   1.1487  nps 225371976
perft(11)  nodes   1665861398  time   7.4696  nps 223017566

    -  -  -  -  -
  M  -  -  M  M
    M  -  -  -  -
  -  k  -  -  M
    M  M  M  k  -
  -  -  -  -  M
    K  -  M  -  -
  -  M  -  -  -
    M  M  M  M  -
  M  -  -  -  -

perft( 1)  nodes           14  time   0.0000  nps    705426
perft( 2)  nodes           55  time   0.0000  nps   4468750
perft( 3)  nodes         1168  time   0.0000  nps  82521739
perft( 4)  nodes         5432  time   0.0000  nps 134250951
perft( 5)  nodes        87195  time   0.0002  nps 367315295
perft( 6)  nodes       629010  time   0.0022  nps 284085951
perft( 7)  nodes      9041010  time   0.0226  nps 399374535
perft( 8)  nodes     86724219  time   0.2402  nps 361067382
perft( 9)  nodes   1216917193  time   3.0534  nps 398544994
perft(10)  nodes  13106503411  time  33.0962  nps 396012665

    -  -  -  -  -
  -  -  -  -  -
    -  m  m  m  -
  m  -  m  m  -
    m  -  m  m  M
  m  M  M  -  M
    -  M  M  M  M
  -  M  M  -  -
    -  -  -  -  -
  -  -  -  -  -

perft( 1)  nodes            6  time   0.0000  nps  39000000
perft( 2)  nodes           12  time   0.0000  nps  17333333
perft( 3)  nodes           30  time   0.0000  nps  26000000
perft( 4)  nodes           73  time   0.0000  nps  29656250
perft( 5)  nodes          215  time   0.0000  nps  37770270
perft( 6)  nodes          590  time   0.0000  nps  41016043
perft( 7)  nodes         1944  time   0.0000  nps  53770213
perft( 8)  nodes         6269  time   0.0001  nps  60145387
perft( 9)  nodes        22369  time   0.0003  nps  69369513
perft(10)  nodes        88050  time   0.0011  nps  83204914
perft(11)  nodes       377436  time   0.0039  nps  96498672
perft(12)  nodes      1910989  time   0.0157  nps 121799608
perft(13)  nodes      9872645  time   0.0780  nps 126636189
perft(14)  nodes     58360286  time   0.3898  nps 149723354
perft(15)  nodes    346184885  time   2.2919  nps 151044008
perft(16)  nodes   2272406115  time  13.4435  nps 169034093
perft(17)  nodes  14962263728  time  89.5945  nps 166999804
For actual game play perft performance is probably not very important, at least when I compare it with chess, move generation takes only a few percent of the total time. Maybe for draughts this is different because the evaluation function is a lot smaller and faster, I don't know.

Joost Buijs
Posts: 325
Joined: Wed May 04, 2016 11:45
Real name: Joost Buijs

Re: Perft

Post by Joost Buijs » Tue Apr 07, 2020 09:09

BertTuyt wrote:
Fri Apr 03, 2020 01:54
Perft is addictive.
With the same processor the Intel Core i7-8700K, and frequency 4.5 GHZ, another test.
This time the perft for the initial position has really improved, others almost the same.
I forgot that I have a switch in my program to disable updating hash etc. when running perft, so I reran the test. At the initial position you are clearly a lot faster, I wonder why because at the Woldouby the performance is roughly even. At the second one with kings magic multiplication really seems to help. I used the latest Intel C++ v19.1 compiler, with LLVM (Clang) and MSVC the results are clearly less. I haven't tried GCC though.

Code: Select all

> perft

    m  m  m  m  m
  m  m  m  m  m
    m  m  m  m  m
  m  m  m  m  m
    -  -  -  -  -
  -  -  -  -  -
    M  M  M  M  M
  M  M  M  M  M
    M  M  M  M  M
  M  M  M  M  M

perft( 1)  nodes            9  time   0.0000  nps  29250000
perft( 2)  nodes           81  time   0.0000  nps  12686747
perft( 3)  nodes          658  time   0.0000  nps 342160000
perft( 4)  nodes         4265  time   0.0000  nps 287279793
perft( 5)  nodes        27117  time   0.0001  nps 271587827
perft( 6)  nodes       167140  time   0.0006  nps 263085119
perft( 7)  nodes      1049442  time   0.0041  nps 257284087
perft( 8)  nodes      6483961  time   0.0247  nps 262965518
perft( 9)  nodes     41022423  time   0.1594  nps 257387396
perft(10)  nodes    258895763  time   0.9703  nps 266814637
perft(11)  nodes   1665861398  time   6.3022  nps 264328567

    -  -  -  -  -
  M  -  -  M  M
    M  -  -  -  -
  -  k  -  -  M
    M  M  M  k  -
  -  -  -  -  M
    K  -  M  -  -
  -  M  -  -  -
    M  M  M  M  -
  M  -  -  -  -

perft( 1)  nodes           14  time   0.0000  nps    812500
perft( 2)  nodes           55  time   0.0000  nps   4931034
perft( 3)  nodes         1168  time   0.0000  nps  60979920
perft( 4)  nodes         5432  time   0.0000  nps 121751724
perft( 5)  nodes        87195  time   0.0002  nps 398430580
perft( 6)  nodes       629010  time   0.0021  nps 296423186
perft( 7)  nodes      9041010  time   0.0210  nps 430770440
perft( 8)  nodes     86724219  time   0.2239  nps 387320903
perft( 9)  nodes   1216917193  time   2.8534  nps 426486880
perft(10)  nodes  13106503411  time  31.0446  nps 422183228

    -  -  -  -  -
  -  -  -  -  -
    -  m  m  m  -
  m  -  m  m  -
    m  -  m  m  M
  m  M  M  -  M
    -  M  M  M  M
  -  M  M  -  -
    -  -  -  -  -
  -  -  -  -  -

perft( 1)  nodes            6  time   0.0000  nps  78000000
perft( 2)  nodes           12  time   0.0000  nps  19500000
perft( 3)  nodes           30  time   0.0000  nps  32500000
perft( 4)  nodes           73  time   0.0000  nps  36500000
perft( 5)  nodes          215  time   0.0000  nps  46583333
perft( 6)  nodes          590  time   0.0000  nps  49166667
perft( 7)  nodes         1944  time   0.0000  nps  63979747
perft( 8)  nodes         6269  time   0.0001  nps  71488596
perft( 9)  nodes        22369  time   0.0003  nps  80866796
perft(10)  nodes        88050  time   0.0009  nps  96668356
perft(11)  nodes       377436  time   0.0034  nps 112355293
perft(12)  nodes      1910989  time   0.0135  nps 141462850
perft(13)  nodes      9872645  time   0.0660  nps 149666992
perft(14)  nodes     58360286  time   0.3386  nps 172332904
perft(15)  nodes    346184885  time   2.0201  nps 171370035
perft(16)  nodes   2272406115  time  11.8539  nps 191701079
perft(17)  nodes  14962263728  time  79.6321  nps 187892361

>

Post Reply