Firstbit() function in Chess using bitboard
Author
Hi,
I am designing a 3D chess in C.
During the evaluation I am using a function which is usually call "Firstbit"
this function return the first square of a given bitboard.
My problem is that I implemented a function but which is very slow because I scan the bitboard until I do not find a piece.
.ie
int First_bit(BitBoard *first_bit_bitboard, MASK_Struct &MASK)
{
int board_square=A1;
BitBoard logic_result;
logic_result=MASK.mask[board_square]&(*first_bit_bitboard);
while((logic_result==0) && (board_square <= H8))
{
board_square++;
logic_result=MASK.mask[board_square]&(*first_bit_bitboard);
}
if(board_square > H8)
return NO_PIECE;
else
{
(*first_bit_bitboard)=(~MASK.mask[board_square])&(*first_bit_bitboard);
return board_square;
}
}
I found some code to do the same thing but I can not understant it
If somebody know some code easy to understand
Thanks
Gazzall50
Firstbit = Bitboard ^ (Bitboard & (bitboard - 1));
This picks up the least significant bit. (which i assume you wanted?)
Firstbit = 0, if no bits are set, or the lsb otherwise.
From,
NIce coder
This picks up the least significant bit. (which i assume you wanted?)
Firstbit = 0, if no bits are set, or the lsb otherwise.
From,
NIce coder
x ^= (x & (x - 1));
Gives you the lsb.
How?
First consider x & (x - 1)
Now, that clears the lsb. (how? consider 01001010110 - 1 = 010001010101 & 01001010110 = 01001010100)
Really simple.
Now, you xor the two values together, so that the only bits that are 1 are bits that are different.
Only the lsb has changed, so thats the only thing that could be a 1.
Because x &(x - 1) clears the lsb, it would only be different if the lsb is 1.
Its a nifty hack. You should use it sometime.
From,
Nice coder
Gives you the lsb.
How?
First consider x & (x - 1)
Now, that clears the lsb. (how? consider 01001010110 - 1 = 010001010101 & 01001010110 = 01001010100)
Really simple.
Now, you xor the two values together, so that the only bits that are 1 are bits that are different.
Only the lsb has changed, so thats the only thing that could be a 1.
Because x &(x - 1) clears the lsb, it would only be different if the lsb is 1.
Its a nifty hack. You should use it sometime.
From,
Nice coder
Author
Sorry but I did not have acces to intenet during the last 3 days.
Thanks a lot Nice coder for your answer that really help me
But do you know how can I get the corresponding square for the bitboard return
ie. 0000010 = B1
0000001 = A1
0000100 = C1
Thank again
Gazzall50
Thanks a lot Nice coder for your answer that really help me
But do you know how can I get the corresponding square for the bitboard return
ie. 0000010 = B1
0000001 = A1
0000100 = C1
Thank again
Gazzall50
You don't need it.
You can do everything in bitboards, you don't need to convert to the other units.
Theres probably an easy hack to find out anyway.
If you need it. (please tell me why, i haven't found a use yet), i'll think of something.
From,
Nice coder
You can do everything in bitboards, you don't need to convert to the other units.
Theres probably an easy hack to find out anyway.
If you need it. (please tell me why, i haven't found a use yet), i'll think of something.
From,
Nice coder
Author
Hi,
I need to know for the evaluation function to know where is the piece on the board.
Thank for your help nice coder
Gazzall50
I need to know for the evaluation function to know where is the piece on the board.
Thank for your help nice coder
Gazzall50
Quote:Original post by Gazzall50Here's one method for 32-bit integers. I assume the method can be extended to handle 64-bit boards too.
I need to know for the evaluation function to know where is the piece on the board.
unsigned int bit_search(unsigned input) { static const unsigned char table[] = { 0, 0, 0,15, 0, 1,28, 0,16, 0, 0, 0, 2,21,29, 0, 0, 0,19,17,10, 0,12, 0, 0, 3, 0, 6, 0,22,30, 0, 14, 0,27, 0, 0, 0,20, 0,18, 9,11, 0, 5, 0, 0,13, 26, 0, 0, 8, 0, 4, 0,25, 0, 7,24, 0,23, 0,31, 0 }; input ^= input - 1; input *= 7 * 255 * 255 * 255; return table[input >> 26];}
ok. You could use it for eval... I suppose.
A1 = 0
A2 = 1
A3 = 2
A4 = 4
A5 = 8
A6 = 16
A7 = 32
A8 = 64
A9 = 128
A10 = 256
...
Using those, its self evident.
Or if, you need a log2 function, heres one.
Dtable:
table1 = {0, 255,255,255,255....} //256 elements long, 1 0, 255 255's.
table2 = {0, 1, 2, 2, } //table2[x] = log2[x]
Ouput = (table2[i[0]] & table1[i[0]]) + ((table2[i[1]] + 8) & table1[i[1]]) + ((table2[i[2]] + 16) & table1[i[2]]) + ((table2[i[3]] + 32) & table1[i[3]]) + //.... For each of the 8 bytes.
Its very parelelisable. (as well as it has a small and constant size lut).
So, its 16 lookups, 8 ands, 14 adds adn thats it. (all lookups in cache tho).
Probably not the best tho. (there are much better versions. like a binary tree for instance. But you don't need it in the first place if you use bittables well).
From,
Nice coder
A1 = 0
A2 = 1
A3 = 2
A4 = 4
A5 = 8
A6 = 16
A7 = 32
A8 = 64
A9 = 128
A10 = 256
...
Using those, its self evident.
Or if, you need a log2 function, heres one.
Dtable:
table1 = {0, 255,255,255,255....} //256 elements long, 1 0, 255 255's.
table2 = {0, 1, 2, 2, } //table2[x] = log2[x]
Ouput = (table2[i[0]] & table1[i[0]]) + ((table2[i[1]] + 8) & table1[i[1]]) + ((table2[i[2]] + 16) & table1[i[2]]) + ((table2[i[3]] + 32) & table1[i[3]]) + //.... For each of the 8 bytes.
Its very parelelisable. (as well as it has a small and constant size lut).
So, its 16 lookups, 8 ands, 14 adds adn thats it. (all lookups in cache tho).
Probably not the best tho. (there are much better versions. like a binary tree for instance. But you don't need it in the first place if you use bittables well).
From,
Nice coder
Quote:Original post by Gazzall50
Hi,
I need to know for the evaluation function to know where is the piece on the board.
Thank for your help nice coder
Gazzall50
Since when?
What are you using it for?
(as in actual code)
From,
Nice coder
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
