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