gnushogi/genmove.c

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