Carnivor (then after, RomiChess) was my first real attempt at programming anything more than a non graphical roulette wheel in Basic. So it is possible I made some weird mistake counting nodes. I did not even know they were called nodes. I just used a global int x, lol. If I remember correctly Car does do shallow searches (1 move + Qsearch) with an open window to score the moves if there are a few plys of depth left. Those iid moves are counted. I guess they are not tree nodes so maybe they should not be counted. All I can suggest is to take a look at the code if it would not be too painful to read such beginner_ish code. And it still compiles without too much trouble.hgm wrote: ↑Sun Feb 28, 2021 11:25 amI still want to understand this better, because it is unusually fast. So I am curious what exactly you are doing here.Mike Sherwin wrote: ↑Wed Feb 24, 2021 6:54 pmIn Carnivor only material counting and psqt evaluation are done and it is also incremental. And everytime a move is made in search the nodes counter is incremented. So for example searching to 13 ply deep takes 17.42 seconds and 448,943,111 moves are made. On my calculator 448943111 / 17.42 = 25,771,705 moves per second.
You mention you count making moves, and this might cause tricky differences, as I am used to counting move generations. So what kind of search is this, exactly? Is there a quiescence search? Is there futility pruning?
I ask that, because futility pruning dispenses with moves without actually making them. This of course makes the engine faster, which is why we do it. But if you count makemoves, it would make the nps go down. So I am a bit worried that the high nps could be a consequences of making mostly useless moves, to nodes for which you knew in advance you did not have to do anything there.
Code: Select all
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <conio.h>
#include <time.h>
#include <signal.h>
#pragma warning(disable : 4996)
#define TRUE 1
#define FALSE 0
#define WHITE 0
#define BLACK 1
#define BOTH 2
#define OFF 3
#define BISHOP 0
#define ROOK 1
#define QUEEN 2
#define KNIGHT 3
#define KING 4
#define PAWN 5
#define CASks 6
#define CASqs 7
#define COMCAS 8
#define VACANT 1
#define FRIEND 0
#define ENEMY 2
#define ILLEGAL 3
#define LR1 0
#define L1 1
#define R1 2
#define LR2 3
#define L2 4
#define R2 5
#define LRE 6
#define LE 7
#define RE 8
#define LRQ 9
#define LQ 10
#define RQ 11
#define MOVE 0
#define MOVEq 1
#define MOVEr 2
#define MOVEb 3
#define MOVEn 4
#define PDMOVE 5
#define CAPTURE 6
#define CAPTUREq 7
#define CAPTUREr 8
#define CAPTUREb 9
#define CAPTUREn 10
#define CEP 11
#define CASTLEwk 12
#define CASTLEwq 13
#define CASTLEbk 14
#define CASTLEbq 15
#define INSwc 16
#define INSwkc 17
#define INSwqc 18
#define INSbc 19
#define INSbkc 20
#define INSbqc 21
#define inf 10002
#define EMPTY 17
#define delete(x) piece[piece[(x)].nxt].prv=piece[(x)].prv;piece[piece[(x)].prv].nxt=piece[(x)].nxt
#define insert(x) piece[piece[(x)].nxt].prv=(x);piece[piece[(x)].prv].nxt=(x)
#define getmove() fs=tree[li].fsq;ts=tree[li].tsq;fid=brd[fs];
#define getunmv() fs=hist[rply].fsq;ts=hist[rply].tsq;fid=brd[ts];
#define evalft() hist[rply].sco=hist[rply-1].sco-pctbl[side][piece[fid].pt][fs]+ \
pctbl[side][piece[fid].pt][ts]
#define evalcap() hist[rply].sco-=pctbl[side^1][piece[tid].pt][ts]
#define evalcas(s,kf,kt,rf,rt) hist[rply].sco=hist[rply-1].sco- \
pctbl[s][4][kf]-pctbl[s][1][rf]+pctbl[s][4][kt]+pctbl[s][1][rt]
#define evalf() hist[rply].sco=hist[rply-1].sco-pctbl[side][piece[fid].pt][fs]
#define evalt() hist[rply].sco+=pctbl[side][piece[fid].pt][ts]
#define storemove() hist[rply].fsq=fs;hist[rply].tsq=ts;hist[rply].typ=mt
#define movepiece() brd[ts]=fid;brd[fs]=EMPTY;piece[fid].ps=ts;storemove()
#define unmvpiece(x) brd[fs]=fid;piece[fid].ps=fs;brd[ts]=x
#define queen(x,y) piece[fid].pt=x;if(side){piece[fid].pv=-y;hist[rply].sco=hist[rply].sco+100-y;} \
else{piece[fid].pv=y;hist[rply].sco=hist[rply].sco-100+y;}
#define unqueen() if(side){piece[fid].pt=5;piece[fid].pv=-100;} \
else{piece[fid].pt=5;piece[fid].pv=100;}
#define remove() tid=brd[ts];car[rply]=tid;delete(tid);hist[rply].sco-=piece[tid].pv;evalcap()
#define putback() tid=car[rply];insert(tid)
#define capep() ceps=(side)?ts+8:ts-8;tid=brd[ceps];brd[ceps]=EMPTY;car[rply]=tid; \
delete(tid);hist[rply].sco=hist[rply].sco-pctbl[side^1][piece[tid].pt][ceps]-piece[tid].pv
#define uncapep() tid=car[rply];brd[piece[tid].ps]=tid;insert(tid)
#define link(x) ti->fsq=fs;ti->tsq=ts;ti->typ=(x);ti++
void initmg(void);
void initdata(void);
void drawgraf(void);
int wmg(void);
int bmg(void);
int wcg(void);
int bcg(void);
void compute(void);
int move(void);
void unmove(void);
void getcmd(void);
int wsearch(int,int,int);
int bsearch(int,int,int);
int wlegal(void);
int blegal(void);
int wquiesce(int,int);
int bquiesce(int,int);
int wpick(void);
int bpick(void);
int wqpick(void);
int bqpick(void);
int reps(void);
void convert(int,int);
void board();
void sortpv(void);
void bench(unsigned);
unsigned char ibrd[]=
{ 14,10,12,15,16,11, 9,13,
5, 4, 3, 2, 1, 8, 7, 6,
17,17,17,17,17,17,17,17,
17,17,17,17,17,17,17,17,
17,17,17,17,17,17,17,17,
17,17,17,17,17,17,17,17,
22,21,20,19,18,25,24,23,
31,27,29,32,33,28,26,30 };
typedef struct
{
int ps;
int pv;
int pt;
int prv;
int nxt;
} pieces;
pieces piece[41];
pieces ipiece[41]=
{
{ 0, 0, 0, 0, 1},
{12, 120, 5, 0, 2},
{11, 120, 5, 1, 3},
{10, 100, 5, 2, 4},
{ 9, 100, 5, 3, 5},
{ 8, 100, 5, 4, 6},
{15, 100, 5, 5, 7},
{14, 100, 5, 6, 8},
{13, 100, 5, 7, 9},
{ 6, 290, 3, 8,10},
{ 1, 290, 3, 9,11},
{ 5, 340, 0,10,12},
{ 2, 340, 0,11,13},
{ 7, 500, 1,12,14},
{ 0, 500, 1,13,15},
{ 3, 950, 2,14,16},
{ 4, 0, 4,15,35},
{ 0, 0, 0, 0,18},
{52,-120, 5,17,19},
{51,-120, 5,18,20},
{50,-100, 5,19,21},
{49,-100, 5,20,22},
{48,-100, 5,21,23},
{55,-100, 5,22,24},
{54,-100, 5,23,25},
{53,-100, 5,24,26},
{62,-290, 3,25,27},
{57,-290, 3,26,28},
{61,-340, 0,27,29},
{58,-340, 0,28,30},
{63,-500, 1,29,31},
{56,-500, 1,30,32},
{59,-950, 2,31,33},
{60, 0, 4,32,37},
{ 0, 0, 8, 0, 0},
{ 0, 0, 6,16,36},
{ 0, 0, 7,35,39},
{ 0, 0, 6,33,38},
{ 0, 0, 7,37,40},
{ 0, 0, 0,36,39},
{ 0, 0, 0,38,40}};
unsigned char wpwn[]=
{ 0, 0, 0, 0, 0, 0, 0, 0,
R2,LR2,LR2,LR2,LR2,LR2,LR2, L2,
R1,LR1,LR1,LR1,LR1,LR1,LR1, L1,
R1,LR1,LR1,LR1,LR1,LR1,LR1, L1,
RE,LRE,LRE,LRE,LRE,LRE,LRE, LE,
R1,LR1,LR1,LR1,LR1,LR1,LR1, L1,
RQ,LRQ,LRQ,LRQ,LRQ,LRQ,LRQ, LQ,
0, 0, 0, 0, 0, 0, 0, 0 };
unsigned char bpwn[]=
{ 0, 0, 0, 0, 0, 0, 0, 0,
LQ,LRQ,LRQ,LRQ,LRQ,LRQ,LRQ, RQ,
L1,LR1,LR1,LR1,LR1,LR1,LR1, R1,
LE,LRE,LRE,LRE,LRE,LRE,LRE, RE,
L1,LR1,LR1,LR1,LR1,LR1,LR1, R1,
L1,LR1,LR1,LR1,LR1,LR1,LR1, R1,
L2,LR2,LR2,LR2,LR2,LR2,LR2, R2,
0, 0, 0, 0, 0, 0, 0, 0 };
unsigned char wtrgt[]=
{ 0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
1,
2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,3 };
unsigned char btrgt[]=
{ 0,
2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,3,
1,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0 };
unsigned char bns[1808],bnd[1808],rns[3704],rnd[3704],qns[3872],qnd[3872];
unsigned char nns[890],kns[694],wpns[360],bpns[360];
unsigned int bol[64],rol[64],qol[64],nol[64],kol[64],pol[64];
unsigned char brd[64];
int away;
typedef struct { unsigned char fsq;
unsigned char tsq;
unsigned char typ;
unsigned char cep; } amove;
typedef union { amove;
int umove; } pmove;
typedef union { int sco;
time_t time; } value;
typedef struct { pmove;
value; } node;
node tree[2000];
node hist[200];
node pvr[200][200];
signed char pctbl[2][7][64]=
{{{ 6, 0, 0, 0, 0, 0, 0, 6,
10, 30, 12, 12, 12, 12, 30, 10,
0, 20, 30, 12, 12, 30, 20, 0,
16, 12, 32, 32, 32, 32, 12, 16,
0, 30, 24, 32, 32, 24, 30, 0,
0, 12, 30, 24, 24, 30, 12, 0,
0, 18, 20, 20, 20, 20, 18, 0,
6, 0, 0, 0, 0, 0, 0, 6 },
{ 6, 10, 12, 14, 14, 12, 10, 6,
8, 10, 10, 16, 16, 10, 10, 8,
6, 8, 10, 12, 12, 10, 8, 6,
4, 6, 8, 10, 10, 8, 6, 4,
4, 6, 8, 10, 10, 8, 6, 4,
6, 8, 10, 12, 12, 10, 8, 6,
20, 20, 20, 20, 20, 20, 20, 20,
18, 18, 18, 18, 18, 18, 18, 18 },
{ 14, 14, 14, 14, 14, 14, 14, 14,
14, 16, 16, 16, 16, 16, 16, 14,
14, 16, 18, 18, 18, 18, 16, 14,
14, 16, 18, 18, 18, 18, 16, 14,
16, 18, 20, 20, 20, 20, 18, 16,
16, 18, 20, 20, 20, 20, 18, 16,
18, 20, 20, 20, 20, 20, 20, 18,
18, 18, 18, 18, 18, 18, 18, 18 },
{ 0,-10, 12, 12, 12, 12,-10, 0,
6, 12, 24, 30, 26, 24, 12, 6,
12, 24, 30, 36, 36, 38, 24, 12,
12, 24, 36, 40, 40, 36, 24, 12,
12, 24, 36, 42, 42, 36, 24, 12,
12, 24, 36, 40, 40, 36, 24, 12,
6, 12, 24, 36, 36, 24, 12, 6,
0, 6, 12, 12, 12, 12, 6, 0 },
{ 30, 60, 20,-40, 0, 20, 60, 30,
-30,-30,-30,-30,-30,-30,-30,-30,
-20,-20,-20,-20,-20,-20,-20,-20,
-10, 0, 20, 20, 20, 20, 0,-10,
-10, 0, 20, 40, 40, 20, 0,-10,
-10, 0, 20, 20, 20, 20, 0,-10,
-10, 0, 0, 0, 0, 0, 0,-10,
-10,-10,-10,-10,-10,-10,-10,-10 },
{ 0, 0, 0, 0, 0, 0, 0, 0,
4, 4,-24,-30,-30, 8, 8, 8,
12, 8, 0,-10,-10, 0, 4, 6,
8, 14, 12, 20, 20, 8, 6, 4,
10, 16, 16, 30, 30, 12, 10, 8,
20, 40, 40, 60, 60, 40, 40, 20,
40, 60, 60, 80, 80, 60, 60, 40,
0, 0, 0, 0, 0, 0, 0, 0 },
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }},
{{ -6, 0, 0, 0, 0, 0, 0, -6,
0,-18,-20,-20,-20,-20,-18, 0,
0,-12,-30,-24,-24,-30,-12, 0,
0,-30,-24,-32,-32,-24,-30, 0,
-16,-12,-32,-32,-32,-32,-12,-16,
0,-20,-30,-12,-12,-30,-20, 0,
-10,-30,-12,-12,-12,-12,-30,-10,
-6, 0, 0, 0, 0, 0, 0, -6 },
{-22,-22,-22,-22,-22,-22,-22,-22,
-24,-24,-24,-24,-24,-24,-24,-24,
-6, -8,-10,-12,-12,-10, -8, -6,
-4, -6, -8,-10,-10, -8, -6, -4,
-4, -6, -8,-10,-10, -8, -6, -4,
-6, -8,-10,-12,-12,-10, -8, -6,
-8,-10,-10,-22,-22,-10,-10, -8,
-8,-10,-12,-20,-20,-12,-10, -8 },
{-18,-18,-18,-18,-18,-18,-18,-18,
-18,-20,-20,-20,-20,-20,-20,-18,
-16,-18,-20,-20,-20,-20,-18,-16,
-16,-18,-20,-20,-20,-20,-18,-16,
-14,-16,-18,-18,-18,-18,-16,-14,
-14,-16,-18,-18,-18,-18,-16,-14,
-14,-16,-16,-16,-16,-16,-16,-14,
-14,-14,-14,-14,-14,-14,-14,-14 },
{ 0, -6,-12,-12,-12,-12, -6, 0,
-6,-12,-24,-36,-36,-24,-12, -6,
-12,-24,-36,-40,-40,-36,-24,-12,
-12,-24,-36,-42,-42,-36,-24,-12,
-12,-24,-36,-40,-40,-36,-24,-12,
-12,-24,-30,-36,-36,-38,-24,-12,
-6,-12,-24,-30,-26,-24,-12, -6,
0, 10,-12,-12,-12,-12, 10, 0 },
{ 10, 10, 10, 10, 10, 10, 10, 10,
10, 0, 0, 0, 0, 0, 0, 10,
10, 0,-20,-20,-20,-20, 0, 10,
10, 0,-20,-40,-40,-20, 0, 10,
10, 0,-20,-20,-20, -0, 0, 10,
20, 20, 20, 20, 20, 20, 20, 20,
30, 30, 30, 30, 30, 30, 30, 30,
-20,-60,-20, 60, 0,-20,-60,-20 },
{ 0, 0, 0, 0, 0, 0, 0, 0,
-40,-60,-60,-80,-80,-60,-60,-40,
-20,-40,-40,-60,-60,-40,-40,-20,
-10,-16,-12,-30,-30,-12, -8, -6,
-8,-14,-16,-20,-20, -8, -6, -4,
-12, -8, 0, 10, 10, 0, -4, -6,
-4, -4, 24, 30, 30, -8, -8, -4,
0, 0, 0, 0, 0, 0, 0, 0 },
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }}};
unsigned int xboard=FALSE,levm,levt,levi,cap,pro,bas,repis,pvl[200],fpv;
signed int tmp,high=0;
unsigned int car[200],first[200],lir[200],fifty[200],m,wi=FALSE,bi=FALSE,md,maxd,z;
unsigned long x;
unsigned int repeat,side,computer,ply,rply,fs,ts,id,fid,tid,mt,li,ptype;
unsigned int wktmp,bktmp,wkrtmp,wqrtmp,bkrtmp,bqrtmp,ceps,wcastmp,bcastmp,i,j;
unsigned int wntmp,bntmp,wcas34,bcas34,nulcas;
unsigned char cmd[20],data[256],c;
time_t st,et,at;
int __cdecl main(void)
{
initmg();
initdata();
drawgraf();
// srand(clock());
maxd=12800;
bas=64;
pro=64;
away=128;
at=120000;
repeat=TRUE;
side=WHITE;
computer=OFF;
while(repeat)
{
if(!xboard)board();
getcmd();
if(computer==side || computer==BOTH) compute();
}
return(0);
}
void getcmd()
{
char retry;
int tmp;
tmp=(side)?blegal():wlegal();
if(!m)
{
if(!xboard)printf("\nCheckmate!\n");
else if(side)
printf("0-1 {Black mates}\n");
else
printf("1-0 {White mates}\n");
}
retry=TRUE;
while(retry)
{
retry=FALSE;
if(!xboard){printf((side)?"Black":"White");printf("%d> ",rply/2);}
if(!fgets(data,256,stdin)){repeat=FALSE;continue;}
if(data[0]=='\n')continue;
sscanf(data,"%s",cmd);
strlwr(cmd);
if(!strcmp(cmd,"xb"))
{
xboard=xboard^1;
continue;
}
if(!strcmp(cmd,"xboard"))
{
xboard=TRUE;
signal(SIGINT,SIG_IGN);
printf("\n");
fflush(stdout);
continue;
}
if(!strcmp(cmd,"white"))
{
side=WHITE;
computer=BLACK;
continue;
}
if(!strcmp(cmd,"black"))
{
side=BLACK;
computer=WHITE;
continue;
}
if(!strcmp(cmd,"both"))
{
computer=BOTH;
continue;
}
if(!strcmp(cmd,"off") || !strcmp(cmd,"force"))
{
computer=OFF;
continue;
}
if(!strcmp(cmd,"go"))
{
computer=side;
continue;
}
if(!strcmp(cmd,"u") || !strcmp(cmd,"undo"))
{
if(rply<3)continue;
computer=OFF;
unmove();
ply=0;
high=0;
continue;
}
if(!strcmp(cmd,"r") || !strcmp(cmd,"remove"))
{
if(rply<3)continue;
unmove();
unmove();
ply=0;
high=0;
continue;
}
if(!strcmp(cmd,"new"))
{
for(i=rply;i>2;i--)unmove();
initdata();
computer=BLACK;
side=WHITE;
high=0;
continue;
}
if(!strcmp(cmd,"quit"))
{
repeat=FALSE;
continue;
}
if(!strcmp(cmd,"sa"))
{
sscanf(data,"sa %d",&away);
away=away<<6;
continue;
}
if(!strcmp(cmd,"sb"))
{
sscanf(data,"sb %d",&bas);
continue;
}
if(!strcmp(cmd,"sp"))
{
sscanf(data,"sp %d",&pro);
continue;
}
if(!strcmp(cmd,"sd"))
{
sscanf(data,"sd %d",&maxd);
maxd=maxd*64;
at=10000000;
continue;
}
if(!strcmp(cmd,"st"))
{
sscanf(data,"st %lu",&at);
at=at*(CLOCKS_PER_SEC/2);
maxd=12800;
continue;
}
if(!strcmp(cmd,"time"))
{
sscanf(data,"time %d",&at);
at=at*4/levm;
maxd=12800;
continue;
}
if(!strcmp(cmd,"level"))
{
sscanf(data,"level %d %d %d",&levm,&levt,&levi);
continue;
}
if(!strcmp(cmd,"bench"))
{
sscanf(data,"bench %d",&i);
z=0;
st=clock();
bench(i);
et=clock();
printf("nodes=%d time=%d\n",z,(int)(et-st));
printf("nodes/sec = %d\n",(int)((float)((float)z/(float)((et-st)/(float)1000))));
continue;
}
retry=TRUE;
if(!m)continue;
fs=cmd[0] - 'a' + 8 * (cmd[1] - '1');
ts=cmd[2] - 'a' + 8 * (cmd[3] - '1');
for(li=first[0];li<first[1];li++)
if(tree[li].fsq==fs && tree[li].tsq==ts)
{ retry=FALSE;
if(tree[li].typ==MOVEq)
{ switch(cmd[4])
{ case 'b':tree[li].typ=MOVEb;break;
case 'n':tree[li].typ=MOVEn;break;
case 'q':break;
case 'r':tree[li].typ=MOVEr;break;
default:
printf("You must enter q,r,b or n when promoting\n");
retry=TRUE;
}
}
else
if(tree[li].typ==CAPTUREq)
{ switch(cmd[4])
{ case 'b':tree[li].typ=CAPTUREb;break;
case 'n':tree[li].typ=CAPTUREn;break;
case 'q':break;
case 'r':tree[li].typ=CAPTUREr;break;
default:
printf("You must enter q,r,b or n when promoting\n");
retry=TRUE;
}
}
break;
}
if(retry==FALSE){lir[rply]=li;move();ply=0;}
else {printf("Error (Unknown command): %s\n",cmd);fflush(stdout);}
break;
}
return;
}
void bench(unsigned depth)
{
if(depth<1)return;
if(side)
{
if(!bmg())return;
while(move())
{
z++;
bench(depth-1);
unmove();
}
}
else
{
if(!wmg())return;
while(move())
{
z++;
bench(depth-1);
unmove();
}
}
}
void compute(void)
{
int best,alpha,beta;
float sec;
unsigned ptr,k;
if(!xboard)printf("Ok I'm thinking.\n");
(side)?blegal():wlegal();
if(!m)
{
computer=OFF;
if(side)
printf("0-1 {Black mates}\n");
else
printf("1-0 {White mates}\n");
return;
}
x=0;
st=clock();
memset(pvr,0,sizeof(pvr));
alpha=-inf;beta=inf;
for(md=bas,i=1;md<=maxd;md+=pro,i++)
{
ply=0;fpv=TRUE;
(side)?bsearch(alpha,beta,md):wsearch(alpha,beta,md);
if(!xboard)printf("\n");
best=(side)?inf:-inf;
for(li=first[0];li<first[1];li++)
{
if(side)
{
if(tree[li].sco<best){best=tree[li].sco;ptr=li;}
}
else if(tree[li].sco>best){best=tree[li].sco;ptr=li;}
}
fs=tree[ptr].fsq;
ts=tree[ptr].tsq;
convert(fs,ts);
et=clock();
if(best>9999)sprintf(cmd,"White MATES!");
if(best<-9999)sprintf(cmd,"Black MATES!");
if(!xboard)
{
printf("%3d %9d %6d ",i,x,best);
for(k=0;k<pvl[0];k++)
{
fs=pvr[0][k].fsq;
ts=pvr[0][k].tsq;
convert(fs,ts);
printf(" %s",cmd);
}
printf("\n");
}
else
{
printf("%d %d %d %d",i,best,(et-st)/CLOCKS_PER_SEC,x);
for(k=0;k<pvl[0];k++)
{
fs=pvr[0][k].fsq;
ts=pvr[0][k].tsq;
convert(fs,ts);
printf(" %s",cmd);
}
printf("\n");
fflush(stdout);
}
if(et-st > at || ((best>9000 || best<-9000) && abs(best)>high))break;
}
et=clock();et=(et-st);sec=(float)et/CLOCKS_PER_SEC;if(sec<.001)sec=(float).001;
if(side)while(bpick() && move())unmove();else while(wpick() && move())unmove();
best=(side)?inf:-inf;
for(li=first[0];li<first[1];li++)
{
if(side)
{
if(tree[li].sco<best){best=tree[li].sco;lir[rply]=li;}
}
else if(tree[li].sco>best){best=tree[li].sco;lir[rply]=li;}
}
if(abs(best)>high)high=best;
move();
convert(fs,ts);
if(best>9999 || best<-9999)
{
printf("move %s\n",cmd);
printf("\ncheckmate\n");
fflush(stdout);
computer=OFF;
return;
}
ply=0;
if(!xboard)
{
printf("\n\nMy move is %s score=%d Nodes=%lu Sec.=%.2f n/s=%lu\n\n"
,cmd,tree[li].sco,x,(float)sec,(long)((float)x/sec));
}
else
{
printf("move %s\n",cmd);
fflush(stdout);
}
}
int wsearch(int alpha,int beta,int depth)
{
unsigned int sli;
int s,ka,n;
pvl[ply]=ply;
if(depth<1)// return wquiesce(alpha,beta);
{
s=wquiesce(alpha,beta);
if(s>=alpha && s<=beta && ply<i)depth=1;
else return s;
}
if(ply)
{
// if(reps())return 0;
if(!wmg())return inf-ply;
}
if(depth>=64)
{
nulcas=piece[33].nxt;piece[33].nxt=40;
side=1^side;ply++;rply++;
s=bquiesce(alpha,beta);
side=1^side;ply--;rply--;
piece[33].nxt=nulcas;
if(s+50>=beta) depth-=(128+(ply<<2));
else
{
ka=FALSE;
if(s<-9000){ka=TRUE;depth+=(128-(ply<<3));}
else if(s<alpha)depth+=(64-(ply<<3));
}
}
if(ply)
{
while(move())
{
tree[li].sco=hist[rply-1].sco;
unmove();
}
if(depth>384)
{
while(wpick() && move())
{
sli=li;
tree[sli].sco=bquiesce(-inf,beta);
unmove();
}
}
}
n=0;
while(wpick() && move())
{
if(ply==1){if(!xboard)printf(".");}
sli=li;
tree[sli].sco=bsearch(alpha,beta,depth-64);
unmove();
if(tree[sli].sco>=beta)return tree[sli].sco;
if(tree[sli].sco>alpha)
{
alpha=tree[sli].sco;
pvr[ply][ply].umove=tree[sli].umove;
for(j=ply+1;j<pvl[ply+1];j++)pvr[ply][j]=pvr[ply+1][j];
pvl[ply]=pvl[ply+1];
}
if(tree[sli].sco>(signed)(-10001+ply))n++;
}
if(!n && !ka)return 0;
// if(fifty[rply-1]==100)return 0;
return alpha;
}
int bsearch(int alpha,int beta,int depth)
{
unsigned int sli;
int s,ka,n;
pvl[ply]=ply;
if(depth<1)// return bquiesce(alpha,beta);
{
s=bquiesce(alpha,beta);
if(s>=alpha && s<=beta && ply<i)depth=1;
else return s;
}
if(ply)
{
// if(reps())return 0;
if(!bmg())return -inf+ply;
}
if(depth>=64)
{
nulcas=piece[16].nxt;piece[16].nxt=39;
side=1^side;ply++;rply++;
s=wquiesce(alpha,beta);
side=1^side;ply--;rply--;
piece[16].nxt=nulcas;
if(s-50<=alpha) depth-=(128+(ply<<2));
else
{
ka=FALSE;
if(s>9000){ka=TRUE;depth+=(128-(ply<<3));}
else if(s>beta)depth+=(64-(ply<<3));
}
}
if(ply)
{
while(move())
{
tree[li].sco=hist[rply-1].sco;
unmove();
}
if(depth>384)
{
while(bpick() && move())
{
sli=li;
tree[sli].sco=wquiesce(alpha,inf);
unmove();
}
}
}
n=0;
while(bpick() && move())
{
if(ply==1){if(!xboard)printf(".");}
sli=li;
tree[sli].sco=wsearch(alpha,beta,depth-64);
unmove();
if(tree[sli].sco<=alpha)return tree[sli].sco;
if(tree[sli].sco<beta)
{
beta=tree[sli].sco;
pvr[ply][ply].umove=tree[sli].umove;
for(j=ply+1;j<pvl[ply+1];j++)pvr[ply][j]=pvr[ply+1][j];
pvl[ply]=pvl[ply+1];
}
if(tree[sli].sco<(signed)(10001-ply))n++;
}
if(!n && !ka)return 0;
// if(fifty[rply-1]==100)return 0;
return beta;
}
int wlegal()
{
unsigned int sli;
int alpha=-inf;
if(!wmg())return FALSE;
while(move())
{
tree[li].sco=hist[rply-1].sco;
unmove();
}
m=0;
while(wpick() && move())
{
m++;
sli=li;
tree[sli].sco=bquiesce(-inf,inf);
unmove();
if(tree[sli].sco==-inf+1)
{
m--;
first[ply+1]--;
li=first[ply+1];
if(li==sli)continue;
tree[sli].fsq=tree[li].fsq;tree[sli].tsq=tree[li].tsq;tree[sli].typ=tree[li].typ;
lir[rply]--;continue;
}
if(tree[sli].sco>alpha)alpha=tree[sli].sco;
}
return alpha;
}
int blegal()
{
unsigned int sli;
int beta=inf;
if(!bmg())return FALSE;
while(move())
{
tree[li].sco=hist[rply-1].sco;
unmove();
}
m=0;
while(bpick() && move())
{
m++;
sli=li;
tree[sli].sco=wquiesce(-inf,inf);
unmove();
if(tree[sli].sco==inf-1)
{
m--;
first[ply+1]--;
li=first[ply+1];
if(li==sli)continue;
tree[sli].fsq=tree[li].fsq;tree[sli].tsq=tree[li].tsq;tree[sli].typ=tree[li].typ;
lir[rply]--;continue;
}
if(tree[sli].sco<beta)beta=tree[sli].sco;
}
return beta;
}
int wquiesce(int alpha,int beta)
{
signed int s;
s=hist[rply-1].sco;
if(s>=beta)return s;
if(s>alpha)alpha=s;
if(!wcg())return inf-ply;
if(first[ply]==first[ply+1])return alpha;
while(move())
{
tree[li].sco=hist[rply-1].sco;
unmove();
}
while(wpick() && move())
{
if(hist[rply-1].sco<alpha){unmove();return hist[rply-1].sco;}
s=bquiesce(alpha,beta);
unmove();
if(s>=beta)return s;
if(s>alpha)alpha=s;
}
return alpha;
}
int bquiesce(int alpha,int beta)
{
int s;
s=hist[rply-1].sco;
if(s<=alpha)return s;
if(s<beta)beta=s;
if(!bcg())return -inf+ply;
if(first[ply]==first[ply+1])return beta;
while(move())
{
tree[li].sco=hist[rply-1].sco;
unmove();
}
while(bpick() && move())
{
if(hist[rply-1].sco>beta){unmove();return hist[rply-1].sco;}
s=wquiesce(alpha,beta);
unmove();
if(s<=alpha)return s;
if(s<beta)beta=s;
}
return beta;
}
int reps()
{
unsigned i;
int b[64];
int c=0;
// int r=0;
if(fifty[rply-1]<=3)return 0;
memset(b,0,sizeof(b));
for(i=rply-1;i>=rply-fifty[rply-1]-1;--i)
{
if(++b[hist[i].fsq]==0)--c;
else ++c;
if(--b[hist[i].tsq]==0)--c;
else ++c;
if(c==0)return 1;
}
return 0;
}
void sortpv()
{
unsigned i;
fpv=FALSE;
for(i=first[ply];i<first[ply+1];i++)
if(tree[i].umove==pvr[0][ply].umove)
{
fpv=TRUE;
tree[i].sco=(side)?-100000:100000;
return;
}
}
int wpick()
{
register signed int best=-20000;
register unsigned int ptr,sli;
register unsigned tmp;
li=lir[rply];
if(li==first[ply+1]-1)return TRUE;
if(li>=first[ply+1]){lir[rply]=first[ply];return FALSE;}
for(sli=li;sli<first[ply+1];sli++)
if(tree[sli].sco>best){best=tree[sli].sco;ptr=sli;}
if(li!=ptr)
{ tmp=tree[ptr].umove;tree[ptr].umove=tree[li].umove;tree[li].umove=tmp;
tree[ptr].sco=tree[li].sco;tree[li].sco=best;
}
return TRUE;
}
int bpick()
{
register signed int best=20000;
register unsigned int ptr,sli;
register unsigned tmp;
li=lir[rply];
if(li==first[ply+1]-1)return TRUE;
if(li>=first[ply+1]){lir[rply]=first[ply];return FALSE;}
for(sli=li;sli<first[ply+1];sli++)
if(tree[sli].sco<best){best=tree[sli].sco;ptr=sli;}
if(li!=ptr)
{ tmp=tree[ptr].umove;tree[ptr].umove=tree[li].umove;tree[li].umove=tmp;
tree[ptr].sco=tree[li].sco;tree[li].sco=best;
}
return TRUE;
}
/*int wqpick()
{
signed int best=-20000,s;
unsigned int ptr,sli;
if(lir[rply]+1==first[ply+1])return TRUE;
li=lir[rply];
if(li>=first[ply+1])return FALSE;
for(sli=li;sli<first[ply+1];sli++)
{
switch(mtl[sli])
{
case CAPTURE:
s=-piece[fid].pv[brd[fsl[sli]]]-piece[fid].pv[brd[tsl[sli]]];
if(s>best){best=s;ptr=sli;}
break;
case CAPTUREq:
s=850-piece[fid].pv[brd[tsl[sli]]];
if(s>best){best=s;ptr=sli;}
break;
case MOVEq:
if(850>best){best=850;ptr=sli;}
break;
case CEP:
if(0>best){best=0;ptr=sli;}
break;
}
}
if(li!=ptr)
{ fs=tree[ptr].fsq;tree[ptr].fsq=tree[li].fsq;tree[li].fsq=fs;
ts=tree[ptr].tsq;tree[ptr].tsq=tree[li].tsq;tree[li].tsq=ts;
mt=tree[ptr].typ;tree[ptr].typ=tree[li].typ;tree[li].typ=mt;
}
return TRUE;
}*/
/*int bqpick()
{
signed int best=20000,s;
unsigned int ptr,sli;
if(lir[rply]+1==first[ply+1])return TRUE;
li=lir[rply];
if(li>=first[ply+1])return FALSE;
for(sli=li;sli<first[ply+1];sli++)
{
switch(mtl[sli])
{
case CAPTURE:
s=-piece[fid].pv[brd[fsl[sli]]]-piece[fid].pv[brd[tsl[sli]]];
if(s<best){best=s;ptr=sli;}
break;
case CAPTUREq:
s=-850-piece[fid].pv[brd[tsl[sli]]];
if(s<best){best=s;ptr=sli;}
break;
case MOVEq:
if(-850<best){best=-850;ptr=sli;}
break;
case CEP:
if(0<best){best=0;ptr=sli;}
break;
}
}
if(li!=ptr)
{ fs=tree[ptr].fsq;tree[ptr].fsq=tree[li].fsq;tree[li].fsq=fs;
ts=tree[ptr].tsq;tree[ptr].tsq=tree[li].tsq;tree[li].tsq=ts;
mt=tree[ptr].typ;tree[ptr].typ=tree[li].typ;tree[li].typ=mt;
}
return TRUE;
}*/