Fix another hardcored 9x9-board hardcoded value.
[gnushogi.git] / gnushogi / search.c
1 /*
2  * FILE: search.c
3  *
4  * ----------------------------------------------------------------------
5  *
6  * Copyright (c) 2012 Free Software Foundation
7  *
8  * GNU SHOGI is based on GNU CHESS
9  *
10  * This file is part of GNU SHOGI.
11  *
12  * GNU Shogi is free software; you can redistribute it and/or modify it
13  * under the terms of the GNU General Public License as published by the
14  * Free Software Foundation; either version 3 of the License,
15  * or (at your option) any later version.
16  *
17  * GNU Shogi is distributed in the hope that it will be useful, but WITHOUT
18  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
19  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
20  * for more details.
21  *
22  * You should have received a copy of the GNU General Public License along
23  * with GNU Shogi; see the file COPYING. If not, see
24  * <http://www.gnu.org/licenses/>.
25  * ----------------------------------------------------------------------
26  *
27  */
28
29 #include "gnushogi.h"
30
31 #if !defined OLDTIME && defined HAVE_GETTIMEOFDAY
32 double pow(double x, double y);
33 #endif
34
35 short background = 0;
36 static short DepthBeyond;
37 unsigned short PrVar[MAXDEPTH];
38 extern short recycle, ISZERO;
39 extern void FlagString(unsigned short flags, char *s);
40
41 #ifdef NULLMOVE
42 short null;         /* Null-move already made or not */
43 short PVari;        /* Is this the PV */
44 #endif
45
46 short zwndw;
47
48
49
50 /* ............    MOVE GENERATION & SEARCH ROUTINES    .............. */
51
52
53
54 /*
55  *  Check for draw by fourfold repetition
56  *  (same side, same captures, same board).
57  *  WARNING: this is not save (sp? safe?) yet due to possible hash collisions.
58  */
59
60 short
61 repetition()
62 {
63     short i, cnt = 0;
64
65 #ifndef NOREPETITION
66     struct GameRec  *g;
67
68     if (GameCnt > Game50 + 6)
69     {
70         for (i = GameCnt - 1; i >= Game50; i -= 2)
71         {
72             g = &GameList[i];
73
74             if (g->hashkey == hashkey && g->hashbd == hashbd)
75                 cnt++;
76         }
77     }
78 #endif
79
80     return cnt;
81 }
82
83
84
85 int plyscore, globalscore;
86
87
88 /*
89  * Find the best move in the tree between indexes p1 and p2. Swap the best
90  * move into the p1 element.
91  */
92
93 int
94 pick(short p1, short p2)
95 {
96     struct leaf  *p, *q, *r, *k;
97     short s0;
98     struct leaf temp;
99
100     k = p = &Tree[p1];
101     q = &Tree[p2];
102     s0 = p->score;
103
104     for (r = p + 1; r <= q; r++)
105     {
106         if ((r->score) > s0)
107         {
108             s0 = r->score;
109             p = r;
110         }
111     }
112
113     if (p != k)
114     {
115         temp = *p;
116         *p = *k;
117         *k = temp;
118         return true;
119     }
120
121     return false;
122 }
123
124 int bookflag = false;
125 int Jscore = 0;
126
127 int TCcount;
128 long TCleft = 0;
129
130
131
132
133 /*
134  * Select a move by calling function search() at progressively deeper ply
135  * until time is up or a mate or draw is reached. An alpha-beta window of
136  * -Awindow to +Bwindow points is set around the score returned from the
137  * previous iteration. If Sdepth != 0 then the program has correctly
138  * predicted the opponents move and the search will start at a depth of
139  * Sdepth + 1 rather than a depth of 1.
140  */
141
142 void
143 SelectMove(short side, SelectMove_mode iop)
144 {
145     static short i, tempb, tempc, tempsf, tempst, xside, rpt;
146     static short alpha, beta, score;
147     static struct GameRec  *g;
148     short sqking, in_check, blockable;
149
150 #ifdef BOOKTEST
151     printf("hashbd = %ld (hashkey >> 16)|side = %d\n",
152            hashbd, (hashkey >> 16)|side);
153 #endif
154
155     flag.timeout = false;
156     flag.back = false;
157     flag.musttimeout = false;
158
159     xside = side ^ 1;
160
161 #if ttblsz
162     recycle = (GameCnt % rehash) - rehash;
163 #endif
164
165     ExaminePosition(side);
166
167     /* if background mode set to infinite */
168     if (iop == BACKGROUND_MODE)
169     {
170         background = true;
171         /* if background mode set response time to infinite */
172         ResponseTime = 9999999;
173     }
174     else
175     {
176         player = side;
177         SetResponseTime(side);
178     }
179
180 #ifdef QUIETBACKGROUND
181     if (!background)
182 #endif /* QUIETBACKGROUND */
183         ShowResponseTime();
184
185     ExtraTime = 0;
186
187     score = ScorePosition(side);
188
189 #ifdef QUIETBACKGROUND
190     if (!background)
191 #endif /* QUIETBACKGROUND */
192         ShowSidetoMove();
193
194 #ifdef QUIETBACKGROUND
195     if (!background)
196 #endif /* QUIETBACKGROUND */
197         SearchStartStuff(side);
198
199 #ifdef HISTORY
200     array_zero(history, sizeof_history);
201 #endif
202
203     FROMsquare = TOsquare = -1;
204     PV = 0;
205
206     if (iop == FOREGROUND_MODE)
207         hint = 0;
208
209     /*
210      * If the last move was the hint, select the computed answer to the
211      * hint as first move to examine.
212      */
213
214 #if MAXDEPTH > 3
215     if (GameCnt > 0)
216     {
217         SwagHt = (GameList[GameCnt].gmove == PrVar[2]) ? PrVar[3] : 0;
218     }
219     else
220 #endif
221         SwagHt = 0;
222
223
224     for (i = 0; i < MAXDEPTH; i++)
225         PrVar[i] = killr0[i] = killr1[i] = killr2[i] = killr3[i] = 0;
226
227     /* set initial window for search */
228
229     if (flag.tsume)
230     {
231         alpha =  -(SCORE_LIMIT + 999);
232         beta = SCORE_LIMIT + 999;
233     }
234     else
235     {
236         alpha = score - ((computer == white) ? BAwindow : WAwindow);
237         beta  = score + ((computer == white) ? BBwindow : WBwindow);
238     }
239
240     rpt = 0;
241     TrPnt[1] = 0;
242     root = &Tree[0];
243
244     sqking = PieceList[side][0];
245     in_check = (board[sqking] == king)
246         ? SqAttacked(sqking, side^1, &blockable)
247         : false;
248
249     MoveList(side, 1, in_check, blockable);
250
251     for (i = TrPnt[1]; i < TrPnt[2]; i++)
252     {
253         if (!pick(i, TrPnt[2] - 1))
254             break;
255     }
256
257     /* Can I get a book move? */
258
259     if (flag.regularstart && Book)
260     {
261         flag.timeout = bookflag = OpeningBook(&hint, side);
262
263         if (TCflag)
264             ResponseTime += ResponseTime;
265     }
266
267     /* Zero stats for hash table. */
268
269     reminus = replus = 0;
270     GenCnt = NodeCnt = ETnodes = EvalNodes = HashCnt
271         = FHashAdd = HashAdd = FHashCnt = THashCol = HashCol = 0;
272
273     globalscore = plyscore = score;
274     Jscore = 0;
275     zwndw = 20;
276
277
278     /********************* main loop ********************************/
279
280     Sdepth = (MaxSearchDepth < (MINDEPTH - 1))
281         ? MaxSearchDepth
282         : (MINDEPTH - 1);
283
284     while (!flag.timeout)
285     {
286         /* go down a level at a time */
287         Sdepth++;
288
289 #ifdef NULLMOVE
290         null = 0;
291         PVari = 1;
292 #endif
293
294         /* terminate search at DepthBeyond ply past goal depth */
295         if (flag.tsume)
296             DepthBeyond = Sdepth;
297         else
298 #if defined SLOW_CPU
299             DepthBeyond = Sdepth + ((Sdepth == 1) ? 3 : 5);
300 #else
301         DepthBeyond = Sdepth + ((Sdepth == 1) ? 7 : 11);
302 #endif
303
304 # ifdef QUIETBACKGROUND
305         if (!background)
306 #endif /* QUIETBACKGROUND */
307             ShowDepth(' ');
308
309         /* search at this level returns score of PV */
310         score = search(side, 1, Sdepth, alpha, beta, PrVar, &rpt);
311
312         /* save PV as killer */
313         for (i = 1; i <= Sdepth; i++)
314             killr0[i] = PrVar[i];
315
316         /* low search failure re-search with (-inf, score) limits  */
317         if (score < alpha)
318         {
319             reminus++;
320 #ifdef QUIETBACKGROUND
321             if (!background)
322 #endif /* QUIETBACKGROUND */
323                 ShowDepth('-');
324
325             if (TCflag && TCcount < MAXTCCOUNTR)
326             {
327                 if (hard_time_limit)
328                     ExtraTime += (MAXTCCOUNTR - TCcount) * TCleft;
329                 else
330                     ExtraTime += (8 * TCleft);
331
332                 TCcount = MAXTCCOUNTR - 1;
333             }
334
335             score = search(side, 1, Sdepth, -(SCORE_LIMIT + 999),
336                            (SCORE_LIMIT + 999), PrVar, &rpt);
337         }
338         /* high search failure re-search with (score, +inf) limits */
339         else if (score > beta && !(root->flags & exact))
340         {
341             replus++;
342 #ifdef QUIETBACKGROUND
343             if (!background)
344 #endif /* QUIETBACKGROUND */
345                 ShowDepth('+');
346
347             score = search(side, 1, Sdepth, -(SCORE_LIMIT + 999),
348                            (SCORE_LIMIT + 999), PrVar, &rpt);
349         }
350
351         /**************** out of search ***********************************/
352         CheckForTimeout(score, globalscore, Jscore, zwndw);
353
354         /************************ time control ****************************/
355
356         /* save PV as killer */
357         for (i = 1; i <= Sdepth + 1; i++)
358             killr0[i] = PrVar[i];
359
360         if (!flag.timeout)
361             Tscore[0] = score;
362
363         /* if (!flag.timeout) */
364         /*
365           for (i = TrPnt[1] + 1; i < TrPnt[2]; i++)
366           if (!pick (i, TrPnt[2] - 1))
367           break;
368         */
369
370         /* if done or nothing good to look at quit */
371         if ((root->flags & exact) || (score < -SCORE_LIMIT))
372             flag.timeout = true;
373
374         /* find the next best move put below root */
375
376         if (!flag.timeout)
377         {
378 #if !defined NODYNALPHA
379             Jscore = (plyscore + score) >> 1;
380 #endif
381             zwndw = 20 + abs(Jscore / 12);
382             plyscore = score;
383
384             /* recompute search window */
385             beta = score + ((computer == white) ? BBwindow : WBwindow);
386 #if !defined NODYNALPHA
387             alpha = ((Jscore < score) ? Jscore : score)
388                 - ((computer == white) ? BAwindow : WAwindow)
389                 - zwndw;
390 #else
391             alpha = score - ((computer == white) ? BAwindow : WAwindow);
392 #endif
393         }
394
395 #ifdef QUIETBACKGROUND
396         if (!background)
397 #endif /* QUIETBACKGROUND */
398             ShowResults(score, PrVar, '.');
399     }
400
401     /********************** end of main loop ***************************/
402
403     /* background mode */
404     if (iop == BACKGROUND_MODE)
405         return;
406
407     if (rpt >= 3)
408     {
409         root->flags |= draw;
410         DRAW = CP[101];     /* Repetition */
411     }
412     else
413     {
414         /*
415          * If there are no moves and we're not in check (stalemate) then
416          * it's mate in shogi (whereas it's a draw in chess).
417          */
418
419         if (GameCnt == MAXMOVES)
420         {
421             root->flags |= draw;
422             DRAW = CP[80];      /* Max Moves */
423         }
424     }
425
426     /* not in book so set hint to guessed move for other side */
427     if (!bookflag)
428         hint = ((PrVar[1]) ? PrVar[2] : 0);
429
430     /* if not mate or draw make move and output it */
431     if (((score > -(SCORE_LIMIT + 999))
432          && (rpt <= 3)) || (root->flags & draw))
433     {
434         MakeMove(side, &Tree[0], &tempb, &tempc,
435                  &tempsf, &tempst, &INCscore);
436         algbr(root->f, root->t, (short) root->flags);
437     }
438     else
439     {
440         algbr(0, 0, 0);       /* Zero move string when mate. */
441         root->score = score;  /* When mate, ignore distinctions!
442                                * --SMC */
443     }
444
445     g = &GameList[GameCnt];
446
447     if ((g->flags & capture) && (g->piece == king))
448         flag.mate = flag.illegal = true;
449
450     /* If Time Control get the elapsed time */
451     if (TCflag)
452         ElapsedTime(COMPUTE_AND_INIT_MODE);
453
454     /* update time control info */
455     OutputMove();
456
457     /* if mate set flag */
458     if ((score == -(SCORE_LIMIT + 999) || score == (SCORE_LIMIT + 998)))
459         flag.mate = true;
460
461     /* add move to game list */
462     g->score = score;
463     g->nodes = NodeCnt;
464     g->time = (et +50)/100;
465     /* g->time = TCcount; */
466     g->depth = Sdepth;
467
468     /* update time control info */
469     if (TCflag)
470     {
471         TimeControl.clock[side] -= (et + OperatorTime);
472         timecomp[compptr] = (et + OperatorTime);
473
474         /* finished our required moves - setup the next set */
475         --TimeControl.moves[side];
476     }
477
478     /* check for end conditions */
479     if ((root->flags & draw) /* && flag.bothsides */)
480     {
481         flag.mate = true;
482     }
483     else if (GameCnt == MAXMOVES)
484     {
485         flag.mate = true;
486     }
487     /* out of move store, you lose */
488     else
489     {
490         /* switch to other side */
491         player = xside;
492     }
493
494     /* if mate clear hint */
495     if (flag.mate)
496         hint = 0;
497
498     Sdepth = 0;
499 }
500
501
502
503 /*
504  * Perform an alpha-beta search to determine the score for the current
505  * board position.  If depth <= 0 only capturing moves and responses to
506  * check are generated and searched, otherwise all moves are processed. The
507  * search depth is modified for check evasions, certain re-captures and
508  * threats.  Extensions may continue for up to 11 ply beyond the nominal
509  * search depth.
510  */
511
512 int
513 search(short side,
514        short ply,
515        short depth,
516        short alpha,
517        short beta,
518        unsigned short *bstline,
519        short *rpt)
520 {
521     short j, pnt;
522     short tempb, tempc, tempsf, tempst;
523     short xside, pbst, score, rcnt, in_check, blockable;
524     unsigned short mv, nxtline[MAXDEPTH];
525     struct leaf  *node, tmp;
526     short best = -(SCORE_LIMIT + 3000);
527     short bestwidth = 0;
528     short mustcut;
529
530 #ifdef NULLMOVE
531     short PVsave;
532     short PVarisave;
533 #endif
534
535     NodeCnt++;
536
537     /* look every ZNODE nodes for a timeout */
538 #ifdef NULLMOVE
539     if (!null)
540     {
541 #endif
542         if (NodeCnt > ETnodes)
543         {
544             ElapsedTime(COMPUTE_MODE);
545
546             if (flag.back)
547             {
548                 flag.back = false;
549                 flag.timeout = true;
550                 flag.musttimeout = false;
551             }
552             else if (TCflag || MaxResponseTime)
553             {
554                 if ((et >= (ResponseTime + ExtraTime))
555                     && (Sdepth > MINDEPTH))
556                 {
557                     /* try to extend to finish ply */
558                     if (flag.back || (TCflag && TCcount < MAXTCCOUNTX))
559                     {
560                         flag.back = false;
561                         flag.musttimeout = true;
562                         TCcount++;
563                         ExtraTime += TCleft;
564                     }
565                     else
566                     {
567                         flag.back = false;
568                         flag.timeout = true;
569                         flag.musttimeout = false;
570                     }
571                 }
572             }
573             else if (flag.back)
574             {
575                 flag.back = false;
576                 flag.timeout = true;
577                 flag.musttimeout = false;
578             }
579
580 #ifdef QUIETBACKGROUND
581             if (!background)
582 #endif
583                 ShowResponseTime();
584         }
585         else if (!TCflag && flag.musttimeout && Sdepth > MINDEPTH)
586         {
587             flag.timeout = true;
588             flag.musttimeout = false;
589         }
590 #ifdef NULLMOVE
591     }
592 #endif
593
594     xside = side ^ 1;
595     score = evaluate(side, ply, alpha, beta,
596                      INCscore, &in_check, &blockable);
597
598     /*
599      * check for possible repitition if so call repitition - rpt is
600      * repeat count
601      */
602
603     if ((ply <= Sdepth + 3) && rpthash[side][hashkey & 0xFF] > 0)
604     {
605         *rpt = repetition();
606
607         /*
608          * repeat position >3 don't need to return score it's taken
609          * care of above
610          */
611
612         if (*rpt == 1)
613         {
614             score /= 3;
615             score *= 2;
616         }
617         else if (*rpt == 2)
618             score /= 2;
619     }
620     else
621     {
622         *rpt = 0;
623     }
624
625     /* score > SCORE_LIMIT its a draw or mate */
626     if (score > SCORE_LIMIT)
627     {
628         bstline[ply] = 0;
629         return score;
630     }
631
632     /* Do we need to add depth because of special conditions */
633     /* if in check or in capture sequence search deeper */
634
635     /***************** depth extensions *****************/
636
637     if (depth > 0)
638     {
639         /* Allow opponent a chance to check again */
640         if (in_check)
641         {
642             if (depth < 2)
643                 depth = 2;
644         }
645         else if (flag.rcptr
646                  && (score > alpha) && (score < beta)
647                  && (ply > 2)
648                  && CptrFlag[ply - 1] && CptrFlag[ply - 2])
649         {
650             if (hard_time_limit)
651             {
652                 if (!flag.timeout)
653                     ++depth;
654             }
655             else
656             {
657                 ++depth;
658             }
659
660         }
661     }
662     else
663     {
664         short timeout = 0;
665
666         if (hard_time_limit)
667             timeout = flag.timeout;
668
669         if ((score >= alpha)
670             && (in_check
671                 || ((!timeout && (hung[side] > 1))
672                     && (ply == Sdepth + 1))))
673         {
674             depth = 1;
675         }
676         else if ((score <= beta)
677                  && (((ply < Sdepth + 4) && (ply > 4))
678                      && ChkFlag[ply - 2]
679                      && ChkFlag[ply - 4]
680                      && (ChkFlag[ply - 2] != ChkFlag[ply - 4])))
681         {
682             depth = 1;
683         }
684     }
685
686     /***************************************************/
687     /* try the local transition table if it's there */
688
689 #if ttblsz
690     if (/* depth > 0 && */ flag.hash && ply > 1)
691     {
692         if (use_ttable
693             && ProbeTTable(side, depth, ply, &alpha, &beta, &score) == true)
694         {
695             bstline[ply] = PV;
696             bstline[ply + 1] = 0;
697
698             if (beta == -((SCORE_LIMIT + 1000) * 2))
699                 return score;
700
701             if (alpha > beta)
702                 return alpha;
703         }
704
705 #ifdef HASHFILE
706         /* ok try the transition file if its there */
707         else if (hashfile
708                  && (depth > HashDepth)
709                  && (GameCnt < HashMoveLimit)
710                  && (ProbeFTable(side, depth, ply, &alpha, &beta, &score)
711                      == true))
712         {
713             PutInTTable(side, score, depth, ply, alpha, beta, PV);
714             bstline[ply] = PV;
715             bstline[ply + 1] = 0;
716
717             if (beta == -((SCORE_LIMIT + 1000) * 2))
718                 return score;
719
720             if (alpha > beta)
721             {
722                 return alpha;
723             }
724         }
725 #endif /* HASHFILE */
726     }
727 #endif /* ttblsz */
728
729     if (TrPnt[ply] > (TREE - 300))
730         mustcut = true;
731     else
732         mustcut = false;
733
734     /*
735      * If more then DepthBeyond ply past goal depth or at goal depth and
736      * score > beta quit - means we are out of the window.
737      */
738
739     if (mustcut || (ply > DepthBeyond) || ((depth < 1) && (score > beta)))
740         return score;
741
742     /*
743      * If below first ply and not at goal depth generate all moves else
744      * only capture moves.
745      */
746
747     if (ply > 1)
748     {
749         if ((depth > 0) || (ply < (SDEPTHLIM))
750             || (background && (ply < Sdepth + 2)))
751             MoveList(side, ply, in_check, blockable);
752         else
753             CaptureList(side, ply, in_check, blockable);
754     }
755
756     /* no moves return what we have */
757
758     /*
759      * normally a search will continue til past goal and no more capture
760      * moves exist
761      */
762
763     /* unless it hits DepthBeyond */
764     if (TrPnt[ply] == TrPnt[ply + 1])
765         return score;
766
767     /* if not at goal set best = -inf else current score */
768     best = (depth > 0) ? -(SCORE_LIMIT + 3000) : score;
769
770 #ifdef NULLMOVE
771
772     PVarisave = PVari;
773
774     /* CHECKME: is the & really an && here? */
775     if (!null  &&                        /* no previous null-move */
776         !PVari &&                        /* no null-move during the PV */
777         (ply > 2) &                      /* not at ply 1 */
778         (ply <= Sdepth) &&
779         (depth > 3) &&
780         !in_check)                       /* no check */
781         /* enough material such that zugzwang is unlikely
782          * but who knows which value is suitable? */
783     {
784         /*
785            OK, we make a null move, i.e.  this means we have nothing to do
786            but we have to keep the some arrays up to date otherwise gnushogi
787            gets confused.  Maybe somebody knows exactly which information is
788            important and which isn't.
789
790            Another idea is that we try the null-move first and generate the
791            moves later.  This may save time but we have to take care that
792            PV and other variables contain the right value so that the move
793            ordering works right.
794         */
795
796         struct GameRec  *g;
797
798         nxtline[ply + 1] = 0;
799         CptrFlag[ply] = 0;
800         TesujiFlag[ply] = 0;
801         Tscore[ply] = score;
802         PVsave = PV;
803         PV = 0;
804         null = 1;
805         g = &GameList[++GameCnt];
806         g->hashkey = hashkey;
807         g->hashbd = hashbd;
808         FROMsquare = TOsquare = -1;
809         g->Game50 = Game50;
810         g->gmove = -1;
811         g->flags = 0;
812         g->piece = 0;
813         g->color = neutral;
814
815         best = -search(xside, ply + 1, depth - 2,
816                        -beta - 1, -beta, nxtline, &rcnt);
817         null = 0;
818         PV = PVsave;
819         GameCnt--;
820
821         if (best < alpha)
822         {
823             best = -(SCORE_LIMIT + 3000);
824         }
825         else if (best > beta)
826         {
827             return best;
828         }
829         else
830         {
831             best = -(SCORE_LIMIT + 3000);
832         }
833     }
834 #endif
835
836     /* if best so far is better than alpha set alpha to best */
837     if (best > alpha)
838         alpha = best;
839
840     /********************** main loop ****************************/
841
842     /* look at each move until no more or beta cutoff */
843     for (pnt = pbst = TrPnt[ply];
844          (pnt < TrPnt[ply + 1]) && (best <= beta);
845          pnt++)
846     {
847         /* find the most interesting looking of the remaining moves */
848         if (ply > 1)
849             pick(pnt, TrPnt[ply + 1] - 1);
850
851 #ifdef NULLMOVE
852         PVari = PVarisave && (pnt == TrPnt[ply]);  /* Is this the PV? */
853 #endif
854
855         node = &Tree[pnt];
856
857         /* is this a forbidden move */
858         if (/* ply == 1 && */ node->score <= DONTUSE)
859             continue;
860
861         nxtline[ply + 1] = 0;
862
863         /* if at top level */
864 #if !defined NOPOST
865         if (ply == 1)
866         {
867 /* at the top update search status */
868             if (flag.post)
869             {
870 #ifdef QUIETBACKGROUND
871                 if (!background)
872 #endif /* QUIETBACKGROUND */
873                     ShowCurrentMove(pnt, node->f, node->t);
874             }
875         }
876 #endif
877
878         if (!(node->flags & exact))
879         {
880             /* make the move and go deeper */
881
882             MakeMove(side, node, &tempb, &tempc, &tempsf,
883                      &tempst, &INCscore);
884             CptrFlag[ply] = ((node->flags & capture) != 0);
885             TesujiFlag[ply] = (node->flags & tesuji)
886                 && (node->flags & dropmask);
887             Tscore[ply] = node->score;
888             PV = node->reply;
889
890             node->score = -search(xside, ply + 1,
891                                   (depth > 0) ? (depth - 1) : 0,
892                                   -beta, -alpha,
893                                   nxtline, &rcnt);
894
895             /*
896              * if(!flag.timeout)
897              *     node->score = score;
898              */
899
900             node->width = ((ply % 2) == 1)
901                 ? (TrPnt[ply + 2] - TrPnt[ply + 1])
902                 : 0;
903
904             if ((node->score > SCORE_LIMIT) || (node->score < -SCORE_LIMIT) )
905                 node->flags |= exact;
906             else if (rcnt == 1)
907                 node->score /= 2;
908
909             if (((rcnt >= 3)
910                  || ((node->score == (SCORE_LIMIT + 999) - ply)
911                      && !ChkFlag[ply])))
912             {
913                 node->flags |= (draw | exact);
914                 DRAW = CP[58];  /* Draw */
915                 node->score = ((side == computer) ? contempt : -contempt);
916             }
917
918             node->reply = nxtline[ply + 1];
919
920             /* reset to try next move */
921             UnmakeMove(side, node, &tempb, &tempc, &tempsf, &tempst);
922         }
923
924         /* if best move so far */
925         /* CHECKME: flag.timeout isn't valid if no hard time limit */
926         if (!flag.timeout
927             && ((node->score > best)
928                 || ((node->score == best) && (node->width > bestwidth))))
929         {
930             /*
931              * All things being equal pick the denser part of the
932              * tree.
933              */
934             bestwidth = node->width;
935
936             /*
937              * If not at goal depth and better than alpha and not
938              * an exact score increment by depth.
939              */
940
941             if ((depth > 0) && (node->score > alpha)
942                 && !(node->flags & exact))
943             {
944                 node->score += depth;
945             }
946
947             best = node->score;
948             pbst = pnt;
949
950             if (best > alpha)
951                 alpha = best;
952
953             /* update best line */
954             for (j = ply + 1; nxtline[j] > 0; j++)
955                 bstline[j] = nxtline[j];
956
957             bstline[j] = 0;
958             bstline[ply] = (node->f << 8) | node->t;
959
960             /* if at the top */
961             if (ply == 1)
962             {
963                 /*
964                  * If it's better than the root score make it the root.
965                  */
966                 if ((best > root->score)
967                     || ((best == root->score)
968                         && (bestwidth > root->width)))
969                 {
970                     tmp = Tree[pnt];
971
972                     for (j = pnt - 1; j >= 0; j--)
973                         Tree[j + 1] = Tree[j];
974
975                     Tree[0] = tmp;
976                     pbst = 0;
977                 }
978
979 #ifdef QUIETBACKGROUND
980                 if (!background)
981                 {
982 #endif /* QUIETBACKGROUND */
983                     if (Sdepth > 2)
984                     {
985                         if (best > beta)
986                         {
987                             ShowResults(best, bstline, '+');
988                         }
989                         else if (best < alpha)
990                         {
991                             ShowResults(best, bstline, '-');
992                         }
993                         else
994                         {
995                             ShowResults (best, bstline, '&');
996                         }
997                     }
998 #ifdef QUIETBACKGROUND
999                 }
1000 #endif
1001             }
1002         }
1003
1004         if (flag.timeout)
1005             return Tscore[ply - 1];
1006     }
1007
1008     /******************************************************/
1009
1010     node = &Tree[pbst];
1011     mv = (node->f << 8) | node->t;
1012
1013 #ifdef NULLMOVE
1014     PVari = PVarisave;
1015 #endif
1016
1017     /*
1018      * We have a move so put it in local table - if it's already there
1019      * done else if not there or needs to be updated also put it in
1020      * hashfile
1021      */
1022
1023 #if ttblsz
1024     if (flag.hash && ply <= Sdepth && *rpt == 0 && best == alpha)
1025     {
1026 #  ifdef HASHFILE /* MCV: warning: this confuses the formatter. */
1027         if (use_ttable
1028             && PutInTTable(side, best, depth, ply, alpha, beta, mv)
1029             && hashfile
1030             && (depth > HashDepth)
1031             && (GameCnt < HashMoveLimit))
1032 #  else
1033         if (use_ttable
1034             && PutInTTable(side, best, depth, ply, alpha, beta, mv))
1035 #  endif
1036         {
1037             PutInFTable(side, best, depth, ply,
1038                         alpha, beta, node->f, node->t);
1039         }
1040     }
1041 #endif /* ttblsz */
1042
1043     if (depth > 0)
1044     {
1045 #if defined HISTORY
1046         unsigned short h, x;
1047         h = mv;
1048
1049         if (history[x = hindex(side, h)] < HISTORYLIM)
1050             history[x] += (unsigned short) 1 << depth;
1051 #endif
1052
1053         if (node->t != (short)(GameList[GameCnt].gmove & 0xFF))
1054         {
1055             if (best <= beta)
1056             {
1057                 killr3[ply] = mv;
1058             }
1059             else if (mv != killr1[ply])
1060             {
1061                 killr2[ply] = killr1[ply];
1062                 killr1[ply] = mv;
1063             }
1064         }
1065
1066         killr0[ply] = ((best > SCORE_LIMIT) ? mv : 0);
1067     }
1068
1069     return best;
1070 }
1071
1072
1073
1074 /*
1075  * Update the PieceList and Pindex arrays when a piece is captured or when a
1076  * capture is unmade.
1077  */
1078
1079 void
1080 UpdatePieceList(short side, short sq, UpdatePieceList_mode iop)
1081 {
1082     short i;
1083
1084     if (iop == REMOVE_PIECE)
1085     {
1086         PieceCnt[side]--;
1087
1088         for (i = Pindex[sq]; i <= PieceCnt[side]; i++)
1089         {
1090             PieceList[side][i] = PieceList[side][i + 1];
1091             Pindex[PieceList[side][i]] = i;
1092         }
1093     }
1094     else if (board[sq] == king)
1095     {
1096         /* king must have index 0 */
1097         for (i = PieceCnt[side]; i >= 0; i--)
1098         {
1099             PieceList[side][i + 1] = PieceList[side][i];
1100             Pindex[PieceList[side][i + 1]] = i + 1;
1101         }
1102
1103         PieceCnt[side]++;
1104         PieceList[side][0] = sq;
1105         Pindex[sq] = 0;
1106     }
1107     else
1108     {
1109         PieceCnt[side]++;
1110         PieceList[side][PieceCnt[side]] = sq;
1111         Pindex[sq] = PieceCnt[side];
1112     }
1113 }
1114
1115
1116
1117 /* Make or Unmake drop move. */
1118
1119 void
1120 drop(short side, short piece, short f, short t, short iop)
1121 {
1122     if (iop == 1)
1123     {
1124         short n;
1125         board[t] = piece;
1126         color[t] = side;
1127
1128 #if !defined SAVE_SVALUE
1129         svalue[t] = 0;
1130 #endif
1131
1132         n = Captured[side][piece]--;
1133
1134         UpdateDropHashbd(side, piece, n);
1135         UpdateHashbd(side, piece, -1, t);
1136         UpdatePieceList(side, t, ADD_PIECE);
1137
1138         if (piece == pawn)
1139         {
1140             ++PawnCnt[side][column(t)];
1141         }
1142
1143         Mvboard[t]++;
1144         HasPiece[side][piece]++;
1145     }
1146     else
1147     {
1148         short n;
1149         board[t] = no_piece;
1150         color[t] = neutral;
1151         n = ++Captured[side][piece];
1152
1153         UpdateDropHashbd(side, piece, n);
1154         UpdateHashbd(side, piece, -1, t);
1155         UpdatePieceList(side, t, REMOVE_PIECE);
1156
1157         if (piece == pawn)
1158             --PawnCnt[side][column(t)];
1159
1160         Mvboard[t]--;
1161         HasPiece[side][piece]--;
1162     }
1163 }
1164
1165
1166 #ifdef HASHKEYTEST
1167 int
1168 CheckHashKey()
1169 {
1170     unsigned long chashkey, chashbd;
1171     short side, sq;
1172     chashbd = chashkey = 0;
1173
1174     for (sq = 0; sq < NO_SQUARES; sq++)
1175     {
1176         if (color[sq] != neutral)
1177         {
1178             chashbd ^= (*hashcode)[color[sq]][board[sq]][sq].bd;
1179             chashkey ^= (*hashcode)[color[sq]][board[sq]][sq].key;
1180         }
1181
1182         /* hashcodes for initial board are 0 ! */
1183         if (Stcolor[sq] != neutral)
1184         {
1185             chashbd ^= (*hashcode)[Stcolor[sq]][Stboard[sq]][sq].bd;
1186             chashkey ^= (*hashcode)[Stcolor[sq]][Stboard[sq]][sq].key;
1187         }
1188     }
1189
1190     for (side = 0; side <= 1; side++)
1191     {
1192         short piece;
1193
1194         for (piece = 0; piece < NO_PIECES; piece++)
1195         {
1196             short n = Captured[side][piece];
1197
1198             if (n > 0)
1199             {
1200                 short i;
1201
1202                 for (i = 1; i <= n; i++)
1203                 {
1204                     chashbd ^= (*drop_hashcode)[side][piece][i].bd;
1205                     chashkey ^= (*drop_hashcode)[side][piece][i].key;
1206                 }
1207             }
1208         }
1209     }
1210
1211     if (chashbd != hashbd)
1212         printf("chashbd %lu != hashbd %lu\n", chashbd, hashbd);
1213
1214     if (chashkey != hashkey)
1215         printf("chashkey %lu != hashkey %lu\n", chashkey, hashkey);
1216
1217     if (chashbd != hashbd || chashkey != hashkey)
1218         return 1;
1219
1220     return 0;
1221 }
1222 #endif
1223
1224
1225
1226
1227 /*
1228  * Update Arrays board[], color[], and Pindex[] to reflect the new board
1229  * position obtained after making the move pointed to by node. Also update
1230  * miscellaneous stuff that changes when a move is made.
1231  */
1232
1233 void
1234 MakeMove(short side,
1235          struct leaf  *node,
1236          short *tempb,  /* piece at to square */
1237          short *tempc,  /* color of to square */
1238          short *tempsf, /* static value of piece on from */
1239          short *tempst, /* static value of piece on to */
1240          short *INCscore)   /* score increment */
1241 {
1242     short f, t, xside;
1243     struct GameRec  *g;
1244     short fromb, fromc;
1245
1246     xside = side ^ 1;
1247     g = &GameList[++GameCnt];
1248     g->hashkey = hashkey;
1249     g->hashbd = hashbd;
1250     FROMsquare = f = node->f;
1251     TOsquare = t = (node->t & 0x7f);
1252     *INCscore = (short)node->INCscore;
1253     g->Game50 = Game50;
1254     g->gmove = (f << 8) | node->t;
1255     g->flags = node->flags;
1256
1257 #ifdef HASHKEYTEST
1258     if (CheckHashKey())
1259     {
1260         short i;
1261         algbr(f, t, node->flags);
1262         printf("error before MakeMove: %s\n", mvstr[0]);
1263         UpdateDisplay(0, 0, 1, 0);
1264
1265         for (i = 1; i <= GameCnt; i++)
1266         {
1267             movealgbr(GameList[i].gmove, mvstr[0]);
1268             printf("%d: %s\n", i, mvstr[0]);
1269         }
1270
1271         exit(1);
1272     }
1273 #endif
1274
1275     rpthash[side][hashkey & 0xFF]++, ISZERO++;
1276
1277     if (f > NO_SQUARES)
1278     {
1279         g->fpiece = (node->flags & pmask);
1280         g->piece = *tempb = no_piece;
1281         g->color = *tempc = neutral;
1282
1283 #if !defined SAVE_SVALUE
1284         *tempsf = 0;
1285         *tempst = svalue[t];
1286 #endif
1287
1288         (void)drop(side, g->fpiece, f, t, 1);
1289     }
1290     else
1291     {
1292 #if !defined SAVE_SVALUE
1293         *tempsf = svalue[f];
1294         *tempst = svalue[t];
1295 #endif
1296
1297         g->fpiece = board[f];
1298         g->piece = *tempb = board[t];
1299         g->color = *tempc = color[t];
1300         fromb = board[f];
1301         fromc = color[f];
1302
1303         if (*tempc != neutral)
1304         {
1305             /* Capture a piece */
1306             UpdatePieceList(*tempc, t, REMOVE_PIECE);
1307
1308             /* if capture decrement pawn count */
1309             if (*tempb == pawn)
1310                 --PawnCnt[*tempc][column(t)];
1311
1312             mtl[xside] -= (*value)[stage][*tempb];
1313             HasPiece[xside][*tempb]--;
1314
1315             {
1316                 short n, upiece = unpromoted[*tempb];
1317
1318                 /* add "upiece" captured by "side" */
1319                 n = ++Captured[side][upiece];
1320
1321                 UpdateDropHashbd(side, upiece, n);
1322                 mtl[side] += (*value)[stage][upiece];
1323             }
1324
1325             /* remove "*tempb" of "xside" from board[t] */
1326             UpdateHashbd(xside, *tempb, -1, t);
1327
1328 #if !defined SAVE_SVALUE
1329             *INCscore += *tempst; /* add value of catched piece
1330                                    * to own score */
1331 #endif
1332
1333             Mvboard[t]++;
1334         }
1335
1336         color[t] = fromc;
1337
1338 #if !defined SAVE_SVALUE
1339         svalue[t] = svalue[f];
1340         svalue[f] = 0;
1341 #endif
1342
1343         Pindex[t] = Pindex[f];
1344         PieceList[side][Pindex[t]] = t;
1345         color[f] = neutral;
1346         board[f] = no_piece;
1347
1348         if (node->flags & promote)
1349         {
1350             short tob;
1351
1352             board[t] = tob = promoted[fromb];
1353
1354             /* remove unpromoted piece from board[f] */
1355             UpdateHashbd(side, fromb, f, -1);
1356
1357             /* add promoted piece to board[t] */
1358             UpdateHashbd(side, tob, -1, t);
1359             mtl[side] += value[stage][tob] - value[stage][fromb];
1360
1361             if (fromb == pawn)
1362                 --PawnCnt[side][column(f)];
1363
1364             HasPiece[side][fromb]--;
1365             HasPiece[side][tob]++;
1366
1367 #if !defined SAVE_SVALUE
1368             *INCscore -= *tempsf;
1369 #endif
1370         }
1371         else
1372         {
1373             board[t] = fromb;
1374             /* remove piece from board[f] and add it to board[t] */
1375             UpdateHashbd(side, fromb, f, t);
1376         }
1377
1378         Mvboard[f]++;
1379     }
1380
1381 #ifdef HASHKEYTEST
1382     algbr(f, t, node->flags);
1383
1384     if (CheckHashKey())
1385     {
1386         printf("error in MakeMove: %s\n", mvstr[0]);
1387         exit(1);
1388     }
1389 #endif
1390 }
1391
1392
1393
1394
1395 /*
1396  * Take back a move.
1397  */
1398
1399 void
1400 UnmakeMove(short side,
1401            struct leaf  *node,
1402            short *tempb,
1403            short *tempc,
1404            short *tempsf,
1405            short *tempst)
1406 {
1407     short f, t, xside;
1408
1409     xside = side ^ 1;
1410     f = node->f;
1411     t = node->t & 0x7f;
1412     Game50 = GameList[GameCnt].Game50;
1413
1414     if (node->flags & dropmask)
1415     {
1416         (void)drop(side, (node->flags & pmask), f, t, 2);
1417
1418 #if !defined SAVE_SVALUE
1419         svalue[t] = *tempst;
1420 #endif
1421     }
1422     else
1423     {
1424         short tob, fromb;
1425
1426         color[f] = color[t];
1427         board[f] = tob = fromb = board[t];
1428
1429 #if !defined SAVE_SVALUE
1430         svalue[f] = *tempsf;
1431 #endif
1432
1433         Pindex[f] = Pindex[t];
1434         PieceList[side][Pindex[f]] = f;
1435         color[t] = *tempc;
1436         board[t] = *tempb;
1437
1438 #if !defined SAVE_SVALUE
1439         svalue[t] = *tempst;
1440 #endif
1441
1442         /* Undo move */
1443         if (node->flags & promote)
1444         {
1445             board[f] = fromb = unpromoted[tob];
1446             mtl[side] += value[stage][fromb] - value[stage][tob];
1447
1448             if (fromb == pawn)
1449                 ++PawnCnt[side][column(f)];
1450
1451             HasPiece[side][fromb]++;
1452             HasPiece[side][tob]--;
1453
1454             /* add unpromoted piece to board[f] */
1455             UpdateHashbd(side, fromb, f, -1);
1456
1457             /* remove promoted piece from board[t] */
1458             UpdateHashbd(side, tob, -1, t);
1459         }
1460         else
1461         {
1462             if (fromb == pawn)
1463             {
1464                 --PawnCnt[side][column(t)];
1465                 ++PawnCnt[side][column(f)];
1466             };
1467
1468             /* remove piece from board[t] and add it to board[f] */
1469             UpdateHashbd(side, fromb, f, t);
1470         }
1471
1472         /* Undo capture */
1473         if (*tempc != neutral)
1474         {
1475             short n, upiece = unpromoted[*tempb];
1476
1477             UpdatePieceList(*tempc, t, ADD_PIECE);
1478
1479             if (*tempb == pawn)
1480                 ++PawnCnt[*tempc][column(t)];
1481
1482             mtl[xside] += (*value)[stage][*tempb];
1483             HasPiece[xside][*tempb]++;
1484             mtl[side] -= (*value)[stage][upiece];
1485
1486             /* remove "upiece" captured by "side" */
1487             n = Captured[side][upiece]--;
1488
1489             UpdateDropHashbd(side, upiece, n);
1490
1491             /* replace captured piece on board[t] */
1492             UpdateHashbd(xside, *tempb, -1, t);
1493             Mvboard[t]--;
1494         }
1495
1496         Mvboard[f]--;
1497     }
1498
1499     GameCnt--;
1500     rpthash[side][hashkey & 0xFF]--, ISZERO--;
1501
1502 #ifdef HASHKEYTEST
1503     algbr(f, t, node->flags);
1504
1505     if (CheckHashKey())
1506     {
1507         printf("error in UnmakeMove: %s\n", mvstr[0]);
1508         exit(1);
1509     }
1510 #endif
1511 }
1512
1513
1514
1515 /*
1516  * Scan thru the board seeing what's on each square. If a piece is found,
1517  * update the variables PieceCnt, PawnCnt, Pindex and PieceList. Also
1518  * determine the material for each side and set the hashkey and hashbd
1519  * variables to represent the current board position. Array
1520  * PieceList[side][indx] contains the location of all the pieces of either
1521  * side. Array Pindex[sq] contains the indx into PieceList for a given
1522  * square.
1523  */
1524
1525 void
1526 InitializeStats(void)
1527 {
1528     short i, sq;
1529
1530     for (i = 0; i < NO_COLS; i++)
1531         PawnCnt[black][i] = PawnCnt[white][i] = 0;
1532
1533     mtl[black] = mtl[white] = 0;
1534     PieceCnt[black] = PieceCnt[white] = 0;
1535     hashbd = hashkey = 0;
1536
1537     for (sq = 0; sq < NO_SQUARES; sq++)
1538     {
1539         if (color[sq] != neutral)
1540         {
1541             mtl[color[sq]] += (*value)[stage][board[sq]];
1542
1543             if (board[sq] == pawn)
1544                 ++PawnCnt[color[sq]][column(sq)];
1545
1546             Pindex[sq] = ((board[sq] == king) ? 0 : ++PieceCnt[color[sq]]);
1547             PieceList[color[sq]][Pindex[sq]] = sq;
1548             UpdateHashbd(color[sq], board[sq], sq, -1);
1549         }
1550
1551         /* hashcodes for initial board are 0 ! */
1552         if (Stcolor[sq] != neutral)
1553             UpdateHashbd(Stcolor[sq], Stboard[sq], sq, -1);
1554     }
1555
1556     {
1557         short side;
1558
1559         for (side = 0; side <= 1; side++)
1560         {
1561             short piece;
1562
1563             for (piece = 0; piece < NO_PIECES; piece++)
1564             {
1565                 short n = Captured[side][piece];
1566
1567                 if (n > 0)
1568                 {
1569                     Captured[side][piece] = 0;
1570
1571                     for (i = 1; i <= n; i++)
1572                     {
1573                         ++Captured[side][piece];
1574                         UpdateDropHashbd(side, piece, i);
1575                         mtl[side] += (*value)[stage][piece];
1576                     }
1577                 }
1578             }
1579         }
1580     }
1581
1582 #ifdef HASHKEYTEST
1583     if (CheckHashKey())
1584     {
1585         printf("error in InitializeStats\n");
1586         exit(1);
1587     }
1588 #endif
1589 }