Question regarding data structures

[OWL]

Hi, I created a draughts engine in Java and for extra speed I want to rewrite it in C++. I just finished the first part of the move generator, but it is slower which is wierd to me.
I store positions as bitboards and moves too, to make/unmake a move I XOR the 2 bitboard arrays together.
In Java I used an Arraylist of arrays to store moves and in C++ I used a vector of a struct.

Code: Select all

struct MOVE
{
    U64 bm;
    U64 bk;
    U64 wm;
    U64 wk;
    int value;
};
std::vector<MOVE> moves;

All the underlying logic is the same, but in Java I get 26000KN/s and in C++ i get 3800KN/s. Is there something clever I can do in C++ to make the move generator faster?


The code for anyone interested

Code: Select all

#include <iostream>
#include <vector>
#include <chrono>

#define U64 unsigned long long
#define contains(bitboard, index) (bitboard & (1LL<<(index))) != 0
#define occupied(pos) pos[0] | pos[1] | pos[2] | pos[3] | 0b1111111111000000000010000000000100000000001000000000010000000000L;

struct MOVE
{
    U64 bm;
    U64 bk;
    U64 wm;
    U64 wk;
    int value;
};

void printBoard(U64* pos){
    U64 occupied = occupied(pos);
    printf("+---+---+---+---+---+---+---+---+---+---+\n");
    printf("|   ");
    int i;
    for(i = 55; i>-1;i--){
        if(!contains(occupied, i)){
            printf("|   |   ");
        }
        if(contains(pos[0], i)){
            printf("| b |   ");
        }
        if(contains(pos[1],i)){
            printf("| B |   ");
        }
        if(contains(pos[2],i)){
            printf("| w |   ");
        }
        if(contains(pos[3],i)){
            printf("| W |   ");
        }
        if(i % 11 == 5){
            printf("\n+---+---+---+---+---+---+---+---+---+---+\n");
        }
        if((i % 11 == 0) & (i != 55)){
            printf("|\n");
            printf("+---+---+---+---+---+---+---+---+---+---+\n");
            if(i!=0){
                printf("|   ");
            }
        }
    }
    printf("\n");
}


void makeMove(U64* pos, MOVE option){
    pos[0] ^= option.bm;
    pos[1] ^= option.bk;
    pos[2] ^= option.wm;
    pos[3] ^= option.wk;
    pos[4] = -pos[4];
}


void slide(U64* pos, std::vector<MOVE> &moves){
    U64 occupied = occupied(pos);
    int color = (int) pos[4];
    if(color == 1){
        // add white sliding moves
        for(int i = 0; i < 49; i++){
            if(contains(pos[2], i)){
                if(!contains(occupied, i+5)){
                    MOVE next = {0, 0, (1LL<<i)+(1LL<<(i+5)), 0, 0};
                    moves.push_back(next);
                }
                if(!contains(occupied, i+6)){
                    MOVE next = {0, 0, (1LL<<i)+(1LL<<(i+6)), 0, 0};
                    moves.push_back(next);
                }
            }
        }
    } else {
        for(int i = 5; i < 54; i++){
            if(contains(pos[0], i)){
                if(!contains(occupied, i-5)){
                    MOVE next = {(1LL<<i)+(1LL<<(i-5)), 0, 0, 0, 0};
                    moves.push_back(next);
                }
                if(!contains(occupied, i-6)){
                    MOVE next = {(1LL<<i)+(1LL<<(i-6)), 0, 0, 0, 0};
                    moves.push_back(next);
                }
            }
        }
    }
}


int perft(U64* pos, int depth){
    if(depth == 0){
        return 1;
    }
    int num = 0;
    std::vector<MOVE> moves;
    slide(pos, moves);

    for(int i = 0; i<moves.size();i++){
        makeMove(pos, moves[i]);
        num += perft(pos, depth - 1);
        makeMove(pos, moves[i]);
    }
    return num;
}


void printMoves(std::vector<MOVE> &moves){
    std::cout<<"Printing moves\n";
    for(int i = 0; i < (int) moves.size();i++){
        std::cout <<"Move "<<i<<": " <<moves[i].bm<<" "<< moves[i].bk<<" "<< moves[i].wm<<" "<< moves[i].wk<<"\n";
    }
}


int main()
{
    U64 bm = 0b0000000000111111111101111111111000000000000000000000000000000000LL;
    U64 bk = 0b0000000000000000000000000000000000000000000000000000000000000000LL;
    U64 wm = 0b0000000000000000000000000000000000000000000111111111101111111111LL;
    U64 wk = 0b0000000000000000000000000000000000000000000000000000000000000000LL;
    U64 pos[5] = {bm, bk, wm, wk, 1};
    printBoard(pos);
    int total;
    for(int i = 1; i<10;i++){
        auto start = std::chrono::steady_clock::now();
        total = perft(pos, i);
        auto end = std::chrono::steady_clock::now();
        int time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
        if(time>0){
            std::cout << "Perft("<< i <<")"<<" N = " << total << " Kn/s: " << total/time << "\n";
        } else {
            std::cout << "Perft("<< i <<")"<<" N = " << total << " Kn/s: 0\n";
        }
    }

    return 0;
}

[Henk]

Doing already all the black magic bitboard operations ?

Better find something clever to prune more nodes.

[Sesse]

!contains() doesn't do what you think it does, due to operator precedence. Don't do macros After that, all of your time is spent in std::vector; use a static array instead, so that you can use the stack instead of all this heap allocation.

[jonkr]

1 : Are you sure you have optimizations on / release mode? (Also I assume you want to compile x64.)
I got 15000 KN/s just using your code, x64 with optimizations on in MS Visual Studio 2019, which seems like too big a difference to be just hardware.

2 : You might want to use a plain array for your moves, but if you use a vector you should reserve a size.
std::vector<MOVE> moves;
moves.reserve(32);
This gives me 46716 KN/s

3 : There are many optimizations that can be done, such as not looping through every square and checking each possible move square individually. It depends on game stage what is most bang for buck. You can check all pieces for each direction by doing a shift on the bitboard of all the pieces of sideToMove (with edge pieces that can't move that direction removed), then & ~occupied, then popping the result destination squares and doing add move.

(Note : I didn't check the code for correctness just ran it as is.)

[Sesse]

With !contains() fixed, vector replaced with an array, and slide set to static (so it can be safely inlined):

Perft(1) N = 9 Kn/s: 0
Perft(2) N = 81 Kn/s: 0
Perft(3) N = 778 Kn/s: 0
Perft(4) N = 7128 Kn/s: 0
Perft(5) N = 69734 Kn/s: 0
Perft(6) N = 650435 Kn/s: 92919
Perft(7) N = 6385430 Kn/s: 112025
Perft(8) N = 59931436 Kn/s: 192705
Perft(9) N = 586567537 Kn/s: 190382

5950X.

[Sesse]

Oh, and going totally crazy with compiler flags and removing the unused “value” field:

Perft(1) N = 9 Kn/s: 0
Perft(2) N = 81 Kn/s: 0
Perft(3) N = 778 Kn/s: 0
Perft(4) N = 7128 Kn/s: 0
Perft(5) N = 69734 Kn/s: 0
Perft(6) N = 650435 Kn/s: 130087
Perft(7) N = 6385430 Kn/s: 172579
Perft(8) N = 59931436 Kn/s: 211026
Perft(9) N = 586567537 Kn/s: 220763

I'm sure you can get much further by doing more all-moves-at-a-time tricks like was suggested here…

[Sesse]

Sorry, will be stopping the silliness now:

Perft(1) N = 9 Kn/s: 6870
Perft(2) N = 81 Kn/s: 72321
Perft(3) N = 778 Kn/s: 102910
Perft(4) N = 7128 Kn/s: 128456
Perft(5) N = 69734 Kn/s: 130163
Perft(6) N = 650435 Kn/s: 128473
Perft(7) N = 6385430 Kn/s: 142481
Perft(8) N = 59931436 Kn/s: 287568
Perft(9) N = 586567537 Kn/s: 282705

[OWL]

Wow that is definitely a lot faster than my implementation, using static arrays and generating all moves at once I get 43000kn/s. Would you mind sharing how you have done it? I would be really interested in studying it.

I used a static array where the first element stores the size of the array so that I can then loop over it without checking if the move is empty. But I think you must have done something more clever, did you achieve this high speed using a stack?

[Sesse]

Like I said, I fixed the contains() macro by putting () around it. After that, it was basically just compiler flags to unroll like crazy.