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