Looking for an CPU Instruction or a Function Which Can ...

[JuLieN]

I did not understand the concept "Most significant bit"clearly. Is that a concept in bitboard domain, or programming domain?

This is a general programming notion. Let's consider the following byte:

Code: Select all

[00000000] // The byte with its height bits
 87654321  // their number or name
 
If we set it to   1, it will look like: 00000001
If we set it to   2, it will look like: 00000010
If we set it to   3, it will look like: 00000011
If we set it to   4, it will look like: 00000100
...
If we set it to 128, it will look like: 10000000
If we set it to 129, it will look like: 10000001

As you can see, between the last two examples, setting the 8th bit to 1 was worth adding "128" to the byte, whereas setting also the 1st bit only added "1" to this byte. That's why this 8th bit was the most significant one (or MSB : Most Significant Bit), whereas the 1st one was the least significant one (or LSB): the 8th bit has much more weight than the 1st one.

[lucasart]

Actually, I want to find a way to generate the "controlled squares" bitboard of queen, rook, or bishop.

Ah, now I understand where you're coming from: rotated bitboards. I did implement that from scratch a long time ago, so I know how it should be done. You can do all that with precomputed bitboards, no need for some magical CPU instruction (which doesn't exist).

[Desperado]

Hello Ma Chao,

ok, you are talking of an attack getter function.
What you described for k1 and k2 are the blockers
along a line (and in your case a diagonal).
Because i was very improper yesterday, alone
with the formular 2*k2 - k1 (sorry for that),
which was meant of course as 2*onebit(k2) - onebit(k1),
i will take the time now to describe an algorithm that
may handle your task. ( Describing not with every minor detail,
but enough to understand the ideas at first glance).

so, before i continue some terminologies.

1a:
===

bitboard : 64-bit number
most significant bit : msb (i will use M , your k2)
least significant bit: lsb (i will use L , your k1)
square : i will use S , your k )

1b:
===

The reason why i use "S" and not "piece" is, that you
can compute attacks from any squares you like, doesnt
matter if it is occupied by a piece or not.

msb,lsb are the obstruction squares including real blockers (pieces)
or artificial obstructions.

1c:
===

it is easier to present the 64bit number as bitboard,
to follow what is happening, like...

Code: Select all

00000000 56...63 (63 == h8)
00000000 48...55
00000000 40...47
00000000 32...39
00000000 24...31
00000000 16...23
00000000  8...15
00000000  0...7  ( 0 == a1)

2a:
===

let us say you have a diagaonal occupied like...

Code: Select all

00000001 56...63 (63 == h8)
00000010 48...55
00000000 40...47
00000000 32...39
000S0000 24...31
00000000 16...23
01000000  8...15
10000000  0...7  ( 0 == a1)

00000001 56...63 (63 == h8)
000000M0 48...55
00000000 40...47
00000000 32...39
000S0000 24...31
00000000 16...23
0L000000  8...15
10000000  0...7  ( 0 == a1)

To get M,L by bitscan you first have to get rid
of the outer bits (in this case a1,h8)

How to get L:
--------------

Code: Select all

hiBits&#58; AllBitsSet << x;

xxxxxxxx 56...63 &#40;63 == h8&#41;
xxxxxxxx 48...55
xxxxxxxx 40...47
xxxxxxxx 32...39
000Sxxxx 24...31
00000000 16...23
0L000000  8...15
10000000  0...7  ( 0 == a1&#41;

if you clear the bits marked as x and S, there
wont be a bit anymore set above L, so L becomes
a msb which you can simply compute with reverse
bitscan (bsr)

How to get M:
--------------

Code: Select all

loBits: onebit(x) - 1;

00000001 56...63 (63 == h8)
000000M0 48...55
00000000 40...47
00000000 32...39
000Sxxxx 24...31
xxxxxxxx 16...23
xxxxxxxx  8...15
xxxxxxxx  0...7  ( 0 == a1)

if you clear the bits marked as x and S, there
wont be a bit anymore set below M, so M becomes
a lsb which you can simply compute with forward
bitscan (bsf)

Hint:
-----

Of course you can compute loBits,hiBits on the
fly with the given formulars, but you can also
precompute these masks for each square.
Second, make sure you also exclude S (the square itself)
to get L,M with the described method.


3:
====

Now we have L,M (k1,k2). All we need to do now is to
connect k2 and k1 along a line.
(diagonal,rank,file, doesnt matter )

we have...

Code: Select all

00000000 56...63 (63 == h8)
000000M0 48...55
00000000 40...47
00000000 32...39
00000000 24...31
00000000 16...23
0L000000  8...15
00000000  0...7  ( 0 == a1)

note: S is excluded to connect M,L

    onebit(M) - onebit(L)  does a connection (not including M)
2 * onebit(M) - onebit(L)  does a connection (    including M)

00000000 56...63 (63 == h8)
111111M0 48...55
11111111 40...47
11111111 32...39
11111111 24...31
11111111 16...23
1L000000  8...15
00000000  0...7  ( 0 == a1)

Mask the result with your line (diagonal in your case),
exclude the square itself and it is done.

Code: Select all

00000000 56...63 (63 == h8)
00000010 48...55
00000100 40...47
00001000 32...39
00000000 24...31
00100000 16...23
01000000  8...15
00000000  0...7  ( 0 == a1)

4:
===

So, here just an impression of the complexity
how it can look like finally (using some minor details ... )

Code: Select all

inline ui64_t attackLine(linemask_t *lmsk,ui64_t occ)
{
 ui64_t lo = onebit(bsr64((lmsk->lineLo & occ)|1));
 ui64_t hi = lmsk->lineHi & occ;
 return(lmsk->lineEx & (2*(hi&-hi)-lo));
}

5:
===


The algorithm i described is named Obstruction Difference.
There are some minor details left out, but i think it is enough
to understand the idea.

if you need code you can pm me.

Hope this time i could help

Best,

Michael

[Desperado]

@ Ma Chao

Just an addition,

in the part with "how to get M,L" you may ask why there
arent any bits inbetween (M,S) or (L,S) set. The reason
is, that the first step is to mask the line (your case diagonal)
with the occupancy to get rid of any bits not on the line.
So, i started with the next step so to say, working with the
occupany on the line.

@moderation

I must really say that this 15min time limit to edit a post
is really crap, i am really angry about that.
Writing a longer post having a short break, coming back
and it is done. No chance for correction or any updates.

Michael

[nkg114mc]

Hi Julien:

Thanks a lot for the explanation about "MSB"! I heard about this concept before, but I have never known its name in English until yesterday .

I did not understand the concept "Most significant bit"clearly. Is that a concept in bitboard domain, or programming domain?

This is a general programming notion. Let's consider the following byte:

Code: Select all

[00000000] // The byte with its height bits
 87654321  // their number or name
 
If we set it to   1, it will look like: 00000001
If we set it to   2, it will look like: 00000010
If we set it to   3, it will look like: 00000011
If we set it to   4, it will look like: 00000100
...
If we set it to 128, it will look like: 10000000
If we set it to 129, it will look like: 10000001

As you can see, between the last two examples, setting the 8th bit to 1 was worth adding "128" to the byte, whereas setting also the 1st bit only added "1" to this byte. That's why this 8th bit was the most significant one (or MSB : Most Significant Bit), whereas the 1st one was the least significant one (or LSB): the 8th bit has much more weight than the 1st one.

[nkg114mc]

Hi Michael:

Thanks so much for such a detailed and patient explanation!

I have totally understood why there is a "2 * onebit64(k2) - onebit64(k1)" in your first reply, which is really smart approach I did not realize before ~

I think I would apply your "Obstruction Difference" idea in my engine. Because it is efficient and does not need to build a look-up table .

Anyway, thanks again for your help!