Bitboards / move generation on larger boards

[Aleks Peshkov]

std::bitset does not have a way to bitscan (iterate through set bits)

[Rein Halbersma]

std::bitset does not have a way to bitscan (iterate through set bits)

But the Boost extension to dynamic_bitset ( http://www.boost.org/doc/libs/1_38_0/li ... itset.html ) does have both count() and find_first() operations. It would be interesting to see what kind of performance overhead this gives compared to manually creating a struct of 64-bit integers and self-coding the bitwise operations.

[diep]

std::bitset does not have a way to bitscan (iterate through set bits)

But the Boost extension to dynamic_bitset ( http://www.boost.org/doc/libs/1_38_0/li ... itset.html ) does have both count() and find_first() operations. It would be interesting to see what kind of performance overhead this gives compared to manually creating a struct of 64-bit integers and self-coding the bitwise operations.

Compilers also mess up when having functions so many layers down things.

Oh experience learns that most C++ coders soon lose factor 2 just because of using 'nice neat classes'. Compilers are not perfect.

Add to that slowdown of course clumsy forms of doing datastructure that you get when using standard functions from libraries. Another few factors usually it is.

See it like this. To experiment with a fast high nps program, i wrote in (non bitboards) at a k7 a simple proggie, that i can call from Diep. It searches at a single core K7 2.1ghz at roughly 2.5 million nps. That includes everything a chessprogram needs (move ordering, checks in qsearch, hashtables, evaluation and so on, realize how slow RAM is on a K7 MP machine); additional it is datastructure compatible to Diep (as i wanted to call it from diep for tactical verification).

All these bitboard programs, a few top programs excepted, they don't even get 2.5 million nps on a A64 2.2Ghz, which with its cache subsystem and memory controller is far superior to that fast proggie i wrote.

I've yet to find someone who writes in C++, other than Anthony Cozzie (or whatever one of the many 'brothers' of him such as Pradu Kannan, Vasik Rajlich or Marco Costalba), who is capable of getting to that speed.

His framework btw (Zappa, Rybka whatever name you want to make) is far over 3.3 mln nps at A64 2.2ghz.

It just proves that very capable c++ programmers, with a single NCSA/MiT/NASA/Orbital exception, are simply not capable of getting that speed.

That's how complicated things are when using generic code.

In C things already is a lot easier. Like Fortran it is a sequential programming language. More mature than C++ to get a lot of NPS.

C++ hasn't matured, that's one of its major disadvantages. Every few years some new extension gets added to it. The language is not reliable. You dont' have HARD specifications how to cross the border. Note that no one would be able to figure that out anyway, as just getting the ISO of c++ is already $500 or so. Then when you would pay that, next year it is outdated as Bjarne Stroustrup added yet another new total useless feature to the language, which slows the language down and gives new manners of messing up.

In C things are easier.

int a;
unsigned int b;

if( a != b ) { x; } else { y; };

Now you have hard definition when x happens and when y happens and
when it is undefined. In c++ you don't have this very important hard definition of when what is allowed to get done. It is just: "figure it out
yourself whether it works for THIS compiler". Alternatively to that,
get the iso for 500 dollar and be busy 10 years figuring out the entire
enceclopedia of possibilities and exceptions. That is very bad.

Vincent

[wgarvin]

Anthony Cozzie (or whatever one of the many 'brothers' of him such as Pradu Kannan, Vasik Rajlich or Marco Costalba),

Odd... Are you claiming that these are all the same person, or did I just misunderstand?

Maybe by 'brothers' do you mean, 'like-minded people' ?

[Aleks Peshkov]

In C things already is a lot easier.

Yes, they are. But C code is not necessary more manageable and robust. C++ designed for large scale programming, so it is easy to fall in trap to overuse OOP and other modern tricks on simple tasks (like basic chess engine) so program will be difficult to understand. But it will hardly be slower, unless bad low level algorithms and technics are used.

Modern C code is C++ code (minor differences in real code can be and should be refactored for portability reasons).

Bitboards favor modern processors because of lower density of conditional branches and loops. Bitboards can win speed exploiting SSE extensions even if bitboards per se are more computational expensive in basic chess engine tasks.

AFAIK Anthony Cozzie's engine is not of bitboard at all. AFAIK Rybka does use old fashioned rotated bitboards, that even Bob does not use anymore.

[Aleks Peshkov]

std::bitset does not have a way to bitscan (iterate through set bits)

But the Boost extension to dynamic_bitset ( http://www.boost.org/doc/libs/1_38_0/li ... itset.html ) does have both count() and find_first() operations. It would be interesting to see what kind of performance overhead this gives compared to manually creating a struct of 64-bit integers and self-coding the bitwise operations.

Bitboards are foundation of bitboard chess program, it is unreasonable to avoid simple hand written bitboard class with value semantic.

std::bitset implementation should be as fast as hand written special code, but unfortunately it is not designed for extending with low level operations like find_first().

Standard chess engines create many temporary bitboards during calculations, so dynamic_bitset would be much slower, because it order to be dynamic it have to use dynamic memory.

[mcostalba]

I've yet to find someone who writes in C++, other than Anthony Cozzie (or whatever one of the many 'brothers' of him such as Pradu Kannan, Vasik Rajlich or Marco Costalba), who is capable of getting to that speed.

First one disclaimer: People you mention are C++ programmers AND chess engines wizard. I am only a C++ programmer.

Chess engine knwoledge is entirely on the big shoulder of Tord from whom Glaurung I have derived Stockfish.

Apart from that I consider C++ much superior to C if properly used. Problem is that is not so immediate to use at it full throttle as is with C because full throttle of C++ is way higher.

Just to discuss on a real example, please look at movegen.cpp in Stockfish. I have completly rewritten the move generation part of Glaurung using C++ templates. Result is hundreds (yes, hundreds) of code lines removed and faster binary. I have not changed functionality in any part.

Now I am working again on movegen.cpp for the new release of Stockfish and I have already cutted another 50 lines of code and made it faster and simpler using a more aggressive use of templates.

Code is also cleaner and much easier to read (but this is a personal taste).

When I started to look at chess engines advertised as developed with C++ I was impressed by the very very basic level of the C++ used: mainly classes and methods instead of structs and functions.

This is not what C++ can give to you. Object oriented programming is just smart name mangling, nothing more, at least as it is used in chess engines. The only thing of object oriented that is not name mangling is polimorphism but is seldom used because it is not needed in chess engine and has some overhead.

Perhaps I have missed something but I still have to see c++ templates in chess engines and this makes little sense to me: when you have to handle a king, a bishop, a knight, etc.. is a natural choice to use a templetize function that is specialized on the type of piece to work out, it can simplify things enourmusly at no speed penalty cost, indeed the result is easily faster.

I really hope that Stockfish could be a (till now missing) example that can give people some hints on what is possible to do with C++ and NOT with other languages...and the next version it will be also more

Thanks
Marco

[Rein Halbersma]

I've yet to find someone who writes in C++, other than Anthony Cozzie (or whatever one of the many 'brothers' of him such as Pradu Kannan, Vasik Rajlich or Marco Costalba), who is capable of getting to that speed.

Perhaps I have missed something but I still have to see c++ templates in chess engines and this makes little sense to me: when you have to handle a king, a bishop, a knight, etc.. is a natural choice to use a templetize function that is specialized on the type of piece to work out, it can simplify things enourmusly at no speed penalty cost, indeed the result is easily faster.

Marco

This is a very true remark! I am busy programming a draughts engine. There are several variants of draughts (straight checkers, Pool checkers, Russian, international etc. etc.) which differ only on some very specific capture and movement rules. THere is a lot of common code that is most easily factored out with C++ templates combined with non-type template parameters to have specialized code for special variants.