src/genmove.c

   1 /*
   2  * genmoves.c - C source for GNU SHOGI
   3  *
   4  * Copyright (c) 1993, 1994 Matthias Mutz
   5  *
   6  * GNU SHOGI is based on GNU CHESS
   7  *
   8  * Copyright (c) 1988,1989,1990 John Stanback
   9  * Copyright (c) 1992 Free Software Foundation
  10  *
  11  * This file is part of GNU SHOGI.
  12  *
  13  * GNU Shogi is free software; you can redistribute it and/or modify
  14  * it under the terms of the GNU General Public License as published by
  15  * the Free Software Foundation; either version 1, or (at your option)
  16  * any later version.
  17  *
  18  * GNU Shogi is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * along with GNU Shogi; see the file COPYING.  If not, write to
  25  * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  26  */
  27
  28 #include "gnushogi.h"
  29
  30 /* #define DONTUSE_HEURISTIC */
  31
  32 #ifdef DEBUG
  33 #include <assert.h>
  34 #endif
  35
  36 short *TrP;
  37
  38 static struct leaf far *node;
  39 static short sqking, sqxking;
  40 static short InCheck = false, GenerateAllMoves = false;
  41 static short check_determined = false;
  42
  43 static short INCscore = 0;
  44
  45 short deepsearchcut = true;
  46 short tas = false, taxs = false, ssa = false;
  47
  48 short generate_move_flags = false;
  49
  50
  51 /*
  52  * Ply limits for deep search cut.
  53  * No moves or drops flagged with "stupid" are considered beyond ply BEYOND_STUPID.
  54  * Only moves or drops flagged with "kingattack" are considered beyond ply BEYOND_KINGATTACK.
  55  * No moves or drops flagged with "questionable" are considered beyond ply BEYOND_QUESTIONABLE.
  56  * Only moves or drops flagged with "tesuji" are considered beyond ply BEYOND_TESUJI.
  57  * No drops are considered beyond ply BEYOND_DROP.
  58  * Exceptions: moves or drops that prevent check or give check are always considered.
  59  */
  60
  61 #if defined THINK_C || defined MSDOS
  62 #define BEYOND_STUPID 0
  63 #define BEYOND_TIMEOUT 2
  64 #define BEYOND_KINGATTACK 4
  65 #define BEYOND_QUESTIONABLE 6
  66 #define BEYOND_TESUJI 6
  67 #define BEYOND_DROP 8
  68 #else
  69 #define BEYOND_STUPID 0
  70 #define BEYOND_TIMEOUT 2
  71 #define BEYOND_KINGATTACK 6
  72 #define BEYOND_QUESTIONABLE 8
  73 #define BEYOND_TESUJI 8
  74 #define BEYOND_DROP 10
  75 #endif
  76
  77 static short MaxNum[MAXDEPTH] =
  78   {-1,40,80,20,40,10, 5, 5, 5, 5,
  79     5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  80     5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  81     5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  82   };
  83
  84 #ifdef HASHKEYTEST
  85     extern int CheckHashKey ();
  86     extern char mvstr[4][6];
  87 #endif
  88
  89
  90 inline
  91 static
  92 void
  93 GenMakeMove (short int side,
  94              short f,
  95              short t,
  96              short int *tempb,  /* piece at to square */
  97              short int *tempc,  /* color of to square */
  98              short int promote_piece)
  99
 100 /*
 101  * Update Arrays board[] and color[] to reflect the new board
 102  * position obtained after making the move pointed to by node.
 103  */
 104
 105 {
 106   register short int piece, upiece, n;
 107
 108   t = t & 0x7f;
 109
 110 #ifdef DEBUG
 111   assert(f!=NO_SQUARES);
 112 #endif
 113
 114   if (f > NO_SQUARES )
 115     {
 116       piece = f - NO_SQUARES;
 117       if ( piece > NO_PIECES ) piece -= NO_PIECES;
 118       board[t] = piece;
 119       color[t] = side;
 120       n = Captured[side][piece]--;
 121       UpdateDropHashbd (side, piece, n);
 122       UpdateHashbd (side, piece, -1, t);
 123       UpdatePieceList (side, t, ADD_PIECE);
 124     }
 125   else
 126     {
 127       *tempb = board[t];
 128       *tempc = color[t];
 129       if ( *tempb != no_piece ) {
 130         n = ++Captured[side][upiece = unpromoted[*tempb]];
 131         UpdateDropHashbd (side, upiece, n);
 132         UpdateHashbd (*tempc, *tempb, -1, t);
 133         UpdatePieceList (*tempc, t, REMOVE_PIECE);
 134       }
 135       piece = board[f];
 136       Pindex[t] = Pindex[f];
 137       PieceList[side][Pindex[t]] = t;
 138       color[f] = neutral;
 139       board[f] = no_piece;
 140       color[t] = side;
 141       if ( promote_piece ) {
 142         UpdateHashbd(side,piece,f,-1);
 143         board[t] = promoted[piece];
 144         UpdateHashbd(side,board[t],-1,t);
 145       } else {
 146         board[t] = piece;
 147         UpdateHashbd(side,piece,f,t);
 148       }
 149     }
 150 #ifdef DEBUG
 151     assert(Captured[black][0]==0 && Captured[white][0]==0);
 152 #endif
 153 #ifdef HASHKEYTEST
 154     if ( CheckHashKey () ) {
 155       algbr(f,t,0);
 156       printf("error in GenMakeMove: %s\n",mvstr[0]);
 157       exit(1);
 158     }
 159 #endif
 160 }
 161
 162 static
 163 void
 164 GenUnmakeMove (short int side,
 165                short f,
 166                short t,
 167                short int tempb,
 168                short int tempc,
 169                short int promote_piece)
 170
 171 /*
 172  * Take back a move.
 173  */
 174
 175 {
 176   register short piece, upiece, n;
 177
 178   t = t & 0x7f;
 179
 180 #ifdef DEBUG
 181   assert(f!=NO_SQUARES);
 182 #endif
 183
 184   if (f > NO_SQUARES )
 185     {
 186       piece = f - NO_SQUARES;
 187       if ( piece > NO_PIECES ) piece -= NO_PIECES;
 188       board[t] = no_piece;
 189       color[t] = neutral;
 190       n = ++Captured[side][piece];
 191       UpdateDropHashbd (side, piece, n);
 192       UpdateHashbd (side, piece, -1, t);
 193       UpdatePieceList (side, t, REMOVE_PIECE);
 194     }
 195   else
 196     {
 197       piece = board[t];
 198       color[t] = tempc;
 199       board[t] = tempb;
 200       Pindex[f] = Pindex[t];
 201       PieceList[side][Pindex[f]] = f;
 202       if ( tempb != no_piece ) {
 203         n = Captured[side][upiece=unpromoted[tempb]]--;
 204         UpdateDropHashbd (side, upiece, n);
 205         UpdateHashbd (tempc, tempb, -1, t);
 206         UpdatePieceList (tempc, t, ADD_PIECE);
 207       }
 208       color[f] = side;
 209       if ( promote_piece ) {
 210         UpdateHashbd(side,piece,-1,t);
 211         board[f] = unpromoted[piece];
 212         UpdateHashbd(side,board[f],f,-1);
 213       } else {
 214         board[f] = piece;
 215         UpdateHashbd(side,piece,f,t);
 216       }
 217     }
 218 #ifdef DEBUG
 219     assert(Captured[black][0]==0 && Captured[white][0]==0);
 220 #endif
 221 #ifdef HASHKEYTEST
 222     if ( CheckHashKey () ) {
 223       algbr(f,t,0);
 224       printf("error in GenUnmakeMove: %s\n",mvstr[0]);
 225       exit(1);
 226     }
 227 #endif
 228 }
 229
 230
 231
 232 static void
 233 gives_check_flag (unsigned short *flags, short side, short f, short t)
 234 {
 235   short tempb, tempc, blockable, promote_piece;
 236   promote_piece = (*flags & promote) != 0;
 237   GenMakeMove (side, f, t, &tempb, &tempc, promote_piece);
 238   if ( SqAtakd(sqxking, side, &blockable) )
 239      *flags |= check;
 240   GenUnmakeMove (side, f, t, tempb, tempc, promote_piece);
 241 }
 242
 243
 244 inline
 245 static
 246 void
 247 Link (short side, short piece,
 248       short from, short to, unsigned short local_flag, short s)
 249 {
 250 #ifdef notdef
 251     if (debug_eval ) {
 252         fprintf ( debug_eval_file, "link from %d to %d InCheck %d tsume %d\n",
 253           from, to, InCheck, flag.tsume );
 254     }
 255 #endif
 256
 257     if ( *TrP == TREE ) {
 258 #ifdef NONDSP
 259       printf("TREE overflow\n");
 260 #else
 261       ShowMessage("TREE overflow\n");
 262 #endif
 263     } else {
 264       node->f = from;
 265       node->t = (local_flag & promote) ? (to | 0x80) : to;
 266       node->reply = 0;
 267       node->flags = local_flag;
 268       node->score = s;
 269       node->INCscore = INCscore;
 270       if ( GenerateAllMoves )
 271         {
 272           (*TrP)++, node++;
 273         }
 274       else if ( InCheck )
 275         {
 276           /* only moves out of check */
 277           short tempb, tempc, sq, threat, blockable, promote_piece;
 278           promote_piece = (node->flags & promote) != 0;
 279           GenMakeMove (side, node->f, node->t, &tempb, &tempc, promote_piece);
 280           sq = (from == sqking) ? to : sqking;
 281           threat = SqAtakd(sq, side ^ 1, &blockable);
 282           GenUnmakeMove (side, node->f, node->t, tempb, tempc, promote_piece);
 283           if ( !threat )
 284             (*TrP)++, node++;
 285         }
 286       else if ( flag.tsume )
 287         {
 288           /* only moves that give check */
 289           if ( !(node->flags & check) && !check_determined ) {
 290             /* determine check flag */
 291             gives_check_flag(&node->flags,side,node->f,node->t);
 292           }
 293           if ( node->flags & check )
 294             (*TrP)++, node++;
 295         }
 296       else
 297         (*TrP)++, node++;
 298     }
 299 }
 300
 301
 302 inline
 303 int
 304 PromotionPossible (short int color, short int f, short int t, short int p)
 305 {
 306   if ( color == black ) {
 307     if ( f < 54 && t < 54 ) return(false);
 308   } else {
 309     if ( f > 26 && t > 26 ) return(false);
 310   };
 311
 312   switch ( p ) {
 313     case pawn: return(true);
 314     case lance: return(true);
 315     case knight: return(true);
 316     case silver: return(true);
 317     case bishop: return(true);
 318     case rook: return(true);
 319   };
 320
 321   return(false);
 322 }
 323
 324
 325 inline
 326 int
 327 NonPromotionPossible (short int color, short int f, short int t, short int p)
 328 {
 329   switch ( p ) {
 330     case pawn :
 331            if ( color == black )
 332              return ((t < 72) ? true : (generate_move_flags ? ILLEGAL_TRAPPED : false));
 333            else
 334              return ((t > 8) ? true : (generate_move_flags ? ILLEGAL_TRAPPED : false));
 335     case lance:
 336            if ( color == black )
 337              return ((t < 72) ? true : (generate_move_flags ? ILLEGAL_TRAPPED : false));
 338            else
 339              return ((t > 8) ? true : (generate_move_flags ? ILLEGAL_TRAPPED : false));
 340     case knight:
 341            if ( color == black )
 342              return ((t < 63) ? true : (generate_move_flags ? ILLEGAL_TRAPPED : false));
 343            else
 344              return ((t > 17) ? true : (generate_move_flags ? ILLEGAL_TRAPPED : false));
 345   };
 346
 347   return(true);
 348 }
 349
 350
 351 #if defined FIELDBONUS || defined DROPBONUS
 352
 353 inline
 354 static
 355 short
 356 field_bonus (short int ply, short int side, short int piece, short int f, short int t,
 357              unsigned short *local_flag)
 358
 359 /* bonus for possible next moves */
 360
 361 {
 362   register short s, u, ptyp;
 363   register unsigned char *ppos, *pdir;
 364   register short c1, c2;
 365 #ifdef SAVE_NEXTPOS
 366   short d;
 367 #endif
 368
 369   c1 = side;
 370   c2 = side ^ 1;
 371
 372   s = 0;
 373
 374   check_determined = true;
 375
 376   ptyp = ptype[side][piece];
 377
 378 #ifdef SAVE_NEXTPOS
 379   u = first_direction(ptyp,&d,t);
 380 #else
 381   ppos = (*nextpos[ptyp])[t];
 382   pdir = (*nextdir[ptyp])[t];
 383   u = ppos[t];
 384 #endif
 385
 386   do
 387     { short coloru = color[u];
 388       if ( piece != king && GameCnt > 40 ) {
 389         if ( distance(u,EnemyKing) <= 1 ) {
 390           /* can reach square near own king */
 391           s += 2;
 392           *local_flag |= kingattack;
 393         } else if ( distance(u,OwnKing) <= 1 ) {
 394           /* can reach square near enemy king */
 395           s++;
 396           *local_flag |= kingattack;
 397         }
 398       }
 399       if (coloru == side ) {
 400         /* impossible next move */
 401 #ifdef SAVE_NEXTPOS
 402         u = next_direction(ptyp,&d,t);
 403 #else
 404         u = pdir[u];
 405 #endif
 406       } else {
 407         /* possible next move */
 408         if (PromotionPossible(side,t,u,piece)) {
 409           /* possible promotion in next move */
 410           if ( piece == pawn )
 411             {
 412               s += 2;
 413 #ifdef TESUJIBONUS
 414               if ( !InPromotionZone(side,t) ) {
 415                 *local_flag |= tesuji; /* The dangling pawn */
 416                 s++;
 417               }
 418 #endif
 419             }
 420           else
 421             s++;
 422         }
 423         if (coloru == neutral) {
 424           /* next move to an empty square */
 425           if ( u == FROMsquare ) {
 426              /* opponent has just left this square */
 427              s++;
 428           }
 429 #ifdef SAVE_NEXTPOS
 430           u = next_position(ptyp,&d,t,u);
 431 #else
 432           u = ppos[u];
 433 #endif
 434         } else {
 435           /* attack opponents piece */
 436 #ifdef TESUJIBONUS
 437           short boardu, upiece, rvupiece, rvuboard;
 438 #endif
 439           s++;
 440           if ( u == TOsquare )
 441             /* opponent has moved to TOsquare */
 442             s++;
 443           if ( (boardu = board[u]) == king ) {
 444               s += 20; INCscore -= 18;
 445               *local_flag |= check; /* move threatens opponents king */
 446           }
 447 #ifdef TESUJIBONUS
 448           upiece = unpromoted[piece];
 449           rvupiece = relative_value[upiece];
 450           rvuboard = relative_value[unpromoted[boardu]];
 451           if ( upiece == pawn && Captured[side][pawn] > 1 )
 452             {
 453               *local_flag |= tesuji; /* The joining pawn attack */
 454               s++;
 455             }
 456           if ( rvupiece <= rvuboard )
 457             {
 458               *local_flag |= tesuji; /* The striking pawn (piece) attack */
 459               if ( f > NO_SQUARES )
 460                 s += 2;
 461               else
 462                 s++;
 463               if ( upiece == pawn ) {
 464                 s++;
 465               }
 466               if ( rvupiece == rvuboard &&
 467                    upiece == pawn || upiece == bishop || upiece == knight ) {
 468                 s++; /* The opposing pawn (piece) */
 469                 if ( upiece == pawn )
 470                   s++;
 471               }
 472             }
 473 #endif
 474 #ifdef SAVE_NEXTPOS
 475           u = next_direction(ptyp,&d,t);
 476 #else
 477           u = pdir[u];
 478 #endif
 479         }
 480       };
 481   } while (u != t);
 482
 483   INCscore += s;
 484
 485   return(s);
 486 }
 487
 488
 489 #endif
 490
 491
 492
 493 /* inline */ void
 494 LinkMove (short int ply, short int f,
 495           register short int t,
 496           unsigned short local_flag,
 497           short int xside,
 498           short int score_if_impossible)
 499
 500 /*
 501  * Add a move to the tree.  Assign a bonus to order the moves as follows:
 502  * 1. Principle variation 2. Capture of last moved piece 3. Other captures
 503  * (major pieces first) 4. Killer moves 5. Tesuji drops 6. Other Moves
 504  * 7. Other drops. 8. Non-promoting moves
 505  * If the flag.tsume is set, assign a high bonus for checks.
 506  */
 507
 508 {
 509   register short s = 0;
 510   register short side, piece, mv;
 511   short flag_tsume, try_link = true;
 512   short c1, c2, ds, is_drop = f > NO_SQUARES;
 513   unsigned long as = 0;
 514
 515   flag_tsume = flag.tsume;
 516
 517   c1 = side = xside ^ 1;
 518   c2 = xside;
 519
 520   /*
 521    * Is it determined whether the move gives check ?
 522    */
 523
 524   check_determined = ((local_flag & check) != 0);
 525
 526   mv = (f << 8) | ((local_flag & promote) ? (t | 0x80) : t);
 527
 528   if ( f > NO_SQUARES ) {
 529     piece = f - NO_SQUARES;
 530     if ( piece > NO_PIECES ) piece -= NO_PIECES;
 531   } else {
 532     piece = board[f];
 533   }
 534
 535   if ( score_if_impossible < 0 ) {
 536     /* The move is flagged as illegal. */
 537     Link (side, piece,
 538         f, t, local_flag, score_if_impossible);
 539     return;
 540   }
 541
 542   INCscore = 0;
 543
 544 #ifdef HISTORY
 545 #ifdef DEBUG
 546   if ( use_history ) {
 547     unsigned short hi;
 548     short ds;
 549     s += (ds = history[hi = hindex(side,mv)]);
 550   }
 551 #else
 552   s += history[hindex(side,mv)];
 553 #endif
 554 #endif
 555
 556   /* If we're running short of tree node, go into tsume mode. */
 557
 558   if ( !(local_flag & capture) )
 559     if ( *TrP > TREE - 300 ) {
 560       /* too close to tree table limit */
 561       flag.tsume = true;
 562     }
 563
 564   /* Guess strength of move and set flags. */
 565
 566   if ( piece != king && !in_opening_stage ) {
 567     if ( distance(t,EnemyKing) <= 1 ) {
 568       /* bonus for square near enemy king */
 569       s += 15; INCscore += 2;
 570       local_flag |= kingattack;
 571     } else if ( distance(t,OwnKing) <= 1 ) {
 572       /* bonus for square near own king */
 573       s += 10; INCscore++;
 574       local_flag |= kingattack;
 575     }
 576   }
 577
 578   if ( tas /* own attack array available */ ) {
 579     /* square t defended by own piece (don't count piece to move) ? */
 580     if ( is_drop ? (as = atak[side][t]) : (as = ((atak[side][t] & CNT_MASK) > 1)) )
 581       s += (ds = in_endgame_stage ? 100 : 10);
 582   }
 583   if ( taxs /* opponents attack array available */ ) {
 584     /* square t not threatened by opponent or
 585      * defended and only threatened by opponents king ?
 586      */
 587     unsigned long axs;
 588     if ( !(axs = atak[xside][t]) ||
 589          (tas && as && (axs & control[king]) && (axs & CNT_MASK) == 1) )
 590       s += (ds = in_endgame_stage ? 200 :
 591                         (is_drop ? (InPromotionZone(side,t) ? 40 + relative_value[piece]: 10) : 20));
 592   }
 593
 594   /* target square near area of action */
 595
 596   if ( TOsquare >= 0 )
 597     s += (9-distance(TOsquare,t));
 598   if ( FROMsquare >= 0 )
 599     s += (9-distance(FROMsquare,t)) / 2;
 600
 601   /* target square near own or enemy king */
 602
 603   if ( !in_opening_stage && piece != king ) {
 604     if ( balance[c1] < 50 )
 605       s += (9-distance(EnemyKing,t)) * (50 - balance[c1]) / 20;
 606     else
 607       s += (9-distance(OwnKing,t)) * (balance[c1] - 50) / 20;
 608   }
 609
 610   if ( f > NO_SQUARES )
 611     {
 612       /* bonus for drops, in order to place drops before questionable moves */
 613       s += in_endgame_stage ? 25 : 10;
 614       if (t == FROMsquare) {
 615         /* drop to the square the opponent has just left */
 616         s += 5;
 617       };
 618       if ( piece == gold )
 619         s -= 32 / Captured[side][gold];
 620       else if ( piece == silver )
 621         s -= 16 / Captured[side][silver];
 622 #if defined DROPBONUS
 623       s += field_bonus(ply,side,piece,f,t,&local_flag);
 624       if ( s == 10 && piece != pawn )
 625       local_flag |= questionable;
 626 #endif
 627     }
 628   else
 629     {
 630       /* bonus for moves (non-drops) */
 631       int consider_last = false;
 632       if ( in_endgame_stage && Captured[side][gold] )
 633         s += 10;
 634       s += 20;
 635       if (t == FROMsquare) {
 636         /* move to the square the opponent has just left */
 637         s += in_endgame_stage ? 10 : 1;
 638       }
 639       if (color[t] != neutral)
 640         {
 641           /* Captures */
 642           if ( in_endgame_stage ) {
 643             s += relative_value[board[t]] - relative_value[piece];
 644           } else {
 645             s += (*value)[stage][board[t]] - relative_value[piece];
 646           }
 647           if (t == TOsquare)
 648             /* Capture of last moved piece */
 649             s += in_endgame_stage ? 5 : 50;
 650         }
 651       if ( local_flag & promote )
 652         {
 653           /* bonus for promotions */
 654           s++;
 655           INCscore += value[stage][promoted[piece]] - value[stage][piece];
 656         }
 657       else
 658         {
 659           /* bonus for non-promotions */
 660           if ( PromotionPossible(side,f,t,piece) )
 661 #ifdef TESUJIBONUS
 662          /* Look at non-promoting silver or knight */
 663             if ( piece == silver || piece == knight )
 664               {
 665                 local_flag |= tesuji; /* Non-promotion */
 666                 s++;
 667               }
 668             else
 669 #endif
 670               {
 671                 consider_last = true;
 672                 if ( piece == pawn || piece == bishop || piece == rook ) {
 673                   local_flag |= stupid;
 674                   INCscore -= 20;
 675                 } else {
 676                   local_flag |= questionable;
 677                   INCscore -= 10;
 678                 }
 679               }
 680         }
 681       if ( consider_last )
 682         {
 683           if ( local_flag & stupid )
 684             s = 0;
 685           else
 686             s = s % 20;
 687         }
 688       else
 689         {
 690           short blockable;
 691 #if defined FIELDBONUS
 692           s += field_bonus(ply,side,piece,f,t,&local_flag);
 693 #endif
 694         }
 695     }
 696
 697 #if defined CHECKBONUS
 698   /* determine check flag */
 699   if ( !(local_flag & check) && !check_determined )
 700     {
 701       gives_check_flag(&local_flag, side, f, t);
 702       if ( local_flag & check )
 703           s += 20;
 704     }
 705 #endif
 706
 707   /* check conditions for deep search cut (flag.tsume = true) */
 708
 709 #ifdef DEEPSEARCHCUT
 710   if ( !flag.tsume && deepsearchcut )
 711     {
 712       if ( ply > BEYOND_STUPID && (local_flag & stupid) ) {
 713           try_link = flag.force || (ply == 1 && side != computer);
 714 #ifdef HARDTIMELIMIT
 715       } else if ( ply > BEYOND_TIMEOUT && flag.timeout ) {
 716           flag.tsume = true;
 717 #endif
 718       } else if ( ply > BEYOND_KINGATTACK && !(local_flag & kingattack) ) {
 719           flag.tsume = true;
 720       } else if ( ply > BEYOND_QUESTIONABLE && (local_flag & questionable) ) {
 721           flag.tsume = true;
 722 #ifdef TESUJIBONUS
 723       } else if ( ply > BEYOND_TESUJI && !(local_flag & tesuji) ) {
 724           flag.tsume = true;
 725 #endif
 726       } else if ( ply > BEYOND_DROP && (f > NO_SQUARES) ) {
 727           flag.tsume = true;
 728       }
 729     }
 730 #endif
 731
 732   if ( try_link || GenerateAllMoves )
 733     Link (side, piece,
 734         f, t, local_flag, s - ((SCORE_LIMIT+1000)*2));
 735
 736   flag.tsume = flag_tsume;
 737 }
 738
 739
 740
 741 short
 742 DropPossible (short int piece, short int side, short int sq)
 743
 744 {
 745   short r = row(sq), possible = true;
 746
 747   if ( board[sq] != no_piece )
 748         possible = false;
 749   else if ( piece == pawn )
 750         {
 751           if ( side == black && r == 8 ) {
 752             possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
 753           } else if ( side == white && r == 0 ) {
 754             possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
 755           } else if ( PawnCnt[side][column(sq)] ) {
 756             possible = (generate_move_flags ? ILLEGAL_DOUBLED : false);
 757           }
 758           /* pawn drops are invalid, if they mate the opponent */
 759           if ( possible )
 760             {   short f, tempb, tempc;
 761                 f = pawn + NO_SQUARES;
 762                 if ( side == white ) f += NO_PIECES;
 763                 GenMakeMove (side, f, sq, &tempb, &tempc, false);
 764                 if ( IsCheckmate(side^1,-1,-1) )
 765                   possible = (generate_move_flags ? ILLEGAL_MATE : false);
 766                 GenUnmakeMove (side, f, sq, tempb, tempc, false);
 767             }
 768         }
 769   else if ( piece == lance )
 770         {
 771           if ( side == black && r == 8 )
 772             possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
 773           else if ( side == white && r == 0 )
 774             possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
 775         }
 776   else if ( piece == knight )
 777         {
 778           if ( side == black && r >= 7 )
 779             possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
 780           else if ( side == white && r <= 1 )
 781             possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
 782         }
 783
 784   return possible;
 785
 786 }
 787
 788
 789 static
 790 void
 791 SortMoves(short int ply)
 792 {
 793   short int p;
 794   for (p = TrPnt[ply]; p < TrPnt[ply+1]; p++)
 795     pick(p,TrPnt[ply+1]-1);
 796 }
 797
 798
 799 #ifdef DONTUSE_HEURISTIC
 800
 801 static void
 802 DontUseMoves(short int ply, short int n)
 803 {
 804   register struct leaf far *p;
 805   short int i,k;
 806 #ifdef DEBUG
 807   short j = 0;
 808 #endif
 809   /* k = number of check moves + number of captures */
 810   for (i = TrPnt[ply], k=0; i < TrPnt[ply+1]; i++) {
 811      p = &Tree[i];
 812      if ( (p->flags & check) || (p->flags & capture) )
 813         if (++k >= n) return;
 814   }
 815   /* use n moves */
 816   for (i = TrPnt[ply]; i < TrPnt[ply+1]; i++) {
 817      p = &Tree[i];
 818      if ( !((p->flags & check) || (p->flags & capture)) ) {
 819        if ( k < n )
 820          k++;
 821        else {
 822          p->score = DONTUSE;
 823 #ifdef DEBUG
 824          j++;
 825 #endif
 826        }
 827      }
 828   }
 829 #ifdef notdef
 830   if ( j )
 831     printf("skipping %d moves at ply %d with allowed %d moves\n",j,ply,n);
 832 #endif
 833 }
 834
 835
 836 #endif
 837
 838
 839 inline
 840 void
 841 GenMoves (register short int ply, register short int sq, short int side,
 842           short int xside)
 843
 844 /*
 845  * Generate moves for a piece. The moves are taken from the precalulated
 846  * array nextpos/nextdir. If the board is free, next move is choosen from
 847  * nextpos else from nextdir.
 848  */
 849
 850 {
 851   register short u, piece, col;
 852   short ptyp, possible;
 853 #ifdef SAVE_NEXTPOS
 854   short d;
 855 #else
 856   register unsigned char *ppos, *pdir;
 857 #endif
 858
 859   piece = board[sq];
 860   ptyp = ptype[side][piece];
 861
 862 #ifdef SAVE_NEXTPOS
 863   u = first_direction(ptyp,&d,sq);
 864 #else
 865   ppos = (*nextpos[ptyp])[sq];
 866   pdir = (*nextdir[ptyp])[sq];
 867   u = ppos[sq];
 868 #endif
 869
 870   do
 871     { unsigned short int local_flag;
 872       short  c;
 873       if ( (c = color[u]) == xside )
 874         local_flag = capture;
 875       else
 876         local_flag = 0;
 877       if ( c != side && board[u] != king ) {
 878         if ( PromotionPossible(color[sq],sq,u,piece) ) {
 879           LinkMove (ply, sq, u, local_flag | promote, xside, true);
 880           if ( possible = NonPromotionPossible(color[sq],sq,u,piece) )
 881             LinkMove (ply, sq, u, local_flag, xside, possible);
 882         } else {
 883           LinkMove (ply, sq, u, local_flag, xside, true);
 884         }
 885       }
 886       if (c == neutral)
 887 #ifdef SAVE_NEXTPOS
 888         u = next_position(ptyp,&d,sq,u);
 889       else
 890         u = next_direction(ptyp,&d,sq);
 891 #else
 892         u = ppos[u];
 893       else
 894         u = pdir[u];
 895 #endif
 896   } while (u != sq);
 897 }
 898
 899
 900
 901 static void
 902 DropToSquare (short side, short xside, short ply, short u)
 903
 904 /*
 905  * Drop each piece in hand of "side" to square "u" (if allowed).
 906  */
 907
 908 {
 909   short i, possible;
 910
 911   for (i = pawn; i < king; i++)
 912     if ( Captured[side][i] )
 913       if ( possible = DropPossible(i,side,u) )
 914         { short f;
 915           f = NO_SQUARES + i;
 916           if ( side == white ) f += NO_PIECES;
 917           LinkMove (ply, f, u, (dropmask | i), xside, possible);
 918         }
 919 }
 920
 921
 922 static void
 923 LinkPreventCheckDrops (short side, short xside, short ply)
 924
 925 /*
 926  * Add drops of side that prevent own king from being in check
 927  * from xside's sweeping pieces.
 928  */
 929
 930 {
 931 #ifdef SAVE_NEXTPOS
 932   short d, dd;
 933 #else
 934   register unsigned char *ppos, *pdir;
 935 #endif
 936   register short piece, u, xu, square, ptyp;
 937   short i, n, drop_square[9];
 938
 939   if ( board[square = PieceList[side][0]] != king )
 940     return;
 941
 942   for (piece = lance; piece <= rook; piece++ )
 943   if ( piece == lance || piece == bishop || piece == rook ) {
 944     /* check for threat of xside piece */
 945     ptyp = ptype[side][piece];
 946     n = 0;
 947 #ifdef SAVE_NEXTPOS
 948     u = first_direction(ptyp,&d,square);
 949 #else
 950     ppos = (*nextpos[ptyp])[square];
 951     pdir = (*nextdir[ptyp])[square];
 952     u = ppos[square];
 953 #endif
 954
 955     do
 956       {
 957         if (color[u] == neutral)
 958           {
 959 #ifdef SAVE_NEXTPOS
 960             dd = d;
 961             xu = next_position(ptyp,&d,square,u);
 962             if ( xu == next_direction(ptyp,&dd,square) )
 963                 n = 0;  /* oops new direction */
 964             else {
 965 #ifdef DEBUG
 966                 assert(n<9);
 967 #endif
 968                 drop_square[n++] = u;
 969             }
 970 #else
 971             if ((xu = ppos[u]) == pdir[u])
 972                 n = 0;  /* oops new direction */
 973             else {
 974 #ifdef DEBUG
 975                 assert(n<9);
 976 #endif
 977                 drop_square[n++] = u;
 978             }
 979 #endif
 980             u = xu;
 981           }
 982         else
 983           {
 984             if (color[u] == xside && (unpromoted[board[u]] == piece))
 985               {
 986                 /* king is threatened by opponents piece */
 987                 while ( n > 0 ) {
 988                   DropToSquare(side,xside,ply,drop_square[--n]);
 989                 }
 990               }
 991             else
 992               n = 0;
 993 #ifdef SAVE_NEXTPOS
 994             u = next_direction(ptyp,&d,square);
 995 #else
 996             u = pdir[u];
 997 #endif
 998           }
 999     } while (u != square);
1000
1001   }
1002
1003 }
1004
1005
1006 static void
1007 LinkCheckDrops (short side, short xside, short ply)
1008
1009 /*
1010  * Add drops that check enemy king.
1011  */
1012
1013 {
1014 #ifdef SAVE_NEXTPOS
1015   short d;
1016 #else
1017   register unsigned char *ppos, *pdir;
1018 #endif
1019   register short u, ptyp;
1020   short square, piece;
1021
1022   if ( board[square = PieceList[xside][0]] != king )
1023     return;
1024
1025   for (piece = pawn; piece < king; piece++)
1026     if ( Captured[side][piece] ) {
1027       /*
1028        * "side" has "piece" in hand. Try to make a piece move from
1029        * opponents king square and drop this piece to each
1030        * reachable empty square. This definitely gives check!
1031        * For a pawn drop it must not double pawns and
1032        * it must not be checkmate!
1033        */
1034       ptyp = ptype[xside][piece];
1035 #ifdef SAVE_NEXTPOS
1036       u = first_direction(ptyp,&d,square);
1037 #else
1038       ppos = (*nextpos[ptyp])[square];
1039       pdir = (*nextdir[ptyp])[square];
1040       u = ppos[square];
1041 #endif
1042       do
1043         {
1044           if (color[u] == neutral)
1045             {
1046               if ( piece != pawn || DropPossible(pawn,side,u) ) {
1047                 short f;
1048                 f = NO_SQUARES + piece;
1049                 if ( side == white ) f += NO_PIECES;
1050                 LinkMove (ply, f, u, (dropmask | piece | check), xside, true);
1051               }
1052 #ifdef SAVE_NEXTPOS
1053               u = next_position(ptyp,&d,square,u);
1054 #else
1055               u = ppos[u];
1056 #endif
1057             }
1058           else
1059             {
1060 #ifdef SAVE_NEXTPOS
1061               u = next_direction(ptyp,&d,square);
1062 #else
1063               u = pdir[u];
1064 #endif
1065             }
1066       } while (u != square);
1067     }
1068
1069 }
1070
1071
1072 void
1073 MoveList (short int side, register short int ply,
1074           short int in_check, short int blockable)
1075
1076 /*
1077  * Fill the array Tree[] with all available moves for side to play. Array
1078  * TrPnt[ply] contains the index into Tree[] of the first move at a ply.
1079  * in_check = 0 side is not in check
1080  * in_check > 1 side is in check
1081  * in_check < 0 don't know
1082  * in_check -2 indicates move generation for book moves
1083  */
1084
1085 {
1086   register short i, xside, f, u;
1087   struct leaf far *firstnode;
1088   short flag_tsume, num;
1089
1090 #ifdef HISTORY
1091   unsigned short hiHt=0, hi0=0, hi1=0, hi2=0, hi3=0, hi4=0;
1092 #endif
1093
1094   flag_tsume = flag.tsume;
1095
1096   xside = side ^ 1;
1097
1098   sqking  = PieceList[side][0];
1099   sqxking = PieceList[xside][0];
1100
1101   if ( in_check >= 0 )
1102     InCheck = in_check;
1103   else
1104     InCheck = (board[sqking] == king) ? SqAtakd(sqking,xside, &blockable) : false;
1105
1106   GenerateAllMoves = (in_check == -2) || generate_move_flags;
1107
1108 #ifdef DEBUG_EVAL
1109   if ( debug_eval )
1110     fprintf ( debug_eval_file, "%s king is %sin check\n",
1111         ColorStr[side],(InCheck ? "" : "not ") );
1112 #endif
1113
1114   if ( InCheck /* && (ply > 1 || side == computer) */ )
1115     {
1116         /* Own king in check */
1117         flag.tsume = true;
1118     }
1119
1120   TrP = &TrPnt[ply + 1];
1121   *TrP = TrPnt[ply];
1122
1123   firstnode = node = &Tree[*TrP];
1124
1125   if (!PV)
1126     Swag0 = killr0[ply];
1127    else Swag0 = PV;
1128   Swag1 = killr1[ply];
1129   Swag2 = killr2[ply];
1130   Swag3 = killr3[ply];
1131   if (ply > 2)
1132     Swag4 = killr1[ply - 2]; else Swag4 = 0;
1133
1134 #ifdef DEBUG_EVAL
1135   if ( debug_eval && (ply == 1 || debug_moves) )
1136   {
1137     char bufHt[8], buf0[8], buf1[8], buf2[8], buf3[8], buf4[8];
1138     movealgbr(SwagHt,bufHt);
1139     movealgbr(Swag0,buf0);
1140     movealgbr(Swag1,buf1);
1141     movealgbr(Swag2,buf2);
1142     movealgbr(Swag3,buf3);
1143     movealgbr(Swag4,buf4);
1144     fprintf(debug_eval_file, "SwagHt=%x %s 0=%x %s 1=%x %s 2=%x %s 3=%x %s 4=%x %s\n",
1145       SwagHt, bufHt, Swag0, buf0, Swag1, buf1, Swag2, buf2, Swag3, buf3, Swag4, buf4);
1146   }
1147 #endif
1148
1149 #ifdef HISTORY
1150   if ( use_history ) {
1151     history[hiHt = hindex(side,SwagHt)] += 5000;
1152     history[hi0  = hindex(side,Swag0)] += 2000;
1153     history[hi1  = hindex(side,Swag1)] += 60;
1154     history[hi2  = hindex(side,Swag2)] += 50;
1155     history[hi3  = hindex(side,Swag3)] += 40;
1156     history[hi4  = hindex(side,Swag4)] += 30;
1157   }
1158 #endif
1159
1160   if ( tas = MatchSignature(threats_signature[side]) ) {
1161 #if defined notdef && defined DEBUG_EVAL && defined NONDSP
1162     printf("threats available at ply %d for side=%s\n",ply,ColorStr[side]);
1163 #endif
1164   }
1165   if ( taxs = MatchSignature(threats_signature[xside]) ) {
1166 #if defined notdef && defined DEBUG_EVAL && defined NONDSP
1167     printf("threats available at ply %d for xside=%s\n",ply,ColorStr[xside]);
1168 #endif
1169   }
1170   if ( ssa = MatchSignature(squares_signature) ) {
1171 #if defined notdef && defined DEBUG_EVAL && defined NONDSP
1172     printf("square statistics available at ply %d\n",ply);
1173 #endif
1174   }
1175
1176   for (i = PieceCnt[side]; i >= 0; i--)
1177     GenMoves (ply, PieceList[side][i], side, xside);
1178
1179   if ( !InCheck || blockable )
1180     if ( flag.tsume )
1181       { /* special drop routine for tsume problems */
1182         if ( InCheck ) {
1183           LinkPreventCheckDrops (side, xside, ply);
1184         } else {
1185           LinkCheckDrops (side, xside, ply);
1186         }
1187
1188       }
1189     else
1190       {
1191         for ( u = 0; u < NO_SQUARES; u++ )
1192           DropToSquare(side,xside,ply,u);
1193       }
1194
1195 #ifdef HISTORY
1196   if ( use_history ) {
1197     history[hiHt] -= 5000;
1198     history[hi0] -= 2000;
1199     history[hi1] -= 60;
1200     history[hi2] -= 50;
1201     history[hi3] -= 40;
1202     history[hi4] -= 30;
1203   }
1204 #endif
1205
1206   SwagHt = 0;                   /* SwagHt is only used once */
1207
1208   if ( flag.tsume && node == firstnode )
1209     (*TrP)++;
1210
1211   GenCnt += (num = (TrPnt[ply+1] - TrPnt[ply]));
1212
1213 #ifdef DEBUG_EVAL
1214   SortMoves(ply);
1215 #endif
1216
1217 #ifdef DONTUSE_HEURISTIC
1218    /* remove some nodes in case of wide spread in depth */
1219    if ( !flag.tsume && (i = MaxNum[ply]) > 0 && num > i) {
1220      SortMoves(ply);
1221      DontUseMoves(ply,i);
1222    }
1223 #endif
1224
1225 #ifdef notdef
1226   printf("%d moves at ply %d\n",num,ply);
1227 #endif
1228
1229   flag.tsume = flag_tsume;
1230
1231 }
1232
1233 void
1234 CaptureList (register short int side, short int ply,
1235              short int in_check, short int blockable)
1236
1237 /*
1238  * Fill the array Tree[] with all available captures for side to play.
1239  * If there is a non-promote option, discard the non-promoting move.
1240  * Array TrPnt[ply] contains the index into Tree[] of the first move
1241  * at a ply.
1242  * If flag.tsume is set, only add captures (but also the non-promoting)
1243  * that threaten the opponents king.
1244  * in_check = 0 side is not in check
1245  * in_check > 1 side is in check
1246  * in_check < 0 don't know
1247  */
1248
1249 {
1250   register short u, sq, xside;
1251 #ifdef SAVE_NEXTPOS
1252   short d;
1253 #else
1254   register unsigned char *ppos, *pdir;
1255 #endif
1256   short i, piece, flag_tsume;
1257   small_short *PL;
1258
1259   xside = side ^ 1;
1260
1261   TrP = &TrPnt[ply + 1];
1262   *TrP = TrPnt[ply];
1263   node = &Tree[*TrP];
1264
1265   flag_tsume = flag.tsume;
1266
1267   sqking = PieceList[side][0];
1268   sqxking = PieceList[xside][0];
1269
1270   if ( in_check >= 0 )
1271     InCheck = in_check;
1272   else
1273     InCheck = (board[sqking] == king) ? SqAtakd(sqking,xside,&blockable) : false;
1274
1275   GenerateAllMoves = (in_check == -2);
1276
1277 #ifdef DEBUG_EVAL
1278   if (debug_eval )
1279     fprintf ( debug_eval_file, "%s king is %sin check\n",
1280         ColorStr[side],(InCheck ? "" : "not ") );
1281 #endif
1282
1283   if ( InCheck && (ply > 1 || side == computer) )
1284     {
1285       /* Own king is in check */
1286       flag.tsume = true;
1287     }
1288
1289   check_determined = false;
1290
1291   PL = PieceList[side];
1292
1293   for (i = 0; i <= PieceCnt[side]; i++)
1294     { short ptyp;
1295       sq = PL[i];
1296       piece = board[sq];
1297       ptyp = ptype[side][piece];
1298 #ifdef SAVE_NEXTPOS
1299       u = first_direction(ptyp,&d,sq);
1300 #else
1301       ppos = (*nextpos[ptyp])[sq];
1302       pdir = (*nextdir[ptyp])[sq];
1303       u = ppos[sq];
1304 #endif
1305       do
1306         {
1307           if (color[u] == neutral)
1308             {
1309 #ifdef SAVE_NEXTPOS
1310               u = next_position(ptyp,&d,sq,u);
1311 #else
1312               u = ppos[u];
1313 #endif
1314             }
1315           else
1316             {
1317               if ( color[u] == xside && board[u] != king )
1318                 {
1319                   short PP;
1320                   if ( PP = PromotionPossible(color[sq],sq,u,piece) ) {
1321                     Link (side, piece,
1322                           sq, u, capture | promote,
1323                           (*value)[stage][board[u]]
1324 #if !defined SAVE_SVALUE
1325                             + svalue[board[u]]
1326 #endif
1327                             - relative_value[piece]);
1328                   }
1329                   if ( !PP || flag.tsume ) {
1330                     Link (side, piece,
1331                           sq, u, capture,
1332                           (*value)[stage][board[u]]
1333 #if !defined SAVE_SVALUE
1334                             + svalue[board[u]]
1335 #endif
1336                             - relative_value[piece]);
1337                   }
1338                 }
1339 #ifdef SAVE_NEXTPOS
1340               u = next_direction(ptyp,&d,sq);
1341 #else
1342               u = pdir[u];
1343 #endif
1344             }
1345         } while (u != sq);
1346     }
1347
1348   flag.tsume = flag_tsume;
1349
1350   SwagHt = 0;                   /* SwagHt is only used once */
1351
1352 #ifdef DEBUG_EVAL
1353   SortMoves(ply);
1354 #endif
1355
1356 }
1357
1358
1359
1360 short
1361 IsCheckmate (short int side, short int in_check, short int blockable)
1362
1363 /*
1364  * If the king is in check, try to find a move that prevents check.
1365  * If such a move is found, return false, otherwise return true.
1366  * in_check = 0: side is not in check
1367  * in_check > 1: side is in check
1368  * in_check < 0: don't know
1369  * blockable > 0 && check: check can possibly prevented by a drop
1370  * blockable = 0 && check: check can definitely not prevented by a drop
1371  * blockable < 0 && check: nothing known about type of check
1372  */
1373
1374 {
1375   register short u, sq, xside;
1376 #ifdef SAVE_NEXTPOS
1377   short d;
1378 #else
1379   register unsigned char *ppos, *pdir;
1380 #endif
1381   short i, piece, flag_tsume;
1382   small_short *PL;
1383   struct leaf far *firstnode;
1384   short tempb, tempc, ksq, threat, dummy, sqking;
1385   short InCheck;
1386
1387   xside = side ^ 1;
1388
1389   sqking = PieceList[side][0];
1390
1391   /*
1392    * Checkmate is possible only if king is in check.
1393    */
1394
1395   if ( in_check >= 0 )
1396       InCheck = in_check;
1397   else if ( board[sqking] == king )
1398       InCheck = SqAtakd(sqking,xside,&blockable);
1399   else
1400       InCheck = false;
1401
1402   if ( !InCheck )
1403     return (false);
1404
1405   /*
1406    * Try to find a move, that prevents check.
1407    */
1408
1409   PL = PieceList[side];
1410
1411   for (i = 0; i <= PieceCnt[side]; i++)
1412     { short ptyp;
1413       sq = PL[i];
1414       piece = board[sq];
1415       ptyp = ptype[side][piece];
1416 #ifdef SAVE_NEXTPOS
1417       u = first_direction(ptyp,&d,sq);
1418 #else
1419       ppos = (*nextpos[ptyp])[sq];
1420       pdir = (*nextdir[ptyp])[sq];
1421       u = ppos[sq];
1422 #endif
1423       do
1424         {
1425           if (color[u] == neutral || color[u] == xside)
1426             {
1427               GenMakeMove (side, sq, u, &tempb, &tempc, false);
1428               ksq = (sq == sqking) ? u : sqking;
1429               threat = SqAtakd(ksq,xside,&dummy);
1430               GenUnmakeMove (side, sq, u, tempb, tempc, false);
1431               if ( !threat )
1432                 return (false);
1433             }
1434 #ifdef SAVE_NEXTPOS
1435             u = (color[u] == neutral) ? next_position(ptyp,&d,sq,u)
1436                                       : next_direction(ptyp,&d,sq);
1437 #else
1438             u = (color[u] == neutral) ? ppos[u] : pdir[u];
1439 #endif
1440         } while (u != sq);
1441     }
1442
1443   /*
1444    * Couldn't find a move that prevents check.
1445    * Try to find a drop, that prevents check.
1446    */
1447
1448   if ( blockable != 0 )
1449     {
1450       for (piece = king-1; piece >= pawn; piece--)
1451         if ( Captured[side][piece] )
1452           {
1453             for (u = 0; u < NO_SQUARES; u++)
1454               if ( DropPossible(piece,side,u) )
1455                 { short f;
1456                   f = NO_SQUARES + piece;
1457                   if ( side == white ) f += NO_PIECES;
1458                   GenMakeMove (side, f, u, &tempb, &tempc, false);
1459                   threat = SqAtakd(sqking,xside,&dummy);
1460                   GenUnmakeMove (side, f, u, tempb, tempc, false);
1461                   if ( !threat )
1462                     return (false);
1463                 }
1464             /*
1465              * If the piece could be dropped at any square, it is
1466              * impossible for any other piece drop to prevent check.
1467              * Drops are restricted for pawns, lances, and knights.
1468              */
1469             if ( piece > knight )
1470                 break;
1471           }
1472      }
1473
1474    return (true);
1475
1476 }
1477
1478