Typical performance gains for bitboard move generators

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Mpsey

Typical performance gains for bitboard move generators

Post by 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 :D), but there seems to be a bottleneck on move serialization.
brianr
Posts: 536
Joined: Thu Mar 09, 2006 3:01 pm

Re: Typical performance gains for bitboard move generators

Post by 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

Re: Typical performance gains for bitboard move generators

Post by 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.
User avatar
Evert
Posts: 2929
Joined: Sat Jan 22, 2011 12:42 am
Location: NL

Re: Typical performance gains for bitboard move generators

Post by Evert »

Mpsey wrote: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 :D), 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
Posts: 2576
Joined: Wed Mar 10, 2010 10:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic

Re: Typical performance gains for bitboard move generators

Post by 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

Re: Typical performance gains for bitboard move generators

Post by Mpsey »

Evert wrote: 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.
User avatar
hgm
Posts: 27701
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Typical performance gains for bitboard move generators

Post by hgm »

Mpsey wrote: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
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Typical performance gains for bitboard move generators

Post by bob »

Mpsey wrote: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 :D), 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
Posts: 686
Joined: Thu Mar 03, 2011 4:57 pm
Location: Germany

Re: Typical performance gains for bitboard move generators

Post by 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
Posts: 1352
Joined: Wed Mar 08, 2006 10:15 pm
Location: San Francisco, California

Re: Typical performance gains for bitboard move generators

Post by JVMerlino »

bob wrote:
Mpsey wrote: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 :D), 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]