Author: Chan Rasjid
Date: 09:24:58 01/20/06
Go up one level in this thread
On January 20, 2006 at 09:02:11, Vasik Rajlich wrote:
>>static const u64 kDzE4 = 0x0000382838000000;
>>static const u64 nDzE4 = 0x0028440044280000;
>>
>>
>>u64 getNMap(int sq){
>> static const u64 nMask[2] = {FILE_3TO8, FILE_1TO6};
>> if (sq >= E4)
>> return (nDzE4 << (sq - E4)) & nMask[FILE64(sq) - 4 >> 31 & 1];
>> return (nDzE4 >> (E4 - sq)) & nMask[FILE64(sq) - 4 >> 31 & 1];
>>}
>>
>>
>>u64 getKMap(int sq){
>> static const u64 kMask[2] = {FILE_2TO8, FILE_1TO7};
>> if (sq >= E4)
>> return (kDzE4 << (sq - E4)) & kMask[FILE64(sq) - 4 >> 31 & 1];
>> return (kDzE4 >> (E4 - sq)) & kMask[FILE64(sq) - 4 >> 31 & 1];
>>}
>>
>>Pawns are simple.
>I'm a little confused as to what exactly you're doing in the above code. For
>example, getting knight target squares is best done via simply:
>
>unsigned int64 knight_targets = knight_target_array [knight_sq] &
>~same_color_pieces;
>
The reason is I learn / over-learn from Fruit's code and after reading some
articles about "locality of references". u64 knight_target_array [64] == 4 x 128
bytes. My getNMap() superficially seems ok, by shifting and masking the N-map of
square E4. Fruit's codes seem not to like jumping about a large address space
and tries to work within 128 bytes; any far variables are "copied" as local at
start of domove(), etc...
>Anyway, it's not clear that an incremental approach is faster - and it's a hell
>of a lot messier. I just compute everything when I need it.
>
I think "a lot messier" is psychological. I did it very smoothly without any
major hitch and all about 300 lines not counting 100 lines of asserts.
My debug auoplay plays 100+ games an all asserts(30%) cleared.
When I was doing my 16x16 domove() and undomove(), it gave greater problems.
There is no incremental updates for P/N/K as long as the full maps inclusive of
all terminal pieces are retained. Only on extracting moves do we do an
& ~same_color_piece otherwise it mess up incremental codes.
The seemingly messy incremental is for the sliding pieces. A loop for 4 types is
done - bishop, rook, Q-as-B, Q-as-R and the codes are the same except for minor
differences. Again all terminal pieces have to be retained otherwise it may mess
up incremental codes. I post my sliding incremental codes below. I only have not
tested if it is fast as the extracting moves part is not completed. Those who
know asm may guess if it's ok.
>>3) QS move generation - In the past debate, it seemed no one mentioned this.
>> 90% of all nodes are QS nodes. Getting BB captures are the simplest. With
>>offset we still have to start from the targets and test by sliding thru empty
>>squares etc. So BB here may have a significantly influential advantage. Is this
>>the "secret of Rybka" ?
>>
>
>I don't know that it's really possible to compare board representations, and a
>few % speedup isn't all that important. Bitboards are certainly very elegant
>when it comes to various forms of "selective move generation".
>
>Vas
>
>>Best Regards,
>>Rasjid
My main incremenatal generation for sliding pieces :-
#ifndef STACK_H
#define STACK_H
const int B_Slide = 0;
const int R_Slide = 1;
const int DirDiag7 = 0;
const int DirDiag9 = 1;
const int DirVert = 0;
const int DirHorz = 1;
//same for p / b
const int DirStep[2][2] = {//[b/r][dir-index]
15, 17,
16, 1
};
struct pkMove_t {//sz 16
u64 bb;// bit and piece have a 1-1 relation for both P/N, so may delete on
//update also in dirDeleted
u64 bal;
// to get bit, shift back to bits[c][Pawns]
};
struct nMove_t {//sz 24
int from;
int nPC;
u64 bb;// bit and piece have a 1-1 relation for both P/N, so may delete on
//update also in dirDeleted
u64 bal;
};
//size = 48 byte
// b/r need 1 element per pc; q need 2 element per pc.
struct brMove_t {//also for king ?
int from;
int padding;
u64 bb[2];// the brq paths with terminal pcs.
u64 dir[2];//full b/r direction bits
u64 bal;//== bb[0] | bb[1], 2 disjoint sets
//u64 bbFrom == bb[0] & bb[1]
};
struct moveStack_t {
brMove_t brq[4][4][1];//[ind][pc >>1, 0 = qR, 1 = b, 2 = r, 3 = qB]
brMove_t kQ[2];//must same type to pass as ptr.
pkMove_t pk[4][1];
nMove_t n[4][1];
u64 kN;//King as N
int nN;
int nB;
int nR;
int nQ;
u64 padding1;
};
/*
note - pclist index corrupts by search, so cannot use as index to stack-move
index
*/
//non recursive search stack
struct stack_t {
move_t moveStack[moveStackSize];//tmp, only for 16x16 to debug BB
move_t pv[MaxHeight];
moveStack_t bbMoveStack[1];//8 x 128 BB move stack
moveStack_t buf[1];//8 x 128 , save at node start, restore on undo
u64 bits[2][8];
undo_t undo[1];//128 byte
u64 * allBits;
int depth;
int alpha;
int beta;
int best;
int bestType;
move_t bestMove;
int pvLength;
move_t * pCurrentMove;
//buffer - save at domove, restore on undomove; todo - may eliminate ?
sq_t sqFrom;//1st in order
sq_t sqCaptureEP;
sq_t sqFromCastleRook;
int fExt;
int flag;
int incheck;
int nGeneratedMove;
int nMoveDone;
//follow 3 pulled out of undo, so undo sz == 128 byte
u64 hashKey;
u64 pawnHashKey;
int promotePc;
int preAlpha;
int pad1;
};
#endif
bool_t genIncrementalBB(board_t * board, stack_t * pS, move_t m, incheck_t *
incheck, sq_t sqCaptureEP, const int c, const int side, u64 all){
static const int DirStep[2][2] = {//[b/r][dir-index]
15, 17, // b / q-asB
16, 1 //r / q-as-R
};
int i, j;
moveStack_t * const pMS = pS->bbMoveStack;
brMove_t *pElem;
const int *lp, loopPc[] = {// 7 == King as Queen
1, 2, 3, 7, 0
};
int nK = 1;
int * const nBRQ[] = {
0,
&pMS->nB,//no of bishop
&pMS->nR,
&pMS->nQ,
0,
0,
0,
&nK
};
//todo - tmp, some available from bbDoMove();
u64 u;
u64 bbTo = SQ_BB(TO(m));
u64 bbFrom = SQ_BB(FROM(m));
u64 bbCapture = 0;
u64 bbEP_Capture = 0;
u64 * pAttackBB = board->undo->attackBB[c];
memset( board->undo->attackBB[c], 0 , sizeof(board->undo->attackBB[c]));
assert(all & bbTo);
if (!IS_MOVE_CAPTURE(m)){
if (!IS_MOVE_EP(m));
else{
bbEP_Capture = SQ_BB(side ? TO(m) - RankStep : TO(m) + RankStep);
}
}else{
bbCapture = bbTo;
}
lp = loopPc;
do{
//pc = *lp << 1;
for ( i = *nBRQ[*lp] - 1; i >= 0; i--){
j = *lp;// has continue after j = 0
j < 7 ? (pElem = pMS->brq[i][j]) : (pElem = pMS->kQ); // j == 7 for K-as Q
u = pElem->bb[0] & pElem->bb[1];
assert(pElem->bb[0]);
assert(pElem->bb[1]);
assert(u == SQ_BB(pElem->from));
assert((pElem->bb[0] | pElem->bb[1]) == pElem->bal);
assert(j == 3 ? pElem->from == pMS->brq[i][0]->from : 1);
if (TO(m) != pElem->from){//may be capt of others
if (u & all);//include cstl rook
else{
//now the pc moves, get full
assert(c == side);
assert(IS_SQ_EMPTY(board->sq[pElem->from]));
if (j == 7)//dont mix- when the king moves; here allow only castle rook
continue;
if (!IS_MOVE_CSTL(m))
pElem->from = TO(m);
else{//cstl rook
assert(j == 2);
assert(TO(m) - FROM(m) & 2);
pElem->from = TO(m) - (TO(m) - FROM(m) >> 1);
}
if (j&1){// bs / q
getBAttackBB_SQ64(pElem, SQ_TO64(pElem->from),
SQ_BB(pElem->from), all);
assert(pElem->bal == getBMap_SQ(pElem->from, all));
*(pAttackBB + (j << 1)) |= pElem->bal;
}
if ( j & 2){
if (j == 2);
else{
pElem = pMS->brq[i][0];//qR
pElem->from = TO(m);
}
getRAttackBB_SQ64(pElem, SQ_TO64(pElem->from), SQ_BB(pElem->from), all);
assert(pElem->bal == getRMap_SQ(pElem->from, all));
*(pAttackBB + (j << 1)) |= pElem->bal;
}
assert(pElem->bal == (pElem->bb[0] | pElem->bb[1]));
continue;//next pc same type
}
Q_ROOK_CUT:
assert(bbFrom != (pElem->bb[0] & pElem->bb[1]));//not moved
assert(bbTo != (pElem->bb[0] & pElem->bb[1]));//not captured
if ( !(pElem->bal & (bbTo ^ bbCapture)) ){//usual not a cut
if ( j < 3 || bbCapture);//ok, also for qR j == 0
else {
j < 7 ? (pElem = pMS->brq[i][j = 0]) : (j = 0, pElem++);//qR
assert((pElem->bb[0] & pElem->bb[1]) == SQ_BB(pElem->from));
assert((pElem->bb[0] | pElem->bb[1]) == pElem->bal);
u = pElem->bb[0] & pElem->bb[1];
assert(u == SQ_BB(pElem->from));
//must loop to do q-as rook
goto Q_ROOK_CUT;
}
}else {// now there is somthing to cut
u64 *pBB;
assert(u == SQ_BB(pElem->from));
pBB = pElem->bb;
if (*pBB & bbTo);
else {
pBB++;
assert(*pBB & bbTo);
}
pElem->bal ^= *pBB;
if (bbTo < u){
*pBB &= BITS_GE(bbTo);
}else{
assert(bbTo > u);
assert( bbTo & BITS_G(u));
*pBB &= BITS_LE(bbTo);
}
pElem->bal |= *pBB;
#ifdef _DEBUG
if (pElem->bal == (db_u1 = pElem->bb[0] | pElem->bb[1]));
else{
printBB("B-bal", pElem->bal, all);
printBB("BB", db_u1, all);
assert(0);
}
#endif
}
if ( j );
else{
j = *lp;//reset
j < 7 ? (pElem = pMS->brq[i][j] ) : (pElem = pMS->kQ);
u = pElem->bb[0] & pElem->bb[1];
}
Q_ROOK_EXT:
// may NOT both cut and ext 1 dir; diff dir ok
if ( !(pElem->bal & bbFrom) ){//usual not an ext
if ( j < 3);//ok, also for qR j == 0
else {
j < 7 ? (pElem = pMS->brq[i][j = 0]) : (j = 0, pElem++);//qR
assert((pElem->bb[0] & pElem->bb[1]) == SQ_BB(pElem->from));
assert((pElem->bb[0] | pElem->bb[1]) == pElem->bal);
u = pElem->bb[0] & pElem->bb[1];
assert(u == SQ_BB(pElem->from));
//loop to ext q-as-rook
goto Q_ROOK_EXT;
}
}else{
i64 lb_ub, v;
u64 *pBB, *pDir;
assert(u == SQ_BB(pElem->from));
pDir = pElem->dir;
pBB = pElem->bb;
if (*pDir & bbFrom);
else {//ext
pDir++;
pBB++;
}
assert(*pBB & bbFrom);
if (bbFrom < u){
lb_ub = 1;
if ( !(v = all & *pDir & BITS_L(u)) );
else {
while ( v & v - 1){
v &= v - 1;
}
lb_ub = v & -v;//lb
// ( i - j ) > 0 has 1's in bit j and the intervening bits
*pBB |= *pDir & (u - lb_ub);// w/o u ok
}else{
lb_ub = 0x8000000000000000;
assert(bbFrom > u);
v = *pDir & all & BITS_GE(bbFrom);
if ( v &= -v ){
lb_ub = v;//ub
}
*pBB |= *pDir & ((lb_ub - u) | lb_ub);
}
pElem->bal |= *pBB;
#ifdef _DEBUG
if (pElem->bal == (db_u1 = pElem->bb[0] | pElem->bb[1]));
else{
printBB("R-bal", pElem->bal, all);
printBB("getBB", db_u1, all);
assert(0);
}
#endif
}
if (bbEP_Capture == 0);
else {//rare special ep case
if (bbFrom != bbEP_Capture){
bbFrom = bbEP_Capture;//may release ext
j = *lp;//reset
j < 7 ? (pElem = pMS->brq[i][j] ) : (pElem = pMS->kQ);
u = pElem->bb[0] & pElem->bb[1];
goto Q_ROOK_EXT;
}
bbFrom = SQ_BB(FROM(m));//reset
}
//no need reset j
#ifdef _DEBUG
//may assert get map only after all cut, extent.
j = *lp;//reset
if (j == 1){
if (pElem->bal == (db_u1 = pElem->bb[0] | pElem->bb[1]));
else{
printBB("B-bal", pElem->bal, all);
printBB("getBB", db_u1, all);
assert(0);
}
db_u1 = getBMap_SQ(pElem->from, all);
if (db_u1 == pElem->bal);
else{
printBB("B-bal", pElem->bal, all);
printBB("getBB", db_u1, all);
assert(0);
}
}
if (j == 2){
if (pElem->bal == (db_u1 = pElem->bb[0] | pElem->bb[1]));
else{
printBB("R-bal", pElem->bal, all);
printBB("getBB", db_u1, all);
assert(0);
}
db_u1 = getRMap_SQ(pElem->from, all);
if (db_u1 == pElem->bal);
else{
printBB("R-bal", pElem->bal, all);
printBB("getBB", db_u1, all);
assert(0);// when EP
}
}
if (j >= 3){
if (j == 3)
pElem = pMS->brq[i][3];
else
pElem = pMS->kQ;
if (pElem->bal == (db_u1 = pElem->bb[0] | pElem->bb[1]));
else{
printBB("qB-bal", pElem->bal, all);
printBB("getBB", db_u1, all);
assert(0);
}
db_u1 = getBMap_SQ(pElem->from, all);
if (db_u1 == pElem->bal);
else{
printBB("qB-bal", pElem->bal, all);
printBB("getBB", db_u1, all);
assert(0);//bal has error, miss end-pc in all
}
if (j == 3)
pElem = pMS->brq[i][0];
else
pElem++;// = pMS->kQ;
if (pElem->bal == (db_u1 = pElem->bb[0] | pElem->bb[1]));
else{
printBB("qR-bal", pElem->bal, all);
printBB("getBB", db_u1, all);
assert(0);
}
db_u1 = getRMap_SQ(pElem->from, all);
if (db_u1 == pElem->bal);
else{
printBB("qR-bal", pElem->bal, all);
printBB("getBB", db_u1, all);
assert(0);//bal has error, miss end-pc in all
}
}
#endif
//end debug
//sum th attacks of same type
if (j == 1 || j == 2)
*(pAttackBB + (j << 1)) |= pElem->bal;
else if (*lp == 3)
*(pAttackBB + Queen) |= pMS->brq[i][3]->bal | pMS->brq[i][0]->bal;
//NOT when a capture move
if (c != side && *lp < 7){
pElem = pMS->brq[i][*lp];
assert(pElem->bal == (pElem->bb[0] | pElem->bb[1]));
if (pElem->bal & board->bits[side][King]){
assert(brqAttack88(board, board->piece[side][0], c));
return False;
}
assert(*lp == 3 ? (pElem - 3)->bal == ((pElem - 3)->bb[0] | (pElem - 3)->bb[1])
: 1);
if (*lp == 3 && (pElem - 3)->bal & board->bits[side][King]){
assert((pElem - 3)->bal == ((pElem - 3)->bb[0] | (pElem - 3)->bb[1]));
assert( pElem - 3 == pMS->brq[i][0]);
assert(brqAttack88(board, board->piece[side][0], c));
return False;
}
}
}else{//this pc captured. delete
assert(j < 7);
assert(c != side);
assert(IS_MOVE_CAPTURE(m));
assert(SQ_PIECE(sqCaptureEP) == (j << 1));
debug_nCapture++;
(*nBRQ[j])--;
assert(*nBRQ[j] >= 0);
if (*nBRQ[j] == 0 || *nBRQ[j] == i);
else{//pMS->nBRQ now last index
//dele pc and swap pc of last index
*pElem = *pMS->brq[*nBRQ[j]][j];//swap last
if ( j < 3 );
else
*pMS->brq[i][0] = *pMS->brq[*nBRQ[j]][0];//swap last q-as-R
assert(IS_SQ_ON(board->sq[pElem->from]));
assert(TO(m) != pElem->from);
assert(SQ_PIECE(board->sq[pElem->from]) == (j << 1));
assert(SQ_COLOR(board->sq[pElem->from]) == c);
}
assert(pElem->bal == (pElem->bb[0] | pElem->bb[1]));
}
//next pc of same type
}//for
}while ( *++lp );
//etc.. trivial for P / n / K
return True;
}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.