Just had a funny idea for pseudo-legal bitboard engines.
Most of the move generation time is spent in extracting bits out of bitboards, and pushing them onto a list.
That effort is wasted if an early move causes a cutoff.
Staged move generation deals with this, but is complicated, and sometimes results in redundant work (depending on implementation).
What if instead of the move generator returning a list of moves, it returns a list of pairs of pieces, and possible destinations in a bitboard?
That way, most of the work (extract the bit) is done only if the move is used, and most of the simplicity of single-stage generation is retained, and there is almost no redundant work at all.
Downside is sorting becomes harder (besides selection sort).
What do you think?
Using bitboards to store move lists
Moderators: hgm, Rebel, chrisw
-
- Posts: 793
- Joined: Sun Aug 03, 2014 4:48 am
- Location: London, UK
Using bitboards to store move lists
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: Using bitboards to store move lists
What is the list you mentioned ? Where would it be used for ? Or is it the moves per search direction for a piece ?matthewlai wrote: Most of the move generation time is spent in extracting bits out of bitboards, and pushing them onto a list.
-
- Posts: 793
- Joined: Sun Aug 03, 2014 4:48 am
- Location: London, UK
Re: Using bitboards to store move lists
Normal move generation is like this -Henk wrote:What is the list you mentioned ? Where would it be used for ? Or is it the moves per search direction for a piece ?matthewlai wrote: Most of the move generation time is spent in extracting bits out of bitboards, and pushing them onto a list.
Code: Select all
for each knight:
destinations = knightAttack[knightPos] & (empty | opponentOccupied)
while (destinations != 0) <--- this loop is the most expensive part of move generation
thisDestination = 1 << BSR(destinations)
movelist.add(thisDestination)
destinations ^= thisDestination
for each rook:
...
I'm proposing something like this -
Code: Select all
for each knight:
movelist.add(knightPos, knightAttack[knightPos] & (empty | opponentOccupied))
for each rook:
...
And not actually extract bits out of the bitboards until the moves actually need to be applied.
One move can be extracted at a time, and as soon as one move fails high, rest of the moves don't need to be extracted.
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: Using bitboards to store move lists
Let x-ray moves = all ever possible moves per piece(Location)
At this moment of writing my engine iterates over pre-computed x-ray moves and test if they are valid or not.
Extracting moves out of a bitboard looks costly too for in the worst case you have to repeat that 64 times. There are less x-ray moves per piece
Usings bitboards for checking if a move is valid looks cheap. So at least I can use that if I cache and reuse them too.
At this moment of writing my engine iterates over pre-computed x-ray moves and test if they are valid or not.
Extracting moves out of a bitboard looks costly too for in the worst case you have to repeat that 64 times. There are less x-ray moves per piece
Usings bitboards for checking if a move is valid looks cheap. So at least I can use that if I cache and reuse them too.
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: Using bitboards to store move lists
Don't know if it is faster. Sorting is an expensive operation.
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Using bitboards to store move lists
And how will you sort the moves?
The only way your method can work is without sorting...
Speed improvement is just an O(1). move sorting reduces your branching factor. it's a no brainer…
The only way your method can work is without sorting...
Speed improvement is just an O(1). move sorting reduces your branching factor. it's a no brainer…
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 793
- Joined: Sun Aug 03, 2014 4:48 am
- Location: London, UK
Re: Using bitboards to store move lists
It's the most costly part of bitboard move generation, but it's still very cheap compared to any kind of square iteration.Henk wrote:Let x-ray moves = all ever possible moves per piece(Location)
At this moment of writing my engine iterates over pre-computed x-ray moves and test if they are valid or not.
Extracting moves out of a bitboard looks costly too for in the worst case you have to repeat that 64 times. There are less x-ray moves per piece
Usings bitboards for checking if a move is valid looks cheap. So at least I can use that if I cache and reuse them too.
Almost all processors now support BSR (find the first set bit) in hardware, so it's 1 simple instruction. There is also no branching, which is detrimental to performance of modern deeply pipelined CPUs.
The biggest goals of magic bitboards and rotated bitboards is to eliminate those branching (testing if a square is valid or blocked).
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.
-
- Posts: 793
- Joined: Sun Aug 03, 2014 4:48 am
- Location: London, UK
Re: Using bitboards to store move lists
It is, but see my other reply.Henk wrote:Don't know if it is faster. Sorting is an expensive operation.
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.
-
- Posts: 793
- Joined: Sun Aug 03, 2014 4:48 am
- Location: London, UK
Re: Using bitboards to store move lists
Hash moves, killers, and history moves can be validated by looping through the move list. That's how many engines do it now anyways, and when each entry contains all moves for 1 piece, it will be faster.lucasart wrote:And how will you sort the moves?
The only way your method can work is without sorting...
Speed improvement is just an O(1). move sorting reduces your branching factor. it's a no brainer…
In move generation, it is also possible to do some preliminary sorting without any overhead.
For example, promotions can be separated out from regular pawn moves, and put in front. Captures can also be easily separated out (so each piece will get 2 bitboards instead of just 1).
The only things that can't be told apart are good and bad captures.
But since in most situations, most captures will be bad, it may be efficient enough to use selection sort to take out good captures first, then all remaining captures will be bad. Or maybe all captures can be extracted and sorted then, in which case this portion will still be no slower than before, just not faster (but other parts are faster).
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: Using bitboards to store move lists
if I understood correctly:
staged generator:
generate moves of stage N and put them in a list.
order & iterate the moves
go to stage n+1
your generator
fast generate all the moves and store thme in bitboard
get the move of a stage from bitboard
order & iterate them
go to stage n+1
so you don't do the serialization of the moves in case you don't need them
I don't think it will be faster of a staged move gen.
I don't think it will be easier than a stage move enerator if you serialize the move you need before ordering them
but it's an interesting try.
I solved the difficult of writing a staged movegen writing a full move list generator and then transforming it in a staged one simply using function TEMPLATE.
you can look at the code of you.
staged generator:
generate moves of stage N and put them in a list.
order & iterate the moves
go to stage n+1
your generator
fast generate all the moves and store thme in bitboard
get the move of a stage from bitboard
order & iterate them
go to stage n+1
so you don't do the serialization of the moves in case you don't need them
I don't think it will be faster of a staged move gen.
I don't think it will be easier than a stage move enerator if you serialize the move you need before ordering them
but it's an interesting try.
I solved the difficult of writing a staged movegen writing a full move list generator and then transforming it in a staged one simply using function TEMPLATE.
you can look at the code of you.