I did some magic bitboard "science" and mostly learned not to worry about it

Discussion of chess software programming and technical issues.

Moderator: Ras

dangi12012
Posts: 1062
Joined: Tue Apr 28, 2020 10:03 pm
Full name: Daniel Infuehr

Re: I did some magic bitboard "science" and mostly learned not to worry about it

Post by dangi12012 »

hgm wrote: Mon Dec 13, 2021 4:12 pm Executing functions from a table does not qualify as branchless. In indirect jump or call virtually guarantees a mispredict, as it would be very hard to predict what function will be chosen for calling.
It would be one jumptable vs a big chain of if else etc.
It wouldnt contain "If castling" "If enpassant" "If taking" because the baked lambda knows everything.

So one jump vs a monolithic block of code with many branches.
Also the coolest part: move sorting can be done on the IDs themselves since you pick them beforehand.

Looping 8x is better than looping N times.
But whats best is when there is no loop anymore and the compiler has already emitted the correct code.
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
User avatar
hgm
Posts: 28353
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: I did some magic bitboard "science" and mostly learned not to worry about it

Post by hgm »

The usual way to do this is with an 'if(special)', which encompasses all the if(castling), if(promotion), if(ep). The latter moves are so rare that this outer branch is virtually always predicted correctly, and the other tests are never made. Note that castling rights do not exist in the root during most of the game, (often the entire game, when castling happened in book), while the game phase determines a very large preference for either promotion or e.p. capture. So usually you don't even have an extra mispredict when you enter the 'special' code branch.

The worst problem is actually Pawn double pushes. These create e.p. rights as a 'non-standard' extra modification of the game state. These are not that uncommon. And to determine whether the e.p. square has to be set is not trivial (you have to test for enemy pawns adjacent to the to-square), so it probably doesn't pay to always execute the code and make the resulting operation a dummy in moves that are not double-pushes.

Of course you could pack the e.p. square in the move, and unconditionally copy it from there. But that would merely displace the problem to move generation. Which in general is a bad idea, because then you are doing it for all moves, while many moves would never reach the MakeMove stage because of beta cutoffs.

OTOH, some 95% of all moves an engine makes are captures, and the double-pushes are only a minor fraction of the other 5%.

With the sorting I suppose you think of sorting the captures, by assigning indexes in MVV/LVA order. (For Non-captures there is usually no relation between the sort key and the move.)