Are Bitboards More Intoxicating Than They Are Good?

[Henk]

I mean if you have an alternative solution for move generation giving significant less code but readable/debugable I would prefer that
if performance is comparable. (Nested expressions should be avoided for they are not debugable). Also bitboards only useful for 64 square games.

[mvanthoor]

A real-world example of the above...

Generating pawn moves:

Code: Select all

    pub fn pawns(&self, board: &Board, list: &mut MoveList, mt: MoveType) {
        const UP: i8 = 8;
        const DOWN: i8 = -8;

        // Create shorthand variables.
        let us = board.us();
        let bb_opponent_pieces = board.bb_side[board.opponent()];
        let bb_empty = !board.occupancy();
        let bb_fourth = BB_RANKS[Board::fourth_rank(us)];
        let direction = if us == Sides::WHITE { UP } else { DOWN };
        let rotation_count = (NrOf::SQUARES as i8 + direction) as u32;
        let mut bb_pawns = board.get_pieces(Pieces::PAWN, us);

        // As long as there are pawns, generate moves for each of them.
        while bb_pawns > 0 {
            let from = bits::next(&mut bb_pawns);
            let to = (from as i8 + direction) as usize;
            let mut bb_moves = 0;

            // Generate pawn pushes
            if mt == MoveType::All || mt == MoveType::Quiet {
                let bb_push = BB_SQUARES[to];
                let bb_one_step = bb_push & bb_empty;
                let bb_two_step = bb_one_step.rotate_left(rotation_count) & bb_empty & bb_fourth;
                bb_moves |= bb_one_step | bb_two_step;
            }

            // Generate pawn captures
            if mt == MoveType::All || mt == MoveType::Capture {
                let bb_targets = self.get_pawn_attacks(us, from);
                let bb_captures = bb_targets & bb_opponent_pieces;
                let bb_ep_capture = match board.game_state.en_passant {
                    Some(ep) => bb_targets & BB_SQUARES[ep as usize],
                    None => 0,
                };
                bb_moves |= bb_captures | bb_ep_capture;
            }

            self.add_move(board, Pieces::PAWN, from, bb_moves, list);
        }
    }

And then adding them to the move list:

Code: Select all

    pub fn add_move(
        &self,
        board: &Board,
        piece: Piece,
        from: Square,
        to: Bitboard,
        list: &mut MoveList,
    ) {
        // Shorthand variiables.
        let mut bb_to = to;
        let us = board.us();
        let promotion_rank = Board::promotion_rank(us);
        let is_pawn = piece == Pieces::PAWN;

        // As long as there are still to-squres in bb_to, this piece has moves to add.
        while bb_to > 0 {
            // More shorthand variables
            let to_square = bits::next(&mut bb_to);
            let capture = board.piece_list[to_square];
            let en_passant = match board.game_state.en_passant {
                Some(square) => is_pawn && (square as usize == to_square),
                None => false,
            };
            let promotion = is_pawn && Board::square_on_rank(to_square, promotion_rank);
            let double_step = is_pawn && ((to_square as i8 - from as i8).abs() == 16);
            let castling = (piece == Pieces::KING) && ((to_square as i8 - from as i8).abs() == 2);

            // Gather all data for this move into one 64-bit integer.
            let mut move_data = (piece)
                | from << Shift::FROM_SQ
                | to_square << Shift::TO_SQ
                | capture << Shift::CAPTURE
                | (en_passant as usize) << Shift::EN_PASSANT
                | (double_step as usize) << Shift::DOUBLE_STEP
                | (castling as usize) << Shift::CASTLING;

            // Push the move to the piece list...
            if !promotion {
                move_data |= Pieces::NONE << Shift::PROMOTION;
                list.push(Move::new(move_data));
            } else {
                // ...or push four promotion moves.
                PROMOTION_PIECES.iter().for_each(|piece| {
                    let promotion_piece = *piece << Shift::PROMOTION;
                    list.push(Move::new(move_data | promotion_piece))
                });
            }
        }
    }

I could have consolidated a lot of this code in MUCH longer lines, but that would also make it much less readable, at least to me. Less code is not always better. Simple code is better, especially with current-day compilers. They're able to consolidate the code for you, and even just completely change an entire block of code into something "5", because that is what will always be the result of that block of code. For the reader (which can be the programmer, 3 years later), it doesn't matter that the result is always 5. The sequence of statements make it clear what the programmer is doing, and why. Let the compiler conclude that "5" is always the result. If you, as the programmer, would have put "5" in there and left it at that, three years down the road you'd probably have forgotten what it even means.

[Daniel Anulliero]

Hi mike
Good post anyway , as I'm writing an Isa Bitboard
Well yesterday I did some measure of speed , with the eval this time
With matérial, psqt, mobility, pieces atacks king, bishop pair, castle safety ( compute where the 3 pawns are) and pawns eval : passers , isolated, doubled
When I run 10 millions time the eval() function , I get 20% speed Ip with the bitboard version (12 seconds vs 15 for Isa "array") .
It seems it is a linear speed up because when I run 1 millions time the eval I get 1.2 ans 1.5 second .
Is + 20% is good ? Well .. better than nothing

[hgm]

Sure. But perhaps using some smarter (but more complex) algorithms for the mailbox board would have given you a speedup of 60%...

[Sven]

When comparing the raw speed of two different engines, there may be a lot more to consider than just mailbox vs bitboards. So is everything else really "the same" between Carnivor and Bricabrac? E.g. search features, move ordering, node counting, PST implementation, legality checking, incremental vs. from scratch calculations, data structures, piece encoding, programming style, compiler, compiler options, ...?

Very similar. Except Carnivor was compiled with Turbo C 1.0 and Bricabrac was compiled with MSVC 2019 Community. They both generate moves and put them in a huge stack with begin and end kept in arrays indexed by ply. The biggest difference is Bric is already set up for mp and therefore all data is in a thread structure whereas Carnivor's data is all global arrays. I get what you are saying, 'there are too many variables of which you have no knowledge of so how could you possibly answer the question'. But you also do not add an opinion based on your own experience! But, there are some people that do have opinions based on experience that they can give that might help form a consensus.

Here is my experience. Jumbo started as a pure mailbox engine. Later I added a bitboard implementation. It was a lot of new code but I decided to keep the mailbox code and to maintain two different binaries: Jumbo with mailbox and Jumbo with bitboards, built via #ifdef from exactly the same codebase. Few source files were split into two files for a better readability but most sources were either unaffected or had a very small amount of #ifdef-s related to different board representations.

It was quite some work to get that running, and it also required some abstractions here and there ... but once it worked, I was able to do a real performance comparison. My result was: bitboards were significantly faster, by some 20-40% I think, I don't remember the details anymore... No surprise here of course, that was the expected and desired result. I admit that my mailbox implementation could have been improved a lot. But, same developer and same style, the same would apply to my bitboard code! The difference might be that it could be harder to make a standard (magic) bitboard code slow than to do the same with mailbox code.

One disadvantage of my approach was a bigger maintenance effort whenever I made changes on the lower levels that were related to the board representation. For instance, adding checks in QS required to add move generator code (generate quiet checks) in two versions. Initially I accepted that challenge but later I became lazy and that led to the mailbox version falling behind in strength due to omitting some features that I only implemented for bitboards. That was especially true for a few new eval features. At some point I decided to drop the mailbox support in Jumbo and made it bitboards-only. The goal of getting a realistic performance comparison was reached, with virtually everything from <copy the list from my post above> being identical so only talking about differences that are actually related to board representation.

In your case I could imagine that differences in data structures (global variables vs. threads) may have a significant impact on speed, although that would not explain 25 vs. 10 Mnps ...Perhaps your bitboard impl has still some room for a big speedup?

[hgm]

It is not a matter of 'coding style', i.e. writing more or less efficient code for doing the same thing. It is a matter of using a more or less efficient algorithm.

'Magic bitboard' is basically a fully specified algorithm; do things in any other way and it no longer qualifies as magic bitboard. But it is very easy to make bitboards inefficient in general. E.g. by making the attacks sets by looping over the bits, and setting them one by one. Then you enter the realm of different algorithms, and the performance differences can get as enormous as they can for different mailbox algorithms.

[Sven]

It is not a matter of 'coding style', i.e. writing more or less efficient code for doing the same thing. It is a matter of using a more or less efficient algorithm.

'Magic bitboard' is basically a fully specified algorithm; do things in any other way and it no longer qualifies as magic bitboard. But it is very easy to make bitboards inefficient in general. E.g. by making the attacks sets by looping over the bits, and setting them one by one. Then you enter the realm of different algorithms, and the performance differences can get as enormous as they can for different mailbox algorithms.

I really appreciate your broad experience and your skills in explaining things other people did not know yet ... And you deserve special honor for always contradicting me

Btw I was talking about making "a standard (magic) bitboard code slow", where "making the attacks sets by looping over the bits, and setting them one by one" is as far away as possible from that standard

[hgm]

Sure, but the point I tried to make that it is not easy to affect the speed of a precisely specified algorithm. While there can be an enormous difference in efficiency between different algorithms.

Although I confess that contradicting you has become kind of a habit , I thought it important to point out that you present the comparison between one of the most advanced bitboard methods (calling it 'standard') with a very simplistic mailbox implementation, which might be 5-10 times slower than what could be achieved with state-of-the-art mailbox techniques. Otherwise the unsuspecting reader could have easily concluded that your observation reflected an intrinsic general speed difference between these board representations.

[mvanthoor]

With regard to bitboards, and chess engine programming in general, I think we must also take into account that Mike has a penchant for writing innovative, and experimental code. He has an entire class of bitboards named after him (how cool is that?!) and some other types of bitboards are based off of those.

In chess programming, only the fastest techniques survive. If someone comes up with an awesome way to create a bitboard move generator, and it turns out to be 10% slower than the magic bitboards, nobody is going ot use it.

So I wouldn't even be surprised if Mike's Briacabrac engine uses some sort of experimental type of bitboards never seen before... but probably they're not as fast as a bitboard engine could have been with established techniques.

[mar]

I see beauty in bitboards (assuming 8x8 boards). I believe Evert even used bitboards for larger boards in SjaakII.

the primary reason why I absolutely love bitboards is that you can recompute a lot of things from scratch very quickly without having to drag around some extra state in your board representation and/or do complicated incremental updates in your make/unmake.

another thing that some problems can be computed for multiple pieces at once easily (like attack mask for all pawns) or slider mobility by doing popcount on attack mask; there's a lot more to bitboards and I can only see the elegance