Typical performance gains for bitboard move generators

[Mpsey]

Hi all,

I was wondering what are typical performance gains for bitboard-based move generators. I use a standard bitboard representation for the time being and am getting a 24% increase in performance over my non-bitboard chess engine for generation of pseudo-legal moves on my x64 machine.

I am very unhappy with this result as I expected a much larger improvement in performance. I am asking if there are any benchmarks for typical performance gains with each board representation. Am I on the right track? Or is this simply bad.

I would like to mention that for generating raw move bitboards (move-target bitboards) my program is impressively fast (In my opinion ), but there seems to be a bottleneck on move serialization.

[brianr]

I would not expect too much from bitboards when just looking at move generation, which is typically less than 20% of overall search time.

BB's become more valuable when integrated into the engine overall (eval patterns, mobility, attack bitmaps, etc).

NPS or raw speed does not mean as much as acutal performance (ELO improvement) vs various other engines.

[Mpsey]

Thank you for the quick response. I should feel lucky then I suppose. I am in the preliminary stages here. I am interested too in the evaluational benefits of bitboards too.

[Evert]

I use a standard bitboard representation for the time being and am getting a 24% increase in performance over my non-bitboard chess engine for generation of pseudo-legal moves on my x64 machine.

I am very unhappy with this result as I expected a much larger improvement in performance.

You're unhappy with a 24% speedup?!

Maybe it's just me, but I would normally expect much smaller improvements from anything I do...

I am asking if there are any benchmarks for typical performance gains with each board representation.

Performance gain over what? You can ask for raw perft results for different engines, which may tell you something - or not, because it depends a lot on implementation details and in the end doesn't say very much about how the thing will perform in real games.

What is a "standard bitboard representation", by the way?

I would like to mention that for generating raw move bitboards (move-target bitboards) my program is impressively fast (In my opinion ), but there seems to be a bottleneck on move serialization.

Of course generating the move bitboards is fast; it's typically just one or two table lookups per piece, which depending on efficiency and test setup will already be in the cache.

How slow serialisation is depends a lot on how and when you do it. Do you use a hardware bitscan? If not, what alternatives have you tried? Can you defer the serialisation (I think there are ways to do that, but the code may become too ugly to deal with and actually perform worse)? Do you only generate legal evasions when in check?

[smatovic]

iirc my mailbox engine made about 300 Knps and the bitboard version about 1Mnps,
like already said, it depends on how you use the bb in evaluation etc.

--
Srdja

[Mpsey]

How slow serialisation is depends a lot on how and when you do it. Do you use a hardware bitscan? If not, what alternatives have you tried? Can you defer the serialisation (I think there are ways to do that, but the code may become too ugly to deal with and actually perform worse)? Do you only generate legal evasions when in check?

I do NOT use hardware bitscan. Since I have posted the question I have realized this is something that could be improved. I generate pseudo-legal moves planning for all illegal moves to be handled in evaluation.

[hgm]

I do NOT use hardware bitscan.

Then it is sort of amazing that you are faster at all. The old generator must have been not very efficient.

[bob]

Hi all,

I was wondering what are typical performance gains for bitboard-based move generators. I use a standard bitboard representation for the time being and am getting a 24% increase in performance over my non-bitboard chess engine for generation of pseudo-legal moves on my x64 machine.

I am very unhappy with this result as I expected a much larger improvement in performance. I am asking if there are any benchmarks for typical performance gains with each board representation. Am I on the right track? Or is this simply bad.

I would like to mention that for generating raw move bitboards (move-target bitboards) my program is impressively fast (In my opinion ), but there seems to be a bottleneck on move serialization.

You should not expect too much. Move generation is a small part of the total execution time in a fairly mature chess program. Bitboards help elsewhere, such as in evaluation where the "bit parallel" operations can save time, examples include "is this pawn passed?" which can be done in one AND operation, or "can this square ever be attacked by an enemy pawn?" also a one AND operation. The savings add up across the pieces of the engine.

[tpetzke]

As you seem very motivated to speed up your perft times you can change your move generation to a legal one. So on the last ply before the horizon you can just return the number of generated moves and don't have to actually make / unmake them to see if they are legal.

Thomas...

[JVMerlino]

Hi all,

I was wondering what are typical performance gains for bitboard-based move generators. I use a standard bitboard representation for the time being and am getting a 24% increase in performance over my non-bitboard chess engine for generation of pseudo-legal moves on my x64 machine.

I am very unhappy with this result as I expected a much larger improvement in performance. I am asking if there are any benchmarks for typical performance gains with each board representation. Am I on the right track? Or is this simply bad.

I would like to mention that for generating raw move bitboards (move-target bitboards) my program is impressively fast (In my opinion ), but there seems to be a bottleneck on move serialization.

You should not expect too much. Move generation is a small part of the total execution time in a fairly mature chess program. Bitboards help elsewhere, such as in evaluation where the "bit parallel" operations can save time, examples include "is this pawn passed?" which can be done in one AND operation, or "can this square ever be attacked by an enemy pawn?" also a one AND operation. The savings add up across the pieces of the engine.

The one thing that shocked me was that my bitboard version, run in 32-bit, was actually up to 30% slower for perft times compared to my 0x88 version in positions with a full or mostly full board.

I'm sure there's plenty of optimization that could be done, but I wonder if anybody else has ever done a similar test after converting a mailbox engine to bitboards?

jm
[/b]