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