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
44 int nodecount;
45 int nodecount2;
46 int pn2;
47 long frees;
48 int iters;
49 int forwards;
50 int maxply;
51 int ply;
52 int pn_time;
53 move_s pn_move;
54 move_s pn_saver;
55
56 bool kibitzed;
57 int forcedwin;
58
59 int rootlosers[PV_BUFF];
60 int alllosers;
61
62 typedef 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 }
74 node_t;
75
76 void pn2_eval (node_t *node);
77 void suicide_pn_eval (node_t *this);
78 void std_pn_eval (node_t *this);
79 void losers_pn_eval (node_t *this);
80
81 unsigned char *membuff;
82 int bufftop = 0;
83
Xmalloc(int size)84 void* Xmalloc(int size)
85 {
86 int oldtop = bufftop;
87
88 bufftop += size;
89
90 return (&membuff[oldtop]);
91 };
92
Xfree(void)93 void Xfree(void)
94 {
95 bufftop = 0;
96 };
97
freenodes(node_t * node)98 void 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
pn_eval(node_t * this)123 void 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
std_pn_eval(node_t * this)139 void 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
suicide_pn_eval(node_t * this)202 void 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
losers_pn_eval(node_t * this)311 void 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
select_most_proving(node_t * node)459 node_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
set_proof_and_disproof_numbers(node_t * node)502 void 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 + floor(ply / 50);
685 node->disproof = l + floor(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 + floor(ply / 30);
696 node->disproof = l + floor(ply / 30);
697 }
698 else
699 {
700 node->proof = 1 + floor(ply / 80);
701 node->disproof = l + floor(ply / 80);
702 }
703 }
704 else
705 {
706 node->proof = 1 + floor(ply / 150);
707 node->disproof = l + floor(ply / 150);
708 }
709 }
710 }
711 else
712 {
713 if ((Variant != Suicide) && (Variant != Losers))
714 {
715 node->proof = l + floor(ply / 50);
716 node->disproof = 1 + floor(ply / 50);
717 }
718 else
719 {
720 if (Variant == Losers)
721 {
722 if (phase == Endgame)
723 {
724 node->proof = l + floor(ply/30);
725 node->disproof = 1 + floor(ply/30);
726
727 }
728 else
729 {
730 node->proof = l + floor(ply/80);
731 node->disproof = 1 + floor(ply/80);
732 }
733 }
734 else
735 {
736 node->proof = l + floor(ply / 150);
737 node->disproof = 1 + floor(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
develop_node(node_t * node)767 void 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 (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 (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
update_ancestors(node_t * node)948 void 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
978 void
pn2_eval(node_t * root)979 pn2_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
proofnumberscan(void)1016 void 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
1306 void
proofnumbersearch(void)1307 proofnumbersearch (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, 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
proofnumbercheck(move_s compmove)1554 move_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, 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