1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
| /***************************************************************************/
/* 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;
}
|