Speed up Move Generation for Mailbox

Discussion of chess software programming and technical issues.

Moderator: Ras

User avatar
hgm
Posts: 28395
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Speed up Move Generation for Mailbox

Post by hgm »

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.
User avatar
lithander
Posts: 915
Joined: Sun Dec 27, 2020 2:40 am
Location: Bremen, Germany
Full name: Thomas Jahn

Re: Speed up Move Generation for Mailbox

Post by lithander »

hgm wrote: Wed Jan 04, 2023 11:32 am 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.
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 🍎 with 🍏 you can compare perft speeds, too. But those citing the biggest numbers seem often intentionally vague about the tricks they used achieve it. And that's where it becomes meaningless bragging...
Minimal Chess (simple, open source, C#) - Youtube & Github
Leorik (competitive, in active development, C#) - Github & Lichess
ndbd
Posts: 9
Joined: Mon Jan 11, 2021 11:15 am
Full name: Roger S.

Re: Speed up Move Generation for Mailbox

Post by ndbd »

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...)
JacquesRW
Posts: 128
Joined: Sat Jul 30, 2022 12:12 pm
Full name: Jamie Whiting

Re: Speed up Move Generation for Mailbox

Post by JacquesRW »

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...)
I have (hopefully) simple sample perft implementations of both mailbox and bitboards: https://github.com/JacquesRW/perft

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 */
}
3. Splitting more complex things up (to avoid branches, and for simplicity):
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 */
Another useful one is for attacks

Code: Select all

captures = attacks & enemies;
/* encode moves with capture flag */
quiets = attacks & empty;
/* encode moves with quiet flag */
tcusr
Posts: 325
Joined: Tue Aug 31, 2021 10:32 pm
Full name: tcusr

Re: Speed up Move Generation for Mailbox

Post by tcusr »

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...)
bitboards allow you to write shorter and clearer code that is sufficiently fast pretty easily.
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.