bitScanReverse32

[metax]

What does the function 'bitScanReverse32()' do in Stockfish?

[bob]

What does the function 'bitScanReverse32()' do in Stockfish?

Scans from the opposite end of the value. In Intel-land, BSF is Bit Scan Forward, which starts at bit 0 and returns the number of the first bit set, going right to left or LSB to MSB. BSR is Bit Scan Reverse, and starts at bit 31 and returns the number of the first bit set, going left to right or MSB to LSB. Bits are always numbered with LSB = 0, MSB = 31, regardless of the direction you search.

[Milos]

What does the function 'bitScanReverse32()' do in Stockfish?

The specific implementation is Nalimov's devide'n'conquer version.
However, in practice on at least double core cpu's the latency of hardware bsr is so much reduced that there is simply no point in using anything but hardware implementation.

All very nice explanations you have on: http://chessprogramming.wikispaces.com/BitScan

[metax]

Thanks. But I was actually only interested in the Stockfish futility values, which are 'hidden' in the new formula. If I got this correctly, the values according to the formula

FutilityValueMargin = 112 * bitScanReverse32(int(depth) * int(depth) / 2)

would be

Code: Select all

Ply  -> FutilityValueMargin
---------------------------

QS   -> 50
1    -> 112
1.5  -> 224
2    -> 336
2.5  -> 336
3    -> 448
3.5  -> 448
4    -> 560
4.5  -> 560
5    -> 560
5.5  -> 560
6    -> 672
6.5  -> 672
7    -> 672

(the QS value is saved in FutilityValueQS). These are still subtracted by 3*moveCount if I understood that correctly.
But why not simply put them into a table and look them up, instead of using a complicated formula?

[mcostalba]

What does the function 'bitScanReverse32()' do in Stockfish?

As you can deduce from definition, it is a cheap way to compute log in base 2 of an integer number.

New futility formula is log based.

[Gerd Isenberg]

Thanks. But I was actually only interested in the Stockfish futility values, which are 'hidden' in the new formula. If I got this correctly, the values according to the formula

FutilityValueMargin = 112 * bitScanReverse32(int(depth) * int(depth) / 2)

would be

Code: Select all

Ply  -> FutilityValueMargin
---------------------------

QS   -> 50
1    -> 112
1.5  -> 224
2    -> 336
2.5  -> 336
3    -> 448
3.5  -> 448
4    -> 560
4.5  -> 560
5    -> 560
5.5  -> 560
6    -> 672
6.5  -> 672
7    -> 672

(the QS value is saved in FutilityValueQS). These are still subtracted by 3*moveCount if I understood that correctly.
But why not simply put them into a table and look them up, instead of using a complicated formula?

Bsr is the floor of the base-2 logarithm. Here from the half of the square of depth.

Code: Select all

FutilityValueMargin = 112 * floor( ld (sqr (depth) /2));

[Gerd Isenberg]

But why not simply put them into a table and look them up, instead of using a complicated formula?

Yes, a lookup by depth seems faster at the first glance, but it may compete with other memory ops, and sometimes it is faster to schedule processor operations to "hide" other independent memory latencies. And mul, bsr, shifts, lea are not that expensive nowadays and despite all dependent likely far below 10 cycles on a core2.

[Eelco de Groot]

I thought it might have been set up this way by Marco with a one variable formula, for easier auto-tuning. The tuning process then only has to tweak a single variable. Thanks for the table Luca, I had been wondering myself and not looked at the Wikipages or anything. With the table the formula is easier for me to understand! Tuning of the Futility Pruning is tricky by the way. I suppose it is also sensitive to the move-ordering.

Eelco

[mcostalba]

I thought it might have been set up this way by Marco with a one variable formula, for easier auto-tuning. The tuning process then only has to tweak a single variable. Thanks for the table Luca, I had been wondering myself and not looked at the Wikipages or anything. With the table the formula is easier for me to understand! Tuning of the Futility Pruning is tricky by the way. I suppose it is also sensitive to the move-ordering.

Eelco

It is sensitive to a lot of stuff, starting from search depth aka time control used for testing.

We have left in a formula first because it is not performance critical code (and is fast anyway) second because it is more easy to tweak. Futility pruning tuning is a never ending story for the reason that you mentioned: it depends on a lot of other stuff so when you change, for instance, more ordering, it could be possible to increase it a bit and so on, there are many examples.

[metax]

Thanks for the table Luca, I had been wondering myself and not looked at the Wikipages or anything. With the table the formula is easier for me to understand!

I have calculated this by hand, so no warranty on the correctness of these numbers. ;)