1 /*
2 Sjeng - a chess variants playing program
3 Copyright (C) 2000-2001 Gian-Carlo Pascutto
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19 File: search.c
20 Purpose: contains functions related to the recursive search
21
22 */
23
24 #include "sjeng.h"
25 #include "extvars.h"
26 #include "protos.h"
27 #include "limits.h"
28
29 unsigned long FH, FHF;
30 unsigned long razor_drop, razor_material, drop_cuts, ext_recap, ext_onerep;
31
32 char true_i_depth;
33
34 int bestmovenum;
35
36 int ugly_ep_hack;
37
38 char postpv[STR_BUFF];
39
40 char searching_move[20];
41 int moveleft;
42 int movetotal;
43
44 int legals;
45
46 int failed;
47 int extendedtime;
48
49 int tradefreely;
50
51 int s_threat;
52
53 unsigned long rootnodecount[MOVE_BUFF];
54
55 bool checks[PV_BUFF];
56
57 #define KINGCAP 50000
58 #define NONE 0
59 #define SINGLE 1
60
61
order_moves(move_s moves[],long int move_ordering[],long int see_values[],int num_moves,int best)62 void order_moves (move_s moves[], long int move_ordering[], long int see_values[], int num_moves, int best) {
63
64 int promoted, captured;
65 int i, from, target, seev;
66 /* fill the move ordering array: */
67
68 /* if searching the pv, give it the highest move ordering, and if not, rely
69 on the other heuristics: */
70 if (searching_pv) {
71 searching_pv = FALSE;
72 for (i = 0; i < num_moves; i++) {
73 from = moves[i].from;
74 target = moves[i].target;
75 promoted = moves[i].promoted;
76 captured = moves[i].captured;
77
78 /* give captures precedence in move ordering, and order captures by
79 material gain */
80 if (captured != npiece)
81 {
82 seev = see(ToMove, target, from);
83
84 if (seev >= -50)
85 move_ordering[i] = 50000 + seev;
86 else
87 move_ordering[i] = seev;
88
89 see_values[i] = seev;
90
91 }
92 else
93 move_ordering[i] = 0;
94
95 /* make the pv have highest move ordering: */
96 if (from == pv[1][ply].from
97 && target == pv[1][ply].target
98 && promoted == pv[1][ply].promoted) {
99 searching_pv = TRUE;
100 move_ordering[i] = INF;
101
102 if (captured != npiece)
103 see_values[i] = see(ToMove, target, from);
104 }
105 else if ((best != -1) && (best != -2) && (i == best))
106 {
107 move_ordering[i] = INF;
108
109 if (captured != npiece)
110 see_values[i] = see(ToMove, target, from);
111 }
112 else if (best == -2)
113 {
114 /* we have an iterative deepening move */
115 if (from == pv[ply+1][ply+1].from
116 && target == pv[ply+1][ply+1].target
117 && promoted == pv[ply+1][ply+1].promoted)
118 {
119 move_ordering[i] = INF;
120 }
121 }
122
123 /* heuristics other than pv (no need to use them on the pv move - it is
124 already ordered highest) */
125 else
126 {
127
128 if (ply != 1 || i_depth < 2)
129 {
130 /* add the history heuristic bonus: */
131 move_ordering[i] += (history_h[from][target]>>i_depth);
132
133 /* add the killer move heuristic bonuses: */
134 if (from == killer1[ply].from && target == killer1[ply].target
135 && promoted == killer1[ply].promoted)
136 move_ordering[i] += 10000;
137 else if (from == killer2[ply].from && target == killer2[ply].target
138 && promoted == killer2[ply].promoted)
139 move_ordering[i] += 5000;
140 else if (from == killer3[ply].from && target == killer3[ply].target
141 && promoted == killer3[ply].promoted)
142 move_ordering[i] += 2500;
143 }
144 else
145 {
146 if ((nodes / 100) > INF)
147 {
148 move_ordering[i] = rootnodecount[i] / 1000;
149 }
150 else
151 {
152 move_ordering[i] = rootnodecount[i] / 100;
153 }
154 }
155 }
156 }
157 }
158
159 /* if not searching the pv: */
160 else {
161 for (i = 0; i < num_moves; i++) {
162 from = moves[i].from;
163 target = moves[i].target;
164 promoted = moves[i].promoted;
165 captured = moves[i].captured;
166
167 /* give captures precedence in move ordering, and order captures by
168 material gain */
169 if ((best != -1) && (i == best))
170 {
171 move_ordering[i] = INF;
172
173 /* make sure we have SEE data */
174 if (captured != npiece)
175 see_values[i] = see(ToMove, target, from);
176
177 }
178 else if (best == -2)
179 {
180 /* we have an iterative deepening move */
181 if (from == pv[ply+1][ply+1].from
182 && target == pv[ply+1][ply+1].target
183 && promoted == pv[ply+1][ply+1].promoted)
184 {
185 move_ordering[i] = INF;
186
187 if (captured != npiece)
188 see_values[i] = see(ToMove, target, from);
189 }
190 }
191 else if (captured != npiece)
192 {
193 seev = see(ToMove, target, from);
194
195 if (seev >= -50)
196 move_ordering[i] = 50000 + seev;
197 else
198 move_ordering[i] = seev;
199
200 see_values[i] = seev;
201
202 }
203 else
204 move_ordering[i] = 0;
205
206 /* heuristics other than pv */
207
208 /* add the history heuristic bonus: */
209 move_ordering[i] += (history_h[from][target]>>i_depth);
210
211 /* add the killer move heuristic bonuses: */
212 if (from == killer1[ply].from && target == killer1[ply].target
213 && promoted == killer1[ply].promoted)
214 move_ordering[i] += 10000;
215 else if (from == killer2[ply].from && target == killer2[ply].target
216 && promoted == killer2[ply].promoted)
217 move_ordering[i] += 5000;
218 else if (from == killer3[ply].from && target == killer3[ply].target
219 && promoted == killer3[ply].promoted)
220 move_ordering[i] += 2500;
221 }
222 }
223
224 }
225
perft(int depth)226 void perft (int depth) {
227
228 move_s moves[MOVE_BUFF];
229 int num_moves, i;
230 int ic;
231
232 //ep_temp = ep_square;
233 num_moves = 0;
234
235 /* return if we are at the maximum depth: */
236 if (!depth) {
237 raw_nodes++;
238 return;
239 }
240
241 /* generate the move list: */
242 gen (&moves[0]);
243 num_moves = numb_moves;
244
245 ic = in_check();
246
247 /* loop through the moves at the current depth: */
248 for (i = 0; i < num_moves; i++) {
249 make (&moves[0], i);
250
251 /* check to see if our move is legal: */
252 if (check_legal (&moves[0], i, ic)) {
253 /* go deeper into the tree recursively, increasing the indent to
254 create the "tree" effect: */
255 perft (depth-1);
256 }
257
258 /* unmake the move to go onto the next: */
259 unmake (&moves[0], i);
260 }
261
262 //ep_square = ep_temp;
263
264 }
265
266
qsearch(int alpha,int beta,int depth)267 long int qsearch (int alpha, int beta, int depth) {
268
269 /* perform a quiscense search on the current node using alpha-beta with
270 negamax search */
271
272 move_s moves[MOVE_BUFF];
273 int num_moves, i, j;
274 long int score = -INF, standpat,
275 move_ordering[MOVE_BUFF],
276 see_values[MOVE_BUFF];
277 bool legal_move, no_moves = TRUE;
278 int sbest, best_score, best, delta, bound;
279 int originalalpha;
280 int oldtime;
281 int seev;
282
283 pv_length[ply] = ply;
284
285 /* before we do anything, see if we're out of time: */
286 if (!(nodes & 8191))
287 {
288 if (interrupt())
289 {
290 time_exit = TRUE;
291 return 0;
292 }
293 else if (((rdifftime (rtime (), start_time) >= time_for_move)) && (i_depth > 1))
294 {
295 if (failed == 1 && !extendedtime
296 && !fixed_time
297 && !go_fast
298 && Variant != Bughouse
299 && (time_left > max(time_for_move*4, 1000)))
300 {
301 extendedtime = 1;
302 oldtime = time_for_move;
303 time_for_move += allocate_time();
304 printf("Extended from %d to %d, time left %d\n", oldtime,
305 time_for_move,
306 time_left);
307 }
308 else
309 {
310 time_exit = TRUE;
311 return 0;
312 }
313 }
314 }
315
316 /* return our score if we're at a leaf node: */
317 if (depth <= 0 || ply > maxdepth)
318 {
319 /* remove leafcounting effect */
320 qnodes--;
321 nodes--;
322 score = eval ();
323 return score;
324 }
325
326 originalalpha = alpha;
327
328 switch (QProbeTT(&bound, alpha, beta, &best))
329 {
330 case EXACT:
331 return bound;
332 break;
333 case UPPER:
334 if (bound <= alpha)
335 return bound;
336 if (bound < beta)
337 beta = bound;
338 break;
339 case LOWER:
340 if (bound >= beta)
341 return bound;
342 if (bound > alpha)
343 alpha = bound;
344 break;
345 case DUMMY:
346 break;
347 case HMISS:
348 best = -1;;
349 break;
350 };
351
352 standpat = eval ();
353
354 if (standpat >= beta) {
355 /* rem check this */
356 QStoreTT(standpat, originalalpha, beta, 500);
357 return standpat;
358 }
359 else if (standpat > alpha) {
360 alpha = standpat;
361 }
362
363 sbest = -1;
364 best_score = -INF;
365 num_moves = 0;
366
367 delta = alpha-150-standpat;
368
369 /* generate and order moves: */
370 gen (&moves[0]);
371 num_moves = numb_moves;
372
373 if (kingcap) return KINGCAP;
374
375 order_moves (&moves[0], &move_ordering[0], &see_values[0], num_moves, best);
376
377 /* loop through the moves at the current node: */
378 while (remove_one (&i, &move_ordering[0], num_moves)) {
379
380 legal_move = FALSE;
381
382 seev = see_values[i];
383
384 if (((seev < delta) || (seev < 0)) && !moves[i].promoted)
385 continue;
386
387 make (&moves[0], i);
388
389 score = -qsearch (-beta, -alpha, depth-1);
390
391 if (score != -KINGCAP)
392 {
393 nodes++;
394 qnodes++;
395
396 legal_move = TRUE;
397 no_moves = FALSE;
398 };
399
400 unmake (&moves[0], i);
401
402 if(score > best_score && legal_move)
403 {
404 best_score = score;
405 };
406
407 /* check our current score vs. alpha: */
408 if (score > alpha && legal_move)
409 {
410
411 /* don't update the history heuristic scores here, since depth is messed
412 up when qsearch is called */
413 best = i;
414
415 /* try for an early cutoff: */
416 if (score >= beta)
417 {
418 QStoreTT(score, originalalpha, beta, i);
419 return score;
420 }
421
422 alpha = score;
423
424 /* update the pv: */
425 pv[ply][ply] = moves[i];;
426 for (j = ply+1; j < pv_length[ply+1]; j++)
427 pv[ply][j] = pv[ply+1][j];
428 pv_length[ply] = pv_length[ply+1];
429 }
430
431 }
432
433 /* we don't check for mate / stalemate here, because without generating all
434 of the moves leading up to it, we don't know if the position could have
435 been avoided by one side or not */
436
437 if (no_moves)
438 {
439 /* we tried all moves and none were good...sack to alpha */
440 return standpat;
441 }
442 else
443 {
444 QStoreTT(alpha, originalalpha, beta, best);
445 return alpha;
446 }
447 }
448
remove_one(int * marker,long int move_ordering[],int num_moves)449 bool remove_one (int *marker, long int move_ordering[], int num_moves) {
450
451 /* a function to give pick the top move order, one at a time on each call.
452 Will return TRUE while there are still moves left, FALSE after all moves
453 have been used */
454
455 int i, best = -INF;
456
457 *marker = -INF;
458
459 for (i = 0; i < num_moves; i++) {
460 if (move_ordering[i] > best) {
461 *marker = i;
462 best = move_ordering[i];
463 }
464 }
465
466 if (*marker > -INF) {
467 move_ordering[*marker] = -INF;
468 return TRUE;
469 }
470 else {
471 return FALSE;
472 }
473
474 }
475
search(int alpha,int beta,int depth,int is_null)476 long int search (int alpha, int beta, int depth, int is_null) {
477
478 /* search the current node using alpha-beta with negamax search */
479
480 move_s moves[MOVE_BUFF];
481 int num_moves, i, j;
482 long int score = -INF, move_ordering[MOVE_BUFF], see_values[MOVE_BUFF];
483 bool no_moves, legal_move;
484 int bound, threat, donull, best, sbest, best_score, old_ep;
485 bool incheck, first;
486 int extend, fscore, fmax, selective;
487 move_s kswap;
488 int ksswap;
489 int originalalpha;
490 int afterincheck;
491 int legalmoves;
492 int dropcut;
493 int oldtime;
494 int egscore;
495 static const int rc_index[14] = {0,1,1,2,2,5,5,3,3,4,4,2,2,0};
496
497 /* before we do anything, see if we're out of time: */
498 if (!(nodes & 8191)) {
499 if (interrupt())
500 {
501 time_exit = TRUE;
502 return 0;
503 }
504 else if (((rdifftime (rtime (), start_time) >= time_for_move)) && (i_depth > 1))
505 {
506 if (failed == 1 && !extendedtime
507 && !fixed_time
508 && !go_fast
509 && Variant != Bughouse
510 && (time_left > max(time_for_move*4, 1000)))
511 {
512 extendedtime = 1;
513 oldtime = time_for_move;
514 time_for_move += allocate_time();
515 printf("Extended from %d to %d, time left %d\n", oldtime,
516 time_for_move,
517 time_left);
518 }
519 else
520 {
521 time_exit = TRUE;
522 return 0;
523 }
524 }
525 }
526
527 originalalpha = alpha;
528 fmax = -INF;
529
530 threat = 0;
531 extend = 0;
532
533 pv_length[ply] = ply;
534
535 if (is_draw ())
536 {
537 return 0;
538 }
539
540 if ((path[ply-1].captured != npiece || ply == 2))
541 {
542 if (piece_count <= EGTBPieces && (Variant == Normal))
543 {
544 egscore = probe_egtb();
545 if (egscore != KINGCAP)
546 return egscore;
547 }
548 else if (piece_count <= 3 && (Variant == Suicide) && SEGTB)
549 {
550 EGTBProbes++;
551
552 egscore = egtb(white_to_move);
553 if (egscore != -128)
554 {
555 EGTBHits++;
556 if (egscore < 0)
557 {
558 return -INF+(129+egscore);
559 }
560 else if (egscore > 0)
561 {
562 return INF-(129-egscore);
563 }
564 else if (egscore == 0)
565 return 0;
566 }
567 }
568 }
569
570 incheck = checks[ply];
571
572 /* perform check extensions if we haven't gone past maxdepth: */
573 if (ply < maxdepth+1 && incheck && ((ply <= i_depth*2) || (depth == 0)))
574 {
575 depth++;
576 ext_check++;
577 extend++;
578 }
579 else if ((ply < maxdepth+1) && (ply > 2) && (ply < (i_depth*2))
580 && (depth <= 2)
581 && cfg_recap
582 && (path[ply-1].captured != 13)
583 && (rc_index[path[ply-1].captured] == rc_index[path[ply-2].captured]))
584 {
585 depth++;
586 ext_recap++;
587 extend++;
588 }
589
590 /* try to find a stable position before passing the position to eval (): */
591 if (depth <= 0 || ply >= maxdepth)
592 {
593
594 if (Variant != Suicide && Variant != Losers)
595 {
596 captures = TRUE;
597 score = qsearch (alpha, beta, maxdepth);
598 captures = FALSE;
599 return score;
600 }
601 else
602 {
603 if (Variant == Suicide)
604 {
605 return suicide_eval();
606
607 }
608 else if (Variant == Losers)
609 {
610 i = losers_eval();
611
612 if (abs(i) == INF)
613 {
614 return ((i > 0) ? INF-ply : -INF+ply);
615 }
616 else
617 {
618 return i;
619 }
620 }
621 }
622 }
623
624 num_moves = 0;
625 no_moves = TRUE;
626
627 switch (ProbeTT(&bound, alpha, beta, &best, &threat, &donull, depth))
628 {
629 case EXACT:
630 return bound;
631 break;
632 case UPPER:
633 if (bound <= alpha)
634 return bound;
635 if (bound < beta)
636 beta = bound;
637 best = -1;
638 break;
639 case LOWER:
640 if (bound >= beta)
641 return bound;
642 if (bound > alpha)
643 alpha = bound;
644 break;
645 case DUMMY:
646 break;
647 case HMISS:
648 best = -1;
649 threat = FALSE;
650 break;
651 };
652
653 if (best == 500) best = -1;
654
655 sbest = -1;
656 best_score = -INF;
657
658 old_ep = ep_square;
659
660 legalmoves = 0;
661
662 if (Variant == Losers)
663 {
664 i = losers_eval();
665
666 if (abs(i) == INF)
667 {
668 return (i > 0) ? i-ply : i+ply;
669 }
670
671 captures = TRUE;
672 gen (&moves[0]);
673 num_moves = numb_moves;
674 captures = FALSE;
675
676 if (num_moves)
677 {
678 for (i = 0; i < num_moves; i++)
679 {
680 make(&moves[0], i);
681 if (check_legal(&moves[0], i, incheck))
682 {
683 legalmoves++;
684 }
685 unmake(&moves[0], i);
686 }
687 }
688 if (!legalmoves)
689 {
690 captures = FALSE;
691 gen(&moves[0]);
692 num_moves = numb_moves;
693 };
694
695 legalmoves = 0;
696 }
697
698 if ((is_null == NONE)
699 && ((phase != Endgame) || ((phase == Endgame) && (depth <= 6)))
700 && !incheck && donull && !searching_pv
701 && (threat == FALSE)
702 && (((Variant != Suicide) && (Variant != Losers))
703 || (Variant == Losers && moves[0].captured == npiece)))
704 {
705
706 ep_square = 0;
707 white_to_move ^= 1;
708 ply++;
709 fifty++;
710 hash ^= 0xDEADBEEF;
711
712 /* use R=1 cos R=2 is too dangerous for our ply depths */
713 if (Variant != Normal && Variant != Losers)
714 score = -search(-beta, -beta+1, ((depth > 3) ? depth-2-1 : depth-1-1), SINGLE);
715 else
716 {
717 if (depth > 11)
718 score = -search(-beta, -beta+1, depth-4-1, SINGLE);
719 else if (depth > 6)
720 score = -search(-beta, -beta+1, depth-3-1, SINGLE);
721 else
722 score = -search(-beta, -beta+1, depth-2-1, SINGLE);
723
724 };
725
726 hash ^= 0xDEADBEEF;
727 fifty--;
728 ply--;
729 white_to_move ^= 1;
730 ep_square = old_ep;
731
732 if (time_exit) return 0;
733
734 NTries++;
735
736 if (score >= beta)
737 {
738
739 NCuts++;
740
741 StoreTT(score, alpha, beta, 500, 0, depth);
742
743 return score;
744 }
745 else if (score < -INF+100)
746 {
747 threat = TRUE;
748 TExt++;
749 depth++;
750 extend++;
751 ext_onerep++;
752 }
753 }
754 else if (threat == TRUE)
755 {
756 TExt++;
757 depth++;
758 extend++;
759 ext_onerep++;
760 }
761
762 score = -INF;
763
764 first = TRUE;
765 selective = 0;
766
767 if (phase != Endgame && (Variant != Suicide) && cfg_futprune)
768 {
769
770 fscore = (white_to_move ? Material : -Material) + 900;
771
772 if (!extend && depth == 3 && fscore <= alpha)
773 depth = 2;
774
775 fscore = (white_to_move ? Material : -Material) + 500;
776
777 if (!extend && depth == 2 && fscore <= alpha)
778 {
779 selective = 1;
780 best_score = fmax = fscore;
781 }
782
783 fscore = (white_to_move ? Material : -Material) + ((Variant == Normal) ? 150 : 200);
784
785 if (!extend && depth == 1 && fscore <= alpha)
786 {
787 selective = 1;
788 best_score = fmax = fscore;
789 }
790 }
791
792 if (Variant != Losers)
793 {
794 /* generate and order moves: */
795 gen (&moves[0]);
796 num_moves = numb_moves;
797 }
798
799
800 if ((Variant == Suicide) && num_moves == 1) depth++;
801 else if ((Variant == Losers) && legalmoves == 1) depth++;
802
803 if (num_moves > 0)
804 {
805
806 order_moves (&moves[0], &move_ordering[0], &see_values[0], num_moves, best);
807
808 /* loop through the moves at the current node: */
809 while (remove_one (&i, &move_ordering[0], num_moves)) {
810
811 make (&moves[0], i);
812
813 legal_move = FALSE;
814
815 hash_history[move_number+ply-1] = hash;
816 path[ply-1] = moves[i];
817
818 //old_ep = ep_square;
819
820 extend = 0; /* dont extend twice */
821
822 /* go deeper if it's a legal move: */
823
824 if (check_legal (&moves[0], i, incheck)) {
825
826 afterincheck = f_in_check(&moves[0], i);
827 checks[ply] = afterincheck;
828
829 if (!afterincheck && ((Variant == Normal)
830 || (Variant == Suicide)
831 || (Variant == Losers)) && (depth < 3) &&
832 (((board[moves[i].target] == wpawn) && (rank(moves[i].target) >= 6)
833 || ((board[moves[i].target] == bpawn) && (rank(moves[i].target) <= 3)))))
834 {
835 extend++;
836 };
837
838 dropcut = 0;
839
840 /* Razoring of uninteresting drops */
841 if ((moves[i].from == 0)
842 && (depth > 1) /* more than pre-frontier nodes */
843 && (afterincheck == 0) /* not a contact checking move */
844 && (incheck == 0) /* not a check evasion */
845 && !searching_pv
846 && cfg_razordrop
847 )
848 { razor_drop++; extend--;}
849 else
850 {
851 if ((moves[i].from == 0) && (depth == 1) && (incheck == 0) && cfg_cutdrop)
852 {
853 if (white_to_move)
854 {
855 dropcut = (calc_attackers(moves[i].target, 1)
856 - calc_attackers(moves[i].target, 0)) > 0;
857 if (dropcut) drop_cuts++;
858 }
859 else
860 {
861 dropcut = (calc_attackers(moves[i].target, 0)
862 - calc_attackers(moves[i].target, 1)) > 0;
863 if (dropcut) drop_cuts++;
864 }
865 }
866
867 }
868
869 if (!dropcut && (!selective || (afterincheck != 0)
870 || (fmax + ((abs(material[moves[i].captured]) *
871 ((Variant == Normal || Variant == Losers)?1:2)
872 )) > alpha)
873 || (moves[i].promoted)))
874 {
875
876 /* we only count the nodes we actually examine */
877
878 nodes++;
879
880 if (first == TRUE)
881 {
882 score = -search (-beta, -alpha, depth+extend-1, NONE);
883 FULL++;
884 }
885 else
886 {
887 score = -search (-alpha-1, -alpha, depth+extend-1, NONE);
888 PVS++;
889
890 if (score > best_score && !time_exit && score != -KINGCAP)
891 {
892 if ((score > alpha) && (score < beta))
893 {
894 score = -search(-beta, -score, depth+extend-1, NONE);
895 // ep_square = old_ep;
896 PVSF++;
897
898 if (score > best_score) best_score = score;
899 }
900 else
901 best_score = score;
902 }
903 }
904
905 legal_move = TRUE;
906
907 }
908 else
909 razor_material++;
910
911
912 legalmoves++;
913 no_moves = FALSE;
914 }
915
916 if (score > best_score && legal_move)
917 {
918 best_score = score;
919 };
920
921 unmake (&moves[0], i);
922
923 /* return if we've run out of time: */
924 if (time_exit) return 0;
925
926 /* check our current score vs. alpha: */
927 if (score > alpha && legal_move) {
928
929 /* try for an early cutoff: */
930 if (score >= beta) {
931
932 /* update the history heuristic since we have a cutoff: */
933 history_h[moves[i].from][moves[i].target] += depth * depth;
934
935 if (moves[i].captured == npiece)
936 {
937 /* we have a cutoff, so update our killers: */
938 /* first, check whether it matches one of the known killers */
939 if (moves[i].from == killer1[ply].from && moves[i].target ==
940 killer1[ply].target && moves[i].promoted == killer1[ply].promoted)
941 {
942 killer_scores[ply]++;
943 }
944 else if (moves[i].from == killer2[ply].from && moves[i].target ==
945 killer2[ply].target && moves[i].promoted == killer2[ply].promoted)
946 {
947 killer_scores2[ply]++;
948
949 if (killer_scores2[ply] > killer_scores[ply])
950 {
951 kswap = killer1[ply];
952 killer1[ply] = killer2[ply];
953 killer2[ply] = kswap;
954 ksswap = killer_scores[ply];
955 killer_scores[ply] = killer_scores2[ply];
956 killer_scores2[ply] = ksswap;
957 }
958 }
959
960 else if (moves[i].from == killer3[ply].from && moves[i].target ==
961 killer3[ply].target && moves[i].promoted == killer3[ply].promoted)
962 {
963
964 killer_scores3[ply]++;
965
966 if (killer_scores3[ply] > killer_scores2[ply])
967 {
968 kswap = killer2[ply];
969 killer2[ply] = killer3[ply];
970 killer3[ply] = kswap;
971 ksswap = killer_scores2[ply];
972 killer_scores2[ply] = killer_scores3[ply];
973 killer_scores3[ply] = ksswap;
974 }
975 }
976 /* if not, replace killer3 */
977 else
978 {
979 killer_scores3[ply] = 1;
980 killer3[ply] = moves[i];
981 }
982 }
983
984 if (first == TRUE) FHF++;
985
986 FH++;
987
988 StoreTT(score, originalalpha, beta, i, threat, depth);
989
990 return score;
991 }
992
993 alpha = score;
994
995 sbest = i;
996
997 /* update the pv: */
998 pv[ply][ply] = moves[i];
999 for (j = ply+1; j < pv_length[ply+1]; j++)
1000 pv[ply][j] = pv[ply+1][j];
1001 pv_length[ply] = pv_length[ply+1];
1002 }
1003
1004 if (legal_move)
1005 first = FALSE;
1006
1007 }
1008
1009 if (legalmoves <= 1 && (Variant != Suicide) && cfg_onerep) threat = TRUE;
1010 }
1011 else
1012 {
1013 /* no generated moves..only happens in suicide */
1014 StoreTT(INF-ply, originalalpha, beta, 0, threat, depth);
1015 return INF-ply;
1016 }
1017
1018 /* check for mate / stalemate: */
1019 if (no_moves)
1020 {
1021 if (Variant != Losers && Variant != Suicide)
1022 {
1023 if (in_check ())
1024 {
1025 StoreTT(-INF+ply, originalalpha, beta, 0, threat, depth);
1026 return (-INF+ply);
1027 }
1028 else
1029 {
1030 StoreTT(0, originalalpha, beta, 0, threat, depth);
1031 return 0;
1032 }
1033 }
1034 else
1035 {
1036 StoreTT(INF-ply, originalalpha, beta, 0, threat, depth);
1037 return (INF-ply);
1038 }
1039 }
1040 else
1041 {
1042 if (fifty > 100)
1043 {
1044 return 0;
1045 }
1046 };
1047
1048 /* doesnt seem to have any effect */
1049 if (sbest == -1) sbest = 500;
1050
1051 if (best_score <= originalalpha)
1052 {
1053 if (!selective)
1054 StoreTT(best_score, originalalpha, beta, sbest, threat, depth);
1055 }
1056 else
1057 {
1058 if (!selective)
1059 StoreTT(best_score, originalalpha, beta, sbest, threat, depth);
1060 else
1061 StoreTT(best_score, -INF, -INF, sbest, threat, depth);/*store lowbound*/
1062 }
1063
1064 return best_score;
1065
1066 }
1067
1068
search_root(int originalalpha,int originalbeta,int depth)1069 move_s search_root (int originalalpha, int originalbeta, int depth) {
1070
1071 /* search the root node using alpha-beta with negamax search */
1072
1073 move_s moves[MOVE_BUFF], best_move = dummy;
1074 int num_moves, i, j;
1075 long int root_score = -INF, move_ordering[MOVE_BUFF], see_values[MOVE_BUFF];
1076 bool no_moves, legal_move, first;
1077 int alpha, beta;
1078 move_s kswap;
1079 move_s oldbest;
1080 int oldbestnum;
1081 int ksswap;
1082 int incheck;
1083 int mc = 0;
1084 int oldnodecount;
1085
1086 alpha = originalalpha;
1087 beta = originalbeta;
1088
1089 num_moves = 0;
1090 no_moves = TRUE;
1091 ply = 1;
1092 searching_pv = TRUE;
1093 time_exit = FALSE;
1094 time_failure = FALSE;
1095 first = TRUE;
1096 cur_score = -INF;
1097
1098 /* check for a draw by 3 fold repetition: */
1099 if (is_draw ())
1100 {
1101 result = draw_by_rep;
1102 cur_score = 0;
1103 pv_length[ply] = 0;
1104 return (dummy);
1105 };
1106
1107 pv_length[ply] = ply;
1108 // GCP
1109 hash_history[move_number+ply-1] = hash;
1110
1111 /*check extensions: */
1112
1113 incheck = in_check ();
1114
1115 if (incheck)
1116 {
1117 ext_check++;
1118 depth++;
1119 };
1120
1121 checks[ply] = incheck;
1122
1123 if (Variant == Losers)
1124 {
1125 legals = 0;
1126 captures = TRUE;
1127 gen (&moves[0]);
1128 num_moves = numb_moves;
1129 captures = FALSE;
1130
1131 if (num_moves)
1132 {
1133 for (i = 0; i < num_moves; i++)
1134 {
1135 make(&moves[0], i);
1136 if (check_legal(&moves[0], i, incheck))
1137 {
1138 legals++;
1139 }
1140 unmake(&moves[0], i);
1141 }
1142 }
1143
1144 if (!legals)
1145 {
1146 captures = FALSE;
1147 gen(&moves[0]);
1148 num_moves = numb_moves;
1149
1150 for (i = 0; i < num_moves; i++)
1151 {
1152 make(&moves[0], i);
1153 if (check_legal(&moves[0], i, incheck))
1154 {
1155 legals++;
1156 }
1157 unmake(&moves[0], i);
1158 }
1159 };
1160 }
1161 else
1162 {
1163 /* generate and order moves: */
1164
1165 gen (&moves[0]);
1166 num_moves = numb_moves;
1167 }
1168
1169 movetotal = legals;
1170
1171 order_moves (&moves[0], &move_ordering[0], &see_values[0], num_moves, -1);
1172
1173 /* loop through the moves at the root: */
1174 while (remove_one (&i, &move_ordering[0], num_moves)) {
1175
1176 if (!alllosers && rootlosers[i] && ((Variant == Losers) || (Variant == Suicide))) continue;
1177
1178 make (&moves[0], i);
1179 legal_move = FALSE;
1180
1181 hash_history[move_number+ply-1] = hash;
1182 path[ply-1] = moves[i];
1183
1184 oldnodecount = nodes;
1185
1186 //old_ep = ep_square;
1187
1188 /* go deeper if it's a legal move: */
1189 if (check_legal (&moves[0], i, incheck)) {
1190
1191 unmake(&moves[0], i);
1192 mc++;
1193 moveleft = movetotal - mc;
1194 comp_to_san(moves[i], searching_move);
1195 make(&moves[0], i);
1196
1197 nodes++;
1198
1199 checks[ply] = f_in_check(&moves[0], i);
1200
1201 if ((first == TRUE) || (i_depth < 2))
1202 {
1203 root_score = -search (-beta, -alpha, depth-1, NONE);
1204 //ep_square = old_ep;
1205
1206 if (!time_exit && (post || !xb_mode) && i_depth >= mindepth)
1207 {
1208 if (root_score >= beta)
1209 {
1210 /* update the pv: */
1211 pv[ply-1][ply-1] = moves[i];
1212 for (j = ply; j < pv_length[ply]; j++)
1213 pv[ply-1][j] = pv[ply][j];
1214 pv_length[ply-1] = pv_length[ply];
1215
1216 post_fh_thinking(root_score, &moves[i]);
1217 }
1218 else if (root_score <= alpha)
1219 {
1220 /* update the pv: */
1221 /* maybe not..fail low yields nonsense */
1222 // pv[ply-1][ply-1] = moves[i];
1223 // for (j = ply; j < pv_length[ply]; j++)
1224 // pv[ply-1][j] = pv[ply][j];
1225 // pv_length[ply-1] = pv_length[ply];
1226
1227 failed = 1;
1228
1229 post_fl_thinking(root_score, &moves[i]);
1230 }
1231 else
1232 {
1233 /* update the pv: */
1234 pv[ply-1][ply-1] = moves[i];
1235 for (j = ply; j < pv_length[ply]; j++)
1236 pv[ply-1][j] = pv[ply][j];
1237 pv_length[ply-1] = pv_length[ply];
1238
1239 post_thinking(root_score);
1240 }
1241
1242 if (root_score > cur_score && !time_exit)
1243 {
1244 cur_score = root_score;
1245 bestmovenum = i;
1246 best_move = moves[i];
1247 }
1248
1249 }
1250 }
1251 else
1252 {
1253 root_score = -search (-alpha-1, -alpha, depth-1, NONE);
1254 //ep_square = old_ep;
1255
1256 if ((root_score > alpha) && (root_score < beta) && !time_exit)
1257 {
1258 post_fail_thinking(root_score, &moves[i]);
1259
1260 oldbest = best_move;
1261 oldbestnum = bestmovenum;
1262
1263 if (root_score > cur_score && !time_exit)
1264 {
1265 cur_score = root_score;
1266 bestmovenum = i;
1267 best_move = moves[i];
1268 }
1269
1270 root_score = -search(-beta, -root_score, depth-1, NONE);
1271 //ep_square = old_ep;
1272
1273 if (root_score > alpha && !time_exit)
1274 {
1275 failed = 0;
1276
1277 cur_score = root_score;
1278 bestmovenum = i;
1279 best_move = moves[i];
1280
1281 if (i_depth >= mindepth)
1282 {
1283 /* update the pv: */
1284 pv[ply-1][ply-1] = moves[i];
1285 for (j = ply; j < pv_length[ply]; j++)
1286 pv[ply-1][j] = pv[ply][j];
1287 pv_length[ply-1] = pv_length[ply];
1288 }
1289 }
1290 else {best_move = oldbest; bestmovenum = oldbestnum; };
1291 }
1292
1293 if (root_score >= beta && !time_exit)
1294 post_fh_thinking(root_score, &moves[i]);
1295 }
1296
1297 if (root_score > cur_score && !time_exit)
1298 {
1299 cur_score = root_score;
1300 bestmovenum = i;
1301 best_move = moves[i];
1302 }
1303
1304 /* check to see if we've aborted this search before we found a move:
1305 * or a failed search <- removed 2000-5-28
1306 * we should use the fail-highs
1307 * and the fail-lows are handled in think */
1308 if (time_exit && (cur_score == -INF))
1309 {
1310 if (no_moves)
1311 time_failure = TRUE;
1312 }
1313
1314 no_moves = FALSE;
1315 legal_move = TRUE;
1316
1317 }
1318
1319 unmake (&moves[0], i);
1320
1321 /* if we've run out of time, return the best we have so far: */
1322 if (time_exit)
1323 return best_move;
1324
1325 /* check our current score vs. alpha: */
1326 if (root_score > alpha && legal_move) {
1327
1328 /* we have a cutoff, so update our killers: */
1329 /* first, check whether it matches one of the known killers */
1330 if (moves[i].from == killer1[ply].from && moves[i].target ==
1331 killer1[ply].target && moves[i].promoted == killer1[ply].promoted)
1332 {
1333 killer_scores[ply]++;
1334 }
1335 else if (moves[i].from == killer2[ply].from && moves[i].target ==
1336 killer2[ply].target && moves[i].promoted == killer2[ply].promoted)
1337 {
1338 killer_scores2[ply]++;
1339
1340 if (killer_scores2[ply] > killer_scores[ply])
1341 {
1342 kswap = killer1[ply];
1343 killer1[ply] = killer2[ply];
1344 killer2[ply] = kswap;
1345 ksswap = killer_scores[ply];
1346 killer_scores[ply] = killer_scores2[ply];
1347 killer_scores2[ply] = ksswap;
1348 }
1349 }
1350 else if (moves[i].from == killer3[ply].from && moves[i].target ==
1351 killer3[ply].target && moves[i].promoted == killer3[ply].promoted)
1352 {
1353 killer_scores3[ply]++;
1354
1355 if (killer_scores3[ply] > killer_scores2[ply])
1356 {
1357 kswap = killer2[ply];
1358 killer2[ply] = killer3[ply];
1359 killer3[ply] = kswap;
1360 ksswap = killer_scores2[ply];
1361 killer_scores2[ply] = killer_scores3[ply];
1362 killer_scores3[ply] = ksswap;
1363 }
1364 }
1365 /* if not, replace killer3 */
1366 else
1367 {
1368 killer_scores3[ply] = 1;
1369 killer3[ply] = moves[i];
1370 }
1371
1372 /* update the history heuristic since we have a cutoff: */
1373 /* PGC square it */
1374 history_h[moves[i].from][moves[i].target] += depth * depth;
1375
1376 alpha = root_score;
1377 best_move = moves[i];
1378 bestmovenum = i;
1379 cur_score = alpha;
1380
1381 /* update the pv: */
1382 pv[ply][ply] = moves[i];
1383 for (j = ply+1; j < pv_length[ply+1]; j++)
1384 pv[ply][j] = pv[ply+1][j];
1385 pv_length[ply] = pv_length[ply+1];
1386
1387 if (cur_score >= beta) return best_move;
1388
1389 /* print out thinking information: */
1390 if (post && i_depth >= mindepth) {
1391 post_thinking (alpha);
1392 }
1393 }
1394 if (legal_move)
1395 first = FALSE;
1396
1397 rootnodecount[i] = nodes - oldnodecount;
1398 }
1399
1400 /* check to see if we are mated / stalemated: */
1401 if (no_moves && !is_pondering)
1402 {
1403 if (Variant != Suicide && Variant != Losers)
1404 {
1405 if (in_check ()) {
1406 if (white_to_move == 1) {
1407 result = white_is_mated;
1408 }
1409 else {
1410 result = black_is_mated;
1411 }
1412 }
1413 else {
1414 result = stalemate;
1415 }
1416 }
1417 else
1418 {
1419 if (white_to_move == 1) {
1420 result = black_is_mated;
1421 }
1422 else {
1423 result = white_is_mated;
1424 }
1425 }
1426 }
1427 else if (!is_pondering)
1428 {
1429 /* check for draw by the 50 move rule: */
1430 if (fifty > 100)
1431 {
1432 result = draw_by_fifty;
1433 cur_score = 0;
1434 pv_length[ply] = 0;
1435 return dummy;
1436 }
1437 }
1438
1439 return best_move;
1440
1441 }
1442
1443
think(void)1444 move_s think (void) {
1445
1446 /* Perform iterative deepening to go further in the search */
1447
1448 move_s comp_move, temp_move, old_move;
1449 int i, j, k;
1450 long int elapsed, temp_score, true_score;
1451 char postmove[STR_BUFF];
1452 clock_t cpu_start, cpu_end;
1453 float et = 0;
1454 int alpha, beta;
1455 int tmptmp;
1456 int rs;
1457 move_s moves[MOVE_BUFF];
1458 int l, lastlegal, ic;
1459 int pn_restart;
1460 int num_moves;
1461 char output[8];
1462
1463 userealholdings = 0;
1464 pn_restart = 0;
1465 restart:
1466 nodes = 0;
1467 qnodes = 0;
1468 ply = 1;
1469
1470 EGTBProbes = 0;
1471 EGTBHits = 0;
1472 ECacheProbes = 0;
1473 ECacheHits = 0;
1474 TTProbes = 0;
1475 TTHits = 0;
1476 TTStores = 0;
1477 NCuts = 0;
1478 NTries = 0;
1479 TExt = 0;
1480 FH = 0;
1481 FHF = 0;
1482 PVS = 0;
1483 FULL = 0;
1484 PVSF = 0;
1485 ext_check = 0;
1486 ext_recap = 0;
1487 ext_onerep = 0;
1488 razor_drop = 0;
1489 razor_material = 0;
1490 drop_cuts = 0;
1491 rs = 0;
1492 extendedtime = 0;
1493 forcedwin = 0;
1494
1495 true_i_depth = 0;
1496 bestmovenum = -1;
1497
1498 /* Don't do anything if the queue isn't clean */
1499 /* PGC: only safe if we're not playing...else partner tells screw us up */
1500 if (interrupt() && (is_analyzing || is_pondering)) return dummy;
1501
1502 //ep_temp = ep_square;
1503
1504 start_time = rtime ();
1505
1506 // we need to know if we must sit or not in bug
1507 //
1508 legals = 0;
1509
1510 if (Variant == Losers) captures = TRUE;
1511 else captures = FALSE;
1512 gen(&moves[0]);
1513 num_moves = numb_moves;
1514
1515 ic = in_check();
1516
1517 for (l = 0; l < numb_moves; l++)
1518 {
1519 make(&moves[0],l);
1520 if (check_legal(&moves[0], l, ic))
1521 {
1522 legals++;
1523 lastlegal = l;
1524 }
1525 unmake(&moves[0],l);
1526 }
1527
1528 if (Variant == Losers && legals == 0)
1529 {
1530 captures = FALSE;
1531 num_moves = 0;
1532 gen(&moves[0]);
1533 num_moves = numb_moves;
1534
1535 for (l = 0; l < numb_moves; l++)
1536 {
1537 make(&moves[0],l);
1538 if (check_legal(&moves[0], l, ic))
1539 {
1540 legals++;
1541 lastlegal = l;
1542 }
1543 unmake(&moves[0],l);
1544 }
1545 };
1546
1547 if (Variant != Bughouse && !is_pondering)
1548 {
1549 if (legals == 1)
1550 {
1551 time_cushion += (inc*100);
1552 return moves[lastlegal];
1553 }
1554 }
1555
1556 //ep_square = ep_temp;
1557
1558 /* before we do anything, check to see if we can make a move from book! */
1559 if (!pn_restart && book_ply < 40 && !is_analyzing && !is_pondering) {
1560 comp_move = choose_book_move();
1561 //ep_square = ep_temp;
1562 /* if choose_book_move() didn't return a junk move indicating that
1563 no book move was found, play the book move! :) */
1564
1565 if (comp_move.target == 0)
1566 comp_move = choose_binary_book_move();
1567
1568 //ep_square = ep_temp;
1569
1570 if (comp_move.target != 0)
1571 {
1572 comp_to_san (comp_move, postmove);
1573 printf("0 0 0 0 %s (Book Move)\n", postmove);
1574 cpu_end = clock ();
1575
1576 //ep_square = ep_temp;
1577
1578 time_cushion += (inc*100);
1579
1580 return comp_move;
1581 }
1582 }
1583
1584 check_phase();
1585
1586 switch(phase)
1587 {
1588 case Opening :
1589 printf("Opening phase.\n");
1590 break;
1591 case Middlegame :
1592 printf("Middlegame phase.\n");
1593 break;
1594 case Endgame :
1595 printf("Endgame phase.\n");
1596 break;
1597 }
1598
1599 /* allocate our time for this move: */
1600
1601 if (!is_pondering)
1602 {
1603 if (!fixed_time)
1604 {
1605 if (go_fast)
1606 {
1607 tmptmp = allocate_time();
1608
1609 if (tmptmp > 40)
1610 {
1611 time_for_move = 40;
1612 }
1613 else
1614 {
1615 time_for_move = tmptmp;
1616 }
1617 }
1618 else
1619 {
1620 time_for_move = allocate_time ();
1621 }
1622 }
1623 else
1624 {
1625 time_for_move = fixed_time;
1626 }
1627 }
1628 else
1629 {
1630 time_for_move = 999999;
1631 };
1632
1633 if (pn_restart) time_for_move = (float)time_for_move * (float)2/((float)pn_restart+1.0);
1634
1635 printf("Time for move : %d\n", time_for_move);
1636
1637 if (time_for_move > 50)
1638 LoadLearn();
1639
1640 if (!pn_restart)
1641 {
1642 clear_dp_tt();
1643 memset(rootlosers, 0, sizeof(rootlosers));
1644 }
1645
1646 if (!pn_restart && !is_pondering && ((Variant == Suicide) || (Variant == Losers))
1647 && (piece_count > 3 || (Variant != Suicide)))
1648 {
1649 pn_time = (int)((float)(time_for_move) * 1.0/3.0);
1650 proofnumberscan();
1651 }
1652 else if (!pn_restart)
1653 pn_move = dummy;
1654
1655 if (result && pn_move.target == dummy.target)
1656 return pn_move;
1657
1658 if ((forcedwin || result) && (pn_move.target != dummy.target)
1659 && !is_analyzing)
1660 {
1661 comp_move = pn_move;
1662 }
1663 else
1664 {
1665 /* clear the pv before a new search: */
1666 for (i = 0; i < PV_BUFF; i++)
1667 for (j = 0; j < PV_BUFF; j++)
1668 pv[i][j] = dummy;
1669
1670 /* clear the history heuristic: */
1671 memset (history_h, 0, sizeof (history_h));
1672
1673 /* clear the killer moves: */
1674 for (i = 0; i < PV_BUFF; i++) {
1675 killer_scores[i] = 0;
1676 killer_scores2[i] = 0;
1677 killer_scores3[i] = 0;
1678 killer1[i] = dummy;
1679 killer2[i] = dummy;
1680 killer3[i] = dummy;
1681 }
1682
1683 memset(rootnodecount, 0, sizeof(rootnodecount));
1684
1685 cpu_start = clock();
1686
1687 temp_score = 0;
1688 cur_score = 0;
1689 true_score = 0;
1690
1691 for (i_depth = 1; i_depth <= maxdepth; i_depth++) {
1692
1693 /* don't bother going deeper if we've already used 2/3 of our time, and we
1694 haven't finished our mindepth search, since we likely won't finsish */
1695 elapsed = rdifftime (rtime (), start_time);
1696 if (elapsed > time_for_move*2.1/3.0 && i_depth > mindepth)
1697 break;
1698
1699 failed = 0;
1700
1701 alpha = temp_score - (Variant == Normal ? 35 : 100);
1702 beta = temp_score + (Variant == Normal ? 35 : 100);
1703
1704 //ep_square = ep_temp;
1705 temp_move = search_root (alpha, beta, i_depth);
1706
1707 if (result) break;
1708
1709 if (cur_score <= alpha) failed = 1;
1710 else failed = 0;
1711
1712 if (cur_score <= alpha && !time_exit) /* fail low */
1713 {
1714 alpha = cur_score - (Variant == Normal ? 350 : 600);
1715 beta = cur_score;
1716
1717 rs++;
1718
1719 //ep_square = ep_temp;
1720 temp_move = search_root (alpha, beta, i_depth);
1721
1722 if (cur_score > alpha && !time_exit) failed = 0;
1723
1724 if (cur_score <= alpha && !time_exit)
1725 {
1726 alpha = -(INF+1);
1727 beta = cur_score;
1728
1729 rs++;
1730
1731 //ep_square = ep_temp;
1732 temp_move = search_root (alpha, beta, i_depth);
1733
1734 if (cur_score > alpha && !time_exit) failed = 0;
1735
1736 }
1737 else if (cur_score >= beta && !time_exit)
1738 {
1739 temp_move = search_root (-INF, +INF, i_depth);
1740 if (!time_exit) failed = 0;
1741 }
1742 }
1743 else if (cur_score >= beta && !time_exit) /* fail high */
1744 {
1745 comp_move = temp_move;
1746 temp_score = cur_score;
1747
1748 alpha = cur_score - 1;
1749 beta = cur_score + (Variant == Normal ? 350 : 600);
1750
1751 rs++;
1752
1753 //ep_square = ep_temp;
1754 temp_move = search_root (alpha, beta, i_depth);
1755
1756 if (cur_score >= beta && !time_exit)
1757 {
1758 comp_move = temp_move;
1759 temp_score = cur_score;
1760
1761 alpha = cur_score - 1;
1762 beta = +(INF+1);
1763
1764 rs++;
1765
1766 //ep_square = ep_temp;
1767 temp_move = search_root (alpha, beta, i_depth);
1768
1769 }
1770 else if (cur_score <= alpha && !time_exit)
1771 {
1772 /* fail high then low...do not make it PV */
1773 failed = 1;
1774 };
1775 };
1776
1777 //ep_square = ep_temp;
1778
1779 if (interrupt() && (i_depth > 1))
1780 {
1781 if (is_pondering)
1782 return dummy;
1783 else if (!go_fast)
1784 break;
1785 }
1786
1787 /* if we haven't aborted our search on time, set the computer's move
1788 and post our thinking: */
1789 if (!time_failure && !failed) {
1790 /* if our search score suddenly drops, and we ran out of time on the
1791 search, just use previous results */
1792 /* GCP except when we found a mate...maybe generalise ? */
1793 /* enabled 2000-5-28 */
1794 // if (time_exit && (cur_score < temp_score-50) && (cur_score > -900000))
1795 // break;
1796
1797 /* acidentally pondering if mated */
1798 if (cur_score == -INF) return dummy;
1799
1800 comp_move = temp_move;
1801 temp_score = cur_score;
1802
1803 stringize_pv(postpv);
1804
1805 if (!time_exit)
1806 {
1807 true_i_depth = i_depth;
1808 }
1809
1810 if (i_depth >= mindepth)
1811 post_thinking (cur_score);
1812
1813 if (temp_score > 900000 && ((int)(1000000-cur_score) < i_depth))
1814 {
1815 break;
1816 };
1817 }
1818
1819 if (time_exit) break;
1820
1821 /* reset the killer scores (we can keep the moves for move ordering for
1822 now, but the scores may not be accurate at higher depths, so we need
1823 to reset them): */
1824 for (j = 0; j < PV_BUFF; j++) {
1825 killer_scores[j] = 0;
1826 killer_scores2[j] = 0;
1827 killer_scores3[j] = 0;
1828 }
1829
1830 }
1831 }
1832
1833 //ep_square = ep_temp;
1834
1835 if (!forcedwin)
1836 {
1837 cpu_end = clock();
1838
1839 et = (cpu_end-cpu_start)/(double) CLOCKS_PER_SEC;
1840
1841 old_move = comp_move;
1842
1843 if ((Variant == Losers || Variant == Suicide) && !result && !alllosers && !is_pondering)
1844 {
1845 s_threat = FALSE;
1846
1847 comp_move = proofnumbercheck(comp_move);
1848
1849 if ((pn_restart < 10) && (s_threat))
1850 {
1851 /* a/b loser */
1852 pn_restart++;
1853
1854 /* mark loser */
1855 for (i = 0; i < num_moves; i++)
1856 {
1857 if (moves[i].from == old_move.from && moves[i].target == old_move.target
1858 && moves[i].promoted == old_move.promoted)
1859 {
1860 rootlosers[i] = TRUE;
1861 break;
1862 }
1863 }
1864 for (j = 0; j < num_moves; j++)
1865 {
1866 if (rootlosers[j]) k++;
1867 }
1868
1869 if (k == legals) alllosers = TRUE;
1870
1871 goto restart;
1872 }
1873 }
1874 };
1875
1876 if (alllosers) comp_move = old_move;
1877
1878 if (pn_restart != 0 && xb_mode)
1879 {
1880 comp_to_san(comp_move, output);
1881 printf("tellics whisper %d restart(s), ended up with %s\n", pn_restart, output);
1882 result = 0;
1883 }
1884 elapsed = rdifftime (rtime (), start_time);
1885
1886 printf("Used time : %d\n", elapsed);
1887
1888 /* update our elapsed time_cushion: */
1889 if (moves_to_tc && !is_pondering) {
1890 time_cushion += time_for_move-elapsed+inc;
1891 }
1892
1893
1894 if (temp_score == INF-2 && !is_pondering/* && pn_move.target == dummy.target*/)
1895 {
1896 if (white_to_move == 1)
1897 {
1898 result = black_is_mated;
1899 }
1900 else
1901 {
1902 result = white_is_mated;
1903 }
1904 }
1905 else if (temp_score == -(INF-2) && !is_pondering/* && pn_move.target == dummy.target*/)
1906 {
1907 if (white_to_move == 1)
1908 {
1909 result = white_is_mated;
1910 }
1911 else
1912 {
1913 result = black_is_mated;
1914 }
1915 }
1916
1917
1918 if (post && xb_mode && !is_pondering &&
1919 result != black_is_mated &&
1920 result != white_is_mated &&
1921 result != draw_by_fifty && result != draw_by_rep &&
1922 result != stalemate && !forcedwin)
1923 {
1924 if (temp_score > INF-400)
1925 {
1926 if (Variant != Bughouse)
1927 {
1928 printf("tellics kibitz Mate in %d\n", (int)((1000000-temp_score)/2));
1929 }
1930 else
1931 {
1932 printf("tellics ptell Mate in %d, give him no more pieces.\n", (int)((1000000-temp_score)/2));
1933 }
1934 }
1935
1936 //comp_to_san (comp_move, postmove);
1937
1938 if ((et > 0) && (Variant != Bughouse))
1939 {
1940 printf("tellics whisper d%d %+.2f %sn: %ld qp: %.0f%% fh: %.0f%% c-x: %d r-x: %d 1-x: %d egtb: %d time: %.2f nps: %ld\n",
1941 true_i_depth, (float)temp_score/100.0, postpv, nodes,
1942 (((float)qnodes*100)/((float)nodes+1)),
1943 ((float)FHF*100)/((float)(FH+1)),
1944 // ((float)PVS*100)/((float)FULL+1),
1945 // ((float)PVSF*100)/((float)PVS+1),
1946 ext_check, ext_recap, ext_onerep, EGTBHits,
1947 ((float)elapsed/100.),
1948 (long)((float) nodes/(float) (et)));
1949 }
1950 }
1951
1952
1953 if ((result != white_is_mated)
1954 && (result != black_is_mated)
1955 && (result != stalemate)
1956 && (result != draw_by_fifty) && (result != draw_by_rep)
1957 && (true_i_depth >= 3)
1958 && pn_move.target == dummy.target
1959 && !is_pondering
1960 && (Variant != Bughouse))
1961 {
1962 if (bestmovenum == -1) DIE;
1963
1964 Learn(temp_score, bestmovenum, true_i_depth);
1965 }
1966
1967 if ((Variant == Bughouse) && temp_score > -999900)
1968 {
1969 if (tradefreely == 0 && !userealholdings)
1970 {
1971 tradefreely = 1;
1972 printf("tellics ptell You can trade freely.\n");
1973 }
1974 }
1975 else if ((temp_score < -999900) && (Variant == Bughouse) && pn_move.target == dummy.target)
1976 {
1977 if (userealholdings)
1978 {
1979 must_sit = TRUE;
1980 }
1981 else
1982 {
1983 userealholdings = 1;
1984 ProcessHoldings(realholdings);
1985 tradefreely = 0;
1986 printf("tellics ptell ---trades\n");
1987 goto restart;
1988 }
1989
1990
1991 /* shut up if the mate is already played */
1992 if (temp_score > -1000000)
1993 {
1994 if (partnerdead)
1995 {
1996 printf("tellics kibitz Both players dead...resigning...\n");
1997 printf("tellics resign\n");
1998 }
1999 else
2000 {
2001 printf("tellics ptell I am forcedly mated (dead). Tell me 'go' to start moving into it.\n");
2002 }
2003 }
2004 }
2005 else if ((temp_score > -60000) && (temp_score < -40000) && (Variant == Bughouse) && !partnerdead && pn_move.target == dummy.target)
2006 {
2007 must_sit = TRUE;
2008 printf("tellics ptell I'll have to sit...(lose piece that mates you)\n");
2009 }
2010
2011 return comp_move;
2012
2013 }
2014
2015
tree(int depth,int indent,FILE * output,char * disp_b)2016 void tree (int depth, int indent, FILE *output, char *disp_b) {
2017
2018 move_s moves[MOVE_BUFF];
2019 int num_moves, i, j;
2020 int ic;
2021
2022 //
2023 //ep_temp = ep_square;
2024 num_moves = 0;
2025
2026 /* return if we are at the maximum depth: */
2027 if (!depth) {
2028 return;
2029 }
2030
2031 /* generate the move list: */
2032 gen (&moves[0]);
2033 num_moves = numb_moves;
2034
2035 ic = in_check();
2036
2037 /* loop through the moves at the current depth: */
2038 for (i = 0; i < num_moves; i++) {
2039 make (&moves[0], i);
2040
2041 /* check to see if our move is legal: */
2042 if (check_legal (&moves[0], i, ic)) {
2043 /* indent and print out our line: */
2044 for (j = 0; j < indent; j++) {
2045 fputc (' ', output);
2046 }
2047 print_move (&moves[0], i, output);
2048 fprintf (output, "\n");
2049
2050 /* display board if desired: */
2051 if (disp_b[0] == 'y')
2052 display_board (output, 1);
2053
2054 /* go deeper into the tree recursively, increasing the indent to
2055 create the "tree" effect: */
2056 tree (depth-1, indent+2, output, disp_b);
2057 }
2058
2059 /* unmake the move to go onto the next: */
2060 unmake(&moves[0], i);
2061 }
2062
2063 //ep_square = ep_temp;
2064
2065 }
2066
2067