X-Git-Url: http://winboard.nl/cgi-bin?a=blobdiff_plain;f=hachu.c;h=a81f25fcca8a9494ed18ffaaad11a49b7cf1f0c8;hb=0eecd39628e105c45f9baf11bcb785315517404b;hp=b6d3786b1af7bda38570d6b3c4ac4a8acae7701f;hpb=24ab76e88481f6e0445bc220845be691435bd755;p=hachu.git diff --git a/hachu.c b/hachu.c index b6d3786..a81f25f 100644 --- a/hachu.c +++ b/hachu.c @@ -11,16 +11,21 @@ // promotions by pieces with Lion power stepping in & out the zone in same turn // promotion on capture -#define VERSION "0.6beta" +#define VERSION "0.7beta" #define PATH level==0 || path[0] == 0xc4028 && (level==1 /*|| path[1] == 0x75967 && (level == 2 || path[2] == 0x3400b && (level == 3))*/) //define PATH 0 +#define HASH +#define KILLERS +#define NULLMOVE + #include #include #include #include #include +#include #ifdef WIN32 # include @@ -79,6 +84,21 @@ void pboard(int *b); void pbytes(unsigned char *b); typedef struct { + int lock[5]; + int move[5]; + short int score[5]; + char depth[5]; + char flag[5]; + char age[4]; +} HashBucket; + +HashBucket *hashTable; +int hashMask; + +#define H_UPPER 2 +#define H_LOWER 1 + +typedef struct { char *name, *promoted; int value; signed char range[8]; @@ -95,7 +115,7 @@ 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, repCnt, comp; -Move retMove, moveStack[10000], path[100], repStack[300], pv[1000], repeatMove[300]; +Move retMove, moveStack[10000], path[100], repStack[300], pv[1000], repeatMove[300], killer[100][2]; int maxDepth; // used by search @@ -699,11 +719,9 @@ void SetUp(char *array, int var) { int i, j, n, m, nr, color; - char c, *q, name[3]; + char c, *q, name[3], prince = 0; PieceDesc *p1, *p2; last[WHITE] = 1; last[BLACK] = 0; - if(var == V_CHESS || var == V_SHATRANJ || var == V_MAKRUK) // add dummy Crown Princes - p[AddPiece(WHITE, LookUp("CP", V_CHU))].pos = p[AddPiece(BLACK, LookUp("CP", V_CHU))].pos = ABSENT; for(i=0; ; i++) { //printf("next rank: %s\n", array); for(j = BW*i; ; j++) { @@ -720,12 +738,14 @@ SetUp(char *array, int var) name[0] += 'A' - 'a'; if(name[1]) name[1] += 'A' - 'a'; } else color = WHITE; + if(!strcmp(name, "CP")) prince |= color+1; // remember if we added Crown Prince p1 = LookUp(name, var); if(!p1) printf("tellusererror Unknown piece '%s' in setup\n", name), exit(-1); if(pflag && p1->promoted) p1 = LookUp(p1->promoted, var); // use promoted piece instead n = AddPiece(color, p1); p[n].pos = j; if(p1->promoted[0] && !pflag) { + if(!strcmp(p1->promoted, "CP")) prince |= color+1; // remember if we added Crown Prince p2 = LookUp(p1->promoted, var); m = AddPiece(color, p2); if(m <= n) n += 2; @@ -741,6 +761,9 @@ SetUp(char *array, int var) } } eos: + // add dummy Crown Princes if not yet added + if(!(prince & WHITE+1)) p[AddPiece(WHITE, LookUp("CP", V_CHU))].pos = ABSENT; + if(!(prince & BLACK+1)) p[AddPiece(BLACK, LookUp("CP", V_CHU))].pos = ABSENT; for(i=0; i<8; i++) fireFlags[i] = 0; for(i=2, n=1; i<10; i++) if(p[i].value == 10*FVAL) { int x = p[i].pos; // mark all burn zones @@ -1553,6 +1576,9 @@ Search (int alpha, int beta, int difEval, int depth, int oldPromo, int promoSupp int score, bestScore, curEval, iterAlpha; Move move, nullMove; UndoInfo tb; +#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); xstm = stm ^ WHITE; //printf("map made\n");fflush(stdout); @@ -1575,9 +1601,27 @@ if(PATH) /*pboard(board),pmap(attacks, BLACK),*/printf("search(%d) {%d,%d} eval= nodes++; pv[pvPtr++] = 0; // start empty PV, directly behind PV of parent + firstMove = curMove = sorted = msp += 50; // leave 50 empty slots in front of move list - tb.fireMask = phase = 0; iterDep=1; replyDep = (depth < 1 ? depth : 1) - 1; - do { + iterDep = 0; tb.fireMask = phase = 0; + +#ifdef HASH + index = hashKeyL & hashMask; nr = hashKeyL >> 30; hit = -1; + if(hashTable[index].lock[nr] == hashKeyH) hit = nr; else + if(hashTable[index].lock[4] == hashKeyH) hit = 4; + if(hit >= 0) { + bestScore = hashTable[index].score[hit]; + if((bestScore <= alpha || hashTable[index].flag[hit] & H_LOWER) && + (bestScore >= beta || hashTable[index].flag[hit] & H_UPPER) ) { + iterDep = hashTable[index].depth[hit]; + } + } else { // decide on replacement + if(depth >= hashTable[index].depth[nr]) hit = nr; else hit = 4; + } +#endif + + replyDep = (depth < 1 ? depth : iterDep < 1 ? 1 : iterDep); + while(++iterDep <= depth) { if(flag && depth>= 0) printf("iter %d:%d\n", depth,iterDep),fflush(stdout); iterAlpha = alpha; bestScore = -INF; bestMoveNr = 0; resDep = 60; for(curMove = firstMove; ; curMove++) { // loop over moves @@ -1590,10 +1634,10 @@ if(flag && depth>= 0) printf("phase=%d: first/curr/last = %d / %d / %d\n", phase bestScore = curEval; resDep = QSdepth; if(bestScore >= beta || depth < -1) goto cutoff; } -#if 0 - if(curEval >= beta) { +#ifdef NULLMOVE + else if(curEval >= beta) { stm ^= WHITE; - score = -Search(-beta, -iterAlpha, -difEval, depth-3, promoSuppress & SQUARE, ABSENT); + score = -Search(-beta, 1-beta, -difEval, depth > 3 ? depth-3 : 0, promoSuppress & SQUARE, ABSENT); stm ^= WHITE; if(score >= beta) { msp = oldMSP; retDep += 3; return score + (score < curEval); } } @@ -1602,6 +1646,12 @@ 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 +#ifdef HASH + if(hashMove) { + moveStack[sorted = msp++] = hashMove; + goto extractMove; + } +#endif phase = 2; case 2: // capture-gen init nextVictim = xstm; @@ -1646,6 +1696,14 @@ if(PATH) printf("%d:%2d:%2d msp=%d\n",level,depth,iterDep,msp); case 6: // non-captures nonCapts = msp; nullMove = GenNonCapts(oldPromo); +#ifdef KILLERS + { // swap killers to front + Move h = killer[level][0]; int j = curMove; + for(i=curMove; i= beta) { // beta cutoff - // update killer +#ifdef KILLERS + if(iterDep == depth && move != killer[level][0]) { + // update killer + killer[level][1] = killer[level][0]; killer[level][0] = move; + } +#endif resDep = retDep; goto cutoff; } @@ -1768,7 +1831,17 @@ if(PATH) printf("%d:%2d:%d %3d %6x %-10s %6d %6d\n", level, depth, iterDep, curM if(GetTickCount() - startTime > tlim1) break; // do not start iteration we can (most likely) not finish } replyDep = iterDep; - } while(++iterDep <= depth); // next depth +#ifdef HASH + // hash store + hashTable[index].lock[hit] = hashKeyH; + hashTable[index].depth[hit] = iterDep; + hashTable[index].flag[hit] = (bestScore < beta) * H_UPPER; + if(bestScore > alpha) { + hashTable[index].flag[hit] |= H_LOWER; + hashTable[index].move[hit] = bestMoveNr ? moveStack[bestMoveNr] : 0; + } else hashTable[index].move[hit] = 0; +#endif + } // next depth retMSP = msp; retFirst = firstMove; msp = oldMSP; // pop move list @@ -1955,6 +2028,19 @@ Setup2 (char *fen) void SetMemorySize (int n) { +#ifdef HASH + static HashBucket *realHash; + static int oldSize; + int m = 1; + intptr_t l; + if(n != 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 + } +#endif } char * @@ -1993,6 +2079,21 @@ ReadSquare (char *p, int *sqr) return 2 + (r + ONE > 9); } +int listStart, listEnd; +char boardCopy[BSIZE]; + +void +ListMoves () +{ // create move list on move stack + int i; + for(i=0; i< BSIZE; i++) boardCopy[i] = !!board[i]; +MapFromScratch(attacks); + postThinking--; repCnt = 0; tlim1 = tlim2 = 1e8; msp = 0; + Search(-INF-1, INF+1, 0, 1, sup1 & ~PROMOTE, sup2); + postThinking++; + listStart = retFirst; listEnd = retMSP; +} + MOVE ParseMove (char *moveText) { @@ -2015,18 +2116,15 @@ ParseMove (char *moveText) ret = f<> SQLEN & SQUARE)) break; // any null move matches @@@@ if((moveStack[i] & (PROMOTE | DEFER-1)) == ret) break; if((moveStack[i] & DEFER-1) == ret) deferred = i; // promoted version of entered non-promotion is legal } -printf("# moveNr = %d in {%d,%d}\n", i, retFirst, retMSP); - if(i>=retMSP) { // no exact match +printf("# moveNr = %d in {%d,%d}\n", i, listStart, listEnd); + if(i>=listEnd) { // no exact match if(deferred) { // but maybe non-sensical deferral int flags = p[board[f]].promoFlag; printf("# deferral of %d\n", deferred); @@ -2037,8 +2135,8 @@ printf("# deferral of %d\n", deferred); if(!(flags & promoBoard[f])) moveStack[i] |= DEFER; // came from outside zone, so essential deferral } } - if(i >= retMSP) { - for(i=retFirst; i= listEnd) { + for(i=listStart; i= retMSP ? INVALID : moveStack[i]); + return (i >= listEnd ? INVALID : moveStack[i]); } void @@ -2059,32 +2157,25 @@ Highlight(char *coords) char b[BSIZE], buf[2000], *q; for(i=0; i>SQLEN & SQUARE)) { int t = moveStack[i] & SQUARE; if(t >= SPECIAL) continue; - b[t] = (board[t] == EMPTY ? 'Y' : 'R'); cnt++; + b[t] = (!boardCopy[t] ? 'Y' : 'R'); cnt++; } } 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=retFirst; i>SQLEN & SQUARE)) { int e, t = moveStack[i] & SQUARE; if(t < SPECIAL) continue; // only special moves e = lastLift + epList[t - SPECIAL]; // decode t = lastLift + toList[t - SPECIAL]; if(e != sqr) continue; - b[t] = (board[t] == EMPTY ? 'Y' : 'R'); cnt++; + b[t] = (!boardCopy[t] ? 'Y' : 'R'); cnt++; } } if(!cnt) return; @@ -2250,29 +2341,13 @@ printf("in: %s\n", command); if(sscanf(inBuf+7, "Contempt=%d", &contemptFactor) == 1) continue; continue; } - if(!strcmp(command, "variant")) { - for(i=0; i<7; i++) { - sscanf(inBuf+8, "%s", command); - if(!strcmp(variants[i].name, command)) { - Init(curVarNr = i); stm = Setup2(NULL); break; - } - } - continue; - } if(!strcmp(command, "sd")) { sscanf(inBuf, "sd %d", &maxDepth); continue; } if(!strcmp(command, "st")) { sscanf(inBuf, "st %d", &timePerMove); continue; } if(!strcmp(command, "memory")) { SetMemorySize(atoi(inBuf+7)); continue; } if(!strcmp(command, "ping")) { printf("pong%s", inBuf+4); continue; } // if(!strcmp(command, "")) { sscanf(inBuf, " %d", &); continue; } - if(!strcmp(command, "new")) { - engineSide = BLACK; Init(V_CHESS); stm = Setup2(NULL); maxDepth = MAXPLY; randomize = OFF; curVarNr = comp = 0; - continue; - } - if(!strcmp(command, "setboard")){ engineSide = NONE; Init(curVarNr); stm = Setup2(inBuf+9); continue; } if(!strcmp(command, "easy")) { ponder = OFF; continue; } if(!strcmp(command, "hard")) { ponder = ON; continue; } - if(!strcmp(command, "undo")) { stm = TakeBack(1); continue; } - if(!strcmp(command, "remove")) { stm = TakeBack(2); continue; } if(!strcmp(command, "go")) { engineSide = stm; continue; } if(!strcmp(command, "post")) { postThinking = ON; continue; } if(!strcmp(command, "nopost")) { postThinking = OFF;continue; } @@ -2295,7 +2370,7 @@ printf("in: %s\n", command); if(!strcmp(command, "accepted")){ continue; } if(!strcmp(command, "rejected")){ continue; } if(!strcmp(command, "result")) { continue; } - if(!strcmp(command, "hover")) { continue; } + if(!strcmp(command, "hover")) { continue; } if(!strcmp(command, "")) { continue; } if(!strcmp(command, "usermove")){ int move = ParseMove(inBuf+9); @@ -2310,6 +2385,22 @@ pboard(board); } continue; } + if(!strcmp(command, "new")) { + engineSide = BLACK; Init(V_CHESS); stm = Setup2(NULL); maxDepth = MAXPLY; randomize = OFF; curVarNr = comp = 0; + continue; + } + if(!strcmp(command, "variant")) { + for(i=0; i<7; i++) { + sscanf(inBuf+8, "%s", command); + if(!strcmp(variants[i].name, command)) { + Init(curVarNr = i); stm = Setup2(NULL); break; + } + } + continue; + } + if(!strcmp(command, "setboard")){ engineSide = NONE; Init(curVarNr); stm = Setup2(inBuf+9); continue; } + if(!strcmp(command, "undo")) { stm = TakeBack(1); continue; } + if(!strcmp(command, "remove")) { stm = TakeBack(2); continue; } printf("Error: unknown command\n"); } }