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