Using bitboards to store move lists

[matthewlai]

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?

[Henk]

Most of the move generation time is spent in extracting bits out of bitboards, and pushing them onto a list.

What is the list you mentioned ? Where would it be used for ? Or is it the moves per search direction for a piece ?

[matthewlai]

Most of the move generation time is spent in extracting bits out of bitboards, and pushing them onto a list.

What is the list you mentioned ? Where would it be used for ? Or is it the moves per search direction for a piece ?

Normal move generation is like this -

Code: Select all

for each knight:
     destinations = knightAttack[knightPos] & (empty | opponentOccupied)
     while &#40;destinations != 0&#41; <--- this loop is the most expensive part of move generation
          thisDestination = 1 << BSR&#40;destinations&#41;
          movelist.add&#40;thisDestination&#41;
          destinations ^= thisDestination

for each rook&#58;
     ...

etc.

I'm proposing something like this -

Code: Select all

for each knight:
     movelist.add(knightPos, knightAttack[knightPos] & (empty | opponentOccupied))

for each rook:
     ...

So that each entry in movelist is a piece, and possible destinations it can move to.

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.

[Henk]

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.

[Henk]

Don't know if it is faster. Sorting is an expensive operation.

[lucasart]

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…

[matthewlai]

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.

It's the most costly part of bitboard move generation, but it's still very cheap compared to any kind of square iteration.

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).

[matthewlai]

Don't know if it is faster. Sorting is an expensive operation.

It is, but see my other reply.

[matthewlai]

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…

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.

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).

[elcabesa]

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.