1. perft is an unusual name for a function that performs a node count. It comes from Dr. Hyatt's Cray Blitz chess code (later Crafty) which he called "Performance Test", and, as usual back in those days, the name was truncated for use on a text-based programmatic interface.
2. The term Divide to troubleshoot perft by enumerating the nodes for each of the legal moves is also a bit off-the-mark. There is no "division" operation at all, perhaps a "separation" or a "stratification", but clearly no inverse operation of multiplication.
3. While the "divide" is helpful in tracking down bugs, as I learned with Aart Bik, my own move generator agreed with his perft counts through ply 12, and I was not given any clue where the error could have been cropping up at first when our counts differed at ply 13.
4. Therefore, I offer a new name for perft: Node Count
5. And I offer a new concept: Node Count Plus, which will enumerate the jumps made, as well as the moves that crowned a king. Also, a count of nodes as a function of the move made in the parent position (the "divide") will also be a part of Node Count Plus. This has a few advantages, namely, you can find which area of your code may be going wrong sooner (promoting a checker to a king and performing jumps and multiple jumps are potential areas where you can mess up).
6. Below are my Node Count Plus results through 17 plies for 8x8 checkers. If I put my global counters in the correct areas, these numbers should be able to be verified if you implement your own Node Count Plus functions.
Code: Select all
PERFORMING NODE COUNT THROUGH DEPTH 2
=================================================================
--------------------------------- Node Count Through 2 Plies Completed
|---| w |---| w |---| w |---| w |
--------------------------------- Nodes from move # 1 = 7
| w |---| w |---| w |---| w |---|
--------------------------------- Nodes from move # 2 = 7
|---| w |---| w |---| w |---| |
--------------------------------- Nodes from move # 3 = 7
| |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 7
|---| |---| |---| r |---| |
--------------------------------- Nodes from move # 5 = 7
| r |---| r |---| r |---| |---|
--------------------------------- Nodes from move # 6 = 7
|---| r |---| r |---| r |---| r |
--------------------------------- Nodes from move # 7 = 7
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 49
TOTAL JUMPS = 0
TOTAL CROWNS = 0
TOTAL TIME = 0.0000 seconds
TOTAL SPEED = ?????? nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 3
=================================================================
--------------------------------- Node Count Through 3 Plies Completed
|---| w |---| w |---| w |---| w |
--------------------------------- Nodes from move # 1 = 47
| w |---| w |---| w |---| w |---|
--------------------------------- Nodes from move # 2 = 40
|---| w |---| w |---| w |---| r |
--------------------------------- Nodes from move # 3 = 47
| |---| |---| |---| |---|
--------------------------------- Nodes from move # 4 = 40
|---| |---| |---| |---| |
--------------------------------- Nodes from move # 5 = 40
| r |---| r |---| r |---| |---|
--------------------------------- Nodes from move # 6 = 48
|---| r |---| r |---| r |---| r |
--------------------------------- Nodes from move # 7 = 40
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 302
TOTAL JUMPS = 11
TOTAL CROWNS = 0
TOTAL TIME = 0.0090 seconds
TOTAL SPEED = 33555.5556 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 4
=================================================================
--------------------------------- Node Count Through 4 Plies Completed
|---| w |---| w |---| w |---| w |
--------------------------------- Nodes from move # 1 = 237
| w |---| w |---| w |---| w |---|
--------------------------------- Nodes from move # 2 = 184
|---| w |---| w |---| |---| r |
--------------------------------- Nodes from move # 3 = 244
| |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 175
|---| |---| |---| |---| |
--------------------------------- Nodes from move # 5 = 185
| r |---| r |---| r |---| |---|
--------------------------------- Nodes from move # 6 = 264
|---| r |---| r |---| r |---| r |
--------------------------------- Nodes from move # 7 = 180
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 1469
TOTAL JUMPS = 176
TOTAL CROWNS = 0
TOTAL TIME = 0.0090 seconds
TOTAL SPEED = 163222.2222 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 5
=================================================================
--------------------------------- Node Count Through 5 Plies Completed
|---| w |---| w |---| w |---| w |
--------------------------------- Nodes from move # 1 = 1207
| w |---| w |---| w |---| w |---|
--------------------------------- Nodes from move # 2 = 860
|---| w |---| w |---| |---| r |
--------------------------------- Nodes from move # 3 = 1299
| |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 874
|---| |---| |---| |---| |
--------------------------------- Nodes from move # 5 = 918
| r |---| r |---| r |---| r |---|
--------------------------------- Nodes from move # 6 = 1345
|---| r |---| r |---| r |---| |
--------------------------------- Nodes from move # 7 = 858
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 7361
TOTAL JUMPS = 1047
TOTAL CROWNS = 0
TOTAL TIME = 0.0090 seconds
TOTAL SPEED = 817888.8889 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 6
=================================================================
--------------------------------- Node Count Through 6 Plies Completed
|---| w |---| w |---| w |---| w |
--------------------------------- Nodes from move # 1 = 5979
| w |---| w |---| w |---| |---|
--------------------------------- Nodes from move # 2 = 4289
|---| w |---| w |---| w |---| r |
--------------------------------- Nodes from move # 3 = 6805
| |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 4265
|---| |---| |---| |---| |
--------------------------------- Nodes from move # 5 = 4659
| r |---| r |---| r |---| r |---|
--------------------------------- Nodes from move # 6 = 6638
|---| r |---| r |---| r |---| |
--------------------------------- Nodes from move # 7 = 4133
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 36768
TOTAL JUMPS = 5311
TOTAL CROWNS = 0
TOTAL TIME = 0.0090 seconds
TOTAL SPEED = 4085333.3333 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 7
=================================================================
--------------------------------- Node Count Through 7 Plies Completed
|---| w |---| w |---| w |---| w |
--------------------------------- Nodes from move # 1 = 29936
| w |---| w |---| w |---| r |---|
--------------------------------- Nodes from move # 2 = 20633
|---| w |---| w |---| w |---| |
--------------------------------- Nodes from move # 3 = 33918
| |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 20647
|---| |---| |---| |---| |
--------------------------------- Nodes from move # 5 = 22848
| r |---| r |---| r |---| r |---|
--------------------------------- Nodes from move # 6 = 31825
|---| r |---| r |---| r |---| |
--------------------------------- Nodes from move # 7 = 19933
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 179740
TOTAL JUMPS = 27460
TOTAL CROWNS = 7
TOTAL TIME = 0.0120 seconds
TOTAL SPEED = 14978333.3333 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 8
=================================================================
--------------------------------- Node Count Through 8 Plies Completed
|---| w |---| w |---| |---| w |
--------------------------------- Nodes from move # 1 = 142459
| w |---| w |---| w |---| |---|
--------------------------------- Nodes from move # 2 = 96625
|---| w |---| w |---| w |---| w |
--------------------------------- Nodes from move # 3 = 163687
| |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 94412
|---| |---| |---| |---| |
--------------------------------- Nodes from move # 5 = 108364
| r |---| r |---| r |---| r |---|
--------------------------------- Nodes from move # 6 = 148117
|---| r |---| r |---| r |---| |
--------------------------------- Nodes from move # 7 = 92267
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 845931
TOTAL JUMPS = 139302
TOTAL CROWNS = 4508
TOTAL TIME = 0.0240 seconds
TOTAL SPEED = 35247125.0000 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 9
=================================================================
--------------------------------- Node Count Through 9 Plies Completed
|---| w |---| w |---| |---| w |
--------------------------------- Nodes from move # 1 = 675656
| w |---| w |---| w |---| |---|
--------------------------------- Nodes from move # 2 = 447325
|---| w |---| w |---| w |---| w |
--------------------------------- Nodes from move # 3 = 765098
| |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 440627
|---| |---| |---| r |---| |
--------------------------------- Nodes from move # 5 = 510964
| r |---| r |---| r |---| |---|
--------------------------------- Nodes from move # 6 = 689582
|---| r |---| r |---| r |---| |
--------------------------------- Nodes from move # 7 = 434428
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 3963680
TOTAL JUMPS = 675447
TOTAL CROWNS = 29761
TOTAL TIME = 0.0800 seconds
TOTAL SPEED = 49546000.0000 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 10
=================================================================
--------------------------------- Node Count Through 10 Plies Completed
|---| w |---| w |---| |---| |
--------------------------------- Nodes from move # 1 = 3118206
| w |---| w |---| w |---| w |---|
--------------------------------- Nodes from move # 2 = 2080244
|---| w |---| w |---| w |---| w |
--------------------------------- Nodes from move # 3 = 3517451
| |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 2031291
|---| |---| |---| r |---| |
--------------------------------- Nodes from move # 5 = 2390844
| r |---| r |---| r |---| |---|
--------------------------------- Nodes from move # 6 = 3230010
|---| r |---| r |---| r |---| |
--------------------------------- Nodes from move # 7 = 2023518
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 18391564
TOTAL JUMPS = 3161784
TOTAL CROWNS = 202284
TOTAL TIME = 0.3520 seconds
TOTAL SPEED = 52248761.3636 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 11
=================================================================
--------------------------------- Node Count Through 11 Plies Completed
|---| w |---| w |---| |---| |
--------------------------------- Nodes from move # 1 = 14371912
| w |---| w |---| w |---| w |---|
--------------------------------- Nodes from move # 2 = 9670066
|---| w |---| w |---| w |---| w |
--------------------------------- Nodes from move # 3 = 15994569
| |---| |---| r |---| w |---|
--------------------------------- Nodes from move # 4 = 9484657
|---| |---| |---| |---| |
--------------------------------- Nodes from move # 5 = 11172881
| r |---| r |---| r |---| |---|
--------------------------------- Nodes from move # 6 = 15022000
|---| r |---| r |---| r |---| |
--------------------------------- Nodes from move # 7 = 9526043
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 85242128
TOTAL JUMPS = 14718460
TOTAL CROWNS = 1068135
TOTAL TIME = 1.5770 seconds
TOTAL SPEED = 54053346.8611 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 12
=================================================================
--------------------------------- Node Count Through 12 Plies Completed
|---| w |---| w |---| |---| |
--------------------------------- Nodes from move # 1 = 65293346
| w |---| w |---| w |---| w |---|
--------------------------------- Nodes from move # 2 = 44399643
|---| w |---| w |---| |---| w |
--------------------------------- Nodes from move # 3 = 71631928
| |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 43299654
|---| |---| w |---| |---| |
--------------------------------- Nodes from move # 5 = 51385120
| r |---| r |---| r |---| |---|
--------------------------------- Nodes from move # 6 = 68552639
|---| r |---| r |---| r |---| |
--------------------------------- Nodes from move # 7 = 44061343
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 388623673
TOTAL JUMPS = 68477043
TOTAL CROWNS = 6448217
TOTAL TIME = 7.3940 seconds
TOTAL SPEED = 52559328.2391 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 13
=================================================================
--------------------------------- Node Count Through 13 Plies Completed
|---| w |---| w |---| |---| |
--------------------------------- Nodes from move # 1 = 293934766
| w |---| w |---| w |---| w |---|
--------------------------------- Nodes from move # 2 = 204580824
|---| w |---| w |---| |---| w |
--------------------------------- Nodes from move # 3 = 317851718
| |---| r |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 199259784
|---| |---| |---| |---| |
--------------------------------- Nodes from move # 5 = 235135012
| r |---| r |---| |---| |---|
--------------------------------- Nodes from move # 6 = 311449243
|---| r |---| r |---| r |---| |
--------------------------------- Nodes from move # 7 = 204412283
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 1766623630
TOTAL JUMPS = 313759533
TOTAL CROWNS = 32921395
TOTAL TIME = 33.2910 seconds
TOTAL SPEED = 53066102.8506 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 14
=================================================================
--------------------------------- Node Count Through 14 Plies Completed
|---| w |---| w |---| |---| |
--------------------------------- Nodes from move # 1 = 1318284511
| w |---| w |---| w |---| w |---|
--------------------------------- Nodes from move # 2 = 934225224
|---| w |---| |---| |---| w |
--------------------------------- Nodes from move # 3 = 1402832208
| |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 903585901
|---| w |---| |---| |---| |
--------------------------------- Nodes from move # 5 = 1070222933
| r |---| r |---| |---| |---|
--------------------------------- Nodes from move # 6 = 1410212017
|---| r |---| r |---| r |---| |
--------------------------------- Nodes from move # 7 = 939076705
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 7978439499
TOTAL JUMPS = 1435892324
TOTAL CROWNS = 182093407
TOTAL TIME = 153.3150 seconds
TOTAL SPEED = 52039523.1973 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 15
=================================================================
--------------------------------- Node Count Through 15 Plies Completed
|---| w |---| w |---| |---| |
--------------------------------- Nodes from move # 1 = 5914921314
| w |---| w |---| w |---| w |---|
--------------------------------- Nodes from move # 2 = 4333487203
|---| w |---| |---| |---| w |
--------------------------------- Nodes from move # 3 = 6220146959
| r |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 4138424572
|---| |---| |---| |---| |
--------------------------------- Nodes from move # 5 = 4891673031
| r |---| |---| |---| |---|
--------------------------------- Nodes from move # 6 = 6414826997
|---| r |---| r |---| r |---| |
--------------------------------- Nodes from move # 7 = 4349687099
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 36263167175
TOTAL JUMPS = 6474802088
TOTAL CROWNS = 887488815
TOTAL TIME = 689.1480 seconds
TOTAL SPEED = 52620289.3645 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 16
=================================================================
--------------------------------- Node Count Through 16 Plies Completed
|---| w |---| w |---| |---| |
--------------------------------- Nodes from move # 1 = 26711634542
| w |---| w |---| w |---| |---|
--------------------------------- Nodes from move # 2 = 20029502668
|---| w |---| |---| w |---| w |
--------------------------------- Nodes from move # 3 = 27831786597
| r |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 18976174039
|---| |---| |---| |---| |
--------------------------------- Nodes from move # 5 = 22382389760
| r |---| |---| |---| |---|
--------------------------------- Nodes from move # 6 = 29457144234
|---| r |---| r |---| r |---| |
--------------------------------- Nodes from move # 7 = 20240937588
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 165629569428
TOTAL JUMPS = 29429000365
TOTAL CROWNS = 4549145800
TOTAL TIME = 3177.9670 seconds
TOTAL SPEED = 52118089.7813 nodes/second.
PERFORMING NODE COUNT THROUGH DEPTH 17
=================================================================
--------------------------------- Node Count Through 17 Plies Completed
|---| w |---| w |---| |---| |
--------------------------------- Nodes from move # 1 = 120925169410
| w |---| w |---| w |---| |---|
--------------------------------- Nodes from move # 2 = 93591896792
|---| w |---| |---| w |---| w |
--------------------------------- Nodes from move # 3 = 124820834902
| r |---| |---| |---| w |---|
--------------------------------- Nodes from move # 4 = 87330512852
|---| |---| |---| |---| |
--------------------------------- Nodes from move # 5 = 102759219739
| r |---| |---| r |---| |---|
--------------------------------- Nodes from move # 6 = 134995374812
|---| r |---| r |---| |---| |
--------------------------------- Nodes from move # 7 = 94395802483
| r |---| r |---| r |---| r |---|
---------------------------------
^^ last node generated ^^
TOTAL NODES = 758818810990
TOTAL JUMPS = 133413032453
TOTAL CROWNS = 21781623227
TOTAL TIME = 14334.4870 seconds
TOTAL SPEED = 52936586.4987 nodes/second.
