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 (&currentnode->move, 0);
1403	    };
1404
1405	  while (currentnode != root)
1406	    {
1407	      unmake (&currentnode->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 (&currentnode->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 (&currentnode->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 (&currentnode->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(&currentnode->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