4 * ----------------------------------------------------------------------
6 * Copyright (c) 2012 Free Software Foundation
8 * GNU SHOGI is based on GNU CHESS
10 * This file is part of GNU SHOGI.
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.
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
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 * ----------------------------------------------------------------------
31 /* #define DONTUSE_HEURISTIC */
35 static struct leaf *node;
36 static short sqking, sqxking;
37 static short InCheck = false, GenerateAllMoves = false;
38 static short check_determined = false;
40 short deepsearchcut = true;
41 short tas = false, taxs = false, ssa = false;
43 short generate_move_flags = false;
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.
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
64 #ifdef DONTUSE_HEURISTIC
65 static short MaxNum[MAXDEPTH] =
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,
75 extern int CheckHashKey();
76 extern char mvstr[4][6];
81 * Update Arrays board[] and color[] to reflect the new board
82 * position obtained after making the move pointed to by node.
86 GenMakeMove(short side,
89 short *tempb, /* piece at to square */
90 short *tempc, /* color of to square */
93 short piece, upiece, n;
99 piece = f - NO_SQUARES;
101 if (piece > NO_PIECES)
106 n = (Captured[side][piece])--;
107 UpdateDropHashbd(side, piece, n);
108 UpdateHashbd(side, piece, -1, t);
109 UpdatePieceList(side, t, ADD_PIECE);
116 if (*tempb != no_piece)
118 n = ++Captured[side][upiece = unpromoted[*tempb]];
119 UpdateDropHashbd(side, upiece, n);
120 UpdateHashbd(*tempc, *tempb, -1, t);
121 UpdatePieceList(*tempc, t, REMOVE_PIECE);
125 Pindex[t] = Pindex[f];
126 PieceList[side][Pindex[t]] = t;
133 UpdateHashbd(side, piece, f, -1);
134 board[t] = promoted[piece];
135 UpdateHashbd(side, board[t], -1, t);
140 UpdateHashbd(side, piece, f, t);
148 printf("error in GenMakeMove: %s\n", mvstr[0]);
161 GenUnmakeMove(short side,
168 short piece, upiece, n;
174 piece = f - NO_SQUARES;
176 if (piece > NO_PIECES)
181 n = ++Captured[side][piece];
182 UpdateDropHashbd(side, piece, n);
183 UpdateHashbd(side, piece, -1, t);
184 UpdatePieceList(side, t, REMOVE_PIECE);
191 Pindex[f] = Pindex[t];
192 PieceList[side][Pindex[f]] = f;
194 if (tempb != no_piece)
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);
207 UpdateHashbd(side, piece, -1, t);
208 board[f] = unpromoted[piece];
209 UpdateHashbd(side, board[f], f, -1);
214 UpdateHashbd(side, piece, f, t);
222 printf("error in GenUnmakeMove: %s\n", mvstr[0]);
231 gives_check_flag(unsigned short *flags, short side, short f, short t)
233 short tempb, tempc, blockable, promote_piece;
234 promote_piece = (*flags & promote) != 0;
235 GenMakeMove(side, f, t, &tempb, &tempc, promote_piece);
237 if (SqAttacked(sqxking, side, &blockable))
240 GenUnmakeMove(side, f, t, tempb, tempc, promote_piece);
245 Link(short side, short piece,
246 short from, short to, unsigned short local_flag, short s)
250 ShowMessage("TREE overflow\n");
255 node->t = (local_flag & promote) ? (to | 0x80) : to;
257 node->flags = local_flag;
259 node->INCscore = INCscore;
261 if (GenerateAllMoves)
263 /* FIXME: gimme a break! */
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);
280 /* FIXME! Gimme a break! */
286 /* only moves that give check */
287 if (!(node->flags & check) && !check_determined)
289 /* determine check flag */
290 gives_check_flag(&node->flags, side, node->f, node->t);
293 if (node->flags & check)
295 /* FIXME! Gimme a break! */
301 /* FIXME! Gimme a break! */
309 PromotionPossible(short color, short f, short t, short p)
313 if ((f < 54) && (t < 54))
318 if ((f > 26) && (t > 26))
322 /* FIXME: this can be simplified... */
339 NonPromotionPossible(short color, short f,
349 : (generate_move_flags ? ILLEGAL_TRAPPED : false));
355 : (generate_move_flags ? ILLEGAL_TRAPPED : false));
363 : (generate_move_flags ? ILLEGAL_TRAPPED : false));
369 : (generate_move_flags ? ILLEGAL_TRAPPED : false));
377 : (generate_move_flags ? ILLEGAL_TRAPPED : false));
383 : (generate_move_flags ? ILLEGAL_TRAPPED : false));
391 #if defined FIELDBONUS || defined DROPBONUS
393 /* bonus for possible next moves */
396 field_bonus(short ply, short side, short piece,
397 short f, short t, unsigned short *local_flag)
400 unsigned char *ppos, *pdir;
410 check_determined = true;
412 ptyp = ptype[side][piece];
415 u = first_direction(ptyp, &d, t);
417 ppos = (*nextpos[ptyp])[t];
418 pdir = (*nextdir[ptyp])[t];
424 short coloru = color[u];
426 if (piece != king && GameCnt > 40)
428 if (distance(u, EnemyKing) <= 1)
430 /* can reach square near own king */
432 *local_flag |= kingattack;
434 else if (distance(u, OwnKing) <= 1)
436 /* can reach square near enemy king */
438 *local_flag |= kingattack;
444 /* impossible next move */
446 u = next_direction(ptyp, &d, t);
453 /* possible next move */
454 if (PromotionPossible(side, t, u, piece))
456 /* possible promotion in next move */
461 if (!InPromotionZone(side, t))
463 *local_flag |= tesuji; /* The dangling pawn */
474 if (coloru == neutral)
476 /* next move to an empty square */
479 /* opponent has just left this square */
484 u = next_position(ptyp, &d, t, u);
491 /* attack opponents piece */
493 short boardu, upiece, rvupiece, rvuboard;
497 if (u == TOsquare) /* opponent has moved to TOsquare */
500 if ((boardu = board[u]) == king)
502 s += 20; INCscore -= 18;
503 *local_flag |= check; /* move threatens
508 upiece = unpromoted[piece];
509 rvupiece = relative_value[upiece];
510 rvuboard = relative_value[unpromoted[boardu]];
512 if ((upiece == pawn) && (Captured[side][pawn] > 1))
514 *local_flag |= tesuji; /* The joining pawn attack */
518 if (rvupiece <= rvuboard)
520 *local_flag |= tesuji; /* The striking pawn
531 /* CHECKME: is this right? */
532 if (((rvupiece == rvuboard) && (upiece == pawn))
533 || (upiece == bishop) || (upiece == knight))
535 s++; /* The opposing pawn (piece) */
544 u = next_direction(ptyp, &d, t);
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.
572 LinkMove(short ply, short f,
574 unsigned short local_flag,
576 short score_if_impossible)
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;
584 flag_tsume = flag.tsume;
586 c1 = side = xside ^ 1;
590 * Is it determined whether the move gives check ?
593 check_determined = ((local_flag & check) != 0);
595 mv = (f << 8) | ((local_flag & promote) ? (t | 0x80) : t);
599 piece = f - NO_SQUARES;
601 if (piece > NO_PIECES)
609 if (score_if_impossible < 0)
611 /* The move is flagged as illegal. */
613 f, t, local_flag, score_if_impossible);
621 s += history[hindex(side, mv)];
624 /* If we're running short of tree nodes, go into tsume mode. */
626 if (!(local_flag & capture))
628 if (*TrP > (TREE - 300))
630 /* too close to tree table limit */
635 /* Guess strength of move and set flags. */
637 if ((piece != king) && (!in_opening_stage))
639 if (distance(t, EnemyKing) <= 1)
641 /* bonus for square near enemy king */
644 local_flag |= kingattack;
646 else if (distance(t, OwnKing) <= 1)
648 /* bonus for square near own king */
651 local_flag |= kingattack;
655 if (tas) /* own attack array available */
657 /* square t defended by own piece (don't count piece to move) ? */
659 ? (as = attack[side][t])
660 : (as = ((attack[side][t] & CNT_MASK) > 1)))
661 s += (ds = in_endgame_stage ? 100 : 10);
664 if (taxs) /* opponents attack array available */
666 /* square t not threatened by opponent or
667 * defended and only threatened by opponents king ?
671 if (!(axs = attack[xside][t])
672 || (tas && as && (axs & control[king]) && (axs & CNT_MASK) == 1))
674 /* FIXME: this is a mess; clean up. */
675 s += (ds = in_endgame_stage
678 ? (InPromotionZone(side, t)
679 ? 40 + relative_value[piece]
685 /* target square near area of action */
688 s += (9 - distance(TOsquare, t));
691 s += (9 - distance(FROMsquare, t)) / 2;
693 /* target square near own or enemy king */
695 if (!in_opening_stage && piece != king)
697 if (balance[c1] < 50)
698 s += (9 - distance(EnemyKing, t)) * (50 - balance[c1]) / 20;
700 s += (9 - distance(OwnKing, t)) * (balance[c1] - 50) / 20;
705 /* bonus for drops, in order to place
706 * drops before questionable moves */
707 s += in_endgame_stage ? 25 : 10;
711 /* drop to the square the opponent has just left */
716 s -= 32 / Captured[side][gold];
717 else if (piece == silver)
718 s -= 16 / Captured[side][silver];
720 #if defined DROPBONUS
721 s += field_bonus(ply, side, piece, f, t, &local_flag);
723 if (s == 10 && piece != pawn)
724 local_flag |= questionable;
729 /* bonus for moves (non-drops) */
730 int consider_last = false;
732 if (in_endgame_stage && Captured[side][gold])
739 /* move to the square the opponent has just left */
740 s += in_endgame_stage ? 10 : 1;
743 if (color[t] != neutral)
746 if (in_endgame_stage)
748 s += relative_value[board[t]] - relative_value[piece];
752 s += (*value)[stage][board[t]] - relative_value[piece];
755 if (t == TOsquare) /* Capture of last moved piece */
756 s += in_endgame_stage ? 5 : 50;
759 if (local_flag & promote)
761 /* bonus for promotions */
763 INCscore += value[stage][promoted[piece]] - value[stage][piece];
767 /* bonus for non-promotions */
768 if (PromotionPossible(side, f, t, piece))
771 /* Look at non-promoting silver or knight */
772 if (piece == silver || piece == knight)
774 local_flag |= tesuji; /* Non-promotion */
780 consider_last = true;
782 if (piece == pawn || piece == bishop || piece == rook)
784 local_flag |= stupid;
789 local_flag |= questionable;
798 if (local_flag & stupid)
805 #if defined FIELDBONUS
806 s += field_bonus(ply, side, piece, f, t, &local_flag);
811 #if defined CHECKBONUS
812 /* determine check flag */
813 if (!(local_flag & check) && !check_determined)
815 gives_check_flag(&local_flag, side, f, t);
817 if (local_flag & check)
822 /* check conditions for deep search cut (flag.tsume = true) */
825 if (!flag.tsume && deepsearchcut)
827 if ((ply > BEYOND_STUPID) && (local_flag & stupid))
829 try_link = flag.force || ((ply == 1) && (side != computer));
831 else if (hard_time_limit && (ply > BEYOND_TIMEOUT) && flag.timeout)
835 else if ((ply > BEYOND_KINGATTACK) && !(local_flag & kingattack))
839 else if ((ply > BEYOND_QUESTIONABLE) && (local_flag & questionable))
844 else if ((ply > BEYOND_TESUJI) && !(local_flag & tesuji))
849 else if ((ply > BEYOND_DROP) && (f > NO_SQUARES))
856 if (try_link || GenerateAllMoves)
858 Link(side, piece, f, t, local_flag,
859 s - ((SCORE_LIMIT + 1000) * 2));
862 flag.tsume = flag_tsume;
868 DropPossible(short piece, short side, short sq)
870 short r = row(sq), possible = true;
872 if (board[sq] != no_piece)
876 else if (piece == pawn)
878 if ((side == black) && (r == 8))
880 possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
882 else if ((side == white) && (r == 0))
884 possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
886 else if (PawnCnt[side][column(sq)])
888 possible = (generate_move_flags ? ILLEGAL_DOUBLED : false);
891 /* Pawn drops are invalid if they mate the opponent. */
894 short f, tempb, tempc;
895 f = pawn + NO_SQUARES;
900 GenMakeMove(side, f, sq, &tempb, &tempc, false);
902 if (IsCheckmate(side^1, -1, -1))
903 possible = (generate_move_flags ? ILLEGAL_MATE : false);
905 GenUnmakeMove(side, f, sq, tempb, tempc, false);
908 else if (piece == lance)
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);
915 else if (piece == knight)
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);
927 #if defined DONTUSE_HEURISTIC
933 for (p = TrPnt[ply]; p < TrPnt[ply+1]; p++)
934 pick(p, TrPnt[ply+1] - 1);
936 #endif /* DONTUSE_HEURISTIC */
939 #ifdef DONTUSE_HEURISTIC
942 DontUseMoves(short ply, short n)
947 /* k = number of check moves + number of captures */
948 for (i = TrPnt[ply], k = 0; i < TrPnt[ply+1]; i++)
952 if ((p->flags & check) || (p->flags & capture))
960 for (i = TrPnt[ply]; i < TrPnt[ply+1]; i++)
964 if (!((p->flags & check) || (p->flags & capture)))
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.
987 GenMoves(short ply, short sq, short side,
991 short ptyp, possible;
995 unsigned char *ppos, *pdir;
999 ptyp = ptype[side][piece];
1002 u = first_direction(ptyp, &d, sq);
1004 ppos = (*nextpos[ptyp])[sq];
1005 pdir = (*nextdir[ptyp])[sq];
1011 unsigned short local_flag;
1014 if ((c = color[u]) == xside)
1015 local_flag = capture;
1019 if (c != side && board[u] != king)
1021 if (PromotionPossible(color[sq], sq, u, piece))
1023 LinkMove(ply, sq, u, local_flag | promote, xside, true);
1026 = NonPromotionPossible(color[sq], sq, u, piece)))
1028 LinkMove(ply, sq, u, local_flag, xside, possible);
1033 LinkMove(ply, sq, u, local_flag, xside, true);
1040 u = next_position(ptyp, &d, sq, u);
1044 u = next_direction(ptyp, &d, sq);
1063 * Drop each piece in hand of "side" to square "u" (if allowed).
1067 DropToSquare(short side, short xside, short ply, short u)
1071 for (i = pawn; i < king; i++)
1073 if (Captured[side][i])
1075 if ((possible = DropPossible(i, side, u)))
1083 LinkMove(ply, f, u, (dropmask | i), xside, possible);
1092 * Add drops of side that prevent own king from being in check
1093 * from xside's sweeping pieces.
1097 LinkPreventCheckDrops(short side, short xside, short ply)
1102 unsigned char *ppos, *pdir;
1104 short piece, u, xu, square, ptyp;
1105 short n, drop_square[9];
1107 if (board[square = PieceList[side][0]] != king)
1110 for (piece = lance; piece <= rook; piece++)
1112 if (piece == lance || piece == bishop || piece == rook)
1114 /* check for threat of xside piece */
1115 ptyp = ptype[side][piece];
1118 u = first_direction(ptyp, &d, square);
1120 ppos = (*nextpos[ptyp])[square];
1121 pdir = (*nextdir[ptyp])[square];
1127 if (color[u] == neutral)
1131 xu = next_position(ptyp, &d, square, u);
1133 if (xu == next_direction(ptyp, &dd, square))
1135 n = 0; /* oops new direction */
1139 drop_square[n++] = u;
1143 if ((xu = ppos[u]) == pdir[u])
1145 n = 0; /* oops new direction */
1149 drop_square[n++] = u;
1156 if (color[u] == xside && (unpromoted[board[u]] == piece))
1158 /* king is threatened by opponents piece */
1161 DropToSquare(side, xside, ply, drop_square[--n]);
1169 u = next_direction(ptyp, &d, square);
1175 while (u != square);
1183 * Add drops that check enemy king.
1187 LinkCheckDrops(short side, short xside, short ply)
1192 unsigned char *ppos, *pdir;
1195 short square, piece;
1197 if (board[square = PieceList[xside][0]] != king)
1200 for (piece = pawn; piece < king; piece++)
1202 if (Captured[side][piece])
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!
1211 ptyp = ptype[xside][piece];
1213 u = first_direction(ptyp, &d, square);
1215 ppos = (*nextpos[ptyp])[square];
1216 pdir = (*nextdir[ptyp])[square];
1221 if (color[u] == neutral)
1223 if (piece != pawn || DropPossible(pawn, side, u))
1226 f = NO_SQUARES + piece;
1232 (dropmask | piece | check), xside, true);
1236 u = next_position(ptyp, &d, square, u);
1244 u = next_direction(ptyp, &d, square);
1250 while (u != square);
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
1267 MoveList(short side, short ply,
1268 short in_check, short blockable)
1271 struct leaf *firstnode;
1272 short flag_tsume, num;
1275 unsigned short hiHt = 0, hi0 = 0, hi1 = 0, hi2 = 0, hi3 = 0, hi4 = 0;
1278 flag_tsume = flag.tsume;
1282 sqking = PieceList[side][0];
1283 sqxking = PieceList[xside][0];
1291 InCheck = (board[sqking] == king)
1292 ? SqAttacked(sqking, xside, &blockable)
1296 GenerateAllMoves = (in_check == -2) || generate_move_flags;
1298 if (InCheck /* && (ply > 1 || side == computer) */)
1300 /* Own king in check */
1304 TrP = &TrPnt[ply + 1];
1307 firstnode = node = &Tree[*TrP];
1310 Swag0 = killr0[ply];
1314 Swag1 = killr1[ply];
1315 Swag2 = killr2[ply];
1316 Swag3 = killr3[ply];
1319 Swag4 = killr1[ply - 2];
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;
1335 for (i = PieceCnt[side]; i >= 0; i--)
1336 GenMoves(ply, PieceList[side][i], side, xside);
1338 if (!InCheck || blockable)
1342 /* special drop routine for tsume problems */
1344 LinkPreventCheckDrops(side, xside, ply);
1346 LinkCheckDrops(side, xside, ply);
1350 for (u = 0; u < NO_SQUARES; u++)
1351 DropToSquare(side, xside, ply, u);
1358 history[hiHt] -= 5000;
1359 history[hi0] -= 2000;
1367 SwagHt = 0; /* SwagHt is only used once */
1369 if (flag.tsume && node == firstnode)
1372 GenCnt += (num = (TrPnt[ply+1] - TrPnt[ply]));
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)
1379 DontUseMoves(ply, i);
1383 flag.tsume = flag_tsume;
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.
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
1401 CaptureList(short side, short ply,
1402 short in_check, short blockable)
1408 unsigned char *ppos, *pdir;
1410 short i, piece, flag_tsume;
1415 TrP = &TrPnt[ply + 1];
1419 flag_tsume = flag.tsume;
1421 sqking = PieceList[side][0];
1422 sqxking = PieceList[xside][0];
1430 InCheck = (board[sqking] == king)
1431 ? SqAttacked(sqking, xside, &blockable)
1435 GenerateAllMoves = (in_check == -2);
1437 if (InCheck && (ply > 1 || side == computer))
1439 /* Own king is in check */
1443 check_determined = false;
1445 PL = PieceList[side];
1447 for (i = 0; i <= PieceCnt[side]; i++)
1452 ptyp = ptype[side][piece];
1454 u = first_direction(ptyp, &d, sq);
1456 ppos = (*nextpos[ptyp])[sq];
1457 pdir = (*nextdir[ptyp])[sq];
1462 if (color[u] == neutral)
1465 u = next_position(ptyp, &d, sq, u);
1472 if (color[u] == xside && board[u] != king)
1476 if ((PP = PromotionPossible(color[sq], sq, u, piece)))
1479 sq, u, capture | promote,
1480 (*value)[stage][board[u]]
1481 #if !defined SAVE_SVALUE
1484 - relative_value[piece]);
1487 if (!PP || flag.tsume)
1491 (*value)[stage][board[u]]
1492 #if !defined SAVE_SVALUE
1495 - relative_value[piece]);
1500 u = next_direction(ptyp, &d, sq);
1509 flag.tsume = flag_tsume;
1511 SwagHt = 0; /* SwagHt is only used once */
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
1529 IsCheckmate(short side, short in_check, short blockable)
1535 unsigned char *ppos, *pdir;
1539 short tempb, tempc, ksq, threat, dummy, sqking;
1544 sqking = PieceList[side][0];
1547 * Checkmate is possible only if king is in check.
1552 else if (board[sqking] == king)
1553 InCheck = SqAttacked(sqking, xside, &blockable);
1561 * Try to find a move that prevents check.
1564 PL = PieceList[side];
1566 for (i = 0; i <= PieceCnt[side]; i++)
1571 ptyp = ptype[side][piece];
1573 u = first_direction(ptyp, &d, sq);
1575 ppos = (*nextpos[ptyp])[sq];
1576 pdir = (*nextdir[ptyp])[sq];
1581 if (color[u] == neutral || color[u] == xside)
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);
1593 u = (color[u] == neutral)
1594 ? next_position(ptyp, &d, sq, u)
1595 : next_direction(ptyp, &d, sq);
1597 u = (color[u] == neutral) ? ppos[u] : pdir[u];
1604 * Couldn't find a move that prevents check.
1605 * Try to find a drop that prevents check.
1610 for (piece = king - 1; piece >= pawn; piece--)
1612 if (Captured[side][piece])
1614 for (u = 0; u < NO_SQUARES; u++)
1616 if (DropPossible(piece, side, u))
1619 f = NO_SQUARES + piece;
1624 GenMakeMove(side, f, u, &tempb, &tempc, false);
1625 threat = SqAttacked(sqking, xside, &dummy);
1626 GenUnmakeMove(side, f, u, tempb, tempc, false);
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.