Architecture for Bitboard Chess Engine

[levykkn]

First of all, I would like to say hello to everyone here. Currently, I am working on my college coursework and have chosen to create a chess engine using C++. I plan to use this engine as a backend for my website, allowing anyone to register and play against it. To achieve this, I intend to implement a modular architecture with object-oriented relationships.
As a newcomer to chess programming, I recently discovered bitboards. I am wondering if anyone can provide guidance on how to structure my project and create appropriate class entities, specifically which class should be responsible for storing pre-calculated attacks, evaluations, moves, hashing, and other related tasks. I have noticed that many chess engines use bitboard representation, but I have yet to see one that uses an object-oriented approach. Additionally, I would appreciate feedback on the appropriateness of my approach. Thank you in advance!

[Steve Maughan]

It's a great project!

There isn't a general approach used by everyone. Chess Programming website it going to be your first port of call for most things:

https://www.chessprogramming.org/Main_Page

Things to think about:

• How are you going to represent the board? As a set of bitboards or also with an array of integers indicating what's on each square? What about the king position — is it worth storing separately?

• Find out about magic move generation of sliding pieces. This will take a little time getting your head around

• Create a generate_moves function (maybe split it into two: generate_moves and generate_evade_check)

• Test the move generation functions by creating a PERFT routine

• Use the UCI protocol — there are others but UCI is solid and quite easy to implement

• Use a piece-square table as a simple evaluation function

• Implement a basic search so the engine actually plays chess

• Implement the quiescent search

• Add the hash table routines

You now have the skeleton of a chess playing engine that probably plays at about 1300 ELO.

Good luck!

Steve

[Mike Sherwin]

• Find out about magic move generation of sliding pieces. This will take a little time getting your head around

The latest test of KGSSB are coming in faster than Magic and even Black Magic fixed shift. This is apparently substantial (+13%) for cpus with less cache as KGSSB uses less memory. KGSSB still needs to be tested on cpus with more cache and running a real world chess engine with a large tt. How KGSSB will perform in a multi threaded engine utilizing all threads compared to magic is also an open question.

[jdart]

Engines don't use an object-oriented approach, in general, because they are optimized for speed. One thing to avoid in particular is any operation that would result in a large number of heap allocations. For example, if you had a std::vector of Move objects, the contents would be on the heap and adding an object would entail the overhead of an allocation.

I would also add, debugging is very, very important. It is better to have a simple engine that is completely correct than a complex one that is full of bugs. Bugs can significantly reduce playing strength, and then it will be hard to progress because you try adding things when the root cause of low strength is bugs in features you already have. perft is a good check on basic correctness, but you should use others, including asserts at key places.

[Carbec]

Hello,
This is two series of videos , they helped me a lot

https://github.com/maksimKorzh/bbc

Good luck
Philippe

[levykkn]

Thank you all for your lovely responses! I find them really helpful. I found a series of video tutorials made by Code Monkey King, so I believe I will stick to that.

[JoAnnP38]

Engines don't use an object-oriented approach, in general, because they are optimized for speed. One thing to avoid in particular is any operation that would result in a large number of heap allocations. For example, if you had a std::vector of Move objects, the contents would be on the heap and adding an object would entail the overhead of an allocation.

Is performance really that different between a C++ application that uses the encapsulation features of class, but not the polymorphism? I am assuming that if there is any performance issue is must be due to the indirect calls that use the v-table for virtual functions. Thinking abstractly with objects is a fine way to keep the application simple and easy to understand (and thus reduce bugs.) Even virtual functions have their uses, even in real-time programming. I'm still in the early stages of my C++ port of Pedantic, but my benchmarks show that using a virtual function for each move type (i.e. normal, en passant, castling, etc) that actually makes the move performs better than using a switch statement and having case specific code.

I am not wanting to start an argument over the virtues of object-oriented programming/design, but I do really want to dig into why using C++ classes for encapsulation (mostly) and not using dynamic memory allocation inside the context of search is less performant than legacy structured programming using C.

[okidoki]

Engines don't use an object-oriented approach, in general, because they are optimized for speed. One thing to avoid in particular is any operation that would result in a large number of heap allocations. For example, if you had a std::vector of Move objects, the contents would be on the heap and adding an object would entail the overhead of an allocation.

Is performance really that different between a C++ application that uses the encapsulation features of class, but not the polymorphism? I am assuming that if there is any performance issue is must be due to the indirect calls that use the v-table for virtual functions. Thinking abstractly with objects is a fine way to keep the application simple and easy to understand (and thus reduce bugs.) Even virtual functions have their uses, even in real-time programming. I'm still in the early stages of my C++ port of Pedantic, but my benchmarks show that using a virtual function for each move type (i.e. normal, en passant, castling, etc) that actually makes the move performs better than using a switch statement and having case specific code.

I am not wanting to start an argument over the virtues of object-oriented programming/design, but I do really want to dig into why using C++ classes for encapsulation (mostly) and not using dynamic memory allocation inside the context of search is less performant than legacy structured programming using C.

Most of the things which appear fast may or may not be fast in real (I learnt this the hard-way). Simple example I had been struggling with was a look-up array vs bitwise operations. In certain larger arrays, bitwise operations out-performed lookup and this was counter intuitive(lookup being O(1)). This was done on my machine which is pretty old and the results may change with newer cpus. Dynamic memory allocation is slow in search since it involves creation of objects this is typically true when the platform manages the memory, typically for .NET, GC has its own overhead for memory allocation.
Just two cents from my side and an experience overall.

Overall, looking stockfish's code is a humbling experience in this context

[JoAnnP38]

Most of the things which appear fast may or may not be fast in real (I learnt this the hard-way). Simple example I had been struggling with was a look-up array vs bitwise operations. In certain larger arrays, bitwise operations out-performed lookup and this was counter intuitive(lookup being O(1)). This was done on my machine which is pretty old and the results may change with newer cpus. Dynamic memory allocation is slow in search since it involves creation of objects this is typically true when the platform manages the memory, typically for .NET, GC has its own overhead for memory allocation.
Just two cents from my side and an experience overall.

Overall, looking stockfish's code is a humbling experience in this context

For GC languages, array access is tricky since the array can be moved around in memory by the GC and most languages that I am familiar with enforce bounds checking on all array accesses. I think the C# optimizer can remove bounds checking if it detects there is no way you can exceed the array bounds, but in general it is a negative for performance. I've seen some programs store all the masks for masking bit when its likely to be faster just performing a shift on a 1 and generate the mask on the fly. The thing that always seems inscrutable to me is whether or not an operation will invalidate a memory cache and blow-up performance. However, the thing I was most wanting to point out is that having a global search() C routine that maintains its state in global variables is probably not any more performant than a Search class that encapsulates that state as long as the search class:
1) Doesn't use virtual methods
2) Doesn't allocate dynamic memory using new/malloc

The search class itself (depending on the size of its state) is probably allocated on the stack or as a global object, so having an encapsulated data type would seem to me to perform as well as a C function as long as you follow the rules.

[jdart]

I am not wanting to start an argument over the virtues of object-oriented programming/design, but I do really want to dig into why using C++ classes for encapsulation (mostly) and not using dynamic memory allocation inside the context of search is less performant than legacy structured programming using C.

Encapsulation is fine. If you are not using virtual functions and only using C++ structs/classes for organization and stack storage of objects, then there should be little to no extra overhead. vTables are not needed/used if there are no virtual functions.