Author: Vasik Rajlich
Date: 07:45:22 01/21/06
Go up one level in this thread
On January 20, 2006 at 12:24:58, Chan Rasjid wrote:
>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...
>
Aha, it's what I was afraid of :)
>>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.
>
Aha, thanks for the code. I can't really dig into it right now, but will keep it
for future reference. At some point I may try an incremental approach in Rybka.
Somehow though I doubt it will give more than a few % speedup (if any).
Computing attacks from scratch with bitboards is a pretty straightforward
operation.
Vas
>>>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.