## Doubled pawns

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, Dann Corbit, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

### Doubled pawns

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 & ~&#40;boMyPawns * BOARD_H_COL&#41;;
``````
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...
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

### Re: Doubled pawns

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
Posts: 25391
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

### Re: Doubled pawns

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

stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

### Re: Doubled pawns

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.
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

### Re: Doubled pawns

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"!
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

Gerd Isenberg
Posts: 2220
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

### Re: Doubled pawns

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 & ~&#40;boMyPawns * 0x0101010101010101&#41; ``
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&#40;U64 gen&#41; &#123;
gen |= &#40;gen <<  8&#41;;
gen |= &#40;gen << 16&#41;;
gen |= &#40;gen << 32&#41;;
return gen;
&#125;
U64 soutFill&#40;U64 gen&#41; &#123;
gen |= &#40;gen >>  8&#41;;
gen |= &#40;gen >> 16&#41;;
gen |= &#40;gen >> 32&#41;;
return gen;
&#125;

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
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

### Re: Doubled pawns

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
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

### Re: Doubled pawns

It is not very efficient but this is what I do now:

Code: Select all

``````inline int CountDoubled&#40;uint64_t boPawns&#41;
&#123;
int n = 0;
if&#40;&#40;boPawns & ~&#40;boPawns * BOARD_H_COL&#41;) != boEmpty&#41;
&#123;
boPawns >>= 8;
uint64_t k = boEmpty;
for&#40;int i = 0; i < 6; i++)
&#123;
k |= &#40;boPawns & BOARD_1_ROW&#41;; // accumula i bit dei pedoni sulla prima riga
uint64_t dbl = k & &#40;boPawns >>= 8&#41;;
n += bits8&#91;dbl&#93;;
&#125;
&#125;
return n;
&#125;
``````
(bits8 contains bits count for the first 256 integers)
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

AndrewGrant
Posts: 871
Joined: Tue Apr 19, 2016 4:08 am
Location: U.S.A
Full name: Andrew Grant
Contact:

### Re: Doubled pawns

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
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

### Re: Doubled pawns

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?
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com