## bit boards - what is betwen

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

### bit boards - what is betwen

What is the fastest way with bitboards to return a bit board of the points between any 2 squares? If the pieces are not on the same diagonal or orthogonal we return 0 of course. If the pieces are touching of course there is nothing between either.

I use a simple 64x64 array but wonder if there is anything clever than can be done without memory access. The array method seems unduly slow although I cannot imagine that it should be. Maybe it's not very cache friendly. I cannot think of anything else that does not require quite a bit of bit fiddling but you can do a lot of calculation in the time you lose with a cache miss.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

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

### Re: bit boards - what is betwen

Don wrote:What is the fastest way with bitboards to return a bit board of the points between any 2 squares? If the pieces are not on the same diagonal or orthogonal we return 0 of course. If the pieces are touching of course there is nothing between either.

I use a simple 64x64 array but wonder if there is anything clever than can be done without memory access. The array method seems unduly slow although I cannot imagine that it should be. Maybe it's not very cache friendly. I cannot think of anything else that does not require quite a bit of bit fiddling but you can do a lot of calculation in the time you lose with a cache miss.
Indexing an array of 240 bitboards by 0x88 square difference and rotate might we worth a try.

Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

### Re: bit boards - what is betwen

Gerd Isenberg wrote:
Don wrote:What is the fastest way with bitboards to return a bit board of the points between any 2 squares? If the pieces are not on the same diagonal or orthogonal we return 0 of course. If the pieces are touching of course there is nothing between either.

I use a simple 64x64 array but wonder if there is anything clever than can be done without memory access. The array method seems unduly slow although I cannot imagine that it should be. Maybe it's not very cache friendly. I cannot think of anything else that does not require quite a bit of bit fiddling but you can do a lot of calculation in the time you lose with a cache miss.
Indexing an array of 240 bitboards by 0x88 square difference and rotate might we worth a try.
That is an excellent idea, similar to the mailbox attack array indexed by the difference in the squares location.

Thanks,

Don
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

Posts: 535
Joined: Tue Dec 12, 2006 9:10 am

### Re: bit boards - what is betwen

Gerd Isenberg wrote:
Don wrote:What is the fastest way with bitboards to return a bit board of the points between any 2 squares? If the pieces are not on the same diagonal or orthogonal we return 0 of course. If the pieces are touching of course there is nothing between either.

I use a simple 64x64 array but wonder if there is anything clever than can be done without memory access. The array method seems unduly slow although I cannot imagine that it should be. Maybe it's not very cache friendly. I cannot think of anything else that does not require quite a bit of bit fiddling but you can do a lot of calculation in the time you lose with a cache miss.
Indexing an array of 240 bitboards by 0x88 square difference and rotate might we worth a try.
Thanks for the idea Gerd! I ended up trying this in Stockfish, and got a small speed win. I ended up using an array of size 120, as I couldn't see how to avoid a conditional on the shift even when using size 240.

Github commit here: https://github.com/glinscott/Stockfish/ ... b79b7606c4.

hgm
Posts: 22184
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

### Re: bit boards - what is betwen

What do you mean by 'without memory access', then? Surely indexing a table counts as a memory access...

Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

### Re: bit boards - what is betwen

hgm wrote:What do you mean by 'without memory access', then? Surely indexing a table counts as a memory access...
I meant without memory access but I would settle for anything that produced a speedup on modern processors.

The mailbox programs would index a much smaller array by using (destination - origin) as the index. To work with a 6 bit square a little bit twiddling would do the job. So if having a small array is a win, it might still be a win despite some additional bit twiddling to convert a 6 bit square to a 7 bit square but it's hard to believe that would make any difference.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

diep
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

### Re: bit boards - what is betwen

Don wrote:
hgm wrote:What do you mean by 'without memory access', then? Surely indexing a table counts as a memory access...
I meant without memory access but I would settle for anything that produced a speedup on modern processors.

The mailbox programs would index a much smaller array by using (destination - origin) as the index. To work with a 6 bit square a little bit twiddling would do the job. So if having a small array is a win, it might still be a win despite some additional bit twiddling to convert a 6 bit square to a 7 bit square but it's hard to believe that would make any difference.
Why would a 64x64 array be slower than executing more code with smaller array access?

The real problem of modern processors is mainly decode speed of instructions.

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

### Re: bit boards - what is betwen

Gerd Isenberg wrote:Indexing an array of 240 bitboards by 0x88 square difference and rotate might we worth a try.
Thanks for the idea Gerd! I ended up trying this in Stockfish, and got a small speed win. I ended up using an array of size 120, as I couldn't see how to avoid a conditional on the shift even when using size 240.

Github commit here: https://github.com/glinscott/Stockfish/ ... b79b7606c4.
Its a matter of correct initialization, to make the rotate left approach with 240 element lookup work, f.i.:

Code: Select all

``````       . . . . . . . .    . . . . . . . .
. . . . . . . .    . . . . . . . 1
. . . . . . . .    . . . . . . 1 .
. . . . . . . .    . . . . . 1 . .
. . . 1 . . . .    . . . . . . . .
. . 1 . . . . .    . . . . . . . .
. 1 . . . . . .    . . . . . . . .
. . . . . . . .    . . . . . . . .

between   &#40;0, 36&#41; 		  &#40;36, 0&#41;
lookup -> &#123; 9, 18, 27&#125;    &#123;37, 46, 55&#125;
rotl   -> &#123; 9, 18, 27&#125;    &#123; 9, 18, 27&#125;

between   &#40;10, 46&#41;        &#40;46, 10&#41;
lookup -> &#123; 9, 18, 27&#125;    &#123;37, 46, 55&#125;
rotl   -> &#123;19, 28, 37&#125;    &#123;19, 28, 37&#125;

between   &#40;27, 63&#41;        &#40;63, 27&#41;
lookup -> &#123; 9, 18, 27&#125;    &#123;37, 46, 55&#125;
rotl   -> &#123;36, 45, 54&#125;    &#123;36, 45, 54&#125;
``````
Otherwise, with 120, to avoid that branch, better use std:abs of the +/- difference.
Last edited by Gerd Isenberg on Mon Dec 03, 2012 9:13 pm, edited 1 time in total.

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

### Re: bit boards - what is betwen

diep wrote:
Don wrote:
hgm wrote:What do you mean by 'without memory access', then? Surely indexing a table counts as a memory access...
I meant without memory access but I would settle for anything that produced a speedup on modern processors.

The mailbox programs would index a much smaller array by using (destination - origin) as the index. To work with a 6 bit square a little bit twiddling would do the job. So if having a small array is a win, it might still be a win despite some additional bit twiddling to convert a 6 bit square to a 7 bit square but it's hard to believe that would make any difference.
Why would a 64x64 array be slower than executing more code with smaller array access?

The real problem of modern processors is mainly decode speed of instructions.
Really? I thought still branches and L1, L2 misses - at least in chess programs.

Sometimes smaller memory pays off, 32K vs. < 2K, likely more often in L1. A few additional instructions may improve ipc and hide latencies. How much is a L1 miss on todays processors?

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm