X-Git-Url: http://winboard.nl/cgi-bin?a=blobdiff_plain;f=hachu.c;h=9adacca17777b6192ead4840869830a380f607a1;hb=0fceb531ee16ce88c906df48c4207fb1e90e1eb5;hp=7838313e1a58416252543cec3533175b262d52aa;hpb=2675827b066faf7d0d5b0f3b619525180041cf3c;p=hachu.git diff --git a/hachu.c b/hachu.c index 7838313..9adacca 100644 --- a/hachu.c +++ b/hachu.c @@ -11,14 +11,15 @@ // promotions by pieces with Lion power stepping in & out the zone in same turn // promotion on capture -#define VERSION "0.7beta" +#define VERSION "0.11 kill" -#define PATH level==0 || path[0] == 0xc4028 && (level==1 /*|| path[1] == 0x75967 && (level == 2 || path[2] == 0x3400b && (level == 3))*/) +#define PATH level==0 || path[0] == 0x848f1 && (level==1 /*|| path[1] == 0x3f081 && (level == 2 || path[2] == 0x6f0ac && (level == 3 || path[3] == 0x3e865 && (level == 4 || path[4] == 0x4b865 && (level == 5))))*/) //define PATH 0 #define HASH #define KILLERS -#define NULLMOVE +#define XNULLMOVE +#define LIONTRAP #include #include @@ -119,19 +120,22 @@ typedef struct { char *name, *promoted; int value; signed char range[8]; + char bulk; char ranking; int whiteKey, blackKey; } PieceDesc; typedef struct { - int from, to, piece, victim, new, booty, epSquare, epVictim[8], ep2Square, revMoveCount, savKeyL, savKeyH; + int from, to, piece, victim, new, booty, epSquare, epVictim[8], ep2Square, revMoveCount; + int savKeyL, savKeyH, gain, loss, filling, saveDelta; char fireMask; } UndoInfo; char *array, fenArray[4000], *reason; -int bWidth, bHeight, bsize, zone, currentVariant, chuFlag, tenFlag, chessFlag, repDraws; -int stm, xstm, hashKeyH, hashKeyL, framePtr, msp, nonCapts, rootEval, retMSP, retFirst, retDep, pvPtr, level, cnt50, mobilityScore; -int nodes, startTime, tlim1, tlim2, tlim3, repCnt, comp, abortFlag; +int bWidth, bHeight, bsize, zone, currentVariant, chuFlag, tenFlag, chessFlag, repDraws, tsume; +int stm, xstm, hashKeyH=1, hashKeyL=1, framePtr, msp, nonCapts, rootEval, filling, promoDelta; +int retMSP, retFirst, retDep, pvPtr, level, cnt50, mobilityScore; +int nodes, startTime, lastRootMove, lastRootIter, tlim1, tlim2, tlim3, repCnt, comp, abortFlag; Move ponderMove; Move retMove, moveStack[10000], path[100], repStack[300], pv[1000], repeatMove[300], killer[100][2]; @@ -154,35 +158,35 @@ Move retMove, moveStack[10000], path[100], repStack[300], pv[1000], repeatMove[3 #define FVAL 500 /* piece value of Fire Demon. Used in code for recognizing moves with it and do burns */ PieceDesc chuPieces[] = { - {"LN", "", LVAL, { L,L,L,L,L,L,L,L } }, // lion - {"FK", "", 60, { X,X,X,X,X,X,X,X } }, // free king - {"SE", "", 55, { X,D,X,X,X,X,X,D } }, // soaring eagle - {"HF", "", 50, { D,X,X,X,X,X,X,X } }, // horned falcon - {"FO", "", 40, { X,X,0,X,X,X,0,X } }, // flying ox - {"FB", "", 40, { 0,X,X,X,0,X,X,X } }, // free boar - {"DK", "SE", 40, { X,1,X,1,X,1,X,1 } }, // dragon king - {"DH", "HF", 35, { 1,X,1,X,1,X,1,X } }, // dragon horse - {"WH", "", 35, { X,X,0,0,X,0,0,X } }, // white horse - {"R", "DK", 30, { X,0,X,0,X,0,X,0 } }, // rook - {"FS", "", 30, { X,1,1,1,X,1,1,1 } }, // flying stag - {"WL", "", 25, { X,0,0,X,X,X,0,0 } }, // whale - {"K", "", 28, { 1,1,1,1,1,1,1,1 }, 4 }, // king - {"CP", "", 27, { 1,1,1,1,1,1,1,1 }, 4 }, // king - {"B", "DH", 25, { 0,X,0,X,0,X,0,X } }, // bishop - {"VM", "FO", 20, { X,0,1,0,X,0,1,0 } }, // vertical mover - {"SM", "FB", 20, { 1,0,X,0,1,0,X,0 } }, // side mover - {"DE", "CP", 20, { 1,1,1,1,0,1,1,1 } }, // drunk elephant - {"BT", "FS", 15, { 0,1,1,1,1,1,1,1 } }, // blind tiger - {"G", "R", 15, { 1,1,1,0,1,0,1,1 } }, // gold - {"FL", "B", 15, { 1,1,0,1,1,1,0,1 } }, // ferocious leopard - {"KN", "LN", 15, { J,1,J,1,J,1,J,1 } }, // kirin - {"PH", "FK", 15, { 1,J,1,J,1,J,1,J } }, // phoenix - {"RV", "WL", 15, { X,0,0,0,X,0,0,0 } }, // reverse chariot - {"L", "WH", 15, { X,0,0,0,0,0,0,0 } }, // lance - {"S", "VM", 10, { 1,1,0,1,0,1,0,1 } }, // silver - {"C", "SM", 10, { 1,1,0,0,1,0,0,1 } }, // copper - {"GB", "DE", 5, { 1,0,0,0,1,0,0,0 } }, // go between - {"P", "G", 4, { 1,0,0,0,0,0,0,0 } }, // pawn + {"LN", "", LVAL, { L,L,L,L,L,L,L,L }, 4 }, // lion + {"FK", "", 60, { X,X,X,X,X,X,X,X }, 4 }, // free king + {"SE", "", 55, { X,D,X,X,X,X,X,D }, 4 }, // soaring eagle + {"HF", "", 50, { D,X,X,X,X,X,X,X }, 4 }, // horned falcon + {"FO", "", 40, { X,X,0,X,X,X,0,X }, 4 }, // flying ox + {"FB", "", 40, { 0,X,X,X,0,X,X,X }, 4 }, // free boar + {"DK", "SE", 40, { X,1,X,1,X,1,X,1 }, 4 }, // dragon king + {"DH", "HF", 35, { 1,X,1,X,1,X,1,X }, 4 }, // dragon horse + {"WH", "", 35, { X,X,0,0,X,0,0,X }, 3 }, // white horse + {"R", "DK", 30, { X,0,X,0,X,0,X,0 }, 4 }, // rook + {"FS", "", 30, { X,1,1,1,X,1,1,1 }, 3 }, // flying stag + {"WL", "", 25, { X,0,0,X,X,X,0,0 }, 4 }, // whale + {"K", "", 28, { 1,1,1,1,1,1,1,1 }, 2, 4 }, // king + {"CP", "", 27, { 1,1,1,1,1,1,1,1 }, 2, 4 }, // king + {"B", "DH", 25, { 0,X,0,X,0,X,0,X }, 2 }, // bishop + {"VM", "FO", 20, { X,0,1,0,X,0,1,0 }, 2 }, // vertical mover + {"SM", "FB", 20, { 1,0,X,0,1,0,X,0 }, 6 }, // side mover + {"DE", "CP", 20, { 1,1,1,1,0,1,1,1 }, 2 }, // drunk elephant + {"BT", "FS", 15, { 0,1,1,1,1,1,1,1 }, 2 }, // blind tiger + {"G", "R", 15, { 1,1,1,0,1,0,1,1 }, 2 }, // gold + {"FL", "B", 15, { 1,1,0,1,1,1,0,1 }, 2 }, // ferocious leopard + {"KN", "LN", 15, { J,1,J,1,J,1,J,1 }, 2 }, // kirin + {"PH", "FK", 15, { 1,J,1,J,1,J,1,J }, 2 }, // phoenix + {"RV", "WL", 15, { X,0,0,0,X,0,0,0 }, 1 }, // reverse chariot + {"L", "WH", 15, { X,0,0,0,0,0,0,0 }, 1 }, // lance + {"S", "VM", 10, { 1,1,0,1,0,1,0,1 }, 2 }, // silver + {"C", "SM", 10, { 1,1,0,0,1,0,0,1 }, 2 }, // copper + {"GB", "DE", 5, { 1,0,0,0,1,0,0,0 }, 1 }, // go between + {"P", "G", 4, { 1,0,0,0,0,0,0,0 }, 2 }, // pawn { NULL } // sentinel }; @@ -203,14 +207,14 @@ PieceDesc shoPieces[] = { }; PieceDesc daiPieces[] = { - {"FD", "G", 15, { 0,2,0,2,0,2,0,2 } }, // Flying Dragon - {"VO", "G", 20, { 2,0,2,0,2,0,2,0 } }, // Violent Ox - {"EW", "G", 8, { 1,1,1,0,0,0,1,1 } }, // Evil Wolf - {"CS", "G", 7, { 0,1,0,1,0,1,0,1 } }, // Cat Sword - {"AB", "G", 6, { 1,0,1,0,1,0,1,0 } }, // Angry Boar - {"I", "G", 8, { 1,1,0,0,0,0,0,1 } }, // Iron - {"N", "G", 6, { N,0,0,0,0,0,0,N } }, // Knight - {"ST", "G", 5, { 0,1,0,0,0,0,0,1 } }, // Stone + {"FD", "G", 15, { 0,2,0,2,0,2,0,2 }, 2 }, // Flying Dragon + {"VO", "G", 20, { 2,0,2,0,2,0,2,0 }, 2 }, // Violent Ox + {"EW", "G", 8, { 1,1,1,0,0,0,1,1 }, 2 }, // Evil Wolf + {"CS", "G", 7, { 0,1,0,1,0,1,0,1 }, 1 }, // Cat Sword + {"AB", "G", 6, { 1,0,1,0,1,0,1,0 }, 1 }, // Angry Boar + {"I", "G", 8, { 1,1,0,0,0,0,0,1 }, 2 }, // Iron + {"N", "G", 6, { N,0,0,0,0,0,0,N }, 0 }, // Knight + {"ST", "G", 5, { 0,1,0,0,0,0,0,1 }, 0 }, // Stone { NULL } // sentinel }; @@ -230,6 +234,7 @@ PieceDesc ddPieces[] = { {"WB", "FT", 1, { 2,X,X,X,2,X,X,X } }, // Water Buffalo {"RB", "FR", 1, { X,X,X,X,0,X,X,X } }, // Rushing Bird {"SB", "", 1, { X,X,2,2,2,2,2,X } }, // Standard Bearer + {"FH", "FK", 1, { 1,2,1,0,1,0,1,2 } }, // Flying Horse {"NK", "SB", 1, { 1,1,1,1,1,1,1,1 } }, // Neighbor King {"BM", "MW", 1, { 0,1,1,1,0,1,1,1 } }, // Blind Monkey @@ -327,10 +332,10 @@ PieceDesc taiPieces[] = { PieceDesc tenjikuPieces[] = { // only those not in Chu, or different (because of different promotion) {"FI", "", FVAL, { X,X,0,X,X,X,0,X } }, // Fire Demon - {"GG", "", 150, { R,R,R,R,R,R,R,R }, 3 }, // Great General - {"VG", "", 140, { 0,R,0,R,0,R,0,R }, 2 }, // Vice General - {"RG", "GG",120, { R,0,R,0,R,0,R,0 }, 1 }, // Rook General - {"BG", "VG",110, { 0,R,0,R,0,R,0,R }, 1 }, // Bishop General + {"GG", "", 150, { R,R,R,R,R,R,R,R }, 0, 3 }, // Great General + {"VG", "", 140, { 0,R,0,R,0,R,0,R }, 0, 2 }, // Vice General + {"RG", "GG",120, { R,0,R,0,R,0,R,0 }, 0, 1 }, // Rook General + {"BG", "VG",110, { 0,R,0,R,0,R,0,R }, 0, 1 }, // Bishop General {"SE", "RG", 1, { X,D,X,X,X,X,X,D } }, // Soaring Eagle {"HF", "BG", 1, { D,X,X,X,X,X,X,X } }, // Horned Falcon {"LH", "", 1, { L,S,L,S,L,S,L,S } }, // Lion-Hawk @@ -535,6 +540,8 @@ typedef struct { char qval; char mobility; char mobWeight; + unsigned char promoGain; + char bulk; } PieceInfo; // piece-list entry int last[2], royal[2]; @@ -557,6 +564,7 @@ typedef struct { int postThinking; int resign; // engine-defined option int contemptFactor; // likewise + int seed; int squareKey[BSIZE]; @@ -566,7 +574,7 @@ int attackMaps[200*BSIZE], *attacks = attackMaps; char distance[2*BSIZE]; // distance table char promoBoard[BSIZE]; // flags to indicate promotion zones char rawFire[BSIZE+2*BWMAX]; // flags to indicate squares controlled by Fire Demons -signed char PST[2*BSIZE]; +signed char PST[3*BSIZE]; #define board (rawBoard + 6*BHMAX + 3) #define fireBoard (rawFire + BWMAX + 1) @@ -638,6 +646,22 @@ Worse (int a, int b) return 0; } +#if 0 +int +Lance (signed char *r) +{ // File-bound forward slider + int i; + for(i=1; i<4; i++) if(r[i] || r[i+4]) return 0; + return r[0] == X; +} +#endif +int +EasyProm (signed char *r) +{ + int i; + return r[0] == X || r[1] == X || r[7] == X; +} + int IsUpwardCompatible (signed char *r, signed char *s) { @@ -721,9 +745,12 @@ AddPiece (int stm, PieceDesc *list) } key = (stm == WHITE ? &list->whiteKey : &list->blackKey); if(!*key) *key = ~(myRandom()*myRandom()); + p[i].promoGain = EasyProm(list->range); // flag easy promotion based on white view p[i].pieceKey = *key; p[i].promoFlag = 0; + p[i].bulk = list->bulk; p[i].mobWeight = v > 600 ? 0 : v >= 400 ? 1 : v >= 300 ? 2 : v > 150 ? 3 : v >= 100 ? 2 : 0; +// if(Lance(list->range)) p[i].mobWeight = 5, p[i].pst = 0; // clear path but don't move forward for(j=stm+2; j<= last[stm]; j+=2) { if(p[j].promo >= i) p[j].promo += 2; } @@ -790,8 +817,24 @@ SetUp(char *array, int var) n <<= 1; } for(i=0; i 0) + p[i].promoGain = (p[j].value - p[i].value - 30)*1.25, p[i].value = p[j].value - 30; + else p[i].promoGain = 0; + board[p[i].pos] = i; + rootEval += p[i].value + PST[p[i].pst + p[i].pos]; + promoDelta += p[i].promoGain; + filling += p[i].bulk; + } else p[i].promoGain = 0; + for(i=BLACK+2; i<=last[BLACK]; i+=2) if(p[i].pos != ABSENT) { + if(p[i].promoGain && (j = p[i].promo) > 0) + p[i].promoGain = (p[j].value - p[i].value - 30)*1.25, p[i].value = p[j].value - 30; + else p[i].promoGain = 0; + board[p[i].pos] = i; + rootEval -= p[i].value + PST[p[i].pst + p[i].pos]; + promoDelta -= p[i].promoGain; + filling += p[i].bulk; + } else p[i].promoGain = 0; StackMultis(WHITE); StackMultis(BLACK); stm = WHITE; xstm = BLACK; @@ -842,10 +885,10 @@ Init (int var) for(i=0; i<2*BSIZE; i++) { distance[i] = 0; } - for(i=0; i<8; i++) - for(j=1; j abs(j) ? abs(i) : abs(j); // hash key tables @@ -870,9 +913,11 @@ Init (int var) for(i=0; i BH-4 ? (i < 3 ? 5 : i == 3 ? 2 : i == 4 ? 1 : 0) : 0; } p[EDGE].qval = 5; // tenjiku jump-capturer sentinel @@ -892,6 +937,20 @@ PSTest () return tot; } +int +Dtest () +{ + int r, f, score, tot=0; + for(r=0; rpiece = board[u->from]; board[u->from] = EMPTY; u->booty = 0; + u->gain = 0; + u->loss = 0; u->revMoveCount = cnt50++; u->savKeyL = hashKeyL; u->savKeyH = hashKeyH; u->epVictim[0] = EMPTY; + u->saveDelta = promoDelta; + u->filling = filling; if(p[u->piece].promoFlag & LAST_RANK) cnt50 = 0; // forward piece: move is irreversible // TODO: put in some test for forward moves of non-backward pieces? @@ -1357,6 +1420,12 @@ MakeMove(Move m, UndoInfo *u) u->to = u->from + toList[u->to - SPECIAL]; u->booty += p[u->epVictim[1]].value + PST[p[u->epVictim[1]].pst + u->ep2Square]; u->booty += p[u->epVictim[0]].value + PST[p[u->epVictim[0]].pst + u->epSquare]; + u->gain += p[u->epVictim[1]].value; + u->gain += p[u->epVictim[0]].value; + promoDelta += p[u->epVictim[0]].promoGain; + promoDelta += p[u->epVictim[1]].promoGain; + filling -= p[u->epVictim[0]].bulk; + filling -= p[u->epVictim[1]].bulk; hashKeyL ^= p[u->epVictim[0]].pieceKey * squareKey[u->epSquare]; hashKeyH ^= p[u->epVictim[0]].pieceKey * squareKey[u->epSquare+BH]; hashKeyL ^= p[u->epVictim[1]].pieceKey * squareKey[u->ep2Square]; @@ -1381,6 +1450,9 @@ MakeMove(Move m, UndoInfo *u) board[x] = EMPTY; // remove it p[burnVictim].pos = ABSENT; u->booty += p[burnVictim].value + PST[p[burnVictim].pst + x]; + u->gain += p[burnVictim].value; + promoDelta += p[burnVictim].promoGain; + filling -= p[burnVictim].bulk; hashKeyL ^= p[burnVictim].pieceKey * squareKey[x]; hashKeyH ^= p[burnVictim].pieceKey * squareKey[x + BH]; cnt50 = 0; // actually burning something makes the move irreversible @@ -1393,11 +1465,18 @@ MakeMove(Move m, UndoInfo *u) u->victim = board[u->to]; p[u->victim].pos = ABSENT; + filling += p[u->new].bulk - p[u->piece].bulk - p[u->victim].bulk; + promoDelta += p[u->new].promoGain - p[u->piece].promoGain + p[u->victim].promoGain; u->booty += p[u->victim].value + PST[p[u->victim].pst + u->to]; - if(u->victim != EMPTY) cnt50 = 0; // capture irreversible + u->gain += p[u->victim].value; + if(u->victim != EMPTY) { + cnt50 = 0; // capture irreversible + if(attacks[2*u->to + xstm]) u->loss = p[u->piece].value; // protected + } p[u->new].pos = u->to; board[u->to] = u->new; + promoDelta = -promoDelta; hashKeyL ^= p[u->new].pieceKey * squareKey[u->to] ^ p[u->piece].pieceKey * squareKey[u->from] @@ -1444,6 +1523,8 @@ UnMake(UndoInfo *u) cnt50 = u->revMoveCount; hashKeyL = u->savKeyL; hashKeyH = u->savKeyH; + filling = u->filling; + promoDelta = u->saveDelta; } void @@ -1570,9 +1651,22 @@ GenCapts(int sqr, int victimValue) } int -Evaluate () +Evaluate (int difEval) { - return (stm ? mobilityScore : -mobilityScore); + int wLion, bLion, score=mobilityScore; + +#ifdef LIONTRAP +#define lionTrap (PST + 2*BH*BW) + // penalty for Lion in enemy corner, when enemy Lion is nearby + if(p[WHITE+2].value == 10*LVAL && (wLion = p[WHITE+2].pos) != ABSENT) + if(p[BLACK+2].value == 10*LVAL && (bLion = p[BLACK+2].pos) != ABSENT) { // both have a Lion + static int distFac[36] = { 0, 0, 10, 9, 8, 7, 5, 3, 1 }; + score -= ( (1+9*!attacks[2*wLion+WHITE]) * lionTrap[BW*(BH-1)+BH-1-wLion] + - (1+9*!attacks[2*bLion+BLACK]) * lionTrap[bLion] ) * distFac[dist[wLion - bLion]]; + } +#endif + + return difEval - (filling*filling*promoDelta >> 16) + (stm ? score : -score); } inline void @@ -1585,13 +1679,14 @@ FireSet (UndoInfo *tb) void TerminationCheck(); -#define QSdepth 0 +#define QSdepth 4 int -Search (int alpha, int beta, int difEval, int depth, int oldPromo, int promoSuppress) +Search (int alpha, int beta, int difEval, int depth, int oldPromo, int promoSuppress, int threshold) { - int i, j, k, firstMove, oldMSP = msp, curMove, sorted, bad, phase, king, iterDep, replyDep, nextVictim, to, defer, dubious, bestMoveNr; - int resDep; + int i, j, k, phase, king, nextVictim, to, defer, autoFail=0; + int firstMove, oldMSP = msp, curMove, sorted, bad, dubious, bestMoveNr; + int resDep, iterDep, ext; int myPV = pvPtr; int score, bestScore, oldBest, curEval, iterAlpha; Move move, nullMove; @@ -1599,9 +1694,19 @@ Search (int alpha, int beta, int difEval, int depth, int oldPromo, int promoSupp #ifdef HASH Move hashMove; int index, nr, hit; #endif -if(PATH) /*pboard(board),pmap(attacks, BLACK),*/printf("search(%d) {%d,%d} eval=%d, stm=%d\n",depth,alpha,beta,difEval,stm),fflush(stdout); +if(PATH) /*pboard(board),pmap(attacks, BLACK),*/printf("search(%d) {%d,%d} eval=%d, stm=%d (flag=%d)\n",depth,alpha,beta,difEval,stm,abortFlag),fflush(stdout); xstm = stm ^ WHITE; //printf("map made\n");fflush(stdout); + + // TSUME filter + if(tsume && tsume & stm+1) { + k = p[king=royal[stm]].pos; +// if( k == ABSENT) k = p[king + 2].pos; + if( k != ABSENT && !attacks[2*k + xstm]) { + retDep = 60; return INF; // we win when not in check + } + } + // KING CAPTURE k = p[king=royal[xstm]].pos; if( k != ABSENT) { @@ -1614,7 +1719,7 @@ if(PATH) /*pboard(board),pmap(attacks, BLACK),*/printf("search(%d) {%d,%d} eval= } //printf("King safe\n");fflush(stdout); // EVALUATION & WINDOW SHIFT - curEval = difEval + Evaluate(); + curEval = Evaluate(difEval); alpha -= (alpha < curEval); beta -= (beta <= curEval); @@ -1623,41 +1728,56 @@ if(PATH) /*pboard(board),pmap(attacks, BLACK),*/printf("search(%d) {%d,%d} eval= firstMove = curMove = sorted = msp += 50; // leave 50 empty slots in front of move list - iterDep = 0; tb.fireMask = phase = 0; + iterDep = -(depth == 0); tb.fireMask = phase = 0; #ifdef HASH - index = hashKeyL & hashMask; nr = hashKeyL >> 30; hit = -1; + index = (hashKeyL ^ 327*stm ^ oldPromo*(63121 + promoSuppress)) & hashMask; + nr = (hashKeyL >> 30) & 3; hit = -1; if(hashTable[index].lock[nr] == hashKeyH) hit = nr; else if(hashTable[index].lock[4] == hashKeyH) hit = 4; +if(PATH) printf("# probe hash index=%x hit=%d\n", index, hit),fflush(stdout); if(hit >= 0) { bestScore = hashTable[index].score[hit]; + hashMove = hashTable[index].move[hit]; if((bestScore <= alpha || hashTable[index].flag[hit] & H_LOWER) && (bestScore >= beta || hashTable[index].flag[hit] & H_UPPER) ) { - iterDep = hashTable[index].depth[hit]; + iterDep = resDep = hashTable[index].depth[hit]; bestMoveNr = 0; + if(!level) iterDep = 0; // no hash cutoff in root } } else { // decide on replacement if(depth >= hashTable[index].depth[nr]) hit = nr; else hit = 4; + hashMove = 0; } +if(PATH) printf("# iterDep = %d score = %d move = %s\n",iterDep,bestScore,MoveToText(hashMove,0)),fflush(stdout); #endif - replyDep = (depth < 1 ? depth : iterDep < 1 ? 1 : iterDep); + if(depth > QSdepth && iterDep < QSdepth) iterDep = QSdepth; // full-width: start at least from 1-ply +if(PATH)printf("iterDep=%d\n", iterDep); while(++iterDep <= depth) { if(flag && depth>= 0) printf("iter %d:%d\n", depth,iterDep),fflush(stdout); + oldBest = bestScore; iterAlpha = alpha; bestScore = -INF; bestMoveNr = 0; resDep = 60; +if(PATH)printf("new iter %d\n", iterDep); + if(depth <= QSdepth) { + bestScore = curEval; resDep = QSdepth; + if(bestScore > alpha) { + alpha = bestScore; +if(PATH)printf("stand pat %d\n", bestScore); + if(bestScore >= beta) goto cutoff; + } + } for(curMove = firstMove; ; curMove++) { // loop over moves if(flag && depth>= 0) printf("phase=%d: first/curr/last = %d / %d / %d\n", phase, firstMove, curMove, msp);fflush(stdout); // MOVE SOURCE if(curMove >= msp) { // we ran out of moves; generate some new +if(PATH)printf("new moves, phase=%d\n", phase); switch(phase) { case 0: // null move - if(depth <= 0) { - bestScore = curEval; resDep = QSdepth; - if(bestScore >= beta || depth < -1) goto cutoff; - } #ifdef NULLMOVE - else if(curEval >= beta) { + if(depth > QSdepth && curEval >= beta) { + int nullDep = depth - 3; stm ^= WHITE; - score = -Search(-beta, 1-beta, -difEval, depth > 3 ? depth-3 : 0, promoSuppress & SQUARE, ABSENT); + score = -Search(-beta, 1-beta, -difEval, nullDep= beta) { msp = oldMSP; retDep += 3; return score + (score < curEval); } } @@ -1666,15 +1786,16 @@ if(flag && depth>= 0) printf("phase=%d: first/curr/last = %d / %d / %d\n", phase //if(PATH) printf("mask=%x\n",tb.fireMask),pbytes(fireBoard); phase = 1; case 1: // hash move + phase = 2; #ifdef HASH - if(hashMove) { + if(hashMove && (depth > QSdepth || // must be capture in QS + (hashMove & SQUARE) >= SPECIAL || board[hashMove & SQUARE] != EMPTY)) { moveStack[sorted = msp++] = hashMove; goto extractMove; } #endif - phase = 2; case 2: // capture-gen init - nextVictim = xstm; + nextVictim = xstm; autoFail = (depth == 0); phase = 3; case 3: // generate captures if(PATH) printf("%d:%2d:%2d next victim %d/%d\n",level,depth,iterDep,curMove,msp); @@ -1686,7 +1807,7 @@ if(PATH) printf("%d:%2d:%2d next victim %d/%d\n",level,depth,iterDep,curMove,msp if(iterDep <= QSdepth + 1 && 2*group + curEval + 30 < alpha) { resDep = QSdepth + 1; goto cutoff; } if(PATH) printf("%d:%2d:%2d group=%d, to=%c%d\n",level,depth,iterDep,group,to%BW+'a',to/BW+ONE); GenCapts(to, 0); -if(PATH) printf("%d:%2d:%2d msp=%d\n",level,depth,iterDep,msp); +if(PATH) printf("%d:%2d:%2d first=%d msp=%d\n",level,depth,iterDep,firstMove,msp); while(nextVictim < last[xstm] && p[nextVictim+2].value == group) { // more victims of same value exist to = p[nextVictim += 2].pos; // take next if(to == ABSENT) continue; // ignore if absent @@ -1695,8 +1816,13 @@ if(PATH) printf("%d:%2d:%2d p=%d, to=%c%d\n",level,depth,iterDep,nextVictim,to%B GenCapts(to, 0); if(PATH) printf("%d:%2d:%2d msp=%d\n",level,depth,iterDep,msp); } -//printf("captures on %d generated, msp=%d\n", nextVictim, msp); - goto extractMove; +if(PATH) printf("captures on %d generated, msp=%d, group=%d, threshold=%d\n", nextVictim, msp, group, threshold); + goto extractMove; // in auto-fail phase, only search if they might auto-fail-hi + } +if(PATH) printf("# autofail=%d\n", autoFail); + if(autoFail) { // non-captures cannot auto-fail; flush queued captures first +if(PATH) printf("# autofail end (%d-%d)\n", firstMove, msp); + autoFail = 0; curMove = firstMove - 1; continue; // release stashed moves for search } // if(currentVariant == V_CHESS && promoSuppress != ABSENT) { // e.p. // int n = board[promoSuppress-1]; @@ -1711,7 +1837,7 @@ if(PATH) printf("%d:%2d:%2d msp=%d\n",level,depth,iterDep,msp); #endif phase = 5; case 5: // killers - if(depth <= QSdepth) { resDep = QSdepth; goto cutoff; } + if(depth <= QSdepth) { if(resDep > QSdepth) resDep = QSdepth; goto cutoff; } phase = 6; case 6: // non-captures nonCapts = msp; @@ -1741,7 +1867,7 @@ if(PATH) printf("%d:%2d:%2d msp=%d\n",level,depth,iterDep,msp); // MOVE EXTRACTION extractMove: -if(flag & depth >= 0) printf("%2d:%d extract %d/%d\n", depth, iterDep, curMove, msp); +//if(flag & depth >= 0 || (PATH)) printf("%2d:%d extract %d/%d\n", depth, iterDep, curMove, msp); if(curMove > sorted) { move = moveStack[sorted=j=curMove]; for(i=curMove+1; i= 0) printf("%2d:%d found %d/%d %08x %s\n", depth, iterDep, cur // RECURSION stm ^= WHITE; defer = MakeMove(move, &tb); + ext = (depth == 0); // when out of depth we extend captures if there was no auto-fail-hi + +// if(level == 1 && randomize) tb.booty += (hashKeyH * seed >> 24 & 31) - 20; + + if(autoFail) { + UnMake(&tb); // never search moves during auto-fail phase + xstm = stm; stm ^= WHITE; + if(tb.gain <= threshold) { // we got to moves that cannot possibly auto-fail + autoFail = 0; curMove = firstMove-1; continue; // release all for search + } + if(tb.gain - tb.loss > threshold) { + bestScore = INF+1; resDep = 0; goto leave; // auto-fail-hi + } else continue; // ignore for now if not obvious refutation + } if(flag & depth >= 0) printf("%2d:%d made %d/%d %s\n", depth, iterDep, curMove, msp, MoveToText(moveStack[curMove], 0)); for(i=2; i<=cnt50; i+=2) if(repStack[level-i+200] == hashKeyH) { @@ -1767,7 +1907,7 @@ if(flag & depth >= 0) printf("%2d:%d made %d/%d %s\n", depth, iterDep, curMove, } repStack[level+200] = hashKeyH; -if(PATH) printf("%d:%2d:%d %3d %6x %-10s %6d %6d\n", level, depth, iterDep, curMove, moveStack[curMove], MoveToText(moveStack[curMove], 0), score, bestScore); +if(PATH) printf("%d:%2d:%d %3d %6x %-10s %6d %6d\n", level, depth, iterDep, curMove, moveStack[curMove], MoveToText(moveStack[curMove], 0), score, bestScore),fflush(stdout); path[level++] = move; attacks += 2*bsize; MapFromScratch(attacks); // for as long as incremental update does not work. @@ -1789,7 +1929,7 @@ MapFromScratch(attacks); // for as long as incremental update does not work. } } #if 1 - score = -Search(-beta, -iterAlpha, -difEval - tb.booty, replyDep, promoSuppress & ~PROMOTE, defer); + score = -Search(-beta, -iterAlpha, -difEval - tb.booty, iterDep-1+ext, promoSuppress & ~PROMOTE, defer, depth ? INF : tb.gain); #else score = 0; #endif @@ -1805,7 +1945,7 @@ printf("# abort (%d) @ %d\n", abortFlag, level); goto leave; } #if 1 -if(PATH) printf("%d:%2d:%d %3d %6x %-10s %6d %6d\n", level, depth, iterDep, curMove, moveStack[curMove], MoveToText(moveStack[curMove], 0), score, bestScore); +if(PATH) printf("%d:%2d:%d %3d %6x %-10s %6d %6d (%d)\n", level, depth, iterDep, curMove, moveStack[curMove], MoveToText(moveStack[curMove], 0), score, bestScore, GetTickCount()),fflush(stdout); // ALPHA-BETA STUFF if(score > bestScore) { @@ -1825,12 +1965,13 @@ if(PATH) printf("%d:%2d:%d %3d %6x %-10s %6d %6d\n", level, depth, iterDep, curM bestMoveNr = firstMove; if(score >= beta) { // beta cutoff #ifdef KILLERS - if(iterDep == depth && move != killer[level][0]) { + if(iterDep == depth && move != killer[level][0] + && (tb.victim == EMPTY && (move & SQUARE) < SPECIAL)) { // update killer killer[level][1] = killer[level][0]; killer[level][0] = move; } #endif - resDep = retDep; + resDep = retDep+1-ext; goto cutoff; } { int i=pvPtr; @@ -1840,26 +1981,29 @@ if(PATH) printf("%d:%2d:%d %3d %6x %-10s %6d %6d\n", level, depth, iterDep, curM } } - if(retDep < resDep) resDep = retDep; + if(retDep+1-ext < resDep) resDep = retDep+1-ext; #endif } // next move cutoff: if(!level) { // root node + lastRootIter = GetTickCount() - startTime; if(postThinking > 0) { int i; // WB thinking output - printf("%d %d %d %d", iterDep, bestScore, (GetTickCount() - startTime)/10, nodes); + printf("%d %d %d %d", iterDep-QSdepth, bestScore, lastRootIter/10, nodes); + if(ponderMove) printf(" (%s)", MoveToText(ponderMove, 0)); for(i=0; pv[i]; i++) printf(" %s", MoveToText(pv[i], 0)); - if(iterDep == 1) printf(" { root eval = %4.2f dif = %4.2f; abs = %4.2f}", curEval/100., difEval/100., PSTest()/100.); + if(iterDep == QSdepth+1) printf(" { root eval = %4.2f dif = %4.2f; abs = %4.2f f=%d D=%4.2f/%4.2f}", curEval/100., difEval/100., PSTest()/100., filling, promoDelta/100., Dtest()/100.); printf("\n"); fflush(stdout); } if(!(abortFlag & 1) && GetTickCount() - startTime > tlim1) break; // do not start iteration we can (most likely) not finish } - replyDep = iterDep; + if(resDep > iterDep) iterDep = resDep; // skip iterations if we got them for free #ifdef HASH // hash store hashTable[index].lock[hit] = hashKeyH; hashTable[index].depth[hit] = iterDep; + hashTable[index].score[hit] = bestScore; hashTable[index].flag[hit] = (bestScore < beta) * H_UPPER; if(bestScore > alpha) { hashTable[index].flag[hit] |= H_LOWER; @@ -1873,8 +2017,8 @@ leave: msp = oldMSP; // pop move list pvPtr = myPV; // pop PV retMove = bestMoveNr ? moveStack[bestMoveNr] : 0; - retDep = resDep + 1; -if(PATH) printf("return %d: %d %d\n", depth, bestScore, curEval); + retDep = resDep; +if(PATH) printf("return %d: %d %d (t=%d s=%d lim=%d)\n", depth, bestScore, curEval, GetTickCount(), startTime, tlim1),fflush(stdout); return bestScore + (bestScore < curEval); } @@ -1883,7 +2027,7 @@ pplist() { int i, j; for(i=0; i<182; i++) { - printf("%3d. %3d %3d %4d %02x %d ", i, p[i].value, p[i].promo, p[i].pos, p[i].promoFlag&255, p[i].qval); + printf("%3d. %3d %3d %4d %02x %d %x %3d ", i, p[i].value, p[i].promo, p[i].pos, p[i].promoFlag&255, p[i].qval, p[i].bulk, p[i].promoGain); for(j=0; j<8; j++) printf(" %2d", p[i].range[j]); if(i<2 || i>11) printf("\n"); else printf(" %02x\n", fireFlags[i-2]&255); } @@ -1950,7 +2094,7 @@ pmoves(int start, int end) // some parameter of your engine #define MAXMOVES 2000 /* maximum game length */ - #define MAXPLY 20 /* maximum search depth */ + #define MAXPLY 30 /* maximum search depth */ #define OFF 0 #define ON 1 @@ -2045,9 +2189,10 @@ Setup2 (char *fen) if(q = strchr(fen, ' ')) stm = (q[1] == 'b' ? BLACK : WHITE); // fen contains color field if(strchr(fen, '.') || strchr(fen, ':')) array = fen; else array = Convert(fen); } + rootEval = promoDelta = filling = cnt50 = moveNr = 0; SetUp(array, currentVariant); sup0 = sup1 = sup2 = ABSENT; - rootEval = cnt50 = hashKeyH = hashKeyL = moveNr = 0; + hashKeyH = hashKeyL = 87620895*currentVariant; return stm; } @@ -2056,15 +2201,14 @@ SetMemorySize (int n) { #ifdef HASH static HashBucket *realHash; - static int oldSize; - int m = 1; - intptr_t l; - if(n != oldSize) { + static intptr_t oldSize; + intptr_t l, m = 1; + while(m*sizeof(HashBucket) <= n*512UL) m <<= 1; // take largest power-of-2 that fits + if(m != oldSize) { if(oldSize) free(realHash); - while(m*sizeof(HashBucket) <= n*512) m <<= 1; - m *= 1024; hashMask = m - 1; - realHash = calloc(m + 1, sizeof(HashBucket)); - l = (intptr_t) realHash; hashTable = (HashBucket*) (l & ~63); // align with cache line + hashMask = m*1024 - 1; oldSize = m; + realHash = malloc(m*1024*sizeof(HashBucket) + 64); + l = (intptr_t) realHash; hashTable = (HashBucket*) (l & ~63UL); // align with cache line } #endif } @@ -2115,7 +2259,7 @@ ListMoves () for(i=0; i< BSIZE; i++) boardCopy[i] = !!board[i]; MapFromScratch(attacks); postThinking--; repCnt = 0; tlim1 = tlim2 = tlim3 = 1e8; abortFlag = msp = 0; - Search(-INF-1, INF+1, 0, 1, sup1 & ~PROMOTE, sup2); + Search(-INF-1, INF+1, 0, QSdepth+1, sup1 & ~PROMOTE, sup2, INF); postThinking++; listStart = retFirst; listEnd = msp = retMSP; } @@ -2241,31 +2385,28 @@ SetSearchTimes (int timeLeft) tlim1 = 0.2*targetTime; tlim2 = 1.9*targetTime; tlim3 = 5*timeLeft / (movesLeft + 4.1); +printf("# limits %d, %d, %d mode = %d\n", tlim1, tlim2, tlim3, abortFlag); } int SearchBestMove (MOVE *move, MOVE *ponderMove) { int score; +printf("# SearchBestMove\n"); startTime = GetTickCount(); nodes = 0; +printf("# s=%d\n", startTime);fflush(stdout); MapFromScratch(attacks); retMove = INVALID; repCnt = 0; - score = Search(-INF-1, INF+1, rootEval, maxDepth, sup1, sup2); + score = Search(-INF-1, INF+1, rootEval, maxDepth, sup1, sup2, INF); *move = retMove; *ponderMove = pv[1]; +printf("# best=%s\n", MoveToText(pv[0],0)); +printf("# ponder=%s\n", MoveToText(pv[1],0)); return score; } -void -PonderUntilInput (int stm) -{ -MapFromScratch(attacks); - repCnt = 0; abortFlag = -1; - Search(-INF-1, INF+1, rootEval, maxDepth, sup1, sup2); -} - int TakeBack(int n) { // reset the game and then replay it to the desired point int last, stm; @@ -2301,6 +2442,17 @@ printf("# in (mode = %d,%d): %s\n", root, abortFlag, command); if(!strcmp(command, "put")) { ReadSquare(inBuf+4, &lastPut); continue; } // ditto if(!strcmp(command, ".")) { inBuf[0] = 0; return; } // ignore for now if(!strcmp(command, "lift")) { inBuf[0] = 0; Highlight(inBuf+5); return; } // treat here + if(!root && !strcmp(command, "usermove")) { +printf("# move = %s#ponder = %s", inBuf+9, ponderMoveText); + abortFlag = !!strcmp(inBuf+9, ponderMoveText); + if(!abortFlag) { // ponder hit, continue as time-based search +printf("# ponder hit\n"); + SetSearchTimes(10*timeLeft + GetTickCount() - startTime); // add time we already have been pondering to total + if(lastRootIter > tlim1) abortFlag = 2; // abort instantly if we are in iteration we should not have started + inBuf[0] = 0; ponderMove = INVALID; + return; + } + } abortFlag = 1; return; } @@ -2323,21 +2475,33 @@ printf("# in (mode = %d,%d): %s\n", root, abortFlag, command); int i, score, curVarNr; Init(V_CHU); // Chu - listEnd = 1; + seed = GetTickCount(); moveNr = 0; // initialize random while(1) { // infinite loop fflush(stdout); // make sure everything is printed before we do something that might take time - *inBuf = 0; + *inBuf = 0; if(moveNr >= 20) randomize = OFF; +//if(moveNr >20) printf("resign\n"); +#ifdef HASH + if(hashMask) +#endif if(listEnd == 0) ListMoves(); // always maintain a list of legal moves in root position - - abortFlag = 0; - if(stm == engineSide) { // if it is the engine's turn to move, set it thinking, and let it move - + abortFlag = -(ponder && WHITE+BLACK-stm == engineSide && moveNr); // pondering and opponent on move + if(stm == engineSide || abortFlag && ponderMove) { // if it is the engine's turn to move, set it thinking, and let it move +printf("# start search: stm=%d engine=%d (flag=%d)\n", stm, engineSide, abortFlag); + if(abortFlag) { + stm = MakeMove2(stm, ponderMove); // for pondering, play speculative move + gameMove[moveNr++] = ponderMove; // remember in game + sprintf(ponderMoveText, "%s\n", MoveToText(ponderMove, 0)); // for detecting ponder hits +printf("# ponder move = %s", ponderMoveText); + } else SetSearchTimes(10*timeLeft); // for thinking, schedule end time pboard(board); score = SearchBestMove(&move, &ponderMove); - + if(abortFlag == 1) { // ponder search was interrupted (and no hit) + UnMake2(INVALID); moveNr--; stm ^= WHITE; // take ponder move back if we made one + abortFlag = 0; + } else if(move == INVALID) { // game apparently ended int kcapt = 0, xstm = stm ^ WHITE, king, k = p[king=royal[xstm]].pos; if( k != ABSENT) { // test if King capture possible @@ -2357,26 +2521,18 @@ pboard(board); PrintResult(stm, score); } else { stm = MakeMove2(stm, move); // assumes MakeMove returns new side to move - gameMove[moveNr++] = move; // remember game + gameMove[moveNr++] = move; // remember game printf("move %s\n", MoveToText(move, 1)); listEnd = 0; + continue; // go check if we should ponder } - } - - fflush(stdout); // make sure everything is printed before we do something that might take time - - // now it is not our turn (anymore) - if(engineSide == ANALYZE) { // in analysis, we always ponder the position - PonderUntilInput(stm); } else - if(engineSide != NONE && ponder == ON && moveNr != 0) { // ponder while waiting for input - if(ponderMove == INVALID) { // if we have no move to ponder on, ponder the position - PonderUntilInput(stm); - } else { - int newStm = MakeMove2(stm, ponderMove); - PonderUntilInput(newStm); - UnMake2(ponderMove); - } + if(engineSide == ANALYZE || abortFlag) { // in analysis, we always ponder the position + Move dummy; + *ponderMoveText = 0; // forces miss on any move + abortFlag = -1; // set pondering + SearchBestMove(&dummy, &dummy); + abortFlag = 0; // } fflush(stdout); // make sure everything is printed before we do something that might take time @@ -2400,12 +2556,19 @@ pboard(board); printf("feature myname=\"HaChu " VERSION "\" highlight=1\n"); printf("feature option=\"Resign -check 0\"\n"); // example of an engine-defined option printf("feature option=\"Contempt -spin 0 -200 200\"\n"); // and another one + printf("feature option=\"Tsume -combo no /// White Mates /// Black mates\"\n"); printf("feature done=1\n"); continue; } if(!strcmp(command, "option")) { // setting of engine-define option; find out which if(sscanf(inBuf+7, "Resign=%d", &resign) == 1) continue; if(sscanf(inBuf+7, "Contempt=%d", &contemptFactor) == 1) continue; + if(sscanf(inBuf+7, "Tsume=%s", command) == 1) { + if(!strcmp(command, "no")) tsume = 0; else + if(!strcmp(command, "White")) tsume = 1; else + if(!strcmp(command, "Black")) tsume = 2; + continue; + } continue; } if(!strcmp(command, "sd")) { sscanf(inBuf, "sd %d", &maxDepth); continue; } @@ -2450,6 +2613,7 @@ pboard(board); } continue; } + ponderMove = INVALID; // the following commands change the position, invalidating ponder move listEnd = 0; if(!strcmp(command, "new")) { engineSide = BLACK; Init(V_CHESS); stm = Setup2(NULL); maxDepth = MAXPLY; randomize = OFF; curVarNr = comp = 0;