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