Doubled pawns

[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...

[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.

[hgm]

Normally this info would come from your Pawn hash, meaning that speed is irrelevant.

[stegemma]

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.

[stegemma]

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"!

[Gerd Isenberg]

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.

[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

[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)

[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?"

[stegemma]

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?