bitScanReverse32

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

bitScanReverse32

Post by metax » Mon Jan 25, 2010 11:32 pm

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

bob
Posts: 20912
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: bitScanReverse32

Post by bob » Tue Jan 26, 2010 1:53 am

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.

Milos
Posts: 3619
Joined: Wed Nov 25, 2009 12:47 am

Re: bitScanReverse32

Post by Milos » Tue Jan 26, 2010 2:11 am

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

metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Re: bitScanReverse32

Post by metax » Tue Jan 26, 2010 2:33 am

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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: bitScanReverse32

Post by mcostalba » Tue Jan 26, 2010 7:18 am

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.

Gerd Isenberg
Posts: 2146
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: bitScanReverse32

Post by Gerd Isenberg » Tue Jan 26, 2010 7:18 am

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));

Gerd Isenberg
Posts: 2146
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: bitScanReverse32

Post by Gerd Isenberg » Tue Jan 26, 2010 8:04 pm

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.

User avatar
Eelco de Groot
Posts: 4244
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: bitScanReverse32

Post by Eelco de Groot » Tue Jan 26, 2010 8:53 pm

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
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: bitScanReverse32

Post by mcostalba » Wed Jan 27, 2010 9:37 am

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.

metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Re: bitScanReverse32

Post by metax » Wed Jan 27, 2010 11:35 am

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. :oops:;)

Post Reply