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