Author: Robert Hyatt
Date: 08:43:42 02/10/06
Go up one level in this thread
On February 10, 2006 at 07:04:19, h.g.muller wrote:
>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...
Remember you have already blown over 50% of your _total_ time allowed, on one of
the 4 programs.
I suspect the intent was to first discover how good the students were at
figuring out which of the assignments were the most doable, and which were going
to be more problematic, even before discovering how good they were at actually
programming.
>
>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 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.