Perft

[Joost Buijs]

And what version of the program is it?

This is the movegenerator I made for v2.0.

Considering the low activity at this forum I have my doubts if it's worthwhile to finish v2.0, on the other hand I already put a lot of time into this project, so it's probably better to try finishing it.

I have to improve my EGDB for Draughts too, currently it's to big because the indexing is not optimal, and I still have to compress it. There are many things that still have to be done, it all takes time.

The point is that Draughts is not the only thing I'm busy with, I'm into Chess too, and I'm still writing data acquisition software for scientific instruments, so the time I can spend on Draughts is limited.

[Krzysztof Grzelak]

This is the movegenerator I made for v2.0.

Considering the low activity at this forum I have my doubts if it's worthwhile to finish v2.0, on the other hand I already put a lot of time into this project, so it's probably better to try finishing it.

I have to improve my EGDB for Draughts too, currently it's to big because the indexing is not optimal, and I still have to compress it. There are many things that still have to be done, it all takes time.

The point is that Draughts is not the only thing I'm busy with, I'm into Chess too, and I'm still writing data acquisition software for scientific instruments, so the time I can spend on Draughts is limited.

I would love to try out the new version of Ares (Ares 2.0) with the latest ending database in the next tournament.

[MichelG]

I just asked openAI codex to optimise the speed. It thought and experimented for 10 minutes, and it increased speed by 11% for the move generator.

Here is the newest perft for dragon, on an intel i9-13900KF, running at 5.4 Ghz. Nps in milions/second.

Code: Select all

    bb  bb  bb  bb  bb
  bb  bb  bb  bb  bb
    bb  bb  bb  bb  bb
  bb  bb  bb  bb  bb
    ..  ..  ..  ..  ..
  ..  ..  ..  ..  ..
    ww  ww  ww  ww  ww
  ww  ww  ww  ww  ww
    ww  ww  ww  ww  ww
  ww  ww  ww  ww  ww
20 20 0

1 9  time: 0.00  nps:0.0
2 81  time: 0.00  nps:0.0
3 658  time: 0.00  nps:0.0
4 4.265  time: 0.00  nps:0.0
5 27.117  time: 0.00  nps:0.0
6 167.140  time: 0.00  nps:0.0
7 1.049.442  time: 0.00  nps:349.8
8 6.483.961  time: 0.02  nps:405.2
9 41.022.423  time: 0.10  nps:406.2
10 258.895.763  time: 0.63  nps:412.9
11 1.665.861.398  time: 3.93  nps:423.6
    ..  ..  ..  ..  ..
  ww  ..  ..  ww  ww
    ww  ..  ..  ..  ..
  ..  BB  ..  ..  ww
    ww  ww  ww  BB  ..
  ..  ..  ..  ..  ww
    WW  ..  ww  ..  ..
  ..  ww  ..  ..  ..
    ww  ww  ww  ww  ..
  ww  ..  ..  ..  ..
17 2 3

1 14  time: 0.00  nps:0.0
2 55  time: 0.00  nps:0.0
3 1.168  time: 0.00  nps:0.0
4 5.432  time: 0.00  nps:0.0
5 87.195  time: 0.00  nps:0.0
6 629.010  time: 0.00  nps:314.5
7 9.041.010  time: 0.03  nps:274.0
8 86.724.219  time: 0.25  nps:344.1
9 1.216.917.193  time: 4.26  nps:285.3
    ..  ..  ..  ..  ..
  ..  ..  ..  ..  ..
    ..  bb  bb  bb  ..
  bb  ..  bb  bb  ..
    bb  ..  bb  bb  ww
  bb  ww  ww  ..  ww
    ..  ww  ww  ww  ww
  ..  ww  ww  ..  ..
    ..  ..  ..  ..  ..
  ..  ..  ..  ..  ..
10 10 0

1 6  time: 0.00  nps:0.0
2 12  time: 0.00  nps:0.0
3 30  time: 0.00  nps:0.0
4 73  time: 0.00  nps:0.0
5 215  time: 0.00  nps:0.0
6 590  time: 0.00  nps:0.0
7 1.944  time: 0.00  nps:0.0
8 6.269  time: 0.00  nps:0.0
9 22.369  time: 0.00  nps:0.0
10 88.050  time: 0.00  nps:88.0
11 377.436  time: 0.00  nps:125.8
12 1.910.989  time: 0.01  nps:173.7
13 9.872.645  time: 0.06  nps:173.2
14 58.360.286  time: 0.31  nps:189.5
15 346.184.885  time: 1.91  nps:181.4
Total time: 11.52

Here is the prompt:

can you start the engine, run the pt command, and store the result to c:\temp\originalPT.txt?

/goal Optimize the move generator

Try to improve that to as low as possible. Only modify the movegenfase.c file. Check the results against the original file. If there is any change in the counts, your modification returned an invalid movelist, and you need to revert back to the previous version.

Keep in a loop trying until you can find no more improvements. At each iteration, report the benchmark time

codex result:
Replaced every bitScan64(x) + 1LL << p sequence with direct low-bit extraction. This removes unnecessary scan/shift work throughout both normal and easy move-generation paths.
pt results:
Original: 12.93 s
Final validation: 11.45 s
Repeats: 11.53 s, 11.44 s, 11.41 s
Improvement: about 11.5%
All three pt position/depth count sequences match the original exactly. Release x64 build succeeds with no warnings. I also tested loop-control simplification and __restrict; neither improved timing, so both were reverted.

[BertTuyt]

Michel, we are entering definitely a new era with Computer Draughts. One day you can (most likely) give a high level prompt like "write a computer draughts program from scratch which beat Kingsrow at a 3-ballot dxp match".
I don't want to put money on this, but if progress continues it could be 2030 - 2035.

But maybe in a few years we will say that was already to pessimistic.

I'm still working on the Damage GUI, also with codex, and did not code a single line (like Gijsbert). It is absolutely magic!
And yes it will make sometime mistakes, or whatever, but I'm sure no one believed that this would be once possible, years ago, when all of us were writing there own GUI.

The question remains what this brings for the future of Computer Draughts. The current running tournament reveals, that the top programs (who all embraced AI-based evaluation) almost never lose, and that final results are basically based upon a few programs at the bottom which were not changed for many years.


Bert

[Joost Buijs]

In my opinion, creating a strong Draughts program depends largely on the dataset you use to train the evaluation function.
If you manage to get AI to generate a dataset for you as well, it might be possible to generate a strong Draughts program using AI.
The rest of the program, such as the move generator and the search engine, generally have less influence on playing strength.

Maybe AI gets so smart that it can generate a perfect set of weights by just looking at the game-parameters, or by grabbing all the data it needs from internet. We'll just have to wait and see.

[MichelG]

I agree with Joost here. 2030 is way to pesimistic.

OpenAI intends to have a automated AI researcher in 2027. Surely it can write a simple draughts-program far before that.

In fact, i think you can do it right now.

What will change is that if you do it now, you may need several days of prompting, and some smart guidance from yourself. (and also some wait time to train the engine ai itself)

In the coming quarters, it will just require less and less prompting and less human guidance.

@Joost: i saw your perft benchmark hitting over 1 billion per second. Do you just count the possible leaves, or do you generate the positions as well? I can't image making my generator a factor 2 faster.

[Joost Buijs]

@Joost: i saw your perft benchmark hitting over 1 billion per second. Do you just count the possible leaves, or do you generate the positions as well? I can't image making my generator a factor 2 faster.

My move generator normally creates a list of moves. For capturing moves, I count the number of moves in the list. With perft, quiet moves (non-captures) at the leaves are not added to a list but are only counted instead.

I use 'magics' to generate king moves. The second position contains kings, which is probably why it runs so fast.

My move generator does more work than strictly necessary for perft; a move generator used solely for perft could probably be made faster. For a full draughts program, this makes little sense; evaluation using a neural network is so slow that the speed of the move generator has very little impact.

[Joost Buijs]

Perft on a GPU can even go faster. This is done with an implementation that dispatches parts of the search-tree to the GPU.

Code: Select all

GPU NVIDIA RTX PRO 4500 Blackwell, 82 multiprocessors, table 16384 MiB, expands 2 plies; table 1024 MiB on the CPU;
Items of depth 5, in levels (64 threads, 4096 MiB), table from depth 2

W:W31-50:B1-20
perft  1                               9       0.172 s                 0.0 Mn/s
perft  2                              81       0.001 s                 0.1 Mn/s
perft  3                             658       0.001 s                 1.0 Mn/s
perft  4                           4,265       0.001 s                 6.1 Mn/s
perft  5                          27,117       0.002 s                16.2 Mn/s
perft  6                         167,140       0.002 s                78.6 Mn/s
perft  7                       1,049,442       0.003 s               408.3 Mn/s
perft  8                       6,483,961       0.004 s              1690.4 Mn/s
perft  9                      41,022,423       0.006 s              6538.3 Mn/s
perft 10                     258,895,763       0.013 s             20421.7 Mn/s
perft 11                   1,665,861,398       0.026 s             63309.2 Mn/s
perft 12                  10,749,771,911       0.069 s            155698.6 Mn/s
perft 13                  70,612,863,532       0.202 s            349922.7 Mn/s
perft 14                 465,829,118,473       0.669 s            695792.9 Mn/s
perft 15               3,120,929,044,364       2.127 s           1466987.4 Mn/s

B:W6,9-11,20-23,30,K31,33,37,41-44,46:BK17,K24
perft  1                              14       0.171 s                 0.0 Mn/s
perft  2                              55       0.003 s                 0.0 Mn/s
perft  3                           1,168       0.002 s                 0.5 Mn/s
perft  4                           5,432       0.003 s                 2.1 Mn/s
perft  5                          87,195       0.004 s                19.7 Mn/s
perft  6                         629,010       0.003 s               209.4 Mn/s
perft  7                       9,041,010       0.004 s              2140.3 Mn/s
perft  8                      86,724,219       0.005 s             16084.2 Mn/s
perft  9                   1,216,917,193       0.010 s            124010.7 Mn/s
perft 10                  13,106,503,411       0.017 s            767705.8 Mn/s
perft 11                 183,848,651,744       0.035 s           5268579.2 Mn/s
perft 12               2,026,297,454,724       0.062 s          32533141.8 Mn/s
perft 13              28,502,670,196,300       0.112 s         255554381.8 Mn/s
perft 14             313,784,387,653,341       0.184 s        1704362514.2 Mn/s
perft 15           4,430,269,571,799,228       0.221 s       20020333509.4 Mn/s
perft 16          48,503,253,678,553,099       0.236 s      205619843648.5 Mn/s
perft 17         687,472,692,301,956,095       1.367 s      502739944492.3 Mn/s
perft 18       7,487,262,800,279,254,994       0.907 s     8250999215570.2 Mn/s

W:W25,27-28,30,32-35,37-38:B12-14,16,18-19,21,23-24,26
perft  1                               6       0.167 s                 0.0 Mn/s
perft  2                              12       0.001 s                 0.0 Mn/s
perft  3                              30       0.001 s                 0.0 Mn/s
perft  4                              73       0.001 s                 0.1 Mn/s
perft  5                             215       0.001 s                 0.2 Mn/s
perft  6                             590       0.002 s                 0.4 Mn/s
perft  7                           1,944       0.002 s                 1.1 Mn/s
perft  8                           6,269       0.002 s                 2.9 Mn/s
perft  9                          22,369       0.003 s                 8.6 Mn/s
perft 10                          88,050       0.004 s                23.3 Mn/s
perft 11                         377,436       0.004 s                92.0 Mn/s
perft 12                       1,910,989       0.005 s               363.2 Mn/s
perft 13                       9,872,645       0.009 s              1138.2 Mn/s
perft 14                      58,360,286       0.017 s              3489.3 Mn/s
perft 15                     346,184,885       0.034 s             10059.7 Mn/s
perft 16                   2,272,406,115       0.092 s             24828.4 Mn/s
perft 17                  14,962,263,728       0.269 s             55578.3 Mn/s
perft 18                 106,965,577,859       0.852 s            125510.1 Mn/s

The current implementation uses 128 bit counters and a 128 bit hash, a perfect hash would be better, but this will take more space. When running the calculation twice with a different hash-function gives the same result, the chance that the result is wrong is almost zero.

The next improvement will be sending the FEN to the GPU and to do all the calculations on the GPU alone, this is way more difficult to get working than the current implementation.

[MichelG]

Interresting idea. I have considered using the GPU , but the round-trip latency holds me back.

I don't understand the table though. Why is perf 18 using less time than 17? And how is mn/s sec computed, even a gpu can not do 10^19 operations per second.

[Joost Buijs]

Latency is a big problem, the GPU is unusable for an evaluation function alone, calculating several plies on the GPU can make the latency less of a problem. A perft-search is very simple though, I don't know if it's possible to put a full fledged search on a GPU.

Half of the GPU memory of 32GB is used as a hash-table, the second position contains kings that start moving around, this creates many transpositions, the counts of whole subtrees can be retrieved from the hash-table, this is why the counts are getting so big. This also explains why the time used for the last iteration is lower than the time used by the previous iteration. My CPU-perft sums the time for all iterations, maybe I have to do the same here too.