Rotated Bitboards

[cms271828]

I realized with rotated bitboards, take the ranks for example..

You don't need to AND it with 255, after shifting (W_TOTAL | B_TOTAL).

But several websites say to do this.

All you need to do is shift (W_TOTAL | B_TOTAL), by an extra bit, then AND with 63, so effectively you have:

RANK[64][64]
FILE[64][64]
NORTH_EAST_DIAGONAL[64][]
SOUTH_EAST_DIAGONAL[64][]

where the diagonal entries will be 0-6 bits.

I guess everyone does this anyway, but it doesn't seem to be mentioned on internet, from what I've seen.

[bob]

I realized with rotated bitboards, take the ranks for example..

You don't need to AND it with 255, after shifting (W_TOTAL | B_TOTAL).

But several websites say to do this.

All you need to do is shift (W_TOTAL | B_TOTAL), by an extra bit, then AND with 63, so effectively you have:

RANK[64][64]
FILE[64][64]
NORTH_EAST_DIAGONAL[64][]
SOUTH_EAST_DIAGONAL[64][]

where the diagonal entries will be 0-6 bits.

I guess everyone does this anyway, but it doesn't seem to be mentioned on internet, from what I've seen.

That was the way Crafty rotated bitboards were implemented in fact. The two "end bits" are not needed, and doing this cuts the size of the table by a factor of 4x...

[cms271828]

Yep, thats what I figured, 4 times smaller arrays, and its a tiny bit faster.

I'm considering making an othello game, but move generation is more like captures in chess, since you need a piece of your own colour at the end of a ray.

But I'm not sure how to do it using Rotated Bitboards / Magic Move generation.

Does anyone have any experience here?

Thanks

[Edmund]

Yep, thats what I figured, 4 times smaller arrays, and its a tiny bit faster.

I'm considering making an othello game, but move generation is more like captures in chess, since you need a piece of your own colour at the end of a ray.

But I'm not sure how to do it using Rotated Bitboards / Magic Move generation.

Does anyone have any experience here?

Thanks

After a little thought I would suggest the following branchless movegenerator for othello:

the code generates the moveto that will hold all possible squares that white can move to. I only demonstrated the code with leftshift. Finally all directions are needed. By "shiftleft" I mean (x<<1)&~0x0101010101010101

Code: Select all

int64 white;
int64 black;

int64 moveto;
int64 movetemp;


left:

movetemp = shiftleft(white);

movetemp &= black;
movetemp = shiftleft(movetemp);
moveto |= movetemp & ~(white|black);

movetemp &= black;
movetemp = shiftleft(movetemp);
moveto |= movetemp & ~(white|black);

movetemp &= black;
movetemp = shiftleft(movetemp);
moveto |= movetemp & ~(white|black);

movetemp &= black;
movetemp = shiftleft(movetemp);
moveto |= movetemp & ~(white|black);

movetemp &= black;
movetemp = shiftleft(movetemp);
moveto |= movetemp & ~(white|black);

movetemp &= black;
movetemp = shiftleft(movetemp);
moveto |= movetemp & ~(white|black);

[cms271828]

Thanks, thats very good, I just tried it with:

[d]8/8/8/8/1Pppp3/1Ppppp2/8/8 w - 0 1

Where the pawns are othello pieces,
I understand how it works, and saves having to test each possibly square one at a time.

But still, you would have to repeat it for all 8 directions.
Perhaps it can condensed to shift left and right at the same time, or maybe even all directions, I'll have to mess about with it.

Assuming that you have all the possible white moves, you still need something to make the move (flipping the counters in all 8 directions),
not sure if a loop should be used here.

Any further thoughts, let me know.
Thanks

[Gerd Isenberg]

Thanks, thats very good, I just tried it with:

8/8/8/8/1Pppp3/1Ppppp2/8/8 w - 0 1

Where the pawns are othello pieces,
I understand how it works, and saves having to test each possibly square one at a time.

But still, you would have to repeat it for all 8 directions.
Perhaps it can condensed to shift left and right at the same time, or maybe even all directions, I'll have to mess about with it.

Assuming that you have all the possible white moves, you still need something to make the move (flipping the counters in all 8 directions),
not sure if a loop should be used here.

Any further thoughts, let me know.
Thanks

The nice thing with setwise fillstuff like dumb7fill or the parallel prefix kogge-stone algorithm - you need no memory lookups. With enough registers available you may process two or more directions in parallel to have two or more independent instruction chains to improve instructions per cycle. X86/64 or 64-bit jvm appreciated, 32-bit mode with so less registers sucks.

Also, if you do that alu-dominated stuff at the beginning of each node before probing the hashtable, you may try a software prefetch (_mm_prefetch intrinsic for some C++ compilers) to get an hashentry from memory already closer to the processor.

Gerd

[Edmund]

Thanks, thats very good, I just tried it with:

[/d]8/8/8/8/1Pppp3/1Ppppp2/8/8 w - 0 1

Where the pawns are othello pieces,
I understand how it works, and saves having to test each possibly square one at a time.

But still, you would have to repeat it for all 8 directions.
Perhaps it can condensed to shift left and right at the same time, or maybe even all directions, I'll have to mess about with it.

Assuming that you have all the possible white moves, you still need something to make the move (flipping the counters in all 8 directions),
not sure if a loop should be used here.

Any further thoughts, let me know.
Thanks

I don't see a way of doing right and left-shifts at once. Still, the algorithm is pretty fast as there are no branches. It will be especially good, when there are many stones on the board, as everything is done at once.

For the flipping the loop would probably be faster.

Edmund

[cms271828]

My thinking was that if you can represent a move by all the pieces that are flipped, then to make/undo move, you simply need to use a couple of binary operations to swap everything over.

But to generate these moves, you would need to somehow scan the board, looking for possible squares to put down on, which is how the other method would be quicker.

So I'm not sure, but I would have thought using magic move generation would be a good idea.