## Fastest pawn quiet move generation I was able to come with

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

### Fastest pawn quiet move generation I was able to come with

Sure someone can improve this, but I think is really fast.

Code: Select all

``````b = bitboard of pawns
increment = 8 or 16

uint8_t cas;
uint8_t casd;
switch &#40;popcount&#40;b&#41;) &#123;
case 8&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 7&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 6&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 5&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 4&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 3&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 2&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 1&#58;
cas = lsb&#40;b&#41;;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 0&#58;
return ml;
default&#58; //> 8 pawns for strange games or positions
altremovpeo2 &#58;
if &#40;b == 0&#41;
return ml;
cas = lsb&#40;b&#41;;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
b &= b - 1;
goto altremovpeo2;
&#125;``````

mkchan
Posts: 83
Joined: Thu Oct 06, 2016 7:17 pm
Location: India
Contact:

### Re: Fastest pawn quiet move generation I was able to come wi

Could do for brevity:

Code: Select all

``````case 8&#58;
case 7&#58;
case 6&#58;
...
case 2&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 1&#58;
...
``````

elcabesa
Posts: 806
Joined: Sun May 23, 2010 11:32 am
Contact:

### Re: Fastest pawn quiet move generation I was able to come wi

cdani wrote:Sure someone can improve this, but I think is really fast.

Code: Select all

``````b = bitboard of pawns
increment = 8 or 16
...
``````
you unrolled the loop, how much faster it's respect to the original loop?
And the most important question, how much elo you gained agaisnt a more readable loop?

Kotlov
Posts: 208
Joined: Fri Jul 10, 2015 7:23 pm
Location: Russia

### Re: Fastest pawn quiet move generation I was able to come wi

"switch - case" is slow construction

mar
Posts: 1986
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

### Re: Fastest pawn quiet move generation I was able to come wi

cdani wrote:Sure someone can improve this, but I think is really fast.
Well, a Duff machine
But where do you check that the squares in front of the pawns are empty?

Code: Select all

``````pawns & shift_backward&#40;~occupied&#41;
``````
What was the performance gain versus a loop? (and overall speed gain?)

hgm
Posts: 23454
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

### Re: Fastest pawn quiet move generation I was able to come wi

Rather than incrementing ml all the time, you could have stored the moves in the opposite order, and hard-code the offset w.r.t. the inintial ml:

Code: Select all

``````switch&#40;&#40;p = popcount&#40;b&#41;)) &#123;
case 8&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml&#91;7&#93;.moviment = MakeMove&#40;cas, casd&#41;;
case 7&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml&#91;6&#93;.moviment = MakeMove&#40;cas, casd&#41;;
...
case 0&#58;
return ml += p;
``````
It is questionable whether an optimizer could do that from your code.

syzygy
Posts: 4446
Joined: Tue Feb 28, 2012 10:56 pm

### Re: Fastest pawn quiet move generation I was able to come wi

hgm wrote:It is questionable whether an optimizer could do that from your code.
The optimizer will certainly not generate code that stores moves in the opposite order.

mar
Posts: 1986
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

### Re: Fastest pawn quiet move generation I was able to come wi

hgm wrote:Rather than incrementing ml all the time, you could have stored the moves in the opposite order, and hard-code the offset w.r.t. the inintial ml:

Code: Select all

``````switch&#40;&#40;p = popcount&#40;b&#41;)) &#123;
case 8&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml&#91;7&#93;.moviment = MakeMove&#40;cas, casd&#41;;
case 7&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml&#91;6&#93;.moviment = MakeMove&#40;cas, casd&#41;;
...
case 0&#58;
return ml += p;
``````
It is questionable whether an optimizer could do that from your code.
Hmm, I liked your original suggestion:

Code: Select all

``````ml += &#40;p = popcount&#40;b&#41;);
switch&#40;p&#41; &#123;
case 8&#58;
....
ml&#91;-8&#93;.m = ...;
...
case 0&#58;
return ml;
&#125;
``````

cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

### Re: Fastest pawn quiet move generation I was able to come wi

mkchan wrote:Could do for brevity:

Code: Select all

``````case 8&#58;
case 7&#58;
case 6&#58;
...
case 2&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 1&#58;
...
``````
This does not work, as the idea is that case 8 executes the code in case 8 + code in case 7 + code in case 6..., and is not doing this with your code.

Kotlov wrote:"switch - case" is slow construction
Yes, but with jump tables is quite fast.

Code: Select all

``````	switch &#40;popcount&#40;b&#41;) &#123;
000000013FC0826B  movzx       ecx,al
000000013FC0826E  cmp         ecx,8
000000013FC08271  ja          peons_moviments_quiets_o_sense_peoalpas+13Bh &#40;013FC0839Bh&#41;
000000013FC08277  mov         eax,ecx
000000013FC08279  lea         rcx,&#91;__rg_language &#40;013FBF0000h&#41;&#93;
000000013FC08280  mov         r9d,dword ptr &#91;rcx+rax*4+183C8h&#93;
000000013FC0828B  jmp         r9
``````
mar wrote: But where do you check that the squares in front of the pawns are empty?

Code: Select all

``````pawns & shift_backward&#40;~occupied&#41;
``````
Yes, b variable has only pawns that can advance.
elcabesa wrote: you unrolled the loop, how much faster it's respect to the original loop?
And the most important question, how much elo you gained agaisnt a more readable loop?
mar wrote: What was the performance gain versus a loop? (and overall speed gain?)
Of course minimal, something like 1100000 n/s to 1100500 n/s to give an idea. Is more for fun than for anything other, and also is interesting to share and to have other ideas. Any elo gain is due to accumulating a few of those things.
hgm wrote:Rather than incrementing ml all the time, you could have stored the moves in the opposite order, and hard-code the offset w.r.t. the inintial ml:
mar wrote: Hmm, I liked your original suggestion:
Nice one! I will try, sure is even better! Thanks.

syzygy
Posts: 4446
Joined: Tue Feb 28, 2012 10:56 pm

### Re: Fastest pawn quiet move generation I was able to come wi

mar wrote:Hmm, I liked your original suggestion:

Code: Select all

``````ml += &#40;p = popcount&#40;b&#41;);
switch&#40;p&#41; &#123;
case 8&#58;
....
ml&#91;-8&#93;.m = ...;
...
case 0&#58;
return ml;
&#125;
``````
OK, that is something the optimizer probably could do, in theory.