Possibly noob question: It seems everyone is using bitboards combined with look up tables to generate moves.
While I understand that for things like "is this square occupied" bitboards are great, I don't quite see the advantage of using them for move generation.
For example, if I have a rook I can iterate over the squares in each direction until I'm blocked, generating the moves on the fly.
What do I gain from a routine that gives me all legal moves with a few bit operations? I still have to classify & sort the moves, and then iterate over them anyway.
What am I missing?
Advantage of using bitboard lookup tables to generate moves?
Moderators: hgm, Rebel, chrisw
-
- Posts: 2
- Joined: Fri Feb 12, 2021 7:15 pm
- Full name: Hamed Ahmadi
-
- Posts: 1871
- Joined: Sat Nov 25, 2017 2:28 pm
- Location: France
Re: Advantage of using bitboard lookup tables to generate moves?
Rook possible landing square for instance, when using bitboard is just something like
which is really fast. Then you have to "convert" this bitboard of possible landing squares (that is already taking occupancy into account) to a list of move. Something like
maybe also taking a capture flag into account.
Code: Select all
BitBoard landing = rookAttacks[square][_pext_u64(occupancy, MagicBB::rook[square].mask)];
Code: Select all
while (b) v.push_back(makeMove(from,popBit(b)));
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Advantage of using bitboard lookup tables to generate moves?
Perhaps that in evaluation or testing for checks you also often need to answer the question 'is this square attacked?'. And bitboards offer the possibility to generate the attacked squares and select subsets of those 'in bulk', and then detect whether there are any, or efficiently examine them one by one without having to spend time on the non-attacked squares, or squares that do not fit the combination of traits you are looking for.
So you are right that for move generation just scanning a mailbox board until you bump into something in your path, cranking out a move every step of the way, is hard to beat. But answering the question "does his Rook on e8 attack my King on e1?" could require you to run through all squares on the e-file without doing anything with the empty squares you encounter. And is not so efficient, which is why bitboards have a chance to be faster.
Of course when you are smart, you would not have to do such a board scan at all, because your mailbox engine would maintain a 'neighbor table' which allows you to see what the Rook on e8 is looking at in the 'southward' direction by a simple lookup: if(neighbor[E8][S] == E1) {...}. Then the bitboards are suddenly not so fast anymore, in comparison.
So I guess the main advantage is really: everyone does it, it is well known how everyone does it, so you can do it without much thinking. And it is faster than other methods you can come up with without much thinking.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Advantage of using bitboard lookup tables to generate moves?
Welcome back to computer chess!CaptainCheckmate wrote: ↑Mon Feb 15, 2021 4:54 pm Possibly noob question: It seems everyone is using bitboards combined with look up tables to generate moves.
While I understand that for things like "is this square occupied" bitboards are great, I don't quite see the advantage of using them for move generation.
For example, if I have a rook I can iterate over the squares in each direction until I'm blocked, generating the moves on the fly.
What do I gain from a routine that gives me all legal moves with a few bit operations? I still have to classify & sort the moves, and then iterate over them anyway.
What am I missing?
One aspect of bitboards is to apply set-theory efficiently - intersection of move targets with opponent pieces, or with squares not attacked by opponent pawns, etc., i.e. to get an early cutoff. And there are other methods than looking up huge lookup tables by square and occupancy-index, i.e. directon-wise for multiple pieces, as obviously for all pawns, but also with fill-algorithms like kogge-stone for rooks/queen or bishops/queen.