1
2 /*
3 * Alphabeta negamax search
4 */
5
6
7 #include "phalanx.h"
8
9 extern long Time;
10
11 #define update_PV(move, ply) \
12 { \
13 register int jj; \
14 PV[ply][ply] = move; \
15 for (jj = ply + 1; PV[ply + 1][jj].from; jj++) \
16 PV[ply][jj] = PV[ply + 1][jj]; \
17 PV[ply][jj].from = 0; /* end of copied line */ \
18 }
19
20
21
sortkey(const void * a,const void * b)22 int sortkey( const void *a, const void *b )
23 { return ( ((tmove*)b)->value - ((tmove*)a)->value ); }
24
25
26
search(tmove * m,int n,int Alpha,int Beta)27 int search(
28 tmove *m, /* move list */
29 int n, /* number of moves */
30 int Alpha, int Beta
31 )
32 {
33
34 int i;
35 int maxi = -1;
36 int result;
37
38 if( Abort && ! NoAbort ) return 0;
39
40 /*** internal iterative deepening ***/
41 #define IID
42 #ifdef IID
43 if( Depth > 200 && Beta-Alpha>1 )
44 {
45 int max=0;
46 for( i=1; i!=n; i++ ) if( m[i].value > m[max].value ) max=i;
47 if( m[max].value != CHECKMATE )
48 {
49 int depth=Depth;
50 Depth -= 200;
51 search( m, n, Alpha, Beta );
52 Depth = depth;
53 #undef DEBUGIID
54 #ifdef DEBUGIID
55 if(Depth>400)
56 {
57 max=0; printboard(NULL);
58 for(i=0;i!=n;i++) if(m[i].value>m[max].value) max=i;
59 printm(m[max],NULL); getchar();
60 }
61 #endif
62 }
63 }
64 #endif
65
66 for( i=0; i!=n; i++ )
67 {
68 int max;
69
70 {
71 int j;
72 max = i;
73 for( j=i+1; j!=n; j++ ) if( m[j].value > m[max].value ) max=j;
74 }
75
76 do_move(m+max);
77
78 S[Ply].check = checktest(Color);
79
80 if( i == 0 || Depth <= 0 )
81 result = - evaluate( -Beta, -Alpha );
82 else
83 {
84 #define LMRLMP /* late move reductions and pruning */
85 #ifdef LMRLMP
86 /* Entry condition simplified since XXIV, now we do reduce captures,
87 * promotions and check evasions. We do not reduce if Alpha is
88 * a mate-in-n score, reducing may then lead to false mate announcements. */
89 if( Depth > 0
90 && Alpha > -29000 && Alpha < 29000
91 && !S[Ply].check /* checking move */
92 && i > 2
93 )
94 {
95 int olddepth=Depth;
96 Depth -= Depth/max(6,(33-i))+i+100;
97
98 if( m[max].value <= 0 ) Depth -= 100;
99
100 if( Depth>0 ) /* reduced search */
101 {
102 result = -evaluate( -Alpha-1, -Alpha );
103 Depth = olddepth;
104 if( result <= Alpha ) goto skipsearch;
105 }
106 else /* prune */
107 {
108 PV[Ply][Ply].from=0;
109 Depth=olddepth;
110 result=Alpha;
111 goto skipsearch;
112 }
113 Depth = olddepth;
114 }
115 #endif /* LMRLMP */
116
117 result = - evaluate( -Alpha-1, -Alpha );
118 if( result>Alpha && result<Beta )
119 result = - evaluate( -Beta, -Alpha-1 );
120
121 skipsearch:;
122 }
123
124 undo_move(m+max);
125
126 FollowPV = 0;
127
128 if( result > Alpha )
129 {
130 /*
131 { int i; for(i=Counter-Ply;i!=Counter;i++) printm(G[i].m,NULL);
132 printf("[%i,%i] %i",Alpha,Beta,result); getchar(); }
133 */
134 update_PV( m[max], Ply );
135 Alpha = result;
136 if(Alpha>=Beta)
137 {
138 if( i>0 ) slash_killers( m, i );
139 m[max].value = (CHECKMATE-5000)+Depth;
140 return Alpha;
141 }
142 maxi = i;
143 }
144 else if( i==0 && Depth>0 ) update_PV( m[max], Ply );
145 /* The line above helps to maintain a nice long PV in those rare
146 * cases, where negascout is not able to confirm the fail-high
147 * and then truncates the PV. */
148
149 { tmove mo=m[max]; m[max] = m[i]; m[i] = mo; }
150 }
151
152 if( maxi != -1 ) m[maxi].value = (CHECKMATE-5000)+Depth;
153
154 return Alpha;
155
156 }
157
158
159
160 int EasyMove;
161 int bgs; /* best group size */
162
163 /**
164 *** Sorting root moves and detecting possible `Easy Move'.
165 **/
sort_root_moves(tmove * m,int n)166 int sort_root_moves( tmove *m, int n )
167 {
168 int i;
169 int best = -CHECKMATE;
170 int secondbest = -CHECKMATE;
171 int result;
172
173 bgs=0;
174
175 FollowPV = 0;
176 PV[0][0] = m[0];
177
178 EasyMove = 0;
179
180 for( i=0; i!=n; i++ )
181 {
182 do_move(m+i);
183
184 result = - evaluate( -CHECKMATE, CHECKMATE );
185
186 m[i].value = result/4;
187 if( m[i].in2 )
188 { m[i].value += Values[ m[i].in2>>4 ]; bgs++; }
189 else if( m[i].special )
190 { m[i].value += 100; bgs++; }
191 if( checktest(Color) )
192 { m[i].value += 150; bgs++; }
193
194 undo_move(m+i);
195
196 if( result > best )
197 {
198 tmove mm=m[0]; m[0]=m[i]; m[i]=mm;
199 secondbest = best; best = result;
200 update_PV( m[0], 0 );
201 }
202 else if( result > secondbest ) secondbest = result;
203 }
204
205 qsort( m+1, n-1, sizeof(tmove), sortkey );
206
207 if( n == 1 ) EasyMove = 3;
208 else
209 if( abs(best) > CHECKMATE - 100 ) EasyMove = 2;
210 else
211 if( best - secondbest > 70 ) EasyMove = 1;
212
213 if( Flag.post && EasyMove!=0 && Flag.xboard<2 )
214 {
215 printf( " -> easy move (%i) ", EasyMove );
216 printm(m[0],NULL); puts(" ");
217 }
218
219 return best;
220 }
221
222
223
224 long LastTurn;
225 int Turns;
root_search(void)226 tmove root_search( void )
227 {
228
229 tmove m[256];
230 int rr[256];
231 int n, i;
232 int Alpha, Beta;
233 int r;
234
235 int Nod[256];
236
237 Abort = 0; NoAbort = 1;
238
239 generate_legal_moves( m, &n, checktest(Color) );
240
241 if( Flag.log != NULL )
242 {
243 char pb[2048];
244
245 if( Counter>0 )
246 {
247 fprintf(Flag.log,"\n");
248 if( Flag.ponder == 2 )
249 fprintf(Flag.log," pondering move ");
250 else
251 fprintf(Flag.log," opponent plays ");
252 printm( G[Counter-1].m, pb );
253 fprintf(Flag.log,"%s\n",pb);
254 }
255
256 printboard(pb);
257 fprintf(Flag.log,"%s\n",pb);
258 }
259
260 if( Flag.book )
261 if( Counter < 20 || Bookout < 4 || Flag.analyze )
262 {
263 int b;
264
265 if( Flag.easy && Counter>4
266 && rand()%5000 < Counter*(50+Flag.easy) )
267 b = -1;
268 else
269 b = bookmove( m, n );
270
271 if( b != -1 )
272 {
273 if( Flag.easy )
274 usleep( (rand()%10000) * (50+2*Flag.easy) );
275 Bookout = 0;
276 PV[0][1].from = 0; /* dont start pondering */
277 m[b].value = 0;
278 do_move(m+b);
279 return m[b];
280 } else Bookout ++;
281 }
282
283 init_killers();
284
285 if( n == 0 ) NoAbort = 0;
286 else
287 {
288 int learndepth = 0;
289 int learnalpha = 0;
290
291 Age ++;
292 Nodes = 0;
293
294 A_n = n; A_m = m; A_i = 0;
295
296 PV[0][0].from = 0;
297
298 l_startsearch();
299
300 Ply = 0;
301
302 if( Flag.nps==0 ) Depth=190;
303 else if( Time>400000/Flag.nps ) Depth=90;
304 else Depth=-10;
305
306 if(!Flag.easy)
307 LastIter = Alpha = sort_root_moves( m, n );
308 else
309 {
310 /* Easy levels: Let's shuffle the moves to add randomness. */
311 int i;
312 for( i=1; i<n; i++ )
313 {
314 tmove mm;
315 int ii = rand()%(i+1);
316 mm=m[i]; m[i]=m[ii]; m[ii]=mm;
317 }
318
319 LastIter = Alpha = -CHECKMATE;
320 }
321
322 LastTurn = ptime();
323
324 if( EasyMove == 3 && ! Flag.analyze ) { do_move(m); return m[0]; }
325
326 /* randomize root moves */
327 if( Flag.random && ( Flag.rndlim==0 || Counter <= Flag.rndlim ) )
328 for( i=0; i!=n; i++ )
329 {
330 rr[i] = rand()%(Flag.random+1) - Flag.random/2;
331 /*
332 printf("%4i:",rr[i]); printm(m[i],NULL);
333 if(i%5==4) printf("\n");
334 */
335 }
336 else for( i=0; i!=n; i++ ) rr[i]=0;
337
338 FollowPV = 1;
339 NoAbort = 0;
340 Depth += 100;
341 Ply = 0;
342 A_d = Depth/100;
343
344 memset( Nod, 0, 256*sizeof(int) );
345
346 if( !Flag.polling ) signal(SIGINT,interrupt);
347
348 Turns=0;
349
350 while( ( Flag.ponder==2 || l_iterate() || Flag.analyze )
351 && !Abort && Depth < MAXPLY*100 )
352 {
353 A_d++;
354 Turns=0;
355
356 Beta = CHECKMATE;
357 Alpha = -CHECKMATE;
358
359 if( Flag.analyze && Flag.xboard!=1 ) { A_i=0; verboseline(); }
360
361 for( i=0; i!=n; i++ )
362 {
363 int64 lastnodes = Nodes;
364 A_i = i;
365
366 if( i == 0 )
367 {
368 do_move(m+i);
369 r = - evaluate( -Beta+rr[i], -Alpha+rr[i] )
370 + rr[i];
371 undo_move(m+i);
372
373 if(!Abort)
374 {
375 m[i].value = Alpha = r;
376 update_PV( m[i], 0 );
377 if( Flag.post ) infoline(1,NULL);
378 }
379 }
380 else
381 {
382 do_move(m+i);
383 r = - evaluate( -Alpha-1+rr[i], -Alpha+rr[i] )+rr[i];
384 undo_move(m+i);
385
386 if(!Abort) m[i].value = r;
387 if( m[i].value > Alpha && !Abort ) /* TURN */
388 {
389 Turns++;
390 if(i>bgs) bgs++;
391 update_PV( m[i], 0 );
392 LastTurn = ptime();
393 if( EasyMove != 0 )
394 {
395 EasyMove = 0;
396 if( Flag.post && Flag.xboard<2 )
397 printf(
398 " -> easy move off \n" );
399 }
400 if( Flag.post ) infoline(2,NULL);
401 do_move(m+i);
402 r = - evaluate( -Beta+rr[i], -Alpha+rr[i] )+rr[i];
403 undo_move(m+i);
404 if(!Abort)
405 {
406 m[i].value = Alpha = r;
407 update_PV( m[i], 0 );
408 if( Flag.post ) infoline(1,NULL);
409 }
410
411 {
412 int j, ipom = Nod[i] = Nodes-lastnodes;
413 tmove pom = m[i];
414 int rrr=rr[i];
415 for( j=i; j>0; j-- )
416 { m[j] = m[j-1]; Nod[j] = Nod[j-1];
417 rr[j] = rr[j-1]; }
418 m[j] = pom; Nod[j] = ipom; rr[j]=rrr;
419 }
420
421 }
422 else /* no turn, bubble up by nodes searched */
423 {
424 int j; int64 ipom; tmove pom;
425 int rrr=rr[i];
426 ipom = Nod[i] = Nodes-lastnodes;
427 /* bubble up */
428 pom = m[i];
429 for( j=i; j>bgs+1 && ipom>Nod[j-1]; j-- )
430 { m[j] = m[j-1]; Nod[j] = Nod[j-1];
431 rr[j]=rr[j-1]; }
432 m[j] = pom; Nod[j] = ipom; rr[j]=rrr;
433 }
434 }
435
436 if( Abort )
437 {
438 if( Abort == 1 && Flag.post )
439 puts("search aborted");
440 break;
441 }
442
443 }
444
445 if( !Abort && Depth>300 )
446 { learndepth = Depth; learnalpha = Alpha; }
447
448 if( Flag.post ) infoline(3,NULL);
449 Depth += 100;
450 FollowPV = 1;
451
452 /* Fix some misbehaviour of root moves randomness when
453 * close to game end. */
454 if( Flag.random && G[Counter].mtrl <= Q_VALUE+R_VALUE )
455 for( i=0; i!=n; i++ )
456 if( abs(Alpha)>29990 ) rr[i]=0;
457 else rr[i]/=2;
458
459 if( abs(Alpha) > 29000 )
460 {
461 if( abs(Alpha)+Depth/100 > CHECKMATE ) break;
462
463 if( EasyMove < 2 )
464 {
465 EasyMove = 2;
466 if( Flag.post && Flag.xboard<2 )
467 printf(
468 " -> forced checkmate -> easy move (2) \n");
469 }
470 }
471
472 LastIter = Alpha;
473 }
474
475 Depth -= 100;
476 AllDepth += Depth;
477 {
478 extern long T1;
479 long t=ptime()-T1;
480 if( t != 0 ) AllNPS += 100*Nodes/t;
481 }
482
483 if( Flag.post ) infoline(0,NULL);
484
485 if( Flag.learn && learndepth ) wlearn( learndepth, learnalpha );
486
487 do_move(PV[0]);
488 }
489
490 signal(SIGINT,SIG_IGN);
491
492 return PV[0][0];
493
494 }
495
496