Sliding Piece Algorithm by Abstract Syntax Tree Sifting [RELEASE]

[dangi12012]

Big News: New Minimal Form for Obstruction Difference found!

The core algorithm for Obstruction Difference can be improved by more than 30% runtime!
I found new minimal form for the Obstruction Difference
- so the same input masks but faster:



The very core of the change is this equivalence found by AST sifting:

Code: Select all

        
uint64_t msb = (1ull << 63ull) >> std::countl_zero(lower | 1);  //Extract Highest Set Isolated Bit
uint64_t lsb = upper & -upper;                                                //Extract Lowest Set Isolated Bit
uint64_t oDif = lsb * 2 - msb;
return mask & oDif;

Above is equivalent to below

Code: Select all

const uint64_t msb = 0x8000000000000000ull >> std::countl_zero(lower | 1);
return (mask & (upper ^ (upper - msb))); //Skip LSB and LEA calculation

Proof of improvement:
https://github.com/Gigantua/Chess_Moveg ... onDiff.hpp

It would be great to update the cpw with this information: https://www.chessprogramming.org/Obstruction_Difference

Now I can see that there are Bitboard native algorithms emerging. These are algorithms that would like the source square to be passed into them in the form of (1ull << sq) and not the commonly used [0..64] sq.
The great thing about Bitboard nativity would be that enumerating set bits could skip the source square resultion - and directly pass the current bitmask.
This will improve performance of any bitboard engine that currently works in 0..64 space.

[tcusr]

how did the sifting algorithm come up with the constant?

[mar]

bswap is byte swap, not bit reverse

[dangi12012]

This project is done. All sliding piece algorithms that had an improvement were implemented.
I will keep this tool around and make it public in time if there is enough intereset.

It can optimize any C++ expression into simpler forms if you provide plausible alternative tokens.
It can prove if an expression is optimal with the tokens provided. This was very useful in finding alternative raymask algorithms

Below images show what I mean exactly - (these algorithmic improvements are non trivial and I was suprised how many chess sliding piece algos are very far from the vanilla versions by the respective authors by now). (no more linex, lower and upper are looked up more effieciently etc)

Proof of optimisation
(This is already optimized compared to the vanilla author code)


I improved above to this in 2022 - and proved its the optimal form.


New Algorithms found
The sifting tool also helped me discover a version of the bitrotation algorithm (which in itself is an improvement upon hyperbola qsc) which works with 8 rays instead of 4: https://github.com/Gigantua/Chess_Moveg ... ic8Ray.hpp

Another example
This code:

Code: Select all

(((0x8040201008040201ULL >> LSB(piecesup)) & (0x8040201008040201ULL << MSB(piecesdo))) ^
((0x8102040810204081ULL >> LSB(piecesle)) & (0x8102040810204081ULL << MSB(piecesri))))

and this code:

Code: Select all

(((0x8040201008040201ULL << msb_do) << lsb_up) >> lsb_up) ^ 
(((0x8102040810204081ULL << msb_le) << lsb_ri) >> lsb_ri);

Are equivalent. Same number of instructions - but one constant less. This is also proven to be the shortest form of itself.

So all in all a verygreat success.

[Gerd Isenberg]

Big News: New Minimal Form for Obstruction Difference found!

The core algorithm for Obstruction Difference can be improved by more than 30% runtime!
I found new minimal form for the Obstruction Difference
- so the same input masks but faster:



The very core of the change is this equivalence found by AST sifting:

Code: Select all

        
uint64_t msb = (1ull << 63ull) >> std::countl_zero(lower | 1);  //Extract Highest Set Isolated Bit
uint64_t lsb = upper & -upper;                                                //Extract Lowest Set Isolated Bit
uint64_t oDif = lsb * 2 - msb;
return mask & oDif;

Above is equivalent to below

Code: Select all

const uint64_t msb = 0x8000000000000000ull >> std::countl_zero(lower | 1);
return (mask & (upper ^ (upper - msb))); //Skip LSB and LEA calculation

Proof of improvement:
https://github.com/Gigantua/Chess_Moveg ... onDiff.hpp

It would be great to update the cpw with this information: https://www.chessprogramming.org/Obstruction_Difference

Now I can see that there are Bitboard native algorithms emerging. These are algorithms that would like the source square to be passed into them in the form of (1ull << sq) and not the commonly used [0..64] sq.
The great thing about Bitboard nativity would be that enumerating set bits could skip the source square resultion - and directly pass the current bitmask.
This will improve performance of any bitboard engine that currently works in 0..64 space.

Congrats, nice finding!
CPW Page updated