X-Git-Url: http://winboard.nl/cgi-bin?a=blobdiff_plain;f=hachu.c;h=ff3c901210d153ab3d8fb0305f421d929fd8bd75;hb=6b4591303085c6c4c0b7c04a3654c88772a2de84;hp=2133ce97d8fb27ba50024e7504170a0f3df01bc7;hpb=bf370f90ab8ae2a240a4afb0b961c272b8da406b;p=hachu.git diff --git a/hachu.c b/hachu.c index 2133ce9..ff3c901 100644 --- a/hachu.c +++ b/hachu.c @@ -14,9 +14,25 @@ #define VERSION 0.0 -#define PATH level==0 || level==1 && path[0] == 0x55893 +//define PATH level==0 || level==1 && path[0] == 0x55893 +#define PATH 0 #include +#include +#include +#include +#include + +#ifdef WIN32 +# include +#else +# include + int GetTickCount() // with thanks to Tord + { struct timeval t; + gettimeofday(&t, NULL); + return t.tv_sec*1000 + t.tv_usec/1000; + } +#endif #define BW 24 #define BH 12 @@ -62,14 +78,16 @@ typedef struct { char *name, *promoted; int value; signed char range[8]; + int whiteKey, blackKey; } PieceDesc; typedef struct { - int from, to, piece, victim, new, booty, epSquare, epVictim, ep2Square, ep2Victim; + int from, to, piece, victim, new, booty, epSquare, epVictim, ep2Square, ep2Victim, revMoveCount, savKeyL, savKeyH; } UndoInfo; -int stm, xstm, hashKeyH, hashKeyL, framePtr, msp, nonCapts, retMSP, retFirst, level, chuFlag=1; -Move retMove, moveStack[10000], path[100]; +int stm, xstm, hashKeyH, hashKeyL, framePtr, msp, nonCapts, rootEval, retMSP, retFirst, pvPtr, level, cnt50, chuFlag=1; +int nodes, startTime, tlim1, tlim2; +Move retMove, moveStack[10000], path[100], repStack[300], pv[1000]; #define X 36 /* slider */ #define J -1 /* jump */ @@ -403,11 +421,12 @@ signed char PST[2*BSIZE]; #define board (rawBoard + 6*BW + 3) #define dist (distance + BSIZE) -int LookUp(char *name, PieceDesc *list) +PieceDesc * +LookUp (char *name, PieceDesc *list) { // find piece of given name in list of descriptors int i=0; while(list->name && strcmp(name, list->name)) i++, list++; - return (list->name == NULL ? -1 : i); + return (list->name == NULL ? NULL : list); } void @@ -490,21 +509,24 @@ Compactify (int stm) } int -AddPiece (int stm, int n, PieceDesc *list) +AddPiece (int stm, PieceDesc *list) { - int i, j; + int i, j, *key; for(i=stm+2; i<=last[stm]; i += 2) { - if(p[i].value < 10*list[n].value || p[i].value == 10*list[n].value && (p[i].promo < 0)) break; + if(p[i].value < 10*list->value || p[i].value == 10*list->value && (p[i].promo < 0)) break; } last[stm] += 2; for(j=last[stm]; j>i; j-= 2) p[j] = p[j-2]; - p[i].value = 10*list[n].value; - for(j=0; j<8; j++) p[i].range[j] = list[n].range[j^4*(WHITE-stm)]; + p[i].value = 10*list->value; + for(j=0; j<8; j++) p[i].range[j] = list->range[j^4*(WHITE-stm)]; switch(Range(p[i].range)) { case 1: p[i].pst = BH; break; case 2: p[i].pst = BSIZE; break; default: p[i].pst = BSIZE + BH; break; } + key = (stm == WHITE ? &list->whiteKey : &list->blackKey); + if(!*key) *key = ~(myRandom()*myRandom()); + p[i].pieceKey = *key; p[i].promoFlag = 0; for(j=stm+2; j<= last[stm]; j+=2) { if(p[j].promo >= i) p[j].promo += 2; @@ -517,8 +539,9 @@ AddPiece (int stm, int n, PieceDesc *list) void SetUp(char *array, PieceDesc *list) { - int i, j, k, k2, n, m, nr, color; + int i, j, n, m, nr, color; char c, *q, name[3]; + PieceDesc *p1, *p2; last[WHITE] = 1; last[BLACK] = 0; for(i=0; ; i++) { //printf("next rank: %s\n", array); @@ -534,17 +557,17 @@ SetUp(char *array, PieceDesc *list) name[0] += 'A' - 'a'; if(name[1]) name[1] += 'A' - 'a'; } else color = WHITE; - k = LookUp(name, list); - n = AddPiece(color, k, list); + p1 = LookUp(name, list); + n = AddPiece(color, p1); p[n].pos = j; - if(list[k].promoted[0]) { - k2 = LookUp(list[k].promoted, list); - m = AddPiece(color, k2, list); + if(p1->promoted[0]) { + p2 = LookUp(p1->promoted, list); + m = AddPiece(color, p2); if(m <= n) n += 2; p[n].promo = m; - p[n].promoFlag = IsUpwardCompatible(list[k2].range, list[k].range) * DONT_DEFER + CAN_PROMOTE; - if(Forward(list[k].range)) p[n].promoFlag |= LAST_RANK; // Pieces that only move forward can't defer on last rank - if(!strcmp(list[k].name, "N")) p[n].promoFlag |= CANT_DEFER; // Knights can't defer on last 2 ranks + p[n].promoFlag = IsUpwardCompatible(p2->range, p1->range) * DONT_DEFER + CAN_PROMOTE; + if(Forward(p1->range)) p[n].promoFlag |= LAST_RANK; // Pieces that only move forward can't defer on last rank + if(!strcmp(p1->name, "N")) p[n].promoFlag |= CANT_DEFER; // Knights can't defer on last 2 ranks p[n].promoFlag &= n&1 ? P_WHITE : P_BLACK; p[m].promo = -1; p[m].pos = ABSENT; @@ -599,7 +622,6 @@ Init() // hash key tables for(i=0; ipiece = board[u->from]; board[u->from] = EMPTY; u->booty = 0; + u->revMoveCount = cnt50++; + u->savKeyL = hashKeyL; + u->savKeyH = hashKeyH; if(m & (PROMOTE | DEFER)) { if(m & DEFER) { @@ -987,6 +1016,7 @@ MakeMove(Move m, UndoInfo *u) p[u->piece].pos = ABSENT; u->new = p[u->piece].promo; u->booty = p[u->new].value - p[u->piece].value; + cnt50 = 0; // promotion irreversible } } else u->new = u->piece; @@ -1012,12 +1042,13 @@ MakeMove(Move m, UndoInfo *u) hashKeyL ^= p[u->ep2Victim].pieceKey * squareKey[u->ep2Square]; hashKeyH ^= p[u->ep2Victim].pieceKey * squareKey[u->ep2Square+BH]; if(p[u->piece].value != 1000 && p[u->epVictim].value == 1000) deferred |= PROMOTE; // flag non-Lion x Lion + cnt50 = 0; // double capture irreversible } else u->epVictim = EMPTY; u->victim = board[u->to]; p[u->victim].pos = ABSENT; u->booty += p[u->victim].value + PST[p[u->victim].pst + u->to]; -// if(p[u->victim].value == 1000 && p[u->piece].value != 1000) deferred |= PROMOTE; // flag non-Lion x Lion + if(u->victim != EMPTY) cnt50 = 0; // capture irreversible p[u->new].pos = u->to; board[u->to] = u->new; @@ -1048,6 +1079,10 @@ UnMake(UndoInfo *u) p[u->new].pos = ABSENT; p[u->piece].pos = u->from; // this can be the same as above board[u->from] = u->piece; + + cnt50 = u->revMoveCount; + hashKeyL = u->savKeyL; + hashKeyH = u->savKeyH; } void @@ -1160,14 +1195,12 @@ Evaluate () return 0; } -int flag; - int Search (int alpha, int beta, int difEval, int depth, int oldPromo, int promoSuppress) { int i, j, k, firstMove, oldMSP = msp, curMove, sorted, bad, phase, king, iterDep, replyDep, nextVictim, to, defer, dubious, bestMoveNr; - int savHashL = hashKeyL, savHashH = hashKeyH; - int score, bestScore, curEval; + int myPV = pvPtr; + int score, bestScore, curEval, iterAlpha; Move move, nullMove; UndoInfo tb; if(PATH) printf("search(%d) %d-%d eval=%d, stm=%d\n",depth,alpha,beta,difEval,stm),fflush(stdout); @@ -1189,11 +1222,14 @@ if(PATH) printf("search(%d) %d-%d eval=%d, stm=%d\n",depth,alpha,beta,difEval,st alpha -= (alpha < curEval); beta -= (beta <= curEval); - firstMove = curMove = sorted = nonCapts = msp += 20; // leave 20 empty slots in front of move list + nodes++; + pv[pvPtr++] = 0; // start empty PV, directly behind PV of parent + + firstMove = curMove = sorted = msp += 20; // leave 20 empty slots in front of move list phase = 0; iterDep=1; replyDep = (depth < 1 ? depth : 1) - 1; do { if(flag && depth>= 0) printf("iter %d:%d\n", depth,iterDep),fflush(stdout); - bestScore = -INF; bestMoveNr = 0; + iterAlpha = alpha; bestScore = -INF; bestMoveNr = 0; 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 @@ -1207,7 +1243,7 @@ if(flag && depth>= 0) printf("phase=%d: first/curr/last = %d / %d / %d\n", phase #if 0 if(curEval >= beta) { stm ^= WHITE; - score = -Search(-beta, -alpha, difEval, depth-3, promoSuppress & SQUARE, ABSENT); + score = -Search(-beta, -iterAlpha, difEval, depth-3, promoSuppress & SQUARE, ABSENT); stm ^= WHITE; if(score >= beta) { msp = oldMSP; return score + (score < curEval); } } @@ -1246,6 +1282,7 @@ if(flag && depth>= 0) printf("phase=%d: first/curr/last = %d / %d / %d\n", phase if(depth <= 0) goto cutoff; phase = 6; case 6: // non-captures + nonCapts = msp; nullMove = GenNonCapts(oldPromo); phase = 7; sorted = msp; // do not sort noncapts @@ -1271,10 +1308,18 @@ if(flag & depth >= 0) printf("%2d:%d extract %d/%d\n", depth, iterDep, curMove, if(move == 0) continue; // skip invalidated move } if(flag & depth >= 0) printf("%2d:%d found %d/%d\n", depth, iterDep, curMove, msp); + // RECURSION stm ^= WHITE; - defer = MakeMove(moveStack[curMove], &tb); -path[level++] = moveStack[curMove]; + defer = MakeMove(move, &tb); + + for(i=2; i<=cnt50; i+=2) if(repStack[level-i+200] == hashKeyH) { + moveStack[curMove] = 0; // erase forbidden move + score = -INF; goto repetition; + } + repStack[level+200] = hashKeyH; + +path[level++] = move; attacks += 2*BSIZE; MapFromScratch(attacks); // for as long as incremental update does not work. if(PATH) pmap(attacks, stm); @@ -1287,27 +1332,27 @@ if(PATH) pmap(attacks, stm); if(promoSuppress & PROMOTE) score = -INF; // non-Lion captures Lion after opponent did same defer |= PROMOTE; // if we started, flag he cannot do it in reply } - if(score == -INF) { moveStack[curMove] = 0; goto abortMove; } + if(score == -INF) { moveStack[curMove] = 0; goto abortMove; } // zap illegal moves } #if 1 - score = -Search(-beta, -alpha, -difEval - tb.booty, replyDep, promoSuppress & ~PROMOTE, defer); + score = -Search(-beta, -iterAlpha, -difEval - tb.booty, replyDep, promoSuppress & ~PROMOTE, defer); #else score = 0; #endif abortMove: attacks -= 2*BSIZE; level--; + repetition: UnMake(&tb); - hashKeyL = savHashL; - hashKeyH = savHashH; xstm = stm; stm ^= WHITE; #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); + // ALPHA-BETA STUFF if(score > bestScore) { bestScore = score; bestMoveNr = curMove; - if(score > alpha) { - alpha = score; + if(score > iterAlpha) { + iterAlpha = score; if(curMove < firstMove + 5) { // if not too much work, sort move to front int i; for(i=curMove; i>firstMove; i--) { @@ -1323,17 +1368,25 @@ if(PATH) printf("%d:%2d:%d %3d %6x %-10s %6d %6d\n", level, depth, iterDep, curM // update killer goto cutoff; } + { int i=pvPtr; + for(pvPtr = myPV+1; pv[pvPtr++] = pv[i++]; ); // copy daughter PV + pv[myPV] = move; // behind our move (pvPtr left at end of copy) + } } } #endif } // next move cutoff: + if(!level) { // root node + if(GetTickCount() - startTime > tlim1) break; // do not start iteration we can (most likely) not finish + } replyDep = iterDep; } while(++iterDep <= depth); // next depth retMSP = msp; retFirst = firstMove; - msp = oldMSP; + msp = oldMSP; // pop move list + pvPtr = myPV; // pop PV retMove = bestMoveNr ? moveStack[bestMoveNr] : 0; if(flag && depth >= 0) printf("return %d: %d %d\n", depth, bestScore, curEval); return bestScore + (bestScore < curEval); @@ -1441,15 +1494,23 @@ int lastLift, lastPut; int MakeMove2 (int stm, MOVE move) { + int i; sup0 = sup1; sup1 = sup2; sup2 = MakeMove(move, &undoInfo); + rootEval = -rootEval - undoInfo.booty; + for(i=0; i<200; i++) repStack[i] = repStack[i+1]; + repStack[199] = hashKeyH; +printf("# makemove %08x %c%d %c%d\n", move, sup1%BW+'a', sup1/BW, sup2%BW+'a', sup2/BW); return stm ^ WHITE; } void UnMake2 (MOVE move) { + int i; + rootEval = -rootEval - undoInfo.booty; UnMake(&undoInfo); + for(i=200; i>0; i--) repStack[i] = repStack[i-1]; sup2 = sup1; sup1 = sup0; } @@ -1458,6 +1519,7 @@ Setup2 (char *fen) { SetUp(chuArray, chuPieces); sup0 = sup1 = sup2 = ABSENT; + rootEval = cnt50 = hashKeyH = hashKeyL = 0; return WHITE; } @@ -1528,15 +1590,16 @@ MapFromScratch(attacks); if(i>=retMSP) { // no exact match if(deferred) { // but maybe non-sensical deferral int flags = p[board[f]].promoFlag; +printf("# deferral of %d\n", deferred); i = deferred; // in any case we take that move if(!(flags & promoBoard[t] & (CANT_DEFER | LAST_RANK))) { // but change it into a deferral if that is allowed moveStack[i] &= ~PROMOTE; if(p[board[f]].value == 40) p[board[f]].promoFlag &= LAST_RANK; else - if(!(flags & promoBoard[t])) moveStack[i] |= DEFER; // came from outside zone, so essential deferral + if(!(flags & promoBoard[f])) moveStack[i] |= DEFER; // came from outside zone, so essential deferral } } if(i >= retMSP) - for(i=20; i= retMSP ? INVALID : moveStack[i]); } @@ -1562,7 +1625,7 @@ flag=0; if(!cnt) { // no moves from given square if(sqr != lastPut) return; // refrain from sending empty FEN // we lifted a piece for second leg of move - for(i=20; i>SQLEN & SQUARE)) { int e, t = moveStack[i] & SQUARE; if(t < SPECIAL) continue; // only special moves @@ -1597,9 +1660,16 @@ flag=0; int SearchBestMove (int stm, int timeLeft, int mps, int timeControl, int inc, int timePerMove, MOVE *move, MOVE *ponderMove) { - int score; + int score, targetTime, movesLeft = 50; + if(mps) movesLeft = mps - (moveNr>>1)%mps; + targetTime = timeLeft*10 / (movesLeft + 1) + 1000 * inc; + if(timePerMove > 0) targetTime = timeLeft * 5; + startTime = GetTickCount(); + tlim1 = 0.3*targetTime; + tlim2 = 1.9*targetTime; + nodes = 0; MapFromScratch(attacks); - score = Search(-INF-1, INF+1, 0, 3, sup1, sup2); + score = Search(-INF-1, INF+1, rootEval, 20, sup1, sup2); *move = retMove; *ponderMove = INVALID; return score; @@ -1642,7 +1712,7 @@ printf("# setup done");fflush(stdout); int maxDepth; // used by search MOVE move, ponderMove; int i, score; - char inBuf[80], command[80]; + char inBuf[8000], command[80]; Init(); SetUp(chuArray, chuPieces); @@ -1714,7 +1784,7 @@ printf("in: %s\n", command); continue; } if(!strcmp(command, "protover")){ - printf("feature ping=1 setboard=1 colors=0 usermove=1 memory=1 debug=1\n"); + printf("feature ping=1 setboard=1 colors=0 usermove=1 memory=1 debug=1 sigint=0 sigterm=0\n"); printf("feature variants=\"chu,12x12+0_fairy\"\n"); printf("feature highlight=1\n"); printf("feature option=\"Resign -check 0\"\n"); // example of an engine-defined option