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