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

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

No thank you?
No rate++?

Mean Gazzall50!

[bawling]
From,
Nice coder

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

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

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

Quote: Original post by Gazzall50
I need to know for the evaluation function to know where is the piece on the board.

Here's one method for 32-bit integers. I assume the method can be extended to handle 64-bit boards too.

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

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