DIRECT BITBOARD MOVEGENERATION

[Gerd Isenberg]

For intels with fast bsr but slower bswap, this approach might be not that bad as I initially thought. Alternatively one can save 5 ops by upper/lower lookups from the very same cacheline to end up with 9 ops per line (file, rank, dia, antidia) and two independent instruction chains until the final lea/and:

Code: Select all

U64 lineAttacks(U64 occ, enumLine line, enumSquare sq) {
   U64 low, high;
   low  = smsk[sq][line].lower & occ;
   high = smsk[sq][line].upper & occ;
   low  = -C64(1) << bsr64(low|1); // ms1b of low (at least bit zero) -> -low
   high = high & -high;            // ls1b of high (if any)
   return smsk[sq][line].maskEx & (2*high+low); // lea option due to add -low
} 

It also looks quite register friendly. 3 regs per line, 6 KByte memory needed for all lines ...

Code: Select all

; rcx - occ
; rdx - pointer to mask structure[sq][line] (not changed)
mov   rax, rcx
and   rcx, [rdx + LOW]
or    rcx, 1
mov   r8, -1
bsr   rcx, rcx
and   rax, [rdx + HIGH]
shl   r8, cl
mov   rcx, rax
neg   rcx
and   rax, rcx
lea   rax, [2*rax + r8]
and   rax, [rdx + MASKEX]

Does it beat Hyperbola or even Magic?

[Desperado]

hi.

the thing i worked out with the less time i have left at the moment.
would be happy again for any idea. if anyone would like to the the
performance, feel free .

Any improvements, explanations what may be wrong here, just
report...thx

Code: Select all

BTB file(const BTB occ,const SQR_ID sq64)
	{
	 //locals
	 BTB fle,lo,hi;

	 //hi: occupancy bits above sq (rnk8 bit is set independent)
	 //lo: occupancy bits below sq (rnk1 bit is set independent)
	 //msk_hi: precalculated bits above sq on file
	 //msk_bit_on_rnkx: corresponding bit for file on rnk x

	 hi = (occ & msk.hi[sq64]) | msk.msk_bit_on_rnk8[sq64];
	 lo = (occ & msk.lo[sq64]) | msk.msk_bit_on_rnk1[sq64];

	 hi &= -hi;									//lsb of bits above sq
	 lo  = BB(bsr64(lo));						//msb of bits below sq

	 fle = (((hi<<1)-lo) & msk.msk_file[sq64]); //connecting bits 

	 return(fle);
	}

[Gerd Isenberg]

Your routine is fine, except three optimizations already posted elsewhere in this thread. "High" don't needs the upper bit set, since you may borrow from hidden 2^64 anyway. Only "low" needs to be at least one in case of empty set, so just or "low" by one.

Code: Select all

BTB file(const BTB occ,const SQR_ID sq64)
{
    //locals
    BTB fle,lo,hi;

    //hi: occupancy bits above sq (may be empty)
    //lo: occupancy bits below sq (at least bit zero)
    //msk_hi: precalculated bits above sq on file
    //msk_bit_on_rnkx: corresponding bit for file on rnk x

    hi = (occ & msk.hi[sq64]);
    lo = (occ & msk.lo[sq64]) | 1;

    hi &= -hi;                           //lsb of bits above sq
    lo  = BB(bsr64(lo));                  //msb of bits below sq

    fle = (((hi<<1)-lo) & msk.msk_file[sq64]); //connecting bits
    return(fle);
}

[Desperado]

of course ! .

20 % faster immediatelly. (about...)

[Gerd Isenberg]

of course ! .

20 % faster immediatelly. (about...)

A possible micro optimization is to use -low = -1 << bsr, for x86 lea-instruction with 2*high+(-low) instead of (high<<1)-low. ) Nine operations. Few registers, independent instruction chains. Your idea has become hot now. Needs a name

[Desperado]

you are making fun !?

[Desperado]

hi.

well, if i am thinking for a name, what do you think about this?

"Significant Bit Solution (SBS)".

So, thank you Gerd for your improvements and explanations.
At the moment i dont know how to get it better.
Maybe the next days (when time is left), i will compare with my magic
bitboard scheme.

[Gerd Isenberg]

hi.

well, if i am thinking for a name, what do you think about this?

"Significant Bit Solution (SBS)".

Sounds a bit frumpy, imho. My proposals:

Hoffmann's Obstructed Difference Action
Desperado's Obstructed Difference
Obstructed Difference

[mcostalba]

Your idea has become hot now. Needs a name

If idea remains hot after speed test vs magic bitboards I would be very glad to try to integrate in Stockfish and test there in real games with a complete chess engine around it.

In any case it is very interesting. The only little issue that I note is the use of bsr64 that is not usable on 32 bit machines, as the one that I have and on which I can test BTW

One of the advantage of magic bitboards is that there exsist a 32 bit friendly version, and this is very important for a candidate general solution to sliding attacks calculation as I think could be this new one.

[xsadar]

hi.

well, if i am thinking for a name, what do you think about this?

"Significant Bit Solution (SBS)".

Sounds a bit frumpy, imho. My proposals:

Hoffmann's Obstructed Difference Action
Desperado's Obstructed Difference
Obstructed Difference

I would vote "Obstruction Difference" (instead of obstructed) or "Hoffman's Obstruction Difference" (omit "action", but we can leave the smiley in the name if you want ).
"Obstructed difference" sounds like it's obstructing the difference somehow, but "obstruction difference" sounds like what it's doing: taking the difference of the obstructions.

By the way, thanks to both of you for working this out. Oddly, just before I read this the other day, I was thinking there had to be a way to generate moves similar to this, but couldn't quite work it out in my head.