Page 1 of 1
bitScanReverse32
Posted: Tue Jan 26, 2010 12:32 am
by metax
What does the function 'bitScanReverse32()' do in Stockfish?
Re: bitScanReverse32
Posted: Tue Jan 26, 2010 2:53 am
by bob
metax wrote: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.
Re: bitScanReverse32
Posted: Tue Jan 26, 2010 3:11 am
by Milos
metax wrote: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
Re: bitScanReverse32
Posted: Tue Jan 26, 2010 3:33 am
by 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?
Re: bitScanReverse32
Posted: Tue Jan 26, 2010 8:18 am
by mcostalba
metax wrote: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.
Re: bitScanReverse32
Posted: Tue Jan 26, 2010 8:18 am
by Gerd Isenberg
metax wrote: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));
Re: bitScanReverse32
Posted: Tue Jan 26, 2010 9:04 pm
by Gerd Isenberg
metax wrote:
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.
Re: bitScanReverse32
Posted: Tue Jan 26, 2010 9:53 pm
by 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
Re: bitScanReverse32
Posted: Wed Jan 27, 2010 10:37 am
by mcostalba
Eelco de Groot wrote: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.
Re: bitScanReverse32
Posted: Wed Jan 27, 2010 12:35 pm
by metax
Eelco de Groot wrote: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.
;)