Need helps with left-shift for combining integers

[phhnguyen]

I have been working on a large bitboard 90 cells (Xiangqi). I use an array of 3 integers 32 bit to define the bitboard and bellow is my code for left-shift:

Code: Select all

class BB {
    u32 u[3]; // u[0] the least significant

    BB(u32 u0, u32 u1, u32 u2) {
        u[0] = u0;  u[1] = u1; u[2] = u2;
    }

    BB operator << (int n) const { // n in 0...89
        if (n==0) {
            return BB(*this); // copy
        }
        if (n>=64) {
            return BB(0, 0, u[0] << (n - 64));
        }
        if (n>32) {
            auto r = n - 32;
            u32 u2 = (u[0] >> (32-r)) | (u[1] << r);
            u32 u1 = u[0] << r;
            return BB(0, u1, u2);
        }
        if (n==32) { // special case to avoid undefined results for both << 32 and >> 32
            return BB(0, u[0], u[1]);
        }
        u32 u2 = (u[1] >> (32-n)) | (u[2] << n);
        u32 u1 = (u[0] >> (32-n)) | (u[1] << n);
        u32 u0 = u[0] << n;
        return BB(u0, u1, u2);
    }

The code works so far. However IMO it looks so slow since it has many ifs inside.
Can someone help me to improve it or show me some better sources / libraries?
I guess someone may face the same problems with other chess variants or working with compilers without int64 for chess.

[Ed Trice]

I did operator overloading 80-bits wide about 13 years ago.

No noticeable slowdown for shifts, ANDs, ORs etc.

Take a look here:

http://www.stmintz.com/ccc/index.php?id=339425

http://www.stmintz.com/ccc/index.php?id=339425


Maybe something you see will give you ideas.

[Evert]

Bitboards are probably not the most optimal for this type of thing. Moreover, Xiangqi offers little in the way of evaluation speed-up by matching bitpatterns (for pawn structure).

I once did exactly what you do here (3x32 bit integer), I'll have to dig out the code to see if it is very different from yours.

You can have a look at SjaakII, which uses 128 bit integers for boards with more than 64 squares. It relies a lot on the compiler providing things like shifts, but it has a fall-back option. It can be compiled for 32 and 64 bit targets, using GCC and MSVS, so it remains fairly portable.

[Gerd Isenberg]

I would go with 2x64-bits.

[phhnguyen]

Thanks Ed Trice, your shift function looks straightforward to me

[phhnguyen]

Thanks Evert Glebbeek. I have a quick look into your open source SjaakII. It will be very useful for me for the next step when I start using 128 bit integers!

I have been managing to implement as many as possible board representations for Xiangqi, to compare and find out their pros and cons. That is why the representation of an array of 3x32 bit integers is a must (as well as 2x64 bit or 1x128 bit integer). To have fair comparisons, I need to optimise enough important operators and functions.

[hgm]

I don't think bitboards can be competitive for Xiangqi. Rotated bitrays updated through carry propagation ('hyperbola quintessence' O^(O-2R) trick) are probably more efficient. There are no diagonal sliders in XQ (if you do not count the Elephants, and these only interact with a very small subset of the board,which you could treat separately). So you only need two rotations: vertical and horizontal.

Mailbox with view distance would probably run circles around that too, though.

[Rein Halbersma]

For my draughts library, I have written a general C++ class template int_set<N> that is very similar to the C++ std::bitset<N> class template, except that it uses set-like naming of member functions (insert, erase, find; instead of set, reset, test) and that it has a for_each member function that allows efficient loops over all 1 bits using CPU intrinsics to scan for bits. You can also easily initialize it using struct like syntax with the squares that are occupied.

Your shift-code is almost identical to what I use, except that my code works for arbitrary arrays of bitboards (with only a special case for 1 bitboard). This code is also almost identical to what gcc uses for it's std:;bitset<N> class template. I have tested this using the same unit tests that Boost uses for dynamic_bitset.

Example:

Code: Select all

#include <iostream>

int main()
{
    using board = xstd::int_set<96>;
    auto b = board{0, 63, 64, 95};

    std::cout << "Size, max size and capacity: ";
    std::cout << b.size() << ", ";
    std::cout << b.max_size() << ", ";
    std::cout << b.capacity() << "\n";
    std::cout << "Occupied: ";
    b.for_each([&](auto sq) {
        std::cout << sq << ", ";
    });
    std::cout << "\n";
    
    b <<= 2;
    
    std::cout << "Size, max size and capacity: ";
    std::cout << b.size() << ", ";
    std::cout << b.max_size() << ", ";
    std::cout << b.capacity() << "\n";
    std::cout << "Occupied: ";
    b.for_each([&](auto sq) {
        std::cout << sq << ", ";
    });
    std::cout << "\n";
}

You can see it live in action. This code will print out 4 and 3 as the number of pieces on the board before and after the bitwise shift (the piece on square 95 gets shifted off the board). The capacity() member function indicates how many bits are used in the class. It currently uses two 64-bit integers, but I also tested it with three 32-bit integers or one 128-bit integer (inspired by Evert's code).

You can extract all the code above it in a single header file and include it in your code. It's on GitHub and Boost licensed. It does require a very modern C++ compiler however, at least Clang 3.9 or higher (mainly because of a few C++17 compiler features that greatly simplify the code). It's not working on gcc or Visual C++ at the moment.

[Evert]

I don't think bitboards can be competitive for Xiangqi. Rotated bitrays updated through carry propagation ('hyperbola quintessence' O^(O-2R) trick) are probably more efficient. There are no diagonal sliders in XQ (if you do not count the Elephants, and these only interact with a very small subset of the board,which you could treat separately). So you only need two rotations: vertical and horizontal.

Bitboards shine when you can do bulk operations. In regular chess, that means pawn moves and captures. Magic generation of slider moves is also neat, but it requires one or two levels of indirection. If you need to serialise the resulting bitboard into a move list anyway, you might as well use a mailbox step propagation. The same holds for leaper moves, which require a table lookup. Bitboards are also very useful for selective move generation, in that you can simply mask out moves to a part of the board (for instance to trap pieces in one part of the board), but that is easy to do by other means as well. Bitmasks and piecelists give you part of the same functionality anyway.
Table lookups are relatively more expensive for Xiangqi simply because the board is larger and tables take more space (competing for the cache).

So I think you're probably right: the things that bitboards are good for don't really come up, and the memory requirement is more of a burden.

Having said all that, a chess program is of course more than just a move generator, and writing a good search and evaluation function can be done with any underlying board representation. I'd be surprised if a properly written bitboard Xiangqi program is 100s of Elo points worse than the equivalent mailbox program.

[phhnguyen]

I don't think bitboards can be competitive for Xiangqi. Rotated bitrays updated through carry propagation ('hyperbola quintessence' O^(O-2R) trick) are probably more efficient. There are no diagonal sliders in XQ (if you do not count the Elephants, and these only interact with a very small subset of the board,which you could treat separately). So you only need two rotations: vertical and horizontal.

Mailbox with view distance would probably run circles around that too, though.

Yes, you are right if we compare them on some aspects, especially about move generating / making speeds. However, from my experience, bitboard have some advantages for installing chess knowledge - thus which is the best representation actually depends on engines / authors.

I have already some speed data of some board representations. It is for Xiangqi but I think it should be close to chess too (at least computer chess of 10 years ago when chess bitboard has to use an array of integer instead of one 64-bit integers nowadays).

What I use to compare is perft speeds since I focus on move generating and making/taking back speeds in this study.

I have implemented some most popular board representations for Xiangqi:

1) Simple mailbox 90 cells, uses very straightforward code of ifs/switches for move generators (similar to FirstChess)
2) Mailbox of 154 cells: uses some border cells with a cleaner move generator (similar to TSCP)
3) Simple mailbox 90 cells, uses pre-computing moves, stored in some arrays
4) Bitboard: uses an array of 3 x 32-bit integers


The result (it may be not the last one since I have been improving my code):
1 > 2 > 4 > 3

Amazingly, the simple mailbox with straightforward move generator is the fastest when bitboard comes 3rd (with a margin of 30%)

What annoying me is the method 3 - it is significantly slower than others. I thought it should be faster or similar to bitboard which has a lot pre-computing moves too. Not sure why. Does anyone have same experience?