The fastest perft in the West

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

The fastest perft in the West

Post by Rein Halbersma » Tue Oct 04, 2022 22:07

What's faster than running perft() in a few seconds? Running perft() in zero seconds of course! And I don't mean computing perft() numbers at program startup time, store them into a table and reading them out again. No, I mean computing perft() completely at compiletime.

Code: Select all

#include <dctl.hpp>

using namespace dctl::core;
using namespace dctl::algo;

int main()
{
  static_assert(
    traversal::depth_limited_count<true>( // perft with bulk-counting
      basic_state<
        international,
        basic_board<international>
      >::initial(),                       // the starting position in International Draughts
      7,                                  // depth = 7
      drop_duplicates_gen                 // no duplicate captures
    ) == 1'049'442
  );
}
Thaty's right: a full perft(7) run, completely done at compiletime. Made possible by g++12 with -std=c++20 and -fconstexpr-ops-limit=34359738368 as compiler options. Running this on my Linux dev box:

Code: Select all

rein@rein-virtual-machine:~/projects/dctl/build$ time example/constexpr 

real	0m0,003s
user	0m0,000s
sys	0m0,003s
So a perfect 0.000s runtime perft(7): I'll take and keep that speed crown forever now :-)

What makes this possible? Short answer: g++12 and a machine with at leat 38Gb of RAM and 15 minutes of compilation time. Long answer: a conforming C++20 compiler. In C++20, almost everything is constexpr: all the Standard Library algorithms and some of the containers such as std::string and std::vector. There are some caveats (e.g. you must use a compiletime std::vector within the constexpr computation).

In C++20, you can also use almost the full language at compile time. I simply sprinkled "constexpr" in front of every function and increased the default compiler limit of constexpr operations by 1000X from 1<<25 to 1<<35. Without this limit expansion, only perft(4) works out of the box. But that's it: my regular perft() function works at compile-time and the compiler can count over a million positions.

Why not the full perft(11)? I tried it, and g++ ran out of memory :-( The perft(7) run took 38Gb of RAM, higher depths consumed at least 48Gb (the size of my Linux VM on my 64Gb machine). Perhaps in the near future, compiler technology improves to a state where perft(11) can be comfortably computed. Since g++12 came out in April 2022, I could have done this computation already 6 months ago, but I only realized it this weekend and it worked almost out of the box with very little modification.

Note to other authors: every draughts program can now achieve this, as long as you mark all your own functions constexpr and use a constexpr container to store your generated moves into (C-array, std::array, std::vector or a homegrown datastructure that is constexpr-ified). You might have troubles using other libraries (I had when I used Boost.StaticVector or Boost.SmallVector to store the generated moves).

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

Re: The fastest perft in the West

Post by Joost Buijs » Wed Oct 05, 2022 09:23

Because template meta-programming is Turing complete you can do these things. It's is a nice programming exercise, often these techniques are not very usable in practice though.

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

Re: The fastest perft in the West

Post by Rein Halbersma » Wed Oct 05, 2022 11:57

Joost Buijs wrote:
Wed Oct 05, 2022 09:23
Because template meta-programming is Turing complete you can do these things. It's is a nice programming exercise, often these techniques are not very usable in practice though.
Ah but this is not template-metaprogramming. Just a regular perft() function but called inside a static_assert(), so done at compiletime. This requires no modification of existing code, apart from prefixing all your functions with "constexpr".

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

Re: The fastest perft in the West

Post by Joost Buijs » Wed Oct 05, 2022 12:38

Rein Halbersma wrote:
Wed Oct 05, 2022 11:57
Joost Buijs wrote:
Wed Oct 05, 2022 09:23
Because template meta-programming is Turing complete you can do these things. It's is a nice programming exercise, often these techniques are not very usable in practice though.
Ah but this is not template-metaprogramming. Just a regular perft() function but called inside a static_assert(), so done at compiletime. This requires no modification of existing code, apart from prefixing all your functions with "constexpr".
Aha, I have to admit that I didn't look at the code snippet and blindly assumed you were using TMP. It's truly amazing that the compiler is capable of checking a complex function like perft() with a static assert, I never thought this would be possible. Of course you could do this with TMP as well, but that would mean writing totally different code.

I wonder whether other C++ compilers like CLang and MSVC are also capable of doing this.

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

Re: The fastest perft in the West

Post by Rein Halbersma » Wed Oct 05, 2022 14:11

Joost Buijs wrote:
Wed Oct 05, 2022 12:38
Rein Halbersma wrote:
Wed Oct 05, 2022 11:57
Joost Buijs wrote:
Wed Oct 05, 2022 09:23
Because template meta-programming is Turing complete you can do these things. It's is a nice programming exercise, often these techniques are not very usable in practice though.
Ah but this is not template-metaprogramming. Just a regular perft() function but called inside a static_assert(), so done at compiletime. This requires no modification of existing code, apart from prefixing all your functions with "constexpr".
Aha, I have to admit that I didn't look at the code snippet and blindly assumed you were using TMP. It's truly amazing that the compiler is capable of checking a complex function like perft() with a static assert, I never thought this would be possible. Of course you could do this with TMP as well, but that would mean writing totally different code.
In theory, a TMP program could also do this already with C++98 code. But I doubt any compiler would be able to do perft(7) using TMP. I used to rotate the bit-layout using TMP and I can tell you that even such "minor" operations took an enormous amount of compile time. With constexpr the slow down is about 100x-1000x. With TMP it's a factor of 1M or more.

I started my DCTL project around 2010 and in the early years I indeed had to heavily rely on TMP (the Boost.MPL library in particular). Around 2013 it became clear to me that C++11 constexpr (only one-line non-mutating functions would be greatly expanded in C++14 (then to all non-virtual non-allocating, but mutating functions). I basically went all in on that bet and wrote my constexpr bitset at that time and largely eliminated TMP from my program. C++17 and C++20 have added virtual and allocating code to constexpr and used the expanded constexpr across the entire Standard Library, to the point where all algorithms and sequence containers are constexpr now.
I wonder whether other C++ compilers like CLang and MSVC are also capable of doing this.
https://en.cppreference.com/w/cpp/compi ... y_features

It appears that Clang 15 and MSVC 2022 have constexpr string/vector and will also be able to run perft() in the compiler. I haven't tested it yet because Clang misses some other C++20 features that my program relies on. I think MSVC 2022 will work out of the box for my program.

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

Re: The fastest perft in the West

Post by Joost Buijs » Thu Oct 06, 2022 11:00

In C++20 there is also 'consteval' to declare an immediate function that has to be evaluated at compile-time and always produces a compile-time constant. This is more strict than 'constexpr' which can be used at run-time as well.

The last years C++ is getting extremely complicated, I take my hat off to the people writing parsers and code-generators for it. :)

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

Re: The fastest perft in the West

Post by Rein Halbersma » Wed Jan 04, 2023 23:44

Joost Buijs wrote:
Wed Oct 05, 2022 12:38
Aha, I have to admit that I didn't look at the code snippet and blindly assumed you were using TMP. It's truly amazing that the compiler is capable of checking a complex function like perft() with a static assert, I never thought this would be possible. Of course you could do this with TMP as well, but that would mean writing totally different code.

I wonder whether other C++ compilers like CLang and MSVC are also capable of doing this.
Clang 16 (development version, will be released in April 2023 I think) now also successfully computes perft(7) at compile time. Most likely Visual C++ as well, but I'm too lazy to install the latest edition again (my dev env is Linux).

Post Reply