Advantages of C++11 for Chess?

[syzygy]

std::sort is not that useful, given its performance and the fact that it is probably quicksort underneath, which is optimized for larger sort jobs than you usually have in chess.

Stockfish likes to use it though... in time-critical code for sorting lists having on average about 1 element

And Stockfish is totally fine calling that. Looking at the libstdc++ implementation of std::sort, it uses intro_sort which will check the input size. For 16 elements or less, it will call an optimized version of insertion_sort, and above it, it will do the recursive quick_sort, again terminating each recursion branch with an insertion_sort when the sub-range is less than 16.

But it can't know the length at compile time, so it will have to generate code for all cases.

[Rein Halbersma]

Oh, algorithms! Of course std::sort is useful (although qsort was nearly as good in C). Besides that, I think I use std::rotate to bring a move to the front of the list when I find an improvement to alpha at the root (which could be done with a one-line loop too). That's about it.

Which of the standard algorithms do you find useful in a chess engine? I am genuinely interested, not being sarcastic or anything: Tone is hard to get right when writing in a foreign language.

I tend to use algorithms everywhere. "No raw loops", except if the loop consists of at most 2 statements or an expression with at most two function calls. See this talk by Sean Parent.

List of algorithms from my draughts program: is_permutation, transform, adjacent_find, none_of, all_of, max, min, min_element, accumulate, copy, copy_backward, copy_n, rotate, partition, sort, is_sorted, find, find_if, fill_n, generate_n, equal, lexicographical_compare, swap, swap_ranges.

Some algorithms are not used because containers make things even easier: e.g. using lower_bound() on a sorted std::vector is equivalent to a std::map member function find().

[AlvaroBegue]

Oh, algorithms! Of course std::sort is useful (although qsort was nearly as good in C). Besides that, I think I use std::rotate to bring a move to the front of the list when I find an improvement to alpha at the root (which could be done with a one-line loop too). That's about it.

Which of the standard algorithms do you find useful in a chess engine? I am genuinely interested, not being sarcastic or anything: Tone is hard to get right when writing in a foreign language.

I tend to use algorithms everywhere. "No raw loops", except if the loop consists of at most 2 statements or an expression with at most two function calls. See this talk by Sean Parent.

List of algorithms from my draughts program: is_permutation, transform, adjacent_find, none_of, all_of, max, min, min_element, accumulate, copy, copy_backward, copy_n, rotate, partition, sort, is_sorted, find, find_if, fill_n, generate_n, equal, lexicographical_compare, swap, swap_ranges.

Some algorithms are not used because containers make things even easier: e.g. using lower_bound() on a sorted std::vector is equivalent to a std::map member function find().

I can't get myself to use algorithms where a simple "raw loop" is perfectly clear.

I am curious, what does the main loop of your alpha-beta search look like?

[Rein Halbersma]

But it can't know the length at compile time, so it will have to generate code for all cases.

Sure, it would be slightly better to call an insertion_sort if you know that most of the time the list is < 16 elements. But the extra code of std::sort would not be in the cache if that were the case, and you'd only pay for some well predictable branches.

[Rein Halbersma]

I can't get myself to use algorithms where a simple "raw loop" is perfectly clear.

I am curious, what does the main loop of your alpha-beta search look like?

Most of my algorithms are in the move generator and in my own version of a std::bitset (I maintain a template library for draughts variants on all board sizes and all known rules, so I needed a generic bitboard for any fixed size and allows efficient iteration over bits).

My alpha-beta currently is entirely text-book, I have to admit. I only use a std::generate_n to generate indices for moves that are to be sorted. Looking at the Stockfish search code, it is obviously a daunting product to emulate. Still it is pages and pages long, and to my eyes it screams out for a better abstraction. I haven't any clear answer to it, but I wrote something about it on the draughts forum a few years ago. I still think that those ideas (in short: defining customization hooks where you can plug in enhancements at specific points in the search) should make it easier to maintain the code, and to experiment with it.

Anyway, in C++17, you can use templates + if-constexpr to statically branch on compile-time contants. E.g. here's my copy-make perft routine in just a few lines (both with and without bulk-counting, using a std::accumulate with a lambda that recursively calls the perft again). Overkill, no doubt, but that's me

Code: Select all

template<bool IsBulk, class Successor, class Position>
auto perft&#40;Successor const& successor, Position const& p, int depth&#41;
        -> int64_t
&#123;
        if constexpr&#40;IsBulk&#41; &#123; if &#40;depth == 1&#41; &#123; return successor.count&#40;s&#41;; &#125;
        &#125; else &#123;               if &#40;depth == 0&#41; &#123; return 1;  &#125; &#125;

        auto const moves = successor.generate&#40;s&#41;; // returns a std&#58;&#58;&#58;array
        return std&#58;&#58;accumulate&#40;moves.cbegin&#40;), moves.cend&#40;), int64_t&#123;0&#125;, &#91;&&#93;&#40;auto sum, auto const& m&#41; &#123;
                return sum + perft<IsBulk>&#40;successor, result&#40;p, m&#41;, depth - 1&#41;;
        &#125;);
&#125;

[Rein Halbersma]

An open “external” question to all gurus: instead of mentioned C++11 in this topic, do you consider to use newer standards of C++? Say C++ 14 (I have been using that) or C++ 17? What are pros and cons (of using lower / higher standards) for chess in your views?

C++14 and C++17 didn't add anything that I have found useful so far. Except for maybe binary literals in C++14 (so instead of `0xaa' you can say `0b10101010').

constexpr on mutating function (C++14) and if-constexpr (C++17) are pretty much game changers for me. It allows to do pretty awesome things. Here's e.g. my version of a bitset (I call it int_set): uses compile-time branching on the number of words (<=64 bits, <=128 bits or bigger), and does loop-unrolling for the smaller boards, and calls STL algorithms otherwise.

Without C++17, this code was 1.5X larger (I had to do partial specialization of the classes, and similar code was not adjacent anymore). Without C++14, most of the member function could not be called at compile-time.

Another nice thing in C++17 is that you can have inline variables, living in header files. You can also call a lambda that initializes an static class-member (e.g. an array holding a pre-computed index table) and do everything inside the header file. All that stuff was infinitely harder before.

[phhnguyen]

since their performances are so bad.

This is very strange, can you make an example?

I used to declare the move list (for move generators) as std::vector<Move> moveList(200). I did not notice its performance for a while since move generators take only small proportion of time when searching. However when running pertf (which is mainly based on move generators), my program was always slower than others for several times. It took me a while to figure out using std::vector was the main problem.

I also found out someone have discussed already that issue in this forum (my solution for declaring movelist is very similar):

http://www.talkchess.com/forum/viewtopic.php?t=53820

[phhnguyen]

I am concerned about portability so I have so far avoided C++14 and later.

IMHO, portability of C++ versions is not a big problem nowadays. If someone can download your sources, he can also update easily his compilers. All recent main compilers (such as gcc, visual c++, xcode) have also supported already higher C++ versions (at least C++14).

[Fulvio]

I used to declare the move list (for move generators) as std::vector<Move> moveList(200).

It is important to know the library and choose the right container. The main characteristic of a vector is that it can be expanded and contracted as needed, and obviously if that is not necessary a fixed size std::array will be faster
(the MoveList class of the post you linked is just a wrapper around an array).

[LocutusOfPenguin]

Nguyen Pham:
I'm happy most of you not begin with C++14! So, i would vote for jdart1.

Right now, having alot of problems with Jessie & Rodent3 which using 14 now.
Building it static, or cross compile from Ubuntu nothing working. The only way is to install the sketch gcc6 (jessie still using an old gcc4.9!) or let the users update their images to sketch.

Both ways are hard for them. The first: explain this to a non-linux user, and the second: forget all update system from picochess and start from scratch (with an image based on sketch).

I can download sourcecode, and compile but im not good enough to get it working without big changing the underlying system..but thats only me

picochess dev, Jürgen