That would be about 150 lines then. Maximax fulfills your conditions, and has 284 lines. But many of those are comments, and many of them are much shorter than 80 characters (not counting the trailing comments), so normally you would combine them if it were not to create space for the comments.
Code: Select all
/***************************************************************************/
/* micro-Max, */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller */
/***************************************************************************/
/* version 3.2 (2000 characters) features: */
/* - recursive negamax search */
/* - quiescence search with recaptures */
/* - recapture extensions */
/* - (internal) iterative deepening */
/* - best-move-first 'sorting' */
/* - a hash table storing score and best move */
/* - full FIDE rules (expt under-promotion) and move-legality checking */
/* This version is for reference only, with all variable names changed to */
/* be more indicative of their meaning, and better layout & more comments. */
/* There is no guarantee, though, that it still compiles or runs. */
#include <stdio.h>
#include <math.h>
#define F(I,S,N) for(I=S;I<N;I++)
#define W(A) while(A)
#define K(A,B) *(int*)(Zobrist+A+(B&8)+S*(B&7))
#define J(A) K(ToSqr+A,Board[ToSqr])-K(FromSqr+A,Piece)-K(CaptSqr+A,Victim)
#define HASHSIZE 16777224
struct _
{ int Key, Score;
char From, To, Draft;
} HashTab[HASHSIZE]; /* hash table, 16M+8 entries*/
int V=112, M=136, S=128, INF=8e3, C=799, /* V=0x70=rank mask, M=0x88 */
Rootep, Nodes, i;
char RootEval, InputFrom, InputTo,
PieceVal[] = {0,1,1,3,-1,3,5,9}, /* relative piece values */
StepVecs[] = /* step-vector lists */
{-16,-15,-17,0, /* white Pawn */
1,16,0, /* Rook */
1,16,15,17,0, /* Q,K, also used for B, bP */
14,18,31,33,0, /* Knight */
7,-1,11,6,8,3,6, /* first direction per piece*/
6,3,5,7,4,5,3,6}, /* initial piece setup */
Board[129], /* board: half of 16x8+dummy*/
Zobrist[1035], /* hash translation table */
Sym[] = ".?+nkbrq?*?NKBRQ"; /* piece symbols on printout*/
int Search(int Side, int Alpha, int Beta, int Eval, int HashKeyLo, int HashKeyHi,
int epSqr, int LastTo, int Depth)
{
int j, StepVec, BestScore, Score, IterDepth, h, i=8, SkipSqr, RookSqr;
char Victim, PieceType, Piece, FromSqr, ToSqr, BestFrom, BestTo, CaptSqr, StartSqr;
struct _*Hash = HashTab;
/* Hash probe. On miss (Internal) Iterative Deepening starts at IterDepth=0, */
/* without move hint. On a hit we start IID from the hashed values, except */
/* when the depth is already sufficient. In this case, if the bound type OK, */
/* we use the hashed score immediately, and otherwise we just do the last */
/* iteration starting with the hash move. */
/* lookup pos. in hash table*/
j = (Side*epSqr^HashKeyLo) & HASHSIZE-9; /* try 8 consec. locations */
while((h=HashTab[++j].Key) && h-HashKeyHi && --i); /* first empty or match */
Hash += i ? j : 0; /* dummy A[0] if miss & full*/
if(Hash->Key) /* hit: pos. is in hash tab */
{ IterDepth = Hash->Draft;
Score = Hash->Score;
BestFrom = Hash->From; /* examine stored data */
if(IterDepth >= Depth) /* if depth sufficient: */
{ if(Score >= Beta|BestFrom&S &&
Score <= Alpha|BestFrom&8
) return Score; /* use if window compatible */
IterDepth = Depth-1; /* or use as iter. start */
}
BestFrom &= ~0x88;
BestTo = Hash->To; /* with best-move hint */
BestTo = IterDepth ? BestTo : 0; /* don't try best at d=0 */
} else IterDepth = BestFrom = BestTo = 0; /* start iter., no best yet */
Nodes++; /* node count (for timing) */
/* We have to search the current node; deepen the search in steps of one */
/* starting from the hashed data as if it were the previous iteration. */
/* In the root (LastTo==8) we deepen until node count or max. depth reached. */
while(IterDepth++ < Depth | /* iterative deepening loop */
LastTo==8 & Nodes<1e7 & IterDepth<98) /* at root until node limit */
{ /* Each iteration consist of a move-generation run, immediately searching */
/* all moves as they are generated. The best move from the previous iter- */
/* ation (still contained in BestFrom, BestTo) is slipped in front, though. */
/* To make this easier, move generation starts at StartSqr = BestFrom. */
/* The S-bit of BestTo indicates if there is a valid best move to try. */
FromSqr = StartSqr = BestFrom; /* start scan at prev. best */
ToSqr |= 8 & ToSqr>>4; /* request try noncastl. 1st*/
BestScore = IterDepth>1 ? -INF : Eval; /* unconsidered:static eval */
do
{ Piece = Board[FromSqr]; /* scan board looking for */
if(Piece & Side) /* own piece (inefficient!)*/
{ StepVec = PieceType = Piece&7; /* set StepVec > 0 */
j = StepVecs[PieceType+16]; /* first step vector Piece */
while(StepVec = PieceType>2&StepVec<0 ? -StepVec : -StepVecs[++j])
/* loop over directions o[] */
{replay: /* resume normal after best */
/* For each direction we scan ToSqr along the ray startig at FromSqr. */
ToSqr = FromSqr;
SkipSqr = RookSqr = S; /* S = 0x80 = dummy square */
do
{ CaptSqr = ToSqr += StepVec; /* ToSqr traverses ray */
/* FromSqr, ToSqr here scan through all tentative moves. If there */
/* is an old best move to try first, this is indicated in the 8-bit */
/* of BestTo (which was copied from the S-bit), and we overrule the */
/* generated ToSqr (which might ly at other distance or in direction) */
/* We then test if ToSqr is on the board, if we have an e.p. capture, */
/* are blocked by an own piece, and if Pawn moves are valid. */
if(BestTo & 8)
CaptSqr = ToSqr = BestTo&~0x88; /* sneak-in prev. best move */
if(ToSqr & 0x88) break; /* board edge hit (M=0x88) */
if(PieceType<3 & ToSqr==epSqr)
CaptSqr = ToSqr^16; /* shift CaptSqr if e.p. */
Victim = Board[CaptSqr];
if(Victim & Side | /* capture own */
PieceType<3 & !(StepVec&7) != !Victim /* bad pawn mode */
) break;
/* If we get here, we have a pseudo-legal move in (FromSqr, ToSqr). */
/* We check it for King capture (or Rook capture after castling). */
/* This can give a beta cutoff, as can the stand-pat score in QS. */
i = 99*PieceVal[Victim&7]; /* value of victim piece */
if(i<0 || /* K capt. or */
epSqr-S && Board[epSqr] && /* non-empty epSqr:castling */
ToSqr-epSqr<2 & epSqr-ToSqr<2 /* bad castling */
) BestScore = INF;
if(BestScore >= Beta) goto cutoff; /* abort on fail high */
/* We now have a move to search. If there is depth left, we different- */
/* ially update the evaluation, Make the move, Search it recursively */
/* UnMake it, and update the best score & move. If not, we ignore it. */
if(h = IterDepth - (ToSqr!=LastTo)) /* remaining depth(-recapt.)*/
{ Score = PieceType<6 ? Board[FromSqr+8]-Board[ToSqr+8] : 0;
/* center positional pts. */
/* Make move & evaluate */
Board[RookSqr] = Board[CaptSqr] = Board[FromSqr] = 0;
Board[ToSqr] = Piece&31; /* do move, strip virgin-bit*/
if(!(RookSqr&0x88))
{ Board[SkipSqr] = Side+6; /* castling: put Rook */
Score += 30; /* & score */
}
if(PieceType<3) /* pawns: */
{ Score -= /* structure, undefended */
9*(((FromSqr-2)&M||Board[FromSqr-2]!=Piece) + /* squares plus bias */
((FromSqr+2)&M||Board[FromSqr+2]!=Piece) - 1);
if(ToSqr+StepVec+1&S)
{ Board[ToSqr] |= 7; /* promote Pawn to Queen, */
i += C; /* add score */
} }
Score = -Search( /* recursive eval. of reply */
24-Side, /* opponent color */
-Beta-(Beta>Eval), /* new Alpha (delayed gain!)*/
BestScore>Alpha ? -BestScore : -Alpha, /* New Beta */
-Eval-Score-i, /* New Eval */
HashKeyLo+J(0), /* New HashKeys */
HashKeyHi+J(8)+SkipSqr-S,/* SkipSqr-S!=0 on castling */
SkipSqr, ToSqr, h); /* New epSqr, LastTo, Depth */
Score -= Score>Eval; /* delayed-gain penalty */
/* If the Search routine was called as move-legality checker, we */
/* now return before unmaking the move if it was the input move. */
if(LastTo==9) /* called as move-legality */
/* checker */
{ if(Score!=-INF & FromSqr==InputFrom & ToSqr==InputTo)/* move found */
{ RootEval = -Eval-i; /* update eval, material */
Rootep = SkipSqr;
return Beta; /* & not in check, signal */
}
Score = BestScore; /* (prevent fail-lows on */
} /* K-capt. replies) */
/* UnMake move */
Board[RookSqr] = Side+38; /* undo move,RookSqr can be */
Board[SkipSqr] = Board[ToSqr] = 0; /* dummy */
Board[FromSqr] = Piece;
Board[CaptSqr] = Victim;
/* Process score. If the move just searched was a previous best */
/* move that was tried first, we take its Score and redo the first */
/* ray of this piece. Otherwise update best score and move. */
if(BestTo&8) /* Move just done was in- */
{ BestScore = Score; /* serted previous best */
BestTo &= ~8;
goto replay;
} /* redo original first move */
if(Score>BestScore)
{ BestScore = Score; /* update max, */
BestFrom = FromSqr; /* best move, */
BestTo = ToSqr | S&RookSqr; /* mark non-castling with S */
} }
/* Determine if we have to continue scanning this ray. We must stop */
/* on a capture, or if the piece is a non-slider, with the exceptions */
/* of double moves for Pawns and King (castlings!). Such double moves */
/* cause setting of the SkipSqr, that otherwise is equal to the dummy S*/
Victim += PieceType<5; /* fake capt. for nonsliding */
if(PieceType<3&6*Side+(ToSqr&0x70)==S /* pawn on 3rd/6th, or */
||(Piece&~24)==36 & /* virgin K, */
j==7 && /* moving sideways, */
RookSqr&0x88 && /* RookSqr not yet set */
Board[RookSqr=(FromSqr|7)-(StepVec>>1&7)]&32 &&
/* virgin Rook in corner */
!(Board[RookSqr^1]|Board[RookSqr^2]) /* 2 empty sqrs. next to R */
) { SkipSqr = ToSqr; Victim--; } /* unfake capt., enable e.p. */
/* continue ray scan if move was non-capture */
} while(!Victim); /* if not capt. continue ray */
} } } while((FromSqr=FromSqr+9&~0x88)-StartSqr); /* next sqr. of board, wrap */
/* All moves have been searched; wrap up iteration by testing for check- or */
/* stalemate, which leave Score at -INF. Call Search with Depth=1 after null */
/* move to determine if we are in check. Finally store result in hash. */
cutoff:
if(BestScore>INF/4 | BestScore<-INF/4)
IterDepth=99; /* mate is indep. of depth */
BestScore = BestScore+INF ? BestScore : /* best loses K: (stale)mate */
-Search(24-Side, -INF, INF, 0, HashKeyLo, HashKeyHi, S, LastTo, 1)/2;
if(!Hash->Key | (Hash->From&M)!=M | Hash->Draft<=IterDepth)
/* if new/better type/depth: */
{ Hash->Key = HashKeyHi; /* store in hash, */
Hash->Score = BestScore;
Hash->Draft = IterDepth;
HashTab->Key = 0; /* dummy stays empty */
Hash->From = BestFrom | /* From & bound type */
8*(BestScore>Alpha) | /* encoded in X S,8 bits */
S*(BestScore<Beta); /* (8=lower, S=upper bound) */
Hash->To = BestTo;
}
/* End of iteration. Start new one if more depth was requested */
/* if(LastTo==8)printf("%2d ply, %9d searched, %6d by (%2x,%2x)\n",
IterDepth-1,Nodes,BestScore,BestFrom,BestTo&0x77); */
}
/* return best score (and in root also best move) after all iterations are done. */
if(LastTo&8)
{ InputFrom = BestFrom;
InputTo = BestTo & ~0x88;
}
return BestScore;
}
int main(void)
{
int j, Side=8, *ptr, InBuf[9]; /* 8=white, 16=black */
/* Initialize board and piece-square table (actually just a square table). */
for(i=0;i<8;i++) /* initial board setup*/
{Board[i] = (Board[i+0x70] = StepVecs[i+24]+40)+8; /* Pieces */
Board[i+0x10] = 18; Board[i+0x60] = 9; /* black, white Pawns */
for(j=0;j<8;j++) Board[16*j+i+8]=(i-4)*(i-4)+(j-3.5)*(j-3.5);
/*common pce-sqr table*/
} /*(in unused half b[])*/
for(i=0x88; i<1035; i++) Zobrist[i]=rand()>>9;
while(1) /* play loop */
{for(i=0;i<121;i++)
printf(" %c", i&8&&(i+=7) ? '\n' : Sym[Board[i]&15]); /* print board */
ptr = InBuf; while((*ptr++ = getchar()) > '\n'); /* read input line */
Nodes=0;
if(*InBuf-'\n')
{InputFrom=InBuf[0]-16*InBuf[1]+C; /* parse entered move */
InputTo =InBuf[2]-16*InBuf[3]+C;
} else Search(Side,-INF,INF,RootEval,1,1,Rootep,8,0); /* or think up one */
for(i=0;i<HASHSIZE;i++)HashTab[i].Key=0; /* clear hash table */
if(Search(Side,-INF,INF,RootEval,1,1,Rootep,9,2)==INF)
Side^=24; /* check legality & do*/
}
return 0;
}
