gnushogi/genmove.c

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