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.
Rotated Bitboards
Moderators: hgm, Rebel, chrisw
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Rotated Bitboards
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 wrote: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.
-
- Posts: 316
- Joined: Wed Apr 12, 2006 10:47 pm
Re: Rotated Bitboards
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
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
Colin
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: Rotated Bitboards
After a little thought I would suggest the following branchless movegenerator for othello:cms271828 wrote: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
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);
-
- Posts: 316
- Joined: Wed Apr 12, 2006 10:47 pm
Re: Rotated Bitboards
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
[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
Colin
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Rotated Bitboards
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.cms271828 wrote: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
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
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: Rotated Bitboards
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.cms271828 wrote: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
For the flipping the loop would probably be faster.
Edmund
-
- Posts: 316
- Joined: Wed Apr 12, 2006 10:47 pm
Re: Rotated Bitboards
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.
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.
Colin