/* Hicin-pah-tum		*/
/* David Roe			*/
/* droe@computermotion.com	*/
/* gcc -O Hicin-pah-tum.c	*/
// Use the C compiler, whatever it is called on your machine.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <sys/times.h>
#define SEVEN 7
#define MAXLINES (SEVEN*(SEVEN-1)*(SEVEN-2))
#define MAXCELLS (SEVEN*SEVEN)
#define WEIRD 9999
#define LINELENG 50
#define HASHSIZE 101
#define HASHMULT 59
#define HASHINIT 0x0
#define MAXABBREV (1+MAXCELLS/16)
#define abs(x) ((x)>0?(x):(-(x)))
#define compded(xp) ((xp)->ded=(((xp)->x>0&&(xp)->o>0)?1:0))
#define SYM 1
#define HALFSEARCH 1
#define TIMING 1
#define MAXTIME 10
#define CLK_TCK 100
#define I_ALTCAN 6
struct stack {
int cell;
float score;
};
struct line {
int x;
int o;
int ded;
};
typedef struct hashlist *Hashptr;
struct hashlist {
Hashptr next;
float score;
unsigned int occab[MAXABBREV];
};
char brd[SEVEN][SEVEN+2];
int *lptr[MAXLINES];
int llen[MAXLINES];
int board[MAXLINES*SEVEN];
Hashptr hashtab[HASHSIZE];
int ncells=MAXCELLS;
int nlines=MAXLINES;
#ifdef TIMING
int g_time=MAXTIME;
#endif
int pmode=0;
int dmode=0;
int hashmode=1;
int strat=0;
int min_choices=2;
int tmode=1;
int vmode=0;
int m_layers=11;
float beamfac=0.;
float (*offense)[SEVEN+1];
float (*defense)[SEVEN+1];
float doffense[SEVEN+1][SEVEN+1];
float off0[SEVEN+1][SEVEN+1] = {
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00 },
{ 0.00,0.00,0.00,0.5,0.25,0.03,0.01,0.00 },
{ 0.00,0.00,0.00,1.2,0.65,0.07,0.02,0.00 },
{ 0.00,0.00,0.00,3.,1.45,0.15,0.05,0.00 },
{ 0.00,0.00,0.00,0.00,4.,0.31,0.09,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,5.,0.18,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,6.,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.  }
};
float def0[SEVEN+1][SEVEN+1] = {
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00 },
{ 0.00,0.00,0.00,0.6,0.25,0.05,0.01,0.00 },
{ 0.00,0.00,0.00,1.5,0.80,0.11,0.03,0.00 },
{ 0.00,0.00,0.00,3.,1.7,0.27,0.06,0.00 },
{ 0.00,0.00,0.00,0.00,4.,0.66,0.10,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,5.,0.20,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,6.,0.0 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.  }
};
float off1[SEVEN+1][SEVEN+1] = {
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00 },
{ 0.00,0.00,0.00,0.4,0.15,0.01,0.00,0.00 },
{ 0.00,0.00,0.00,1.0,0.45,0.03,0.00,0.00 },
{ 0.00,0.00,0.00,3.,0.85,0.07,0.00,0.00 },
{ 0.00,0.00,0.00,0.00,4.,0.31,0.00,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,5.,0.00,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,6.,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.  }
};
float def1[SEVEN+1][SEVEN+1] = {
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00 },
{ 0.00,0.00,0.00,0.6,0.35,0.05,0.01,0.00 },
{ 0.00,0.00,0.00,1.5,0.99,0.11,0.03,0.00 },
{ 0.00,0.00,0.00,3.,1.9,0.27,0.06,0.00 },
{ 0.00,0.00,0.00,0.00,4.,0.96,0.20,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,5.,0.80,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,6.,0.0 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.  }
};
float off2[SEVEN+1][SEVEN+1] = {
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00 },
{ 0.00,0.00,0.00,0.5,0.25,0.03,0.00,0.00 },
{ 0.00,0.00,0.00,1.2,0.65,0.07,0.00,0.00 },
{ 0.00,0.00,0.00,3.,1.45,0.15,0.00,0.00 },
{ 0.00,0.00,0.00,0.00,4.,0.31,0.00,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,5.,0.00,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,6.,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.  }
};
float def2[SEVEN+1][SEVEN+1] = {
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00 },
{ 0.00,0.00,0.00,0.6,0.25,0.05,0.01,0.00 },
{ 0.00,0.00,0.00,1.5,0.80,0.11,0.03,0.00 },
{ 0.00,0.00,0.00,3.,1.7,0.27,0.06,0.00 },
{ 0.00,0.00,0.00,0.00,4.,0.66,0.10,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,5.,0.20,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,6.,0.0 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.  }
};
float off3[SEVEN+1][SEVEN+1] = {
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00 },
{ 0.00,0.00,0.00,0.5,0.25,0.03,0.01,0.00 },
{ 0.00,0.00,0.00,1.2,0.65,0.07,0.02,0.00 },
{ 0.00,0.00,0.00,3.,1.45,0.15,0.05,0.00 },
{ 0.00,0.00,0.00,0.00,4.,0.31,0.09,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,5.,0.18,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,6.,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.  }
};
float def3[SEVEN+1][SEVEN+1] = {
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00 },
{ 0.00,0.00,0.00,0.6,0.25,0.05,0.01,0.00 },
{ 0.00,0.00,0.00,1.5,0.80,0.11,0.03,0.00 },
{ 0.00,0.00,0.00,3.,1.7,0.27,0.06,0.00 },
{ 0.00,0.00,0.00,0.00,4.,0.66,0.10,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,5.,0.20,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,6.,0.0 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.  }
};
float off4[SEVEN+1][SEVEN+1] = {
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00 },
{ 0.00,0.00,0.00,0.5,0.25,0.03,0.01,0.00 },
{ 0.00,0.00,0.00,1.2,0.65,0.07,0.02,0.00 },
{ 0.00,0.00,0.00,3.,1.45,0.15,0.05,0.00 },
{ 0.00,0.00,0.00,0.00,4.,0.31,0.09,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,5.,0.18,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,6.,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.  }
};
float def4[SEVEN+1][SEVEN+1] = {
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00 },
{ 0.00,0.00,0.00,0.6,0.25,0.04,0.01,0.00 },
{ 0.00,0.00,0.00,1.5,0.80,0.09,0.03,0.00 },
{ 0.00,0.00,0.00,3.,1.7,0.17,0.06,0.00 },
{ 0.00,0.00,0.00,0.00,4.,0.46,0.10,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,5.,0.20,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,6.,0.0 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.  }
};
float off5[SEVEN+1][SEVEN+1] = {
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00 },
{ 0.00,0.00,0.00,0.5,0.19,0.03,0.01,0.00 },
{ 0.00,0.00,0.00,1.2,0.65,0.07,0.02,0.00 },
{ 0.00,0.00,0.00,3.,1.45,0.15,0.05,0.00 },
{ 0.00,0.00,0.00,0.00,4.,0.31,0.09,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,5.,0.18,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,6.,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.  }
};
float def5[SEVEN+1][SEVEN+1] = {
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00 },
{ 0.00,0.00,0.00,0.6,0.20,0.05,0.01,0.00 },
{ 0.00,0.00,0.00,1.5,0.70,0.11,0.03,0.00 },
{ 0.00,0.00,0.00,3.,1.5,0.27,0.06,0.00 },
{ 0.00,0.00,0.00,0.00,4.,0.66,0.10,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,5.,0.20,0.00 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,6.,0.0 },
{ 0.00,0.00,0.00,0.00,0.00,0.00,0.00,7.  }
};
char * int2label();
void printocc();
#ifdef TIMING
int checktime()
{
static struct tms TMS;
times(&TMS);
return (MAXTIME - (TMS.tms_stime + TMS.tms_utime)/CLK_TCK);
}
#endif
void printoccab(unsigned int *occab) {
int j;
for (j=0;j<MAXABBREV;j++)
printf("%2d:0x%x ",j*16,occab[j]);
printf("\n");
}
void copyoccab(unsigned int * occato,unsigned int * occafrom) {
register int i=MAXABBREV-1;
while(i-- >=0) *occato++ = *occafrom++;
}
int equaloccab(unsigned int *occato,unsigned int * occafrom) {
register int i=MAXABBREV-1;
while(i-- >=0) if (*occato++ != *occafrom++) return 0;
return 1;
}
void occ2occab(unsigned int * occab,int *occ) {
register unsigned int regi=0;
unsigned int j;
for (j=0;j<MAXCELLS;j++) {
regi=(occ[j]&0x3)+(regi<<2);
if ((j&0xF)==15) {
occab[j>>4]=regi;
regi=0;
}
}
if((MAXCELLS&0xF)!=0)
occab[MAXABBREV-1]=regi;
}
void hashinit() {
int i;
for (i=0;i<HASHSIZE;i++)
hashtab[i]=NULL;
}
unsigned int hashfunc(unsigned int *hoccab) {
unsigned int hashval=HASHINIT;
unsigned int *s;
s=hoccab+MAXABBREV-1;
for (hashval=HASHINIT;s>=hoccab;s--) {
hashval=HASHMULT*hashval+ *s;
}
return hashval%HASHSIZE;
}
Hashptr hashlookup(int *hoccab) {
register Hashptr np;
unsigned int hashval;
hashval=hashfunc(hoccab);
for (np=hashtab[hashval];np!=NULL;np=np->next) {
if (equaloccab(hoccab,np->occab)) {
return np;
}
}
return NULL;
}
Hashptr hashinstall(int *hocc) {
Hashptr np;
register unsigned int hashval;
unsigned int hoccab[MAXABBREV];
occ2occab(hoccab,hocc);
if ((np=hashlookup(hoccab))==NULL) {
np=(Hashptr)malloc(sizeof(struct hashlist));
if (np==NULL) {
return NULL;
}
copyoccab(np->occab,hoccab);
hashval=hashfunc(hoccab);
np->next=hashtab[hashval];
hashtab[hashval]=np;
np->score=WEIRD;
return np;
}
return np;
}
#ifdef SYM
float lines2score(lines,player)
struct line lines[];
int player;
{
register int i;
register struct line *lp;
int count[SEVEN+1][SEVEN+1],j,*ip;
float score=0.0;
for (ip= &(count[SEVEN][SEVEN]);ip>=count[0];ip--) *ip=0;
for (i=nlines-1;i>=0;i--) {
lp= &lines[i];
if (lp->ded) continue;
if (lp->x >=1)
count[lp->x][llen[i]]++;
else if (lp->o >=1)
count[lp->o][llen[i]]--;
}
for (j=3;j<=SEVEN;j++) {
for (i=0;i<=j;i++) {
if (count[i][j]>0)
score += count[i][j]*(player==1? offense[i][j] : defense[i][j]);
else if (count[i][j]<0)
score += count[i][j]*(player==1? defense[i][j] : offense[i][j]);
}
}
return(score);
}
#else
float lines2score(lines,player)
struct line lines[];
int player;
{
register int i;
register struct line *lp;
float score=0.0;
for (i=0;i<nlines;i++) {
lp= &lines[i];
if (lp->ded) continue;
if (lp->x >=1)
score += (player==1 ? offense[lp->x][llen[i]]:defense[lp->x][llen[i]] );
else if (lp->o >=1)
score -=(player==(-1) ? offense[lp->o][llen[i]]:defense[lp->o][llen[i]]);
}
return(score);
}
#endif
int readbrd() {
int i;
int io=0;
int ix=0;
int ip=0;
int im=0;
char *cptr,buf[LINELENG+1];
for (i=0;i<SEVEN;i++) {
if (fgets(buf,LINELENG,stdin)==NULL || strlen(buf)<SEVEN) {
fprintf(stderr,"error in input,row=%d: %s\n",i,buf);
exit(1);
}
strncpy(brd[i],buf,SEVEN);
brd[i][SEVEN]='\0';
for (cptr=brd[i];*cptr!='\n' && *cptr!='\0';cptr++) {
if (*cptr=='+') ip++;
else if (*cptr=='X') ix++;
else if (*cptr=='O') io++;
else if (*cptr=='-') im++;
else {
fprintf(stderr,"error in input,row %d: %s,%c\n",
i,brd[i],*cptr);
exit(1);
}
}
}
if (im==0) {
fprintf(stderr,"no legal moves remain\n");
return (0);
}
return (ix>io ? -1 : 1);
}
void copystak(struct stack *tostak,
struct stack *bs_p,
struct stack *futstak)
{
int i;
struct stack *sptr;
for (i=0; i<MAXCELLS; i++) {
if (i>=1 && futstak[i-1].cell==WEIRD) break;
sptr = (i==0 ? bs_p : &futstak[i-1] );
tostak[i].cell=sptr->cell;
tostak[i].score=sptr->score;
}
tostak[i].cell=WEIRD;
tostak[i].score=9.99;
}
void printshtak(
int indent,
int amoves,
struct stack *bstak,
char pch,
char *omode)
{
register int j;
int mode=0;
if (strcmp(omode,"out")==0) mode=1;
for (j=indent;j>0;j--) printf("  ");
printf(" %c %s: ",pch,omode);
for (j=0;j<amoves;j++) {
printf("%s%c%.1f%c ",int2label(bstak[j].cell),(mode?'(':'{'),
bstak[j].score,(mode?')':'}'));
}
printf("\n");
fflush(stdout);
}
void printbrd(char (*tbrd)[SEVEN+2],float scor) {
register int i;
for (i=0;i<SEVEN;i++) {
if (dmode>=1 && i==SEVEN/2)
printf("%s  SCORE=%.2f\n",tbrd[i],scor);
else
printf("%s\n",tbrd[i]);
}
}
void searchmoves(lines,occ,bstak,stak_pos,nmoves,player)
struct line lines[];
int occ[];
struct stack bstak[];
int stak_pos[];
int nmoves;
int player;
{
register struct line *lp;
register int j;
register int nn;
float ds;
int i,len;
ds=lines2score(lines,player);
for (i=0;i<nmoves;i++) bstak[i].score=ds;
for (i=0;i<nlines;i++) {
lp= &lines[i];
len=llen[i];
if (lp->ded) continue;
if (lp->o>=len || lp->x>=len) continue;
if (player==1)
ds=(lp->o>0 ? defense[lp->o][len]: doffense[lp->x][len] );
if (player==(-1))
ds= -(lp->x>0? defense[lp->x][len]: doffense[lp->o][len] );
for (nn=len-1;nn>=0;nn--) {
j= *(lptr[i]+nn);
if (occ[j]==0) {
bstak[stak_pos[j]].score+=ds;
}
}
}
}
void printstack(stak,n)
struct stack stak[];
int n;
{
int i;
printf(" move  score\n");
for (i=0;i<n;i++) {
printf(" %4s %5.2f\n",int2label(stak[i].cell),stak[i].score);
if (stak[i].cell==WEIRD) break;
}
fflush(stdout);
}
void topsortstack(stak,n,player)
struct stack stak[];
int player;
{
register struct stack *jp,*jgp;
float tf;
int ti;
jgp= stak;
if (player==1) {
for (jp=&stak[n-1];jp>jgp;jp--) {
if (jp->score > jgp->score) {
tf=jp->score;
ti=jp->cell;
jp->score=jgp->score;
jp->cell=jgp->cell;
jgp->score=tf;
jgp->cell=ti;
}
}
}
else {
for (jp=&stak[n-1];jp>jgp;jp--) {
if (jp->score < jgp->score) {
tf=jp->score;
ti=jp->cell;
jp->score=jgp->score;
jp->cell=jgp->cell;
jgp->score=tf;
jgp->cell=ti;
}
}
}
}
void sortstack(stak,n,player)
struct stack stak[];
int player;
{
int i,j,gap,ti;
register struct stack *jp,*jgp;
float tf;
for (gap=n/2;gap>0;gap/=2) {
for (i=gap;i<n;i++) {
for (j=i-gap;j>=0;j-=gap) {
jgp= &stak[j+gap];
jp= &stak[j];
if ((jp->score - jgp->score) * player >= 0) break;
tf=jp->score;
ti=jp->cell;
jp->score=jgp->score;
jp->cell=jgp->cell;
jgp->score=tf;
jgp->cell=ti;
}
}
}
}
int legal_moves(bocc,bstak,stak_pos)
int bocc[];
struct stack bstak[];
int stak_pos[];
{
int count,i;
count=0;
for (i=0;i<ncells;i++) {
if (bocc[i]==0) {
stak_pos[i]=count;
bstak[count++].cell=i;
}
}
bstak[count].cell=WEIRD;
return(count);
}
int addcell(cell,player,occ,lines)
int cell,player;
int occ[];
struct line lines[];
{
register int i,*cellptr;
struct line *lp;
if (occ[cell] != 0) {
printf("addcell error: cell %s occupied %d\n",
int2label(cell),occ[cell]);
return(occ[cell]);
}
occ[cell]=player;
for (i=nlines-1;i>=0;i--) {
for (cellptr=lptr[i]+llen[i]-1;cellptr>=lptr[i];cellptr--) {
if (*cellptr==cell) {
lp= &lines[i];
if (player==1) lp->x++;
else if (player==(-1)) lp->o++;
compded(lp);
break;
}
}
}
return(0);
}
int subcell(cell,player,occ,lines)
int cell,player;
int occ[];
struct line lines[];
{
register int i,*cellptr;
struct line *lp;
if (occ[cell] != player) {
printf("subcell error: cell %s not occupied %d",
int2label(cell),occ[cell]);
printf(" by player %d\n",player);
return(-2);
}
occ[cell]=0;
for (i=nlines-1;i>=0;i--) {
for (cellptr=lptr[i]+llen[i]-1;cellptr>=lptr[i];cellptr--) {
if (*cellptr==cell) {
lp= &lines[i];
if (player==1) lp->x--;
else if (player==(-1)) lp->o--;
compded(lp);
break;
}
}
}
return(0);
}
void makemove(move,player,occ,lines)
int move,player;
int occ[];
struct line lines[];
{
if (move<0 || move>ncells || occ[move]!=0 ) {
printf("Illegal move %s (cell %d)\n",int2label(move),move);
}
addcell(move,player,occ,lines);
}
struct stack *bestmove(bocc,blines,layers,indent,player,altcan,tostak)
int bocc[];
struct line blines[];
int layers;
int indent;
int player;
int altcan;
struct stack *tostak;
{
struct stack bstak[MAXCELLS+1],*bs_p;
static struct stack topstak;
struct stack futstak[MAXCELLS+1];
struct stack weirdstak;
Hashptr np;
float lines2score(),bestsofar;
int stak_pos[MAXCELLS];
int nmoves,i,amoves=1,mod_amoves;
int beam_moves=1;
float bstak0score;
static int b_pos=0;
static int b_deep=0;
static int b_skip=0;
static int b_max=0;
char pch;
#ifdef TIMING
if (tmode && layers>3)
g_time=checktime();
#endif
pch=(player>0 ? 'X' : 'O' );
bestsofar=(float)player*(-WEIRD);
weirdstak.cell=WEIRD;
weirdstak.score=bestsofar;
if (indent==0)
b_max=b_skip=b_deep=b_pos=0;
nmoves=legal_moves(bocc,bstak,stak_pos);
if (dmode>=1) {
b_pos += nmoves;
if (indent>b_max) b_max=indent;
}
searchmoves(blines,bocc,bstak,stak_pos,nmoves,player);
amoves = (nmoves<altcan ? nmoves : altcan );
if (layers>1 && amoves>1) {
sortstack(bstak,nmoves,player);
}
else {
topsortstack(bstak,nmoves,player);
}
bstak0score=bstak[0].score;
if (pmode>=indent && dmode>=1) {
if (layers>1)
printshtak(indent,amoves,bstak,pch,"in ");
}
if (dmode>=1)
copystak(tostak,bstak,&weirdstak);
if (layers<=1 || nmoves<=1) {
amoves=1;
goto nocal;
}
for (i=0;i<amoves;i++) {
addcell(bstak[i].cell,player,bocc,blines);
if (hashmode && (np=hashinstall(bocc))!=NULL && np->score<WEIRD) {
if (dmode>=1) b_skip++;
bstak[i].score= np->score;
}
else {
if (dmode>=1) {
b_deep++;
if (pmode>indent)
printshtak(indent,1,&bstak[i],pch,"try");
}
#ifdef HALFSEARCH
mod_amoves=amoves-((indent+1)&0x1);
#else
mod_amoves=amoves;
#endif
#ifdef TIMING
if (g_time<3)
mod_amoves=amoves-1;
#endif
if (mod_amoves<min_choices) mod_amoves=min_choices;
if (beamfac>0.0) {
beam_moves=amoves-(int)(player*beamfac*(bstak0score-bstak[i].score));
if (mod_amoves>beam_moves) mod_amoves=beam_moves;
if (mod_amoves<1) mod_amoves=1;
}
#ifdef TIMING
if (g_time<1)
bs_p=bestmove(bocc,blines,(layers>3?layers-3:layers-1),
indent+1,(-player),mod_amoves,futstak);
else
#endif
bs_p=bestmove(bocc,blines,layers-1,
indent+1,(-player),mod_amoves,futstak);
if (layers==2 && vmode)
bstak[i].score=0.25*(bstak[i].score+3.*bs_p->score);
else
bstak[i].score=bs_p->score;
}
subcell(bstak[i].cell,player,bocc,blines);
if (hashmode && np!=NULL && np->score>=WEIRD)
np->score=bstak[i].score;
if (dmode>=1 && player*(bstak[i].score-bestsofar)>0) {
copystak(tostak,&bstak[i],futstak);
bestsofar=bstak[i].score;
}
}
topsortstack(bstak,amoves,player);
nocal:
if (dmode>=1) {
if (pmode>=indent)
printshtak(indent,(layers==1?1:amoves),bstak,pch,"out");
if (indent==0) {
printf("Examined %d positions,%d in depth. Skipped %d deep searches.",
b_pos,b_deep,b_skip);
printf("\nDeepest search was %d moves.\n",b_max);
}
}
topstak.score=bstak[0].score;
topstak.cell=bstak[0].cell;
return(&topstak);
}
void printline(int n,struct line linesloc[]) {
int i;
for (i=0;i<SEVEN;i++) {
if (i<llen[n])
printf(" %s ",int2label(*(lptr[n]+i)));
else if (linesloc!=NULL)
printf("  ");
}
if (linesloc==NULL)
printf("\n");
else
printf(" X=%d,O=%d,%s\n",
linesloc[n].x,linesloc[n].o,
(linesloc[n].ded==0 ? "OK" : "dead"));
}
void brd2occ(char (*pbrd)[SEVEN+2],int *occ)
{
int i,j;
char *cptr;
for (i=0;i<SEVEN;i++) {
for (j=0;j<SEVEN;j++) {
cptr=pbrd[i]+j;
if (*cptr=='+') occ[SEVEN*i+j]=2;
else if (*cptr=='X') occ[SEVEN*i+j]=1;
else if (*cptr=='O') occ[SEVEN*i+j]=(-1);
else occ[SEVEN*i+j]=0;
}
}
}
void brd2board()
{
char *cptr;
int i,j,len;
nlines=0;
for (i=0;i<MAXCELLS;i++) {
board[i]=i;
board[i+MAXCELLS]=(i*SEVEN)%MAXCELLS+i/SEVEN;
}
for (i=0;i<SEVEN;i++) {
for (j=0;j<SEVEN-2;j++) {
for (len=0;len<SEVEN-j;len++) {
cptr=brd[i]+j+len;
if (*cptr=='+') break;
if (len>=2) {
lptr[nlines]=board+i*SEVEN+j;
llen[nlines]=len+1;
nlines++;
}
}
}
}
for (j=0;j<SEVEN;j++) {
for (i=0;i<SEVEN-2;i++) {
for (len=0;len<SEVEN-i;len++) {
cptr=brd[i+len]+j;
if (*cptr=='+') break;
if (len>=2) {
lptr[nlines]=board+MAXCELLS+j*SEVEN+i;
llen[nlines]=len+1;
nlines++;
}
}
}
}
}
void initboard(occ,lines)
int occ[];
struct line lines[];
{
register int i;
for (i=0;i<ncells;i++)
occ[i]=0;
for (i=0;i<nlines;i++)
lines[i].x=lines[i].o=lines[i].ded=0;
}
void printlines(lines)
struct line lines[];
{
int nn,i;
struct line *lp;
for (i=0;i<nlines;i++) {
lp= &lines[i];
for (nn=0;nn<llen[i];nn++)
printf("%s ",int2label(*(lptr[i]+nn)));
if (lp->ded)
printf(": dead\n");
else if (lp->x)
printf(": X %2d\n",lp->x);
else if (lp->o)
printf(": O %2d\n",lp->o);
else
printf(": open\n");
}
}
void occ2lines(occ,lines)
int occ[];
struct line lines[];
{
int i,j,nn;
struct line *lp;
for (i=0;i<nlines;i++) {
lp= &lines[i];
lp->x=lp->o=0;
for (nn=llen[i]-1;nn>=0;nn--) {
j= *(lptr[i]+nn);
if (occ[j]==0) continue;
if (occ[j]==1) lp->x++;
if (occ[j]==(-1)) lp->o++;
}
compded(lp);
}
}
void copybrd(char (*tbrd)[SEVEN+2],char (*fbrd)[SEVEN+2]) {
int i;
for (i=0;i<SEVEN;i++) {
strcpy(tbrd[i],fbrd[i]);
}
}
char *int2label(in_cell)
int in_cell;
{
static char label[10],c;
int row,column;
if (in_cell==WEIRD) {
strcpy(label,"weird");
}
else if (in_cell<0 || in_cell>=MAXCELLS) {
fprintf(stderr,"int2label(): input cell out of range %d (%d,%d)\n",
in_cell,SEVEN,SEVEN);
strcpy(label,"__");
}
else {
row=1+(in_cell)/SEVEN;
column=1+in_cell%SEVEN;
c=(char)(column-1+(int)'a');
sprintf(label,"%d%c",row,c);
if (dmode>5) printf("int2string(%d) => %s\n",in_cell,label);
}
return(&label[0]);
}
void occ2brd(occ)
int occ[];
{
register int i;
register char c;
for (i=0;i<MAXCELLS;i++) {
if (occ[i]==0) c='-';
else if (occ[i]==1) c='X';
else if (occ[i]==(-1)) c='O';
else if (occ[i]==2) c='+';
else c='M';
brd[i/SEVEN][i%SEVEN]=c;
}
}
void printocc(occ,lines)
int occ[];
struct line lines[];
{
int i,j,k;
printf("\n  ");
for (j=0;j<SEVEN;j++)
printf(" %c",(char)((int)'a'+j));
printf("\n");
for (i=0;i<SEVEN;i++) {
printf("%-4d",(i+1));
for (j=0;j<SEVEN;j++) {
k=SEVEN*i+j;
if (occ[k]<0) printf(" O");
else if (occ[k]==2) printf(" +");
else if (occ[k]>0) printf(" X");
else printf(" .");
}
printf("\n");
}
}
int main(argc,argv)
int argc;
char *argv[];
{
struct line lines[MAXLINES];
struct stack *sp,*bestmove(),*cmove;
int occ[MAXCELLS],i,j;
struct stack outstak[MAXCELLS+1];
int altcan=I_ALTCAN;
int fplayer=1;
char ch,*int2label(),*s;
float score;
while (--argc>0 && (*++argv)[0] =='-') {
for (s=argv[0]+1;*s!='\0';s++) {
switch (*s) {
case 'a':
altcan=atoi(++s);
goto afor;
case 'l':
m_layers=atoi(++s);
goto afor;
case 'b':
beamfac=atof(++s);
if (beamfac<=0.0) beamfac=0.;
goto afor;
case 'd':
dmode=atoi(++s);
goto afor;
case 'h':
hashmode=0;
break;
case 'p':
pmode=atoi(++s);
goto afor;
case 's':
strat=atoi(++s);
goto afor;
case 'o':
min_choices=1;
break;
case 't':
tmode=0;
break;
case 'v':
vmode=1;
break;
default:
fprintf(stderr,"rj: illegal option %s\n",s);
fprintf(stderr,"useage: rj [-t -aN -dN -pN -lN -sN]\n");
exit(1);
}
}
afor: ;
}
switch (strat) {
case 5:
offense=off5;
defense=def5;
break;
case 4:
offense=off4;
defense=def4;
break;
case 3:
offense=off3;
defense=def3;
break;
case 2:
offense=off2;
defense=def2;
break;
case 1:
offense=off1;
defense=def1;
break;
default:
case 0:
offense=off0;
defense=def0;
}
if (hashmode) hashinit();
for (j=0;j<=SEVEN;j++) {
for (i=0;i<SEVEN;i++) {
doffense[i][j]=offense[i+1][j]-offense[i][j];
}
doffense[SEVEN][j]=0.;
}
ncells=MAXCELLS;
nlines=MAXLINES;
initboard(occ,lines);
fplayer=readbrd();
brd2board();
brd2occ(brd,occ);
occ2lines(occ,lines);
if (fplayer==0) {
score=lines2score(lines,1);
printbrd(brd,score);
exit(0);
}
cmove=bestmove(occ,lines,m_layers,0,fplayer,altcan,outstak);
ch=(fplayer>0 ? 'X' : 'O' );
makemove(cmove->cell,fplayer,occ,lines);
occ2brd(occ);
if (dmode>=1) {
printf("checktime()=%d\n",checktime());
printf("future moves: ");
for (sp=outstak; sp->cell!=WEIRD; sp++) {
printf(" %c:%s",
ch,int2label(sp->cell));
ch = (ch=='X' ? 'O' : 'X');
}
printf("\n");
}
printbrd(brd,cmove->score);
fflush(stdout);
exit(0);
}