1

Context

I'm developing a chess engine of my own, where if anything can be pre-initialized/pre-calculated, should be. This is because speed is the number-1 priority, and every extra second you spend calculating stuff that could've been calculated before-hand, stacks up and ultimately makes you lose a lot of important time that should have been used for things that cannot be pre-calculated, like evaluation.

The main pre-initialized variables are the various Bitboard masks.

  • Diagonals
  • Ranks
  • Files
  • Different square patterns ( center ,edges, light squares, dark squares )
  • Attacks for pieces that can be pre-calculated - Knight, King, Pawns

constepxr is present everywhere.
I have a separate header file that manages all of these. They can be initialized once in the start and then used throughout the program several times.

Question

What I am currently doing is using nested namespaces

Mask.h

 // Bitboard is an alias for uint64_t
 // NB_SQ is the number of squares (64)
 
namespace Mask 
{
    void InitMasks();
    void InitAttacks();

    namespace File
    { // few examples
        constexpr Bitboard FileA = 0x0101010101010101;
        constexpr Bitboard FileB = FileA << 1;
        constexpr Bitboard FileC = FileB << 1;
        constexpr Bitboard FileD = FileC << 1;
        constexpr Bitboard FileE = FileD << 1;
        constexpr Bitboard FileF = FileE << 1;
        ...

        constexpr Bitboard notFileAB = ~(FileA | FileB)
        constexpr Bitboard notFileGF = ~(FileG | FileF)
        extern uint64_t AllFiles[NB_SQ] 
    }
    
    namespace Rank{...}

    namespace Diagonal {...}

    namespace Attack
    {
        extern Bitboard PawnAttacks[NB_SQ];
        extern Bitboard KnightAttacks[NB_SQ];
        ...
    }
    
}

All extern arrays are initialized once using InitMasks() and InitAttacks()

Examples

I can know how many white pawns are on the 7th rank

WhitePawnsBB & Mask::Rank::Rank7

Or If I want to get the file mask of a specific square

Mask::File::AllFiles[SQ]

If I need to get the pre-calculated set of attacks for a knight on any square

Mask::Attack::KnightAttacks[SQ];

But I am really not happy with this, it gets very messy to know which mask can belong where. Moreover, this isn't the purpose of namespaces, Is there a better way I can structure this?

Improve this question
0

1 Answer 1

Reset to default
0

There is still a cost to having precomputed bitmasks in that it fills up cache. Memory is SSSSOOOOOOO SSSSSSSLLLLLOOOOOOOOOWWWWWWWWWWWW by comparison, so it might just turn out to be faster to compute these bitmaps on the fly.

But lets say you've done the due diligence. How about compile-time functions. This allows you to be specific about the logic, and allow the compiler to decide if a precompiled bitmask, or a dynamic calculation is the better way to go.

constexpr uint64_t horse_attack(uint32_t location)
{
    return /*bit twiddles on the constant location*/;
}

If you really want constants though, consider pre-allocated arrays. Yes there is a dereference operation involved, but it does avoid embbeding the bitmasks (potentially many times) in the opcode stream and can be more easily cached.

Extra points if you detect the memory alignment of the cache and force the array to be overaligned at cache boundaries.

uint64_t horse_move[64] = {
    //each mask for each successive location.
};

If you would like to not have to hand calculate the lot of this consider writing a program to generate and list these constants. Its not going to get as bored as you at writing board masks out.

Improve this answer
7
  • Thanks a lot for this answer! Will multiple bitwise operations prove to be faster than pre-calculated bitmasks? I like to read the source code of other chess engines specifically the Stockfish and I find that it has pre-calculated almost everything. At the very least it has a pre-calculated array for individual squares, which is just a single << instruction Commented Nov 11, 2020 at 6:50
  • It will depend very much on the specifics of the machine language, and specific machine you are targeting. As with any optimisation technique you have to produce two alternatives and verify which one is better under what circumstances. Case in point: ByteCode. Interpreted languages are very slow, but being able to know the exact cpu/memory parameters allow for JIT compilation to produce code that executes as fast as and sometimes faster than code from off-line compilation done on a dev machine targeting just the architecture. Commented Nov 11, 2020 at 6:57
  • (From your last point) I previously did the exact same thing, made a simple program that wrote out the piece's attacks of every successive square into a text file so that I could directly initialize the array. But that looked exclusively ugly and I switched to a function that would initialize them one by one. Will it really be faster? Sorry for asking so many questions, it's just that Id like to do the smaller things right Commented Nov 11, 2020 at 7:03
  • My suggestion was to actually write a program to generate the given .h file. Not a text file that still requires some manual adjustments in order to compile. As to faster it does depend. Its unlikely you will get the rules correct off the bat, so it will probably pay off to spend the little extra time to make it compilable from the get go. But no free lunch your going to have to weigh it up based on your own skills, dev environment, and goals. Commented Nov 11, 2020 at 7:17
  • This answer (and comments) is a bit misleading. The compiler will not generate memory load instructions for constexpr variables. The variable is replace with it's value at compile time. All optimizations can be applied with a known value. In the best case it can reduce the entire program to a single constant. constexpr deffinitely is the way to go here, you can't beat it with smart tricks. Commented Nov 19, 2020 at 18:51