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