Page 1 of 2
Doubled pawns
Posted: Wed May 11, 2016 6:50 pm
by stegemma
Experimenting for the fastest way to find if there is one or more doubled pawns, I've found this simple formula:
Code: Select all
#define BOARD_H_COL 0x0101010101010101ULL
uint64_t boMyDoubled = boMyPawns & ~(boMyPawns * BOARD_H_COL);
This formula just say if there are any doubled pawn (result <>0) but can't say if there are more than one of it.
Any hint, to find how many doubled pawns there are on a bitboard, with few instructions?
PS: detecting passed pawns is more complex...
Re: Doubled pawns
Posted: Wed May 11, 2016 6:54 pm
by Evert
Intersect the pawn bitboard with the forward-span bitboard. For white this can be calculated by multiplying the pawn bitboard with the a2-a7 file, for black I guess dividing by it is better. Otherwise a series of shifts will do, but I don't think you can parallelise those.
Re: Doubled pawns
Posted: Wed May 11, 2016 7:07 pm
by hgm
Normally this info would come from your Pawn hash, meaning that speed is irrelevant.
Re: Doubled pawns
Posted: Wed May 11, 2016 7:09 pm
by stegemma
Evert wrote:Intersect the pawn bitboard with the forward-span bitboard. For white this can be calculated by multiplying the pawn bitboard with the a2-a7 file, for black I guess dividing by it is better. Otherwise a series of shifts will do, but I don't think you can parallelise those.
This looks like what I'm already doing, but I've the lowest bit in h1, so I multiply by the h1-h8 column. I always multiply, because it works even for black.
Re: Doubled pawns
Posted: Wed May 11, 2016 7:12 pm
by stegemma
hgm wrote:Normally this info would come from your Pawn hash, meaning that speed is irrelevant.
Ok, maybe pawn hash will be the next step in my "to do list"!
Re: Doubled pawns
Posted: Wed May 11, 2016 10:13 pm
by Gerd Isenberg
stegemma wrote:Evert wrote:Intersect the pawn bitboard with the forward-span bitboard. For white this can be calculated by multiplying the pawn bitboard with the a2-a7 file, for black I guess dividing by it is better. Otherwise a series of shifts will do, but I don't think you can parallelise those.
This looks like what I'm already doing, but I've the lowest bit in h1, so I multiply by the h1-h8 column. I always multiply, because it works even for black.
Nope, in least significant file mapping, due to file-overflows, multiplication by 0x0101010101010101 with multiple bits per file, i.e. doubled or tripled pawns, is not appropriate for north fill or front span. As already mentioned in your first post
Code: Select all
boMyPawns & ~(boMyPawns * 0x0101010101010101)
is a boolean condition whether there is at least a doubled pawn, but does not neccessarly leave a set of front or back doubled pawns, i.e.:
Code: Select all
0x0000040204020000 * 0x0101010101010101 = 0x0C0C0C0806020000
0x0000040204020000 & ~0x0C0C0C0806020000 = 0x0000000200000000
Kogge-Stone fills and extra shift for the front- or back-spans are neccessary for setwise approaches.
Code: Select all
U64 nortFill(U64 gen) {
gen |= (gen << 8);
gen |= (gen << 16);
gen |= (gen << 32);
return gen;
}
U64 soutFill(U64 gen) {
gen |= (gen >> 8);
gen |= (gen >> 16);
gen |= (gen >> 32);
return gen;
}
nortSpan = nortFill << 8;
soutSpan = soutFill >> 8;
Passers are own pawns not on opponent's pawn front span or opponent's pawn
attack front span.
Re: Doubled pawns
Posted: Thu May 12, 2016 12:06 am
by stegemma
Yes, that's true, but in my engine I only need to know if there is a doubled pawn and possibly how many of them there are. I must multiply the number of doubled pawn by a value, to obtain a penalty. It is not important, to me, to know if the signaled doubled pawn is the north or the south one.
The simplified formula could make my engine playing positions with more than 1 doubled pawn, without the right penalty and that's not good. having a pawn hash (that I haven't right now) could be a better solution, as suggested by Muller.
PS: this gives me an idea: I can use the simplified formula to know if there are any doubled pawn and only if yes then iterates through the rows, to know how many doubled pawns there are, avoiding the test if there are none
Re: Doubled pawns
Posted: Thu May 12, 2016 12:43 am
by stegemma
It is not very efficient but this is what I do now:
Code: Select all
inline int CountDoubled(uint64_t boPawns)
{
int n = 0;
if((boPawns & ~(boPawns * BOARD_H_COL)) != boEmpty)
{
boPawns >>= 8;
uint64_t k = boEmpty;
for(int i = 0; i < 6; i++)
{
k |= (boPawns & BOARD_1_ROW); // accumula i bit dei pedoni sulla prima riga
uint64_t dbl = k & (boPawns >>= 8);
n += bits8[dbl];
}
}
return n;
}
(bits8 contains bits count for the first 256 integers)
Re: Doubled pawns
Posted: Thu May 12, 2016 3:36 am
by AndrewGrant
Here's what I do in my engine.
I'm concerned about about whether or not there is a set of stacked pawns in a file. I am not concerned about whether it is 2 pawns, or 3 pawns, or 4..."
The code looks something like this
wa = whitePawns & FILE_A;
wb = whitePawns & FILE_B;
.....
.....
.....
bh = blackPawns & FILE_H;
eval -= StackedPenaltyFileA * ((wa & (wa-1)) != 0)
eval -= StackedPenaltyFileB * ((wb & (wb-1)) != 0)
.....
.....
.....
eval += StackedPenaltyFileH * ((bh & (bh-1)) != 0)
the ((x & (x-1)) != 0) Is the same as saying, "Is there more than one bit set in x?"
Re: Doubled pawns
Posted: Thu May 12, 2016 8:15 am
by stegemma
AndrewGrant wrote:Here's what I do in my engine.
I'm concerned about about whether or not there is a set of stacked pawns in a file. I am not concerned about whether it is 2 pawns, or 3 pawns, or 4..."
The code looks something like this
wa = whitePawns & FILE_A;
wb = whitePawns & FILE_B;
.....
.....
.....
bh = blackPawns & FILE_H;
eval -= StackedPenaltyFileA * ((wa & (wa-1)) != 0)
eval -= StackedPenaltyFileB * ((wb & (wb-1)) != 0)
.....
.....
.....
eval += StackedPenaltyFileH * ((bh & (bh-1)) != 0)
the ((x & (x-1)) != 0) Is the same as saying, "Is there more than one bit set in x?"
The "-1" idea is interesting; the same is for the penalty differentiated by columns. The only issue is that you can't handle triple doubled pawns, as you say. Maybe can you try to see if adding the simplified formula could give you a little speedup, just prepending all with a single if?