// promotions by pieces with Lion power stepping in & out the zone in same turn\r
// promotion on capture\r
\r
-#define VERSION "0.6beta"\r
+#define VERSION "0.7beta"\r
\r
#define PATH level==0 || path[0] == 0xc4028 && (level==1 /*|| path[1] == 0x75967 && (level == 2 || path[2] == 0x3400b && (level == 3))*/)\r
//define PATH 0\r
\r
+#define HASH\r
+#define KILLERS\r
+#define NULLMOVE\r
+\r
#include <stdio.h>\r
#include <stdlib.h>\r
#include <string.h>\r
#include <signal.h>\r
#include <time.h>\r
+#include <stdint.h>\r
\r
#ifdef WIN32 \r
# include <windows.h>\r
void pbytes(unsigned char *b);\r
\r
typedef struct {\r
+ int lock[5];\r
+ int move[5];\r
+ short int score[5];\r
+ char depth[5];\r
+ char flag[5];\r
+ char age[4];\r
+} HashBucket;\r
+\r
+HashBucket *hashTable;\r
+int hashMask;\r
+\r
+#define H_UPPER 2\r
+#define H_LOWER 1\r
+\r
+typedef struct {\r
char *name, *promoted;\r
int value;\r
signed char range[8];\r
int bWidth, bHeight, bsize, zone, currentVariant, chuFlag, tenFlag, chessFlag, repDraws;\r
int stm, xstm, hashKeyH, hashKeyL, framePtr, msp, nonCapts, rootEval, retMSP, retFirst, retDep, pvPtr, level, cnt50, mobilityScore;\r
int nodes, startTime, tlim1, tlim2, repCnt, comp;\r
-Move retMove, moveStack[10000], path[100], repStack[300], pv[1000], repeatMove[300];\r
+Move retMove, moveStack[10000], path[100], repStack[300], pv[1000], repeatMove[300], killer[100][2];\r
\r
int maxDepth; // used by search\r
\r
SetUp(char *array, int var)\r
{\r
int i, j, n, m, nr, color;\r
- char c, *q, name[3];\r
+ char c, *q, name[3], prince = 0;\r
PieceDesc *p1, *p2;\r
last[WHITE] = 1; last[BLACK] = 0;\r
- if(var == V_CHESS || var == V_SHATRANJ || var == V_MAKRUK) // add dummy Crown Princes\r
- p[AddPiece(WHITE, LookUp("CP", V_CHU))].pos = p[AddPiece(BLACK, LookUp("CP", V_CHU))].pos = ABSENT;\r
for(i=0; ; i++) {\r
//printf("next rank: %s\n", array);\r
for(j = BW*i; ; j++) {\r
name[0] += 'A' - 'a';\r
if(name[1]) name[1] += 'A' - 'a';\r
} else color = WHITE;\r
+ if(!strcmp(name, "CP")) prince |= color+1; // remember if we added Crown Prince\r
p1 = LookUp(name, var);\r
if(!p1) printf("tellusererror Unknown piece '%s' in setup\n", name), exit(-1);\r
if(pflag && p1->promoted) p1 = LookUp(p1->promoted, var); // use promoted piece instead\r
n = AddPiece(color, p1);\r
p[n].pos = j;\r
if(p1->promoted[0] && !pflag) {\r
+ if(!strcmp(p1->promoted, "CP")) prince |= color+1; // remember if we added Crown Prince\r
p2 = LookUp(p1->promoted, var);\r
m = AddPiece(color, p2);\r
if(m <= n) n += 2;\r
}\r
}\r
eos:\r
+ // add dummy Crown Princes if not yet added\r
+ if(!(prince & WHITE+1)) p[AddPiece(WHITE, LookUp("CP", V_CHU))].pos = ABSENT;\r
+ if(!(prince & BLACK+1)) p[AddPiece(BLACK, LookUp("CP", V_CHU))].pos = ABSENT;\r
for(i=0; i<8; i++) fireFlags[i] = 0;\r
for(i=2, n=1; i<10; i++) if(p[i].value == 10*FVAL) {\r
int x = p[i].pos; // mark all burn zones\r
int score, bestScore, curEval, iterAlpha;\r
Move move, nullMove;\r
UndoInfo tb;\r
+#ifdef HASH\r
+ Move hashMove; int index, nr, hit;\r
+#endif\r
if(PATH) /*pboard(board),pmap(attacks, BLACK),*/printf("search(%d) {%d,%d} eval=%d, stm=%d\n",depth,alpha,beta,difEval,stm),fflush(stdout);\r
xstm = stm ^ WHITE;\r
//printf("map made\n");fflush(stdout);\r
nodes++;\r
pv[pvPtr++] = 0; // start empty PV, directly behind PV of parent\r
\r
+\r
firstMove = curMove = sorted = msp += 50; // leave 50 empty slots in front of move list\r
- tb.fireMask = phase = 0; iterDep=1; replyDep = (depth < 1 ? depth : 1) - 1;\r
- do {\r
+ iterDep = 0; tb.fireMask = phase = 0;\r
+\r
+#ifdef HASH\r
+ index = hashKeyL & hashMask; nr = hashKeyL >> 30; hit = -1;\r
+ if(hashTable[index].lock[nr] == hashKeyH) hit = nr; else\r
+ if(hashTable[index].lock[4] == hashKeyH) hit = 4;\r
+ if(hit >= 0) {\r
+ bestScore = hashTable[index].score[hit];\r
+ if((bestScore <= alpha || hashTable[index].flag[hit] & H_LOWER) &&\r
+ (bestScore >= beta || hashTable[index].flag[hit] & H_UPPER) ) {\r
+ iterDep = hashTable[index].depth[hit];\r
+ }\r
+ } else { // decide on replacement\r
+ if(depth >= hashTable[index].depth[nr]) hit = nr; else hit = 4;\r
+ }\r
+#endif\r
+\r
+ replyDep = (depth < 1 ? depth : iterDep < 1 ? 1 : iterDep);\r
+ while(++iterDep <= depth) {\r
if(flag && depth>= 0) printf("iter %d:%d\n", depth,iterDep),fflush(stdout);\r
iterAlpha = alpha; bestScore = -INF; bestMoveNr = 0; resDep = 60;\r
for(curMove = firstMove; ; curMove++) { // loop over moves\r
bestScore = curEval; resDep = QSdepth;\r
if(bestScore >= beta || depth < -1) goto cutoff;\r
}\r
-#if 0\r
- if(curEval >= beta) {\r
+#ifdef NULLMOVE\r
+ else if(curEval >= beta) {\r
stm ^= WHITE;\r
- score = -Search(-beta, -iterAlpha, -difEval, depth-3, promoSuppress & SQUARE, ABSENT);\r
+ score = -Search(-beta, 1-beta, -difEval, depth > 3 ? depth-3 : 0, promoSuppress & SQUARE, ABSENT);\r
stm ^= WHITE;\r
if(score >= beta) { msp = oldMSP; retDep += 3; return score + (score < curEval); }\r
}\r
//if(PATH) printf("mask=%x\n",tb.fireMask),pbytes(fireBoard);\r
phase = 1;\r
case 1: // hash move\r
+#ifdef HASH\r
+ if(hashMove) {\r
+ moveStack[sorted = msp++] = hashMove;\r
+ goto extractMove;\r
+ }\r
+#endif\r
phase = 2;\r
case 2: // capture-gen init\r
nextVictim = xstm;\r
case 6: // non-captures\r
nonCapts = msp;\r
nullMove = GenNonCapts(oldPromo);\r
+#ifdef KILLERS\r
+ { // swap killers to front\r
+ Move h = killer[level][0]; int j = curMove;\r
+ for(i=curMove; i<msp; i++) if(moveStack[i] == h) { moveStack[i] = moveStack[j]; moveStack[j++] = h; break; }\r
+ h = killer[level][1];\r
+ for(i=curMove; i<msp; i++) if(moveStack[i] == h) { moveStack[i] = moveStack[j]; moveStack[j++] = h; break; }\r
+ }\r
+#endif\r
phase = 7;\r
sorted = msp; // do not sort noncapts\r
break;\r
}\r
bestMoveNr = firstMove;\r
if(score >= beta) { // beta cutoff\r
- // update killer\r
+#ifdef KILLERS\r
+ if(iterDep == depth && move != killer[level][0]) {\r
+ // update killer\r
+ killer[level][1] = killer[level][0]; killer[level][0] = move;\r
+ }\r
+#endif\r
resDep = retDep;\r
goto cutoff;\r
}\r
if(GetTickCount() - startTime > tlim1) break; // do not start iteration we can (most likely) not finish\r
}\r
replyDep = iterDep;\r
- } while(++iterDep <= depth); // next depth\r
+#ifdef HASH\r
+ // hash store\r
+ hashTable[index].lock[hit] = hashKeyH;\r
+ hashTable[index].depth[hit] = iterDep;\r
+ hashTable[index].flag[hit] = (bestScore < beta) * H_UPPER;\r
+ if(bestScore > alpha) {\r
+ hashTable[index].flag[hit] |= H_LOWER;\r
+ hashTable[index].move[hit] = bestMoveNr ? moveStack[bestMoveNr] : 0;\r
+ } else hashTable[index].move[hit] = 0;\r
+#endif\r
+ } // next depth\r
retMSP = msp;\r
retFirst = firstMove;\r
msp = oldMSP; // pop move list\r
void\r
SetMemorySize (int n)\r
{\r
+#ifdef HASH\r
+ static HashBucket *realHash;\r
+ static int oldSize;\r
+ int m = 1;\r
+ intptr_t l;\r
+ if(n != oldSize) {\r
+ if(oldSize) free(realHash);\r
+ while(m*sizeof(HashBucket) <= n*512) m <<= 1;\r
+ m *= 1024; hashMask = m - 1;\r
+ realHash = calloc(m + 1, sizeof(HashBucket));\r
+ l = (intptr_t) realHash; hashTable = (HashBucket*) (l & ~63); // align with cache line\r
+ }\r
+#endif\r
}\r
\r
char *\r
return 2 + (r + ONE > 9);\r
}\r
\r
+int listStart, listEnd;\r
+char boardCopy[BSIZE];\r
+\r
+void\r
+ListMoves ()\r
+{ // create move list on move stack\r
+ int i;\r
+ for(i=0; i< BSIZE; i++) boardCopy[i] = !!board[i];\r
+MapFromScratch(attacks);\r
+ postThinking--; repCnt = 0; tlim1 = tlim2 = 1e8; msp = 0;\r
+ Search(-INF-1, INF+1, 0, 1, sup1 & ~PROMOTE, sup2);\r
+ postThinking++;\r
+ listStart = retFirst; listEnd = retMSP;\r
+}\r
+\r
MOVE\r
ParseMove (char *moveText)\r
{\r
ret = f<<SQLEN | t2;\r
if(*moveText != '\n' && *moveText != '=') ret |= PROMOTE;\r
printf("# suppress = %c%d\n", sup1%BW+'a', sup1/BW);\r
-MapFromScratch(attacks);\r
- postThinking--; repCnt = 0;\r
- Search(-INF-1, INF+1, 0, 1, sup1 & ~PROMOTE, sup2);\r
- postThinking++;\r
- for(i=retFirst; i<retMSP; i++) {\r
+ ListMoves();\r
+ for(i=listStart; i<listEnd; i++) {\r
if(moveStack[i] == INVALID) continue;\r
if(c == '@' && (moveStack[i] & SQUARE) == (moveStack[i] >> SQLEN & SQUARE)) break; // any null move matches @@@@\r
if((moveStack[i] & (PROMOTE | DEFER-1)) == ret) break;\r
if((moveStack[i] & DEFER-1) == ret) deferred = i; // promoted version of entered non-promotion is legal\r
}\r
-printf("# moveNr = %d in {%d,%d}\n", i, retFirst, retMSP);\r
- if(i>=retMSP) { // no exact match\r
+printf("# moveNr = %d in {%d,%d}\n", i, listStart, listEnd);\r
+ if(i>=listEnd) { // no exact match\r
if(deferred) { // but maybe non-sensical deferral\r
int flags = p[board[f]].promoFlag;\r
printf("# deferral of %d\n", deferred);\r
if(!(flags & promoBoard[f])) moveStack[i] |= DEFER; // came from outside zone, so essential deferral\r
}\r
}\r
- if(i >= retMSP) {\r
- for(i=retFirst; i<retMSP; i++) printf("# %d. %08x %08x %s\n", i-50, moveStack[i], ret, MoveToText(moveStack[i], 0));\r
+ if(i >= listEnd) {\r
+ for(i=listStart; i<listEnd; i++) printf("# %d. %08x %08x %s\n", i-50, moveStack[i], ret, MoveToText(moveStack[i], 0));\r
reason = NULL;\r
for(i=0; i<repCnt; i++) {if((repeatMove[i] & 0xFFFFFF) == ret) {\r
if(repeatMove[i] & 1<<24) reason = (repeatMove[i] & 1<<25 ? "Distant capture of protected Lion" : "Counterstrike against Lion");\r
}\r
}\r
}\r
- return (i >= retMSP ? INVALID : moveStack[i]);\r
+ return (i >= listEnd ? INVALID : moveStack[i]);\r
}\r
\r
void\r
char b[BSIZE], buf[2000], *q;\r
for(i=0; i<bsize; i++) b[i] = 0;\r
ReadSquare(coords, &sqr);\r
-MapFromScratch(attacks);\r
-//pmap(attacks, WHITE);\r
-//pmap(attacks, BLACK);\r
-//flag=1;\r
- postThinking--; repCnt = 0;\r
- Search(-INF-1, INF+1, 0, 1, sup1 & ~PROMOTE, sup2);\r
- postThinking++;\r
-flag=0;\r
- for(i=retFirst; i<retMSP; i++) {\r
+ ListMoves();\r
+ for(i=listStart; i<listEnd; i++) {\r
if(sqr == (moveStack[i]>>SQLEN & SQUARE)) {\r
int t = moveStack[i] & SQUARE;\r
if(t >= SPECIAL) continue;\r
- b[t] = (board[t] == EMPTY ? 'Y' : 'R'); cnt++;\r
+ b[t] = (!boardCopy[t] ? 'Y' : 'R'); cnt++;\r
}\r
}\r
if(!cnt) { // no moves from given square\r
if(sqr != lastPut) return; // refrain from sending empty FEN\r
// we lifted a piece for second leg of move\r
- for(i=retFirst; i<retMSP; i++) {\r
+ for(i=listStart; i<listEnd; i++) {\r
if(lastLift == (moveStack[i]>>SQLEN & SQUARE)) {\r
int e, t = moveStack[i] & SQUARE;\r
if(t < SPECIAL) continue; // only special moves\r
e = lastLift + epList[t - SPECIAL]; // decode\r
t = lastLift + toList[t - SPECIAL];\r
if(e != sqr) continue;\r
- b[t] = (board[t] == EMPTY ? 'Y' : 'R'); cnt++;\r
+ b[t] = (!boardCopy[t] ? 'Y' : 'R'); cnt++;\r
}\r
}\r
if(!cnt) return;\r