H.G. Muller's ideas were exactly what I was looking for. Clever uses of bits in the piece values to efficiently test for enemy piece, or test for enemy piece or empty, and in both cases, the border square is handled for free.
Funny, I pack bits for the moves, and I pack bits for the hash table, but it never occured to me to pack bits for the pieces themselves. Aside from color and piece type, one could pack a lot more info in those piece bits...
move generation with one dimensional "12 x 10" arr
Moderator: Ras
-
- Posts: 28356
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: move generation with one dimensional "12 x 10"
One other trick that might be useful, when packing bits in the pieces, is this:
If you store piece numbers in the board (rather than piece types), it is in many places very handy if you can immediately see if a piece is a Pawn. So in Joker, I have received the numbers 32-47 (binary 00100000-00101111) for white non-Pawns, and 48-63 (binary 00110000-00111111) for white Pawns. (And similarly 64-79 for black pieces, 80-95 for black Pawns). So in this casethe white bit is 32 and the black bit 64.
That way I can test if a board square has a Pawn on it by &32. That is useful in the attack test, as there are at most 2 Pawns that can attack a square. So it is much quicker to check those two squares on the board, than to run through the list of Pawns. To test oif the pieces can go there, I do run thhrough the list of pieces, applying the usual 0x88 test.
If you store piece numbers in the board (rather than piece types), it is in many places very handy if you can immediately see if a piece is a Pawn. So in Joker, I have received the numbers 32-47 (binary 00100000-00101111) for white non-Pawns, and 48-63 (binary 00110000-00111111) for white Pawns. (And similarly 64-79 for black pieces, 80-95 for black Pawns). So in this casethe white bit is 32 and the black bit 64.
That way I can test if a board square has a Pawn on it by &32. That is useful in the attack test, as there are at most 2 Pawns that can attack a square. So it is much quicker to check those two squares on the board, than to run through the list of Pawns. To test oif the pieces can go there, I do run thhrough the list of pieces, applying the usual 0x88 test.
-
- Posts: 128
- Joined: Sat Sep 23, 2006 7:10 pm
- Location: Prague
Re: move generation with one dimensional "12 x 10"
Why? Could you elaborate little bit? I used to have precomputed knight and king moves (with 0x88) before I moved to bitboards.Aleks Peshkov wrote:IMO old Gnuchess table-based move generation with plain 8x8 board is better.
Yes, in fact I have to do it in both directions (8x8->0x88 & 0x88->8x8) due to the bitboards/0x88 cooperation.It is very cheap to covert 8x8 to x88 coordinates sq_x88 = sq + (sq & 070); in rare cases when you need 0x88 tricks.
I don't know what is better. Bitboards/8x8 and conversions for 0x88 tricks or Bitboards/0x88. And I like those 0x88 tricks so I use them quite frequently.
Big issue is here that rewriting my datastructers to 8x8 would be very painful operation and I am not sure that it would pay off ...
-
- Posts: 895
- Joined: Sun Nov 19, 2006 9:16 pm
- Location: Russia
- Full name: Aleks Peshkov
Re: move generation with one dimensional "12 x 10"
http://www.talkchess.com/forum/viewtopi ... 029#159029tvrzsky wrote:Why? Could you elaborate little bit? I used to have precomputed knight and king moves (with 0x88) before I moved to bitboards.Aleks Peshkov wrote:IMO old Gnuchess table-based move generation with plain 8x8 board is better.
http://www.talkchess.com/forum/viewtopic.php?p=159201
-
- Posts: 794
- Joined: Wed Jul 19, 2006 9:58 am
Re: move generation with one dimensional "12 x 10"
My "newer" version of Lime I've been working on for a while uses 12x12 (same principle), generation og bishop moves:
I also computed attack tables, which helped for faster attck detection.
I don't use -ve values for one set of pieces though - as already said, just set a particular bit for white, another for black.
Richard
Code: Select all
tsq=sq144+13;
while (Br->pce[tsq] == ety) {plist[*pcount]=( (sq144<<8) | (tsq) | mNORM); (*pcount)++;tsq+=13; }
if(Br->col[tsq]==os) { plist[*pcount]=( (sq144<<8) | (tsq) | mCAP); (*pcount)++;}
tsq=sq144+11;
while (Br->pce[tsq] == ety) {plist[*pcount]=( (sq144<<8) | (tsq) | mNORM); (*pcount)++;tsq+=11; }
if(Br->col[tsq]==os) { plist[*pcount]=( (sq144<<8) | (tsq) | mCAP); (*pcount)++;}
tsq=sq144-13;
while (Br->pce[tsq] == ety) {plist[*pcount]=( (sq144<<8) | (tsq) | mNORM); (*pcount)++;tsq-=13; }
if(Br->col[tsq]==os) { plist[*pcount]=( (sq144<<8) | (tsq) | mCAP); (*pcount)++;}
tsq=sq144-11;
while (Br->pce[tsq] == ety) {plist[*pcount]=( (sq144<<8) | (tsq) | mNORM); (*pcount)++;tsq-=11; }
if(Br->col[tsq]==os) { plist[*pcount]=( (sq144<<8) | (tsq) | mCAP); (*pcount)++;}
Code: Select all
void init_B_delta()
{
int delta[5] = { 13, 11, -13, -11, 0 };
int one,two;
int *pdelta,tsq;
for(one=0;one<144;++one)
{
for(two=0;two<144;++two)
{
for(pdelta=delta; *pdelta; pdelta++)
{
tsq=one+*pdelta;
while(sqonbrd(tsq))
{
if(tsq == two)
{
deltatab[one][two] |= (Bbit | Qbit);
}
tsq+=*pdelta;
}
}
}
}
}
Richard
Re: move generation with one dimensional "12 x 10"
bob wrote:If that were the only benefit I agree. But the ability to ask "are these two squares on the same diagonal" and get an answer that does not break due to wrap-around is a plus for attack detection.Zach Wegner wrote:Personally I think traditional 0x88 is obsolete. You must test the square number first in order to see if its on the board, but you are in most cases going to access the contents of the square anyway to see if the square is empty. If I was going to do a mailbox approach, I'd do 12x16.
Code: Select all
uint64 canAttack[64];
// init canAttack
if (canAttack[fromSquare] & setMask[toSquare])
....
Tony