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