Speed up Move Generation for Mailbox
Moderator: Ras
-
- Posts: 28395
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Speed up Move Generation for Mailbox
But comparing perft is even more meaningless. Because what perft does is very different from what any engine does, much more so than the difference between different engines.
-
- Posts: 915
- Joined: Sun Dec 27, 2020 2:40 am
- Location: Bremen, Germany
- Full name: Thomas Jahn
Re: Speed up Move Generation for Mailbox
I compare nps after a code change to judge the performance impact. And working towards fast and correct perft is a good first milestone when you are starting with a new engine. If you make sure to compare
-
- Posts: 9
- Joined: Mon Jan 11, 2021 11:15 am
- Full name: Roger S.
Re: Speed up Move Generation for Mailbox
Thanks for all the insight. I now have several ideas how to speed up the implementation. Nevertheless I feel that some of the points are tricky to implement.
For those who have done both: What is your impresseion is the quicker and more straight-forward approach? a) improving a mailbox implementation with the tricks mentioned here, or b) rewrite to a bitboard implementation from scratch? (Right now I tend to b) just out of curiosity and the excercise...)
For those who have done both: What is your impresseion is the quicker and more straight-forward approach? a) improving a mailbox implementation with the tricks mentioned here, or b) rewrite to a bitboard implementation from scratch? (Right now I tend to b) just out of curiosity and the excercise...)
-
- Posts: 128
- Joined: Sat Jul 30, 2022 12:12 pm
- Full name: Jamie Whiting
Re: Speed up Move Generation for Mailbox
I have (hopefully) simple sample perft implementations of both mailbox and bitboards: https://github.com/JacquesRW/perftndbd wrote: ↑Wed Jan 04, 2023 4:35 pm Thanks for all the insight. I now have several ideas how to speed up the implementation. Nevertheless I feel that some of the points are tricky to implement.
For those who have done both: What is your impresseion is the quicker and more straight-forward approach? a) improving a mailbox implementation with the tricks mentioned here, or b) rewrite to a bitboard implementation from scratch? (Right now I tend to b) just out of curiosity and the excercise...)
In my opinion, the simplicity of mailbox disappears pretty quickly once you want more performance - you end up holding a lot of (mostly) redundant information that needs to be updated correctly (HGM is the guy to go to for this).
Bitboards are very straightforward once you've got used to them, and in particular with a decent sliding piece attack generator is_legal checks become much cheaper than the equivalent for mailbox.
The basic recipes for move generation with bitboards are:
1. Precalculate arrays of attack bitboards for each piece-type:
This is so you can look up the attacks a specific piece will have indexed by the square it is on, rather than calculating them.
2. Bitboard serialisation:
First to extract attackers from e.g. a rook bitboard, to calculate an attacks bitboard for each piece.
Then again for that attack bitboard to extract the possible target squares and encode them into moves.
Like
Code: Select all
while (bb) {
idx = bitscan_reverse(bb); // gets index of least significant bit
bb &= bb - 1; // clears least significant bit
/* whatever needs to be done here, like gettting attacks or encoding move */
}
For example if you have a white pawn bitboard, you can separate the different pawn cases by
Code: Select all
promotable = pawns & RANK_7_MASK;
/* promotion code */
dbl_pushable = pawns & RANK_2_MASK;
/* double push code */
normal_pawns = pawns & ~(RANK_7_MASK | RANK_2_MASK);
/* normal pawn code */
Code: Select all
captures = attacks & enemies;
/* encode moves with capture flag */
quiets = attacks & empty;
/* encode moves with quiet flag */
-
- Posts: 325
- Joined: Tue Aug 31, 2021 10:32 pm
- Full name: tcusr
Re: Speed up Move Generation for Mailbox
bitboards allow you to write shorter and clearer code that is sufficiently fast pretty easily.ndbd wrote: ↑Wed Jan 04, 2023 4:35 pm Thanks for all the insight. I now have several ideas how to speed up the implementation. Nevertheless I feel that some of the points are tricky to implement.
For those who have done both: What is your impresseion is the quicker and more straight-forward approach? a) improving a mailbox implementation with the tricks mentioned here, or b) rewrite to a bitboard implementation from scratch? (Right now I tend to b) just out of curiosity and the excercise...)
a mailbox implementation needs a lot of adjustments to get to the level that bitboards have by default. i have written a mailbox perft that uses all the known tricks and it resulted in 1k LOC whereas my whole bitboard engine is 1.6K LOC.