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