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: proof.c 20 Purpose: contains functions related to the pn-search 21 22 */ 23 24#include "sjeng.h" 25#include "extvars.h" 26#include "protos.h" 27#include "limits.h" 28#include "math.h" 29 30#define FALSE 0 31#define TRUE 1 32#define UNKNOWN 2 33#define STALEMATE 3 /* special case because pn-search only assumes 1/0 */ 34 35#define PN_INF 100000000 36 37/* we can exceed PBSize before exiting the main search loop */ 38#define SAFETY 10000 39 40 41/* define this to use the pn^2 search */ 42#undef PN2 43 44int nodecount; 45int nodecount2; 46int pn2; 47int32_t frees; 48int iters; 49int forwards; 50int maxply; 51int ply; 52int pn_time; 53move_s pn_move; 54move_s pn_saver; 55 56bool kibitzed; 57int forcedwin; 58 59int rootlosers[PV_BUFF]; 60int alllosers; 61 62typedef struct node 63 { 64 unsigned char value; 65 unsigned char num_children; 66 unsigned char expanded; 67 unsigned char evaluated; 68 int proof; 69 int disproof; 70 struct node **children; 71 struct node *parent; 72 move_s move; 73 } 74node_t; 75 76void pn2_eval (node_t *node); 77void suicide_pn_eval (node_t *this); 78void std_pn_eval (node_t *this); 79void losers_pn_eval (node_t *this); 80 81unsigned char *membuff; 82int bufftop = 0; 83 84void* Xmalloc(int size) 85{ 86 int oldtop = bufftop; 87 88 bufftop += size; 89 90 return (&membuff[oldtop]); 91}; 92 93void Xfree(void) 94{ 95 bufftop = 0; 96}; 97 98void freenodes (node_t * node) 99{ 100 int i; 101 102 if (!node) 103 return; 104 105 if (node->children) 106 { 107 if (node->num_children > 0) 108 { 109 for (i = 0; i < (node->num_children); i++) 110 { 111 if (node->children[i] != 0) 112 { 113 freenodes (node->children[i]); 114 }; 115 }; 116 free (node->children); 117 } 118 }; 119 120 free (node); 121}; 122 123void pn_eval(node_t * this) 124{ 125 if (Variant == Suicide) 126 { 127 suicide_pn_eval(this); 128 } 129 else if (Variant == Losers) 130 { 131 losers_pn_eval(this); 132 } 133 else 134 { 135 std_pn_eval(this); 136 } 137} 138 139void std_pn_eval (node_t * this) 140{ 141 int num_moves; 142 move_s moves[MOVE_BUFF]; 143 int mate; 144 int i; 145 146 this->evaluated = TRUE; 147 148 //ep_temp = ep_square; 149 150 if ((white_to_move && is_attacked (wking_loc, WHITE)) 151 || (!white_to_move && is_attacked (bking_loc, BLACK))) 152 { 153 154 num_moves = 0; 155 gen (&moves[0]); 156 num_moves = numb_moves; 157 158 mate = TRUE; 159 160 for (i = 0; i < num_moves; i++) 161 { 162 make (&moves[0], i); 163 164 /* check to see if our move is legal: */ 165 if (check_legal (&moves[0], i, TRUE)) 166 { 167 mate = FALSE; 168 unmake (&moves[0], i); 169 break; 170 }; 171 172 unmake (&moves[0], i); 173 } 174 175 if (mate == TRUE) 176 { 177 /* proven or disproven */ 178 if (ToMove == root_to_move) 179 { 180 /* root mover is mated-> disproven */ 181 this->value = FALSE; 182 } 183 else 184 { 185 this->value = TRUE; 186 }; 187 } 188 else 189 { 190 this->value = UNKNOWN; 191 }; 192 } 193 else 194 { 195 this->value = UNKNOWN; 196 }; 197 198 //ep_square = ep_temp; 199 200}; 201 202void suicide_pn_eval(node_t *this) 203{ 204 int j, a, i; 205 int wp = 0, bp = 0; 206 int egscore; 207 208 this->evaluated = TRUE; 209 210 if (piece_count <= 3 && (Variant == Suicide) && SEGTB) 211 { 212 egscore = egtb(white_to_move); 213 214 if (egscore != -128) 215 { 216 if (egscore > 0) 217 { 218 if (ToMove == root_to_move) 219 { 220 this->value = TRUE; 221 return; 222 } 223 else 224 { 225 this->value = FALSE; 226 return; 227 } 228 } 229 else if (egscore < 0) 230 { 231 if (ToMove == root_to_move) 232 { 233 this->value = FALSE; 234 return; 235 } 236 else 237 { 238 this->value = TRUE; 239 return; 240 } 241 } 242 else 243 { 244 this->value = UNKNOWN; 245 return; 246 } 247 } 248 } 249 250 for (j = 1, a = 1; (a <= piece_count); j++) 251 { 252 i = pieces[j]; 253 254 if (!i) 255 continue; 256 else 257 a++; 258 259 switch (board[i]) 260 { 261 case wpawn: 262 case wbishop: 263 case wrook: 264 case wking: 265 case wqueen: 266 case wknight: wp++; break; 267 case bpawn: 268 case bbishop: 269 case brook: 270 case bking: 271 case bqueen: 272 case bknight: bp++; break; 273 } 274 275 if (wp && bp) break; 276 } 277 278 if (!wp) 279 { 280 /* white has no pieces */ 281 /* proven or disproven */ 282 if (!root_to_move) 283 { 284 /* root mover is mated-> proven */ 285 this->value = TRUE; 286 } 287 else 288 { 289 this->value = FALSE; 290 }; 291 } 292 else if (!bp) 293 { 294 /* black has no pieces */ 295 if (!root_to_move) 296 { 297 /* root mover is mated-> disproven */ 298 this->value = FALSE; 299 } 300 else 301 { 302 this->value = TRUE; 303 }; 304 } 305 else 306 { 307 this->value = UNKNOWN; 308 }; 309}; 310 311void losers_pn_eval(node_t *this) 312{ 313 int num_moves; 314 move_s moves[MOVE_BUFF]; 315 int mate; 316 int i; 317 int j, a; 318 int wp = 0, bp = 0; 319 320 this->evaluated = TRUE; 321 322 //ep_temp = ep_square; 323 324 for (j = 1, a = 1; (a <= piece_count); j++) 325 { 326 i = pieces[j]; 327 328 if (!i) 329 continue; 330 else 331 a++; 332 333 switch (board[i]) 334 { 335 case wpawn: 336 case wbishop: 337 case wrook: 338 case wqueen: 339 case wknight: wp++; break; 340 case bpawn: 341 case bbishop: 342 case brook: 343 case bqueen: 344 case bknight: bp++; break; 345 } 346 347 if (wp && bp) break; 348 } 349 350 351 if (!wp) 352 { 353 /* proven or disproven */ 354 if (!root_to_move) 355 { 356 /* root mover is mated-> disproven */ 357 this->value = TRUE; 358 } 359 else 360 { 361 this->value = FALSE; 362 }; 363 return; 364 } 365 else if (!bp) 366 { 367 if (root_to_move) 368 { 369 /* root mover is mated-> disproven */ 370 this->value = TRUE; 371 } 372 else 373 { 374 this->value = FALSE; 375 }; 376 return; 377 } 378 379 if ((white_to_move && is_attacked(wking_loc, WHITE)) 380 || (!white_to_move && is_attacked(bking_loc, BLACK))) 381 { 382 383 captures = TRUE; 384 385 num_moves = 0; 386 gen (&moves[0]); 387 num_moves = numb_moves; 388 captures = FALSE; 389 390 mate = TRUE; 391 392 for (i = 0; i < num_moves; i++) 393 { 394 make (&moves[0], i); 395 396 /* check to see if our move is legal: */ 397 if (check_legal (&moves[0], i, TRUE)) 398 { 399 mate = FALSE; 400 unmake(&moves[0], i); 401 break; 402 }; 403 404 unmake(&moves[0], i); 405 } 406 407 if (mate == TRUE) 408 { 409 /* no legal capture..do non-captures */ 410 captures = FALSE; 411 num_moves = 0; 412 gen (&moves[0]); 413 num_moves = numb_moves; 414 415 for (i = 0; i < num_moves; i++) 416 { 417 make (&moves[0], i); 418 419 /* check to see if our move is legal: */ 420 if (check_legal (&moves[0], i, TRUE)) 421 { 422 mate = FALSE; 423 unmake(&moves[0], i); 424 break; 425 }; 426 427 unmake(&moves[0], i); 428 } 429 } 430 431 if (mate == TRUE) 432 { 433 /* proven or disproven */ 434 if (ToMove == root_to_move) 435 { 436 /* root mover is mated-> disproven */ 437 this->value = TRUE; 438 } 439 else 440 { 441 this->value = FALSE; 442 }; 443 } 444 else 445 { 446 this->value = UNKNOWN; 447 }; 448 } 449 else 450 { 451 this->value = UNKNOWN; 452 }; 453 454 //ep_square = ep_temp; 455 456}; 457 458 459node_t *select_most_proving (node_t * node) 460{ 461 int i; 462 node_t *tnode; 463 464 tnode = node; 465 466 while (tnode->expanded) 467 { 468 if (ToMove == root_to_move) 469 { 470 i = 0; 471 472 while (tnode->children[i]->proof != tnode->proof) 473 { 474 i++; 475 }; 476 } 477 else 478 { 479 i = 0; 480 481 while (tnode->children[i]->disproof != tnode->disproof) 482 { 483 i++; 484 }; 485 }; 486 487 tnode = tnode->children[i]; 488 489 hash_history[move_number+ply-1] = hash; 490 491 make (&tnode->move, 0); 492 493 if (ply > maxply) 494 maxply = ply; 495 496 }; 497 498 return tnode; 499 500}; 501 502void set_proof_and_disproof_numbers (node_t * node) 503{ 504 int proof; 505 int disproof; 506 int i; 507 move_s moves[MOVE_BUFF]; 508 int l, num_moves; 509 int reploop; 510 int ic; 511 512 if (node->expanded) 513 { 514 if (ToMove != root_to_move) 515 { 516 proof = 0; 517 disproof = +PN_INF; 518 519 for (i = 0; i < node->num_children; i++) 520 { 521 proof += node->children[i]->proof; 522 523 if (proof > PN_INF) 524 proof = PN_INF; 525 526 if (node->children[i]->disproof < disproof) 527 { 528 disproof = node->children[i]->disproof; 529 } 530 } 531 532 if ((proof == 0) || (disproof == PN_INF)) 533 { 534 forwards++; 535 StoreTT(+INF-500, +INF, -INF, -1, 0, 200); 536 } 537 else if ((disproof == 0) || (proof == PN_INF)) 538 { 539 forwards++; 540 StoreTT(-INF+500, +INF, -INF, -1, 0, 200); 541 } 542 } 543 else 544 { 545 disproof = 0; 546 proof = +PN_INF; 547 548 for (i = 0; i < node->num_children; i++) 549 { 550 551 disproof += node->children[i]->disproof; 552 553 if (disproof > PN_INF) 554 disproof = PN_INF; 555 556 if (node->children[i]->proof < proof) 557 { 558 proof = node->children[i]->proof; 559 } 560 } 561 562 if ((proof == 0) || (disproof == PN_INF)) 563 { 564 forwards++; 565 StoreTT(+INF-500, +INF, -INF, -1, 0, 200); 566 } 567 else if ((disproof == 0) || (proof == PN_INF)) 568 { 569 forwards++; 570 StoreTT(-INF+500, +INF, -INF, -1, 0, 200); 571 } 572 } 573 574 hash_history[move_number+ply-1] = hash; 575 576 node->proof = proof; 577 node->disproof = disproof; 578 579 } 580 else if (node->evaluated) 581 { 582 if (node->value == UNKNOWN) 583 { 584 585 hash_history[move_number+ply-1] = hash; 586 587 if (is_draw() || ply > 200) 588 { 589 node->proof = 50000; 590 node->disproof = 50000; 591 return; 592 } 593 594 //ept = ep_square; 595 596 if (Variant != Losers) 597 { 598 num_moves = 0; 599 gen (&moves[0]); 600 num_moves = numb_moves; 601 602 ic = in_check(); 603 604 if (Variant != Suicide) 605 { 606 l = 0; 607 608 for (i = 0; i < num_moves; i++) 609 { 610 make (&moves[0], i); 611 /* check to see if our move is legal: */ 612 if (check_legal (&moves[0], i, ic)) 613 { 614 l++; 615 } 616 unmake (&moves[0], i); 617 }; 618 } 619 else 620 { 621 l = numb_moves; 622 }; 623 } 624 else 625 { 626 /* Losers...this a bit more messy */ 627 628 l = 0; 629 captures = TRUE; 630 num_moves = 0; 631 gen (&moves[0]); 632 num_moves = numb_moves; 633 captures = FALSE; 634 635 ic = in_check(); 636 637 if (num_moves) 638 { 639 for (i = 0; i < num_moves; i++) 640 { 641 make(&moves[0], i); 642 643 if (check_legal(&moves[0], i, ic)) 644 { 645 l++; 646 } 647 unmake(&moves[0], i); 648 } 649 } 650 651 // 652 //ep_square = ept; 653 654 if (!l) 655 { 656 captures = FALSE; 657 num_moves = 0; 658 gen(&moves[0]); 659 num_moves = numb_moves; 660 661 for (i = 0; i < num_moves; i++) 662 { 663 make(&moves[0], i); 664 665 if (check_legal(&moves[0], i, ic)) 666 { 667 l++; 668 } 669 unmake(&moves[0], i); 670 } 671 }; 672 } 673 674 if (l == 0) 675 { 676 /* might be stalemate too */ 677 node->proof = 1; 678 node->disproof = 1; 679 } 680 else if (ToMove == root_to_move) /* OR */ 681 { 682 if ((Variant != Suicide) && (Variant != Losers)) 683 { 684 node->proof = 1 + floorf(ply / 50); 685 node->disproof = l + floorf(ply / 50); 686 } 687 else 688 { 689 if (Variant == Losers) 690 { 691 /* this is probably a bogus line, 692 so breathen the tree */ 693 if (phase == Endgame) 694 { 695 node->proof = 1 + floorf(ply / 30); 696 node->disproof = l + floorf(ply / 30); 697 } 698 else 699 { 700 node->proof = 1 + floorf(ply / 80); 701 node->disproof = l + floorf(ply / 80); 702 } 703 } 704 else 705 { 706 node->proof = 1 + floorf(ply / 150); 707 node->disproof = l + floorf(ply / 150); 708 } 709 } 710 } 711 else 712 { 713 if ((Variant != Suicide) && (Variant != Losers)) 714 { 715 node->proof = l + floorf(ply / 50); 716 node->disproof = 1 + floorf(ply / 50); 717 } 718 else 719 { 720 if (Variant == Losers) 721 { 722 if (phase == Endgame) 723 { 724 node->proof = l + floorf(ply/30); 725 node->disproof = 1 + floorf(ply/30); 726 727 } 728 else 729 { 730 node->proof = l + floorf(ply/80); 731 node->disproof = 1 + floorf(ply/80); 732 } 733 } 734 else 735 { 736 node->proof = l + floorf(ply / 150); 737 node->disproof = 1 + floorf(ply / 150); 738 } 739 } 740 } 741 742 //ep_square = ept; 743 } 744 else if (node->value == FALSE) 745 { 746 node->proof = +PN_INF; 747 node->disproof = 0; 748 } 749 else if (node->value == TRUE) 750 { 751 node->proof = 0; 752 node->disproof = +PN_INF; 753 } 754 else if (node->value == STALEMATE) 755 { 756 /* don't look at this node, its a dead-end */ 757 node->proof = 50000; 758 node->disproof = 50000; 759 }; 760 } 761 else 762 { 763 node->proof = node->disproof = 1; 764 } 765} 766 767void develop_node (node_t * node) 768{ 769 int num_moves; 770 move_s moves[MOVE_BUFF]; 771 int i, l; 772 node_t *newnode; 773#ifdef PN2 774 node_t **newchildren; 775#endif 776 int leg; 777 int ic; 778 779 //ept = ep_square; 780 781#ifdef PN2 782 if (!pn2) 783 pn2_eval(node); 784#endif 785 786 ic = in_check(); 787 788 if (Variant != Losers) 789 { 790 num_moves = 0; 791 gen (&moves[0]); 792 num_moves = numb_moves; 793 } 794 else 795 { 796 captures = TRUE; 797 leg = FALSE; 798 num_moves = 0; 799 800 gen (&moves[0]); 801 num_moves = numb_moves; 802 captures = FALSE; 803 804 for (i = 0; i < num_moves; i++) 805 { 806 make (&moves[0], i); 807 808 /* check to see if our move is legal: */ 809 if (check_legal (&moves[0], i, ic)) 810 { 811 leg = TRUE; 812 unmake(&moves[0], i); 813 break; 814 }; 815 816 unmake(&moves[0], i); 817 } 818 819 if (leg == FALSE) 820 { 821 captures = FALSE; 822 num_moves = 0; 823 gen (&moves[0]); 824 num_moves = numb_moves; 825 } 826 } 827 828#ifdef PN2 829 if (pn2) 830#endif 831 node->children = (node_t **) Xmalloc ((int32_t)(num_moves * sizeof (node_t **))); 832#ifdef PN2 833 else 834 newchildren = (node_t **) malloc (num_moves * sizeof (node_t **)); 835#endif 836 837 l = 0; 838 839 for (i = 0; i < num_moves; i++) 840 { 841 hash_history[move_number+ply-1] = hash; 842 843 make (&moves[0], i); 844 845 /* check to see if our move is legal: */ 846 if (check_legal (&moves[0], i, ic)) 847 { 848#ifdef PN2 849 if (pn2) 850#endif 851 newnode = (node_t *) Xmalloc ((int32_t)sizeof (node_t)); 852#ifdef PN2 853 else 854 newnode = (node_t *) malloc (sizeof (node_t)); 855#endif 856 newnode->value = 0; 857#ifdef PN2 858 if (!pn2) 859 { 860 newnode->proof = node->children[l]->proof; 861 newnode->disproof = node->children[l]->disproof; 862 } 863 else 864 { 865#endif 866 newnode->proof = newnode->disproof = 1; 867#ifdef PN2 868 }; 869#endif 870 871 newnode->num_children = 0; 872 newnode->parent = node; 873 newnode->evaluated = FALSE; 874 newnode->expanded = FALSE; 875 newnode->move = moves[i]; 876 877#ifdef PN2 878 if (!pn2) 879 newchildren[l] = newnode; 880 else 881#endif 882 node->children[l] = newnode; 883 884 l++; 885#ifdef PN2 886 if (pn2 == FALSE) 887 /*use delayed eval */; 888 else if (pn2) 889#endif 890 pn_eval (newnode); 891#ifdef PN2 892 if (pn2) 893#endif 894 set_proof_and_disproof_numbers (newnode); 895 896 unmake (&moves[0], i); 897 898 } 899 else 900 unmake (&moves[0], i); 901 }; 902 903 node->expanded = TRUE; 904 node->num_children = l; 905 906#ifdef PN2 907 if (!pn2) 908 node->children = newchildren; 909#endif 910 911 /* account for stalemate ! */ 912 if (node->num_children == 0) 913 { 914 node->expanded = FALSE; 915 node->evaluated = TRUE; 916 if (Variant != Suicide && Variant != Losers) 917 { 918 node->value = STALEMATE; 919 } 920 else 921 { 922 if (ToMove == root_to_move) 923 { 924 node->value = TRUE; 925 } 926 else 927 { 928 node->value = FALSE; 929 } 930 }; 931 932 }; 933#ifdef PN2 934 if (pn2) 935 nodecount2 += num_moves; 936 else 937#endif 938 nodecount += num_moves; 939 940 frees += num_moves; 941 942 //ep_square = ept; 943#ifdef PN2 944 if (!pn2) Xfree(); 945#endif 946}; 947 948void update_ancestors (node_t * node) 949{ 950 node_t *tnode, *prevnode; 951 952 tnode = node; 953 prevnode = node; 954 955 while (tnode != 0) 956 { 957 set_proof_and_disproof_numbers (tnode); 958 959 prevnode = tnode; 960 961 if (tnode->move.target != 0) 962 { /* traverse */ 963 unmake (&tnode->move, 0); 964 } 965 966 tnode = tnode->parent; 967 }; 968 969 if (prevnode->move.target != 0) 970 { 971 make (&prevnode->move, 0); 972 } 973 974 return; 975 976}; 977 978void 979pn2_eval (node_t * root) 980{ 981 node_t *mostproving; 982#ifdef PN2 983 node_t *newroot; 984#endif 985 node_t *currentnode; 986 node_t *oldparent; 987 988 nodecount2 = 0; 989 pn2 = TRUE; 990 991 oldparent = root->parent; 992 root->parent = 0; 993 994 pn_eval (root); 995 996 set_proof_and_disproof_numbers (root); 997 998 currentnode = root; 999 1000 while (root->proof != 0 && root->disproof != 0 && nodecount2 < nodecount ) 1001 { 1002 mostproving = select_most_proving (root); 1003 develop_node (mostproving); 1004 update_ancestors (mostproving); 1005 }; 1006 1007 root->expanded = FALSE; 1008 root->num_children = 0; 1009 1010 root->parent = oldparent; 1011 1012 pn2 = FALSE; 1013 1014}; 1015 1016void proofnumberscan (void) 1017{ 1018 move_s moves[MOVE_BUFF]; 1019 int islegal[MOVE_BUFF]; 1020 int nodesspent[MOVE_BUFF]; 1021 int i, l, legal; 1022 int num_moves; 1023 rtime_t xstart_time; 1024 node_t *root; 1025 node_t *mostproving; 1026 node_t *currentnode; 1027 int leastlooked, leastlooked_l, leastlooked_i; 1028 int losers; 1029 int xnodecount; 1030 int firsts, alternates; 1031 char output[8]; 1032 int ic; 1033 float bdp; 1034 int altlosers; 1035 1036 xstart_time = rtime (); 1037 1038 membuff = (unsigned char *) calloc(PBSize, sizeof(node_t)); 1039 1040 root = (node_t *) calloc (1, sizeof (node_t)); 1041 1042 gen (&moves[0]); 1043 num_moves = numb_moves; 1044 1045 alllosers = FALSE; 1046 memset(rootlosers, 0, sizeof(rootlosers)); 1047 memset(nodesspent, 0, sizeof(nodesspent)); 1048 1049 pn_move = dummy; 1050 1051 legal = 0; 1052 1053 ic = in_check(); 1054 1055 for (i = 0; i < num_moves; i++) 1056 { 1057 make (&moves[0], i); 1058 1059 /* check to see if our move is legal: */ 1060 if (check_legal (&moves[0], i, ic)) 1061 { 1062 legal++; 1063 islegal[i] = 1; 1064 } 1065 else 1066 { 1067 islegal[i] = 0; 1068 }; 1069 1070 unmake(&moves[0], i); 1071 } 1072 1073 if (legal == 0) 1074 { 1075 Xfree(); 1076 free(membuff); 1077 free(root); 1078 return; 1079 } 1080 1081 losers = 0; 1082 1083 nodecount = 1; 1084 iters = 0; 1085 maxply = 0; 1086 forwards = 0; 1087 firsts = 0; 1088 alternates = 0; 1089 hash_history[move_number+ply-1] = hash; 1090 root_to_move = ToMove; 1091 1092 pn_eval (root); 1093 1094 if (root->value == TRUE || root->value == FALSE) 1095 { 1096 Xfree(); 1097 free(membuff); 1098 free(root); 1099 pn_move = dummy; 1100 return; 1101 } 1102 1103 set_proof_and_disproof_numbers (root); 1104 1105 while ((rdifftime (rtime (), xstart_time) < pn_time) && !interrupt() 1106 && (bufftop < ((PBSize-SAFETY) * sizeof(node_t))) 1107 && root->proof != 0 && root->disproof != 0) 1108 { 1109 1110 iters++; 1111 xnodecount = nodecount; 1112 1113 if ((nodecount % 100) < 66) 1114 { 1115 firsts++; 1116 1117 /* pick normal pn move */ 1118 currentnode = root; 1119 1120 mostproving = select_most_proving (currentnode); 1121 develop_node (mostproving); 1122 update_ancestors (mostproving); 1123 1124 /* what was the mostproving node ? */ 1125 i = 0; 1126 while (root->children[i]->proof != root->proof) i++; 1127 1128 nodesspent[i] += nodecount - xnodecount; 1129 1130 if (root->proof == 0 && root->disproof == PN_INF) 1131 { 1132 forcedwin = TRUE; 1133 1134 if (!kibitzed) 1135 { 1136 kibitzed = TRUE; 1137 printf("tellics kibitz Forced win!\n"); 1138 } 1139 1140 pn_move = root->children[i]->move; 1141 1142 } 1143 else if (root->disproof == 0 && root->proof == PN_INF) 1144 { 1145 pn_move = dummy; 1146 losers++; 1147 } 1148 } 1149 else 1150 { 1151 /* pick alternate move */ 1152 alternates++; 1153 1154 leastlooked = PN_INF; 1155 l = 0; 1156 1157 for (i = 0; i < num_moves; i++) 1158 { 1159 if ((nodesspent[i] < leastlooked) && islegal[i] && !rootlosers[i]) 1160 { 1161 leastlooked = nodesspent[i]; 1162 leastlooked_i = i; 1163 leastlooked_l = l; 1164 } 1165 if (islegal[i]) l++; 1166 } 1167 1168 if (leastlooked == PN_INF) 1169 { 1170 /* could not find a nonlosing legal move */ 1171 nodecount += 30; 1172 continue; 1173 } 1174 1175 make(&moves[0], leastlooked_i); 1176 1177 currentnode = root->children[leastlooked_l]; 1178 1179 mostproving = select_most_proving (currentnode); 1180 develop_node (mostproving); 1181 update_ancestors (mostproving); 1182 1183 nodesspent[leastlooked_i] += nodecount - xnodecount; 1184 1185 /* should be back at root now */ 1186 1187 if (root->children[leastlooked_l]->proof == 0 && 1188 root->children[leastlooked_l]->disproof == PN_INF) 1189 { 1190 /* alternate move was forced win */ 1191 forcedwin = TRUE; 1192 1193 if (!kibitzed) 1194 { 1195 kibitzed = TRUE; 1196 printf("tellics kibitz Forced win! (alt)\n"); 1197 } 1198 1199 pn_move = root->children[leastlooked_l]->move; 1200 } 1201 else if (root->children[leastlooked_l]->disproof == 0 1202 && root->children[leastlooked_l]->proof == PN_INF) 1203 { 1204 /* alternate move loses */ 1205 rootlosers[leastlooked_i] = 1; 1206 losers++; 1207 } 1208 } 1209 }; 1210 1211 l = 0; 1212 bdp = -1; 1213 altlosers = 0; 1214 1215 if (root->expanded) 1216 { 1217 for (i = 0; i < num_moves; i++) 1218 { 1219 if (islegal[i]) 1220 { 1221 comp_to_san(moves[i], output); 1222 //printf("checked %s, nodes: %d, pn: %d, dp: %d\n", 1223 // output, nodesspent[i], root->children[l]->proof, root->children[l]->disproof); 1224 1225 if (root->children[l]->proof != 0) 1226 { 1227 if (((float)root->children[l]->disproof / (float)root->children[l]->proof) > bdp) 1228 { 1229 bdp = ((float)root->children[l]->disproof / (float)root->children[l]->proof); 1230 pn_move = root->children[l]->move; 1231 } 1232 1233 if ((root->children[l]->disproof == 0) && (root->children[l]->proof == PN_INF)) 1234 { 1235 altlosers++; 1236 1237 make(&moves[0], i); 1238 1239 Learn(-INF+500, 255, 200); 1240 1241 unmake(&moves[0], i); 1242 1243 } 1244 } 1245 else 1246 { 1247 forcedwin = TRUE; 1248 pn_move = root->children[l]->move; 1249 bdp = PN_INF; 1250 } 1251 l++; 1252 } 1253 } 1254 } 1255 1256 comp_to_san(pn_move, output); 1257 1258 if (xb_mode && post) 1259 printf ("tellics whisper proof %d, disproof %d, %d losers, highest depth %d, primary %d, secondary %d\n", root->proof, root->disproof, altlosers, maxply, firsts, alternates); 1260 1261#if 0 1262 if (forcedwin && maxply == 0) 1263 { 1264 if (root_to_move == WHITE) 1265 { 1266 result = black_is_mated; 1267 } 1268 else 1269 { 1270 result = white_is_mated; 1271 } 1272 } 1273#endif 1274 1275 if (altlosers == (legal - 1)) 1276 { 1277 printf("tellics whisper Forced reply\n"); 1278 1279 for (i = 0; i < num_moves; i++) 1280 { 1281 if (!rootlosers[i] && islegal[i]) 1282 { 1283 /* not really forced win but setting this flag 1284 * just means 'blindy trust pnsearch' */ 1285 forcedwin = TRUE; 1286 pn_move = moves[i]; 1287 break; 1288 } 1289 } 1290 } 1291 1292 if (altlosers == legal) 1293 { 1294 alllosers = TRUE; 1295 } 1296 1297 Xfree(); 1298 free(membuff); 1299 free(root); 1300 1301 return; 1302 1303}; 1304 1305 1306void 1307proofnumbersearch (void) 1308{ 1309 node_t *root; 1310 node_t *mostproving; 1311 node_t *currentnode; 1312 rtime_t xstart_time; 1313 char output[8192]; 1314 char PV[8192]; 1315 int i; 1316 float bdp; 1317 int oldply; 1318 1319 nodecount = 1; 1320 iters = 0; 1321 frees = 0; 1322 ply = 1; 1323 maxply = 0; 1324 forwards = 0; 1325 hash_history[move_number+ply-1] = hash; 1326 root_to_move = ToMove; 1327 1328 //eps = ep_square; 1329 1330 xstart_time = rtime (); 1331 1332 root = (node_t *) calloc (1, sizeof (node_t)); 1333 1334 membuff = (unsigned char *) calloc(PBSize, sizeof(node_t)); 1335 1336 pn_eval (root); 1337 1338 if (root->value == FALSE) 1339 { 1340 pn_move = dummy; 1341 Xfree(); 1342 free(root); 1343 free(membuff); 1344 return; 1345 } 1346 1347 set_proof_and_disproof_numbers (root); 1348 1349 currentnode = root; 1350 1351 while (root->proof != 0 && root->disproof != 0 1352 && (bufftop < ((PBSize-SAFETY) * sizeof(node_t)))) 1353 { 1354 mostproving = select_most_proving (currentnode); 1355 develop_node (mostproving); 1356 update_ancestors (mostproving); 1357 1358 iters++; 1359 1360#ifdef PN2 1361 if (iters) 1362#else 1363 if ((iters % 32) == 0) 1364#endif 1365 { 1366#ifdef PN2 1367 printf("P: %d D: %d N: %d S: %d Mem: %2.2fM Iters: %d ", root->proof, root->disproof, nodecount, frees, (((nodecount) * sizeof(node_t) / (float)(1024*1024))), iters); 1368 1369 printf ("PV: "); 1370 1371 memset (output, 0, sizeof (output)); 1372 memset (PV, 0, sizeof (PV)); 1373 //currentnode = root; 1374 ply = 1; 1375 1376 while (currentnode->expanded) 1377 { 1378 if (ToMove == root_to_move) 1379 { 1380 i = 0; 1381 while (currentnode->children[i]->proof != currentnode->proof) 1382 { 1383 i++; 1384 }; 1385 } 1386 else 1387 { 1388 i = 0; 1389 while (currentnode->children[i]->disproof != currentnode->disproof) 1390 { 1391 i++; 1392 } 1393 }; 1394 1395 currentnode = currentnode->children[i]; 1396 1397 comp_to_coord (currentnode->move, output); 1398 printf ("%s ", output); 1399 strcat (PV, output); 1400 strcat (PV, " "); 1401 1402 make (¤tnode->move, 0); 1403 }; 1404 1405 while (currentnode != root) 1406 { 1407 unmake (¤tnode->move, 0); 1408 currentnode = currentnode->parent; 1409 }; 1410 1411 printf("\n"); 1412#endif 1413 if ((rdifftime (rtime (), xstart_time) > pn_time) && !interrupt()) 1414 break; 1415 } 1416 }; 1417 1418 printf ("P: %d D: %d N: %d S: %d Mem: %2.2fM Iters: %d MaxDepth: %d\n", root->proof, root->disproof, nodecount, (int)frees, (((nodecount) * sizeof (node_t) / (float) (1024 * 1024))), iters,maxply); 1419 1420 if (xb_mode && post) 1421 printf ("tellics whisper proof %d, disproof %d, %d nodes, %d forwards, %d iters, highest depth %d\n", root->proof, root->disproof, nodecount, forwards, iters, maxply); 1422 1423 if (!xb_mode) 1424 printf("Time : %f\n", (float)rdifftime(rtime(), xstart_time)/100.); 1425 1426 while (currentnode != root) 1427 { 1428 unmake (¤tnode->move, 0); 1429 currentnode = currentnode->parent; 1430 }; 1431 1432 if (root->proof == 0) 1433 { 1434 root->value = TRUE; 1435 1436 printf ("This position is WON.\n"); 1437 printf ("PV: "); 1438 1439 memset (output, 0, sizeof (output)); 1440 memset (PV, 0, sizeof (PV)); 1441 //currentnode = root; 1442 ply = 1; 1443 1444 while (currentnode->expanded) 1445 { 1446 if (ToMove == root_to_move) 1447 { 1448 i = 0; 1449 while (currentnode->children[i]->proof != currentnode->proof) 1450 { 1451 i++; 1452 }; 1453 } 1454 else 1455 { 1456 i = 0; 1457 while (currentnode->children[i]->disproof != currentnode->disproof) 1458 { 1459 i++; 1460 } 1461 }; 1462 1463 currentnode = currentnode->children[i]; 1464 1465 comp_to_coord (currentnode->move, output); 1466 printf ("%s ", output); 1467 strcat (PV, output); 1468 strcat (PV, " "); 1469 1470 make (¤tnode->move, 0); 1471 1472 if (ply == 1) 1473 pn_move = currentnode->move; 1474 1475 forcedwin = TRUE; 1476 }; 1477 1478 oldply = ply; 1479 1480 while (currentnode != root) 1481 { 1482 unmake (¤tnode->move, 0); 1483 currentnode = currentnode->parent; 1484 }; 1485 1486 if (!kibitzed && xb_mode && post) 1487 { 1488 kibitzed = TRUE; 1489 printf ("\ntellics kibitz Forced win in %d moves.\n", oldply/2); 1490 } 1491 1492 if (oldply == 1 && (root->proof == 0 || root->disproof == 0)) 1493 { 1494 if (root_to_move == WHITE) 1495 { 1496 printf("\n1-0 {White mates}\n"); 1497 result = black_is_mated; 1498 } 1499 else 1500 { 1501 printf("\n0-1 {Black mates}\n"); 1502 result = white_is_mated; 1503 } 1504 } 1505 1506 printf ("\n"); 1507 } 1508 else if (root->disproof == 0) 1509 { 1510 root->value = FALSE; 1511 printf ("This position is LOST.\n"); 1512 1513 pn_move = dummy; 1514 } 1515 else 1516 { 1517 root->value = UNKNOWN; 1518 printf ("This position is UNKNOWN.\n"); 1519 1520 pn_move = dummy; 1521 }; 1522 1523 /* find the move which is least likely to lose */ 1524 bdp = -1; 1525 1526 for (i = 0; i < root->num_children; i++) 1527 { 1528 if (root->children[i]->proof != 0) 1529 { 1530 if (((float)(root->children[i]->disproof) / (float)(root->children[i]->proof)) > bdp) 1531 { 1532 bdp = (float)root->children[i]->disproof / (float)(root->children[i]->proof); 1533 pn_move = root->children[i]->move; 1534 } 1535 } 1536 else 1537 { 1538 pn_move = root->children[i]->move; 1539 break; 1540 } 1541 }; 1542 1543 pn_saver = pn_move; 1544 1545 free(root); 1546 Xfree(); 1547 free(membuff); 1548 1549 //ep_square = eps; 1550 1551 return; 1552} 1553 1554move_s proofnumbercheck(move_s compmove) 1555{ 1556 node_t* root; 1557 node_t *mostproving; 1558 node_t *currentnode; 1559 rtime_t xstart_time; 1560 move_s resmove; 1561 1562 if (piece_count <= 3 && (Variant == Suicide)) 1563 { 1564 return compmove; 1565 } 1566 1567 nodecount = 0; 1568 iters = 0; 1569 frees = 0; 1570 ply = 1; 1571 maxply = 0; 1572 1573 /* make our move to check */ 1574 make(&compmove, 0); 1575 1576 hash_history[move_number+ply-1] = hash; 1577 1578 root_to_move = ToMove; 1579 1580 //eps = ep_square; 1581 1582 xstart_time = rtime(); 1583 1584 root = (node_t *) calloc(1, sizeof(node_t)); 1585 1586 membuff = (unsigned char *) calloc(PBSize, sizeof(node_t)); 1587 1588 pn_eval(root); 1589 1590 set_proof_and_disproof_numbers(root); 1591 1592 currentnode = root; 1593 1594 while (root->proof != 0 && root->disproof != 0 1595 && (bufftop < ((PBSize-SAFETY) * sizeof(node_t)))) 1596 { 1597 mostproving = select_most_proving(currentnode); 1598 develop_node(mostproving); 1599 update_ancestors(mostproving); 1600 1601 iters++; 1602 1603 if ((iters % 32) == 0) 1604 { 1605 // printf("P: %d D: %d N: %d S: %d Mem: %2.2fM Iters: %d\n", root->proof, root->disproof, nodecount, frees, (((nodecount) * sizeof(node_t) / (float)(1024*1024))), iters); 1606 if ((rdifftime (rtime (), xstart_time) > pn_time)) 1607 break; 1608 } 1609 }; 1610 1611 printf("P: %d D: %d N: %d S: %d Mem: %2.2fM Iters: %d\n", root->proof, root->disproof, nodecount, (int)frees, (((nodecount) * sizeof(node_t) / (float)(1024*1024))), iters); 1612 1613 while(currentnode != root) 1614 { 1615 unmake(¤tnode->move, 0); 1616 currentnode = currentnode->parent; 1617 }; 1618 1619 unmake(&compmove, 0); 1620 1621 if (root->proof == 0) 1622 { 1623 /* ok big problem our ab move loses */ 1624 root->value = TRUE; 1625 1626 /* use best disprover instead */ 1627 resmove = pn_move; 1628 1629 s_threat = TRUE; 1630 } 1631 else if (root->disproof == 0) 1632 { 1633 /* ab move wins...unlikely due to earlier pnsearch */ 1634 1635 root->value = FALSE; 1636 resmove = compmove; 1637 1638 } 1639 else 1640 { 1641 root->value = UNKNOWN; 1642 resmove = compmove; 1643 1644 }; 1645 1646 Xfree(); 1647 free(root); 1648 free(membuff); 1649 1650 //ep_square = eps; 1651 1652 return resmove; 1653} 1654