To make software PEXT useful for chess, it needs to be on par with magic multiplication. And I really don't think the above will be.
So, the choice is still between hardware PEXT and Magic.
PEXT Bitboards
Moderators: hgm, Rebel, chrisw
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: PEXT Bitboards
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: PEXT Bitboards
For move generation, I agree,: magic should be faster than software PEXT. But you can also use PDEP / PEXT when computing endgame database indices when there are multiple pieces of one kind, see Ronald's posts. Still a niche use case in chess, but the default for draughts endgames.lucasart wrote:To make software PEXT useful for chess, it needs to be on par with magic multiplication. And I really don't think the above will be.
So, the choice is still between hardware PEXT and Magic.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: PEXT Bitboards
Also for didactic purpose - very nice!Rein Halbersma wrote:For move generation, I agree,: magic should be faster than software PEXT. But you can also use PDEP / PEXT when computing endgame database indices when there are multiple pieces of one kind, see Ronald's posts. Still a niche use case in chess, but the default for draughts endgames.lucasart wrote:To make software PEXT useful for chess, it needs to be on par with magic multiplication. And I really don't think the above will be.
So, the choice is still between hardware PEXT and Magic.
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: PEXT Bitboards
Of course, the main reason for such a routine would be to make your program compatible with older processors.lucasart wrote:To make software PEXT useful for chess, it needs to be on par with magic multiplication. And I really don't think the above will be.
So, the choice is still between hardware PEXT and Magic.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: PEXT Bitboards
My tablebase generator uses pdep/pext only for move/attack generation. It would be interesting to find other uses.Rein Halbersma wrote:For move generation, I agree,: magic should be faster than software PEXT. But you can also use PDEP / PEXT when computing endgame database indices when there are multiple pieces of one kind, see Ronald's posts. Still a niche use case in chess, but the default for draughts endgames.lucasart wrote:To make software PEXT useful for chess, it needs to be on par with magic multiplication. And I really don't think the above will be.
So, the choice is still between hardware PEXT and Magic.
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: PEXT Bitboards
Here's my untested pencil and paper PDEP attempt that loops over the 1-bits to be deposited, computing the number of skipped 0-bits in val (using the SSE 4.2 ctzll intrinsic), and doing the same number of skips over the 1-bits in maskRein Halbersma wrote: For machines without BMI2 but with SSE 4.2, it should be faster to only loop over the bits bits to be extracted, and for each such bit count the number of mask bits behind it (performance is untested, but should be correct at least, hopefully)The corresponding PDEP emulation using popcnt is left as an exercise for the reader (I am not near a machine to test it for the moment, and it's slightly more involved than the PEXT emulation, will post something next week)Code: Select all
uint64 _pext_u64(uint64 val, uint64 mask) { uint64 res = 0; for (uint64 src = val & mask; src; src &= src - 1) { res |= bit[popcnt(((src & -src) - 1) & mask)]; } return res; }
Code: Select all
uint64 _pdep_u64(uint64 val, uint64 mask)
{
uint64 res = 0;
for (int skipped = 0; val && mask; val &= val - 1, mask &= mask - 1)
{
for (int skip = ctzll(val) - skipped, skipped += skip; skip > 0; --skip)
{
mask &= mask - 1;
}
res |= mask & -mask;
}
return res;
}
Last edited by Rein Halbersma on Mon Jul 17, 2017 10:25 pm, edited 1 time in total.
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: PEXT Bitboards
Your indexing formula does not take care of interfering pieces. I know this has other benefits because your index factors per piece type can vary independently, and that the larger index range is almost entirely compressed away in the end result. But in draughts, computing the 4 vs 4 piece databases gives just too much overhead during generation. You can then index eg the black pieces in the usual way, but use PEXT(wp, ~bp) to index the white pieces in the bitboard of squares not occupied by black pieces. Similarly using PDEP when de-indexing (placing pieces on the board).
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: PEXT Bitboards
The indexing function used during generation indeed does not take care of interfering pieces or of mutiple pieces of the same kind. The indexing function for the compressed format does both, at least in most cases.Rein Halbersma wrote:Your indexing formula does not take care of interfering pieces.
The pdep/pext instructions might indeed be useful for converting a not-so-dumb index into a bitboard of occupied squares during generation.
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: PEXT Bitboards
You didn't understand my point.jwes wrote:Of course, the main reason for such a routine would be to make your program compatible with older processors.lucasart wrote:To make software PEXT useful for chess, it needs to be on par with magic multiplication. And I really don't think the above will be.
So, the choice is still between hardware PEXT and Magic.
PEXT is used in chess engines as a replacement for magic mask/multiply/shift operation. What it does is map the (masked) occupancy into an index of N bits, where N=popcnt(mask).
But software PEXT is useless, unless it's as fast (or faster) than magics. On PEXT processors, of course, you should use hardware PEXT (the fastest, faster than magics). But on PEXTless processors, you still should use magics, because they are faster than software PEXT.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: PEXT Bitboards
It's a choice of how to spend your time. I would rather make my program stronger on newer processers while doing the minimum necessary to make it run on older processors. I went from rotated bitmaps to PEXT and have no desire to implement magic bitmaps.lucasart wrote:You didn't understand my point.jwes wrote:Of course, the main reason for such a routine would be to make your program compatible with older processors.lucasart wrote:To make software PEXT useful for chess, it needs to be on par with magic multiplication. And I really don't think the above will be.
So, the choice is still between hardware PEXT and Magic.
PEXT is used in chess engines as a replacement for magic mask/multiply/shift operation. What it does is map the (masked) occupancy into an index of N bits, where N=popcnt(mask).
But software PEXT is useless, unless it's as fast (or faster) than magics. On PEXT processors, of course, you should use hardware PEXT (the fastest, faster than magics). But on PEXTless processors, you still should use magics, because they are faster than software PEXT.