Author: h.g.muller
Date: 04:04:19 02/10/06
Go up one level in this thread
This one seems to do it. It took me 70 miniutes, (without cheating or debugger),
so the other 3 problems better be really easy compared to this one...
int vectors[] = {16,15,17,0,-16,-15,-17,0,1,-1,16,-16,0,
1,-1,16,-16,15,-15,17,-17,0,
14,-14,18,-18,31,-31,33,-33,0};
int firstdir[] = {2,-1,3,21,12,16,7,12};
char board[128];
int orig, targ;
int negamax(int color, int depth)
{
int origsqr, targsqr, bestorig, besttarg, score, bestscore,
piece, piecetype, victim, dirnr, stepvec;
bestscore = depth<=1 ? 0 : -2;
for(origsqr=0; origsqr<128; origsqr = (origsqr+9) & ~8)
{
piece = board[origsqr];
piecetype = piece&7;
if(piece&color)
{
dirnr = firstdir[piecetype];
while(stepvec = vectors[++dirnr])
{
targsqr = origsqr;
do {
targsqr += stepvec;
if(targsqr & 0x88) break;
victim = board[targsqr];
if(victim & color) break;
if(piecetype<3 &&
( (victim==0) != ((stepvec&7)==0) )
) break;
if((victim&7) == 4) {bestscore = 2; goto cutoff;}
if(depth>1)
{
board[origsqr] = 0; board[targsqr] = piece;
score = -negamax(24-color, depth-1);
board[origsqr] = piece; board[targsqr] = victim;
/*printf("%d: (%2x,%2x) %d %d\n", depth, origsqr,
targsqr, score, bestscore);/**/
if(score>bestscore)
{
bestscore = score;
bestorig = origsqr;
besttarg = targsqr;
}
}
victim += (piecetype < 5);
} while(victim==0);
}
}
}
if(bestscore == -1)
bestscore = -negamax(24-color, 0)/2;
cutoff:
orig = bestorig;
targ = besttarg;
return bestscore;
}
int main(void)
{
int i, j, k, s;
char buf[80], c;
for(i=0;i<128;i+=16)
{
for(j=0;j<8;j++)
{ c = getchar();
k=8;
if(c>='a') {c += 'A'-'a'; k=16;}
switch(c)
{
case 'K': s=4; break;
case 'Q': s=7; break;
case 'R': s=6; break;
case 'B': s=5; break;
case 'N': s=3; break;
case 'P': s=k==8?1:2; break;
case '.': s=0; break;
default: printf("bad piece %c at %d,%d\n",c,i,j); exit(0);
}
if(s) s+= k;
board[i+j] = s;
}
if(getchar() != '\n') {printf("bad format\n"); exit(0);}
}
for(i=2;i<=4;i+=2)
if(negamax(8,i+1))
{
printf("mate in %d by %c%c%c%c\n", i/2,
(orig&7)+'a', (orig>>4)+'1',
(targ&7)+'a', (targ>>4)+'1');
exit(0);
}
printf("no mate found\n");
}
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.