4 * ----------------------------------------------------------------------
5 * Copyright (c) 1993, 1994, 1995 Matthias Mutz
6 * Copyright (c) 1999 Michael Vanier and the Free Software Foundation
7 * Copyright (c) 2008, 2013, 2014 Yann Dirson and the Free Software Foundation
9 * GNU SHOGI is based on GNU CHESS
11 * Copyright (c) 1988, 1989, 1990 John Stanback
12 * Copyright (c) 1992 Free Software Foundation
14 * This file is part of GNU SHOGI.
16 * GNU Shogi is free software; you can redistribute it and/or modify it
17 * under the terms of the GNU General Public License as published by the
18 * Free Software Foundation; either version 3 of the License,
19 * or (at your option) any later version.
21 * GNU Shogi is distributed in the hope that it will be useful, but WITHOUT
22 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
23 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
26 * You should have received a copy of the GNU General Public License along
27 * with GNU Shogi; see the file COPYING. If not, see
28 * <http://www.gnu.org/licenses/>.
29 * ----------------------------------------------------------------------
35 /* #define DONTUSE_HEURISTIC */
39 static struct leaf
*node
;
40 static short sqking
, sqxking
;
41 static bool InCheck
= false, GenerateAllMoves
= false;
42 static bool check_determined
= false;
44 static bool deepsearchcut
= true;
45 static bool tas
= false, taxs
= false;
47 bool generate_move_flags
= false;
51 * Ply limits for deep search cut. No moves or drops flagged with "stupid"
52 * are considered beyond ply BEYOND_STUPID. Only moves or drops flagged
53 * with "kingattack" are considered beyond ply BEYOND_KINGATTACK. No moves
54 * or drops flagged with "questionable" are considered beyond ply
55 * BEYOND_QUESTIONABLE. Only moves or drops flagged with "tesuji" are
56 * considered beyond ply BEYOND_TESUJI. No drops are considered beyond ply
57 * BEYOND_DROP. Exceptions: moves or drops that prevent check or give
58 * check are always considered.
61 #define BEYOND_STUPID 0
62 #define BEYOND_TIMEOUT 2
63 #define BEYOND_KINGATTACK 6
64 #define BEYOND_QUESTIONABLE 8
65 #define BEYOND_TESUJI 8
66 #define BEYOND_DROP 10
68 #ifdef DONTUSE_HEURISTIC
69 static short MaxNum
[MAXDEPTH
] =
71 -1, 40, 80, 20, 40, 10, 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 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
79 extern int CheckHashKey();
80 extern char mvstr
[4][6];
85 * Update Arrays board[] and color[] to reflect the new board
86 * position obtained after making the move pointed to by node.
90 GenMakeMove(short side
,
93 short *tempb
, /* piece at to square */
94 short *tempc
, /* color of to square */
97 short piece
, upiece
, n
;
103 piece
= f
- NO_SQUARES
;
105 if (piece
> NO_PIECES
)
110 n
= (Captured
[side
][piece
])--;
111 UpdateDropHashbd(side
, piece
, n
);
112 UpdateHashbd(side
, piece
, -1, t
);
113 UpdatePieceList(side
, t
, ADD_PIECE
);
120 if (*tempb
!= no_piece
)
122 n
= ++Captured
[side
][upiece
= unpromoted
[*tempb
]];
123 UpdateDropHashbd(side
, upiece
, n
);
124 UpdateHashbd(*tempc
, *tempb
, -1, t
);
125 UpdatePieceList(*tempc
, t
, REMOVE_PIECE
);
129 Pindex
[t
] = Pindex
[f
];
130 PieceList
[side
][Pindex
[t
]] = t
;
137 UpdateHashbd(side
, piece
, f
, -1);
138 board
[t
] = promoted
[piece
];
139 UpdateHashbd(side
, board
[t
], -1, t
);
144 UpdateHashbd(side
, piece
, f
, t
);
152 printf("error in GenMakeMove: %s\n", mvstr
[0]);
165 GenUnmakeMove(short side
,
172 short piece
, upiece
, n
;
178 piece
= f
- NO_SQUARES
;
180 if (piece
> NO_PIECES
)
185 n
= ++Captured
[side
][piece
];
186 UpdateDropHashbd(side
, piece
, n
);
187 UpdateHashbd(side
, piece
, -1, t
);
188 UpdatePieceList(side
, t
, REMOVE_PIECE
);
195 Pindex
[f
] = Pindex
[t
];
196 PieceList
[side
][Pindex
[f
]] = f
;
198 if (tempb
!= no_piece
)
200 /* FIXME: make this next line a bit more reasonable... */
201 n
= (Captured
[side
][upiece
= unpromoted
[tempb
]])--;
202 UpdateDropHashbd(side
, upiece
, n
);
203 UpdateHashbd(tempc
, tempb
, -1, t
);
204 UpdatePieceList(tempc
, t
, ADD_PIECE
);
211 UpdateHashbd(side
, piece
, -1, t
);
212 board
[f
] = unpromoted
[piece
];
213 UpdateHashbd(side
, board
[f
], f
, -1);
218 UpdateHashbd(side
, piece
, f
, t
);
226 printf("error in GenUnmakeMove: %s\n", mvstr
[0]);
235 gives_check_flag(unsigned short *flags
, short side
, short f
, short t
)
238 bool blockable
, promote_piece
;
239 promote_piece
= (*flags
& promote
) != 0;
240 GenMakeMove(side
, f
, t
, &tempb
, &tempc
, promote_piece
);
242 if (SqAttacked(sqxking
, side
, &blockable
))
245 GenUnmakeMove(side
, f
, t
, tempb
, tempc
, promote_piece
);
251 short from
, short to
, unsigned short local_flag
, short s
)
255 dsp
->ShowMessage("TREE overflow\n");
260 node
->t
= (local_flag
& promote
) ? (to
| 0x80) : to
;
262 node
->flags
= local_flag
;
264 node
->INCscore
= INCscore
;
266 if (GenerateAllMoves
)
268 /* FIXME: gimme a break! */
273 /* only moves out of check */
274 short tempb
, tempc
, sq
, threat
;
275 bool blockable
, promote_piece
;
276 promote_piece
= (node
->flags
& promote
) != 0;
277 GenMakeMove(side
, node
->f
, node
->t
,
278 &tempb
, &tempc
, promote_piece
);
279 sq
= (from
== sqking
) ? to
: sqking
;
280 threat
= SqAttacked(sq
, side
^ 1, &blockable
);
281 GenUnmakeMove(side
, node
->f
, node
->t
,
282 tempb
, tempc
, promote_piece
);
286 /* FIXME! Gimme a break! */
292 /* only moves that give check */
293 if (!(node
->flags
& check
) && !check_determined
)
295 /* determine check flag */
296 gives_check_flag(&node
->flags
, side
, node
->f
, node
->t
);
299 if (node
->flags
& check
)
301 /* FIXME! Gimme a break! */
307 /* FIXME! Gimme a break! */
315 PromotionPossible(short color
, short f
, short t
, short p
)
319 if ((!InWhiteCamp(f
)) && (!InWhiteCamp(t
)))
324 if ((!InBlackCamp(f
)) && (!InBlackCamp(t
)))
328 /* FIXME: this can be simplified... */
347 NonPromotionPossible(short color
,
355 return ((t
< NO_COLS
* (NO_ROWS
- 1))
357 : (generate_move_flags
? ILLEGAL_TRAPPED
: false));
361 return ((t
>= NO_COLS
)
363 : (generate_move_flags
? ILLEGAL_TRAPPED
: false));
370 return ((t
< NO_COLS
* (NO_ROWS
- 1))
372 : (generate_move_flags
? ILLEGAL_TRAPPED
: false));
376 return ((t
>= NO_COLS
)
378 : (generate_move_flags
? ILLEGAL_TRAPPED
: false));
384 return ((t
< NO_COLS
* (NO_ROWS
- 2))
386 : (generate_move_flags
? ILLEGAL_TRAPPED
: false));
390 return ((t
>= 2 * NO_COLS
)
392 : (generate_move_flags
? ILLEGAL_TRAPPED
: false));
401 #if defined FIELDBONUS || defined DROPBONUS
403 /* bonus for possible next moves */
406 field_bonus(short side
, short piece
,
407 short f
, short t
, unsigned short *local_flag
)
410 unsigned char *ppos
, *pdir
;
420 check_determined
= true;
422 ptyp
= ptype
[side
][piece
];
425 u
= first_direction(ptyp
, &d
, t
);
427 ppos
= (*nextpos
[ptyp
])[t
];
428 pdir
= (*nextdir
[ptyp
])[t
];
434 short coloru
= color
[u
];
436 if (piece
!= king
&& GameCnt
> 40)
438 if (distance(u
, EnemyKing
) <= 1)
440 /* can reach square near own king */
442 *local_flag
|= kingattack
;
444 else if (distance(u
, OwnKing
) <= 1)
446 /* can reach square near enemy king */
448 *local_flag
|= kingattack
;
454 /* impossible next move */
456 u
= next_direction(ptyp
, &d
, t
);
463 /* possible next move */
464 if (PromotionPossible(side
, t
, u
, piece
))
466 /* possible promotion in next move */
471 if (!InPromotionZone(side
, t
))
473 *local_flag
|= tesuji
; /* The dangling pawn */
484 if (coloru
== neutral
)
486 /* next move to an empty square */
489 /* opponent has just left this square */
494 u
= next_position(ptyp
, &d
, t
, u
);
501 /* attack opponents piece */
503 short boardu
, upiece
, rvupiece
, rvuboard
;
507 if (u
== TOsquare
) /* opponent has moved to TOsquare */
510 if ((boardu
= board
[u
]) == king
)
512 s
+= 20; INCscore
-= 18;
513 *local_flag
|= check
; /* move threatens
518 upiece
= unpromoted
[piece
];
519 rvupiece
= relative_value
[upiece
];
520 rvuboard
= relative_value
[unpromoted
[boardu
]];
522 if ((upiece
== pawn
) && (Captured
[side
][pawn
] > 1))
524 *local_flag
|= tesuji
; /* The joining pawn attack */
528 if (rvupiece
<= rvuboard
)
530 *local_flag
|= tesuji
; /* The striking pawn
541 /* CHECKME: is this right? */
542 if (((rvupiece
== rvuboard
) && (upiece
== pawn
))
543 || (upiece
== bishop
)
545 || (upiece
== knight
)
549 s
++; /* The opposing pawn (piece) */
558 u
= next_direction(ptyp
, &d
, t
);
578 * Add a move to the tree. Assign a bonus to order the moves as follows:
579 * 1. Principle variation 2. Capture of last moved piece 3. Other captures
580 * (major pieces first) 4. Killer moves 5. Tesuji drops 6. Other Moves
581 * 7. Other drops. 8. Non-promoting moves
582 * If the flag.tsume is set, assign a high bonus for checks.
586 LinkMove(short ply
, short f
,
588 unsigned short local_flag
,
590 short score_if_impossible
)
593 short side
, piece
, mv
;
594 bool flag_tsume
, try_link
= true;
595 short c1
, c2
, ds
, is_drop
= f
> NO_SQUARES
;
596 unsigned long as
= 0;
598 flag_tsume
= flag
.tsume
;
600 c1
= side
= xside
^ 1;
604 * Is it determined whether the move gives check ?
607 check_determined
= ((local_flag
& check
) != 0);
609 mv
= (f
<< 8) | ((local_flag
& promote
) ? (t
| 0x80) : t
);
613 piece
= f
- NO_SQUARES
;
615 if (piece
> NO_PIECES
)
623 if (score_if_impossible
< 0)
625 /* The move is flagged as illegal. */
627 f
, t
, local_flag
, score_if_impossible
);
635 s
+= history
[hindex(side
, mv
)];
638 /* If we're running short of tree nodes, go into tsume mode. */
640 if (!(local_flag
& capture
))
642 if (*TrP
> (TREE
- 300))
644 /* too close to tree table limit */
649 /* Guess strength of move and set flags. */
651 if ((piece
!= king
) && (!in_opening_stage
))
653 if (distance(t
, EnemyKing
) <= 1)
655 /* bonus for square near enemy king */
658 local_flag
|= kingattack
;
660 else if (distance(t
, OwnKing
) <= 1)
662 /* bonus for square near own king */
665 local_flag
|= kingattack
;
669 if (tas
) /* own attack array available */
671 /* square t defended by own piece (don't count piece to move) ? */
673 ? (as
= attack
[side
][t
])
674 : (as
= ((attack
[side
][t
] & CNT_MASK
) > 1)))
675 s
+= (ds
= in_endgame_stage
? 100 : 10);
678 if (taxs
) /* opponents attack array available */
680 /* square t not threatened by opponent or
681 * defended and only threatened by opponents king ?
685 if (!(axs
= attack
[xside
][t
])
686 || (tas
&& as
&& (axs
& control
[king
]) && (axs
& CNT_MASK
) == 1))
688 /* FIXME: this is a mess; clean up. */
689 s
+= (ds
= in_endgame_stage
692 ? (InPromotionZone(side
, t
)
693 ? 40 + relative_value
[piece
]
699 /* target square near area of action */
702 s
+= (9 - distance(TOsquare
, t
));
705 s
+= (9 - distance(FROMsquare
, t
)) / 2;
707 /* target square near own or enemy king */
709 if (!in_opening_stage
&& piece
!= king
)
711 if (balance
[c1
] < 50)
712 s
+= (9 - distance(EnemyKing
, t
)) * (50 - balance
[c1
]) / 20;
714 s
+= (9 - distance(OwnKing
, t
)) * (balance
[c1
] - 50) / 20;
719 /* bonus for drops, in order to place
720 * drops before questionable moves */
721 s
+= in_endgame_stage
? 25 : 10;
725 /* drop to the square the opponent has just left */
730 s
-= 32 / Captured
[side
][gold
];
731 else if (piece
== silver
)
732 s
-= 16 / Captured
[side
][silver
];
734 #if defined DROPBONUS
735 s
+= field_bonus(side
, piece
, f
, t
, &local_flag
);
737 if (s
== 10 && piece
!= pawn
)
738 local_flag
|= questionable
;
743 /* bonus for moves (non-drops) */
744 bool consider_last
= false;
746 if (in_endgame_stage
&& Captured
[side
][gold
])
753 /* move to the square the opponent has just left */
754 s
+= in_endgame_stage
? 10 : 1;
757 if (color
[t
] != neutral
)
760 if (in_endgame_stage
)
762 s
+= relative_value
[board
[t
]] - relative_value
[piece
];
766 s
+= (*value
)[stage
][board
[t
]] - relative_value
[piece
];
769 if (t
== TOsquare
) /* Capture of last moved piece */
770 s
+= in_endgame_stage
? 5 : 50;
773 if (local_flag
& promote
)
775 /* bonus for promotions */
777 INCscore
+= value
[stage
][promoted
[piece
]] - value
[stage
][piece
];
781 /* bonus for non-promotions */
782 if (PromotionPossible(side
, f
, t
, piece
))
785 /* Look at non-promoting silver or knight */
792 local_flag
|= tesuji
; /* Non-promotion */
798 consider_last
= true;
800 if (piece
== pawn
|| piece
== bishop
|| piece
== rook
)
802 local_flag
|= stupid
;
807 local_flag
|= questionable
;
816 if (local_flag
& stupid
)
823 #if defined FIELDBONUS
824 s
+= field_bonus(side
, piece
, f
, t
, &local_flag
);
829 #if defined CHECKBONUS
830 /* determine check flag */
831 if (!(local_flag
& check
) && !check_determined
)
833 gives_check_flag(&local_flag
, side
, f
, t
);
835 if (local_flag
& check
)
840 /* check conditions for deep search cut (flag.tsume = true) */
843 if (!flag
.tsume
&& deepsearchcut
)
845 if ((ply
> BEYOND_STUPID
) && (local_flag
& stupid
))
847 try_link
= flag
.force
|| ((ply
== 1) && (side
!= computer
));
849 else if (hard_time_limit
&& (ply
> BEYOND_TIMEOUT
) && flag
.timeout
)
853 else if ((ply
> BEYOND_KINGATTACK
) && !(local_flag
& kingattack
))
857 else if ((ply
> BEYOND_QUESTIONABLE
) && (local_flag
& questionable
))
862 else if ((ply
> BEYOND_TESUJI
) && !(local_flag
& tesuji
))
867 else if ((ply
> BEYOND_DROP
) && (f
> NO_SQUARES
))
874 if (try_link
|| GenerateAllMoves
)
876 Link(side
, f
, t
, local_flag
,
877 s
- ((SCORE_LIMIT
+ 1000) * 2));
880 flag
.tsume
= flag_tsume
;
886 DropPossible(short piece
, short side
, short sq
)
888 short r
= row(sq
), possible
= true;
890 if (board
[sq
] != no_piece
)
894 else if (piece
== pawn
)
896 if ((side
== black
) && (r
== 8))
898 possible
= (generate_move_flags
? ILLEGAL_TRAPPED
: false);
900 else if ((side
== white
) && (r
== 0))
902 possible
= (generate_move_flags
? ILLEGAL_TRAPPED
: false);
904 else if (PawnCnt
[side
][column(sq
)])
906 possible
= (generate_move_flags
? ILLEGAL_DOUBLED
: false);
909 /* Pawn drops are invalid if they mate the opponent. */
912 short f
, tempb
, tempc
;
913 f
= pawn
+ NO_SQUARES
;
918 GenMakeMove(side
, f
, sq
, &tempb
, &tempc
, false);
920 if (IsCheckmate(side
^1, -1, -1))
921 possible
= (generate_move_flags
? ILLEGAL_MATE
: false);
923 GenUnmakeMove(side
, f
, sq
, tempb
, tempc
, false);
927 else if (piece
== lance
)
929 if ((side
== black
) && (r
== 8))
930 possible
= (generate_move_flags
? ILLEGAL_TRAPPED
: false);
931 else if ((side
== white
) && (r
== 0))
932 possible
= (generate_move_flags
? ILLEGAL_TRAPPED
: false);
934 else if (piece
== knight
)
936 if ((side
== black
) && (r
>= 7))
937 possible
= (generate_move_flags
? ILLEGAL_TRAPPED
: false);
938 else if ((side
== white
) && (r
<= 1))
939 possible
= (generate_move_flags
? ILLEGAL_TRAPPED
: false);
947 #if defined DONTUSE_HEURISTIC
953 for (p
= TrPnt
[ply
]; p
< TrPnt
[ply
+1]; p
++)
954 pick(p
, TrPnt
[ply
+1] - 1);
956 #endif /* DONTUSE_HEURISTIC */
959 #ifdef DONTUSE_HEURISTIC
962 DontUseMoves(short ply
, short n
)
967 /* k = number of check moves + number of captures */
968 for (i
= TrPnt
[ply
], k
= 0; i
< TrPnt
[ply
+1]; i
++)
972 if ((p
->flags
& check
) || (p
->flags
& capture
))
980 for (i
= TrPnt
[ply
]; i
< TrPnt
[ply
+1]; i
++)
984 if (!((p
->flags
& check
) || (p
->flags
& capture
)))
1001 * Generate moves for a piece. The moves are taken from the precalculated
1002 * array nextpos/nextdir. If the board is free, next move is chosen from
1003 * nextpos else from nextdir.
1007 GenMoves(short ply
, short sq
, short side
,
1011 short ptyp
, possible
;
1015 unsigned char *ppos
, *pdir
;
1019 ptyp
= ptype
[side
][piece
];
1022 u
= first_direction(ptyp
, &d
, sq
);
1024 ppos
= (*nextpos
[ptyp
])[sq
];
1025 pdir
= (*nextdir
[ptyp
])[sq
];
1031 unsigned short local_flag
;
1034 if ((c
= color
[u
]) == xside
)
1035 local_flag
= capture
;
1039 if (c
!= side
&& board
[u
] != king
)
1041 if (PromotionPossible(color
[sq
], sq
, u
, piece
))
1043 LinkMove(ply
, sq
, u
, local_flag
| promote
, xside
, true);
1046 = NonPromotionPossible(color
[sq
], u
, piece
)))
1048 LinkMove(ply
, sq
, u
, local_flag
, xside
, possible
);
1053 LinkMove(ply
, sq
, u
, local_flag
, xside
, true);
1060 u
= next_position(ptyp
, &d
, sq
, u
);
1064 u
= next_direction(ptyp
, &d
, sq
);
1083 * Drop each piece in hand of "side" to square "u" (if allowed).
1087 DropToSquare(short side
, short xside
, short ply
, short u
)
1091 for (i
= pawn
; i
< king
; i
++)
1093 if (Captured
[side
][i
])
1095 if ((possible
= DropPossible(i
, side
, u
)))
1103 LinkMove(ply
, f
, u
, (dropmask
| i
), xside
, possible
);
1112 * Add drops of side that prevent own king from being in check
1113 * from xside's sweeping pieces.
1117 LinkPreventCheckDrops(short side
, short xside
, short ply
)
1122 unsigned char *ppos
, *pdir
;
1124 short piece
, u
, xu
, square
, ptyp
;
1125 short n
, drop_square
[9];
1127 if (board
[square
= PieceList
[side
][0]] != king
)
1130 for (piece
= pawn
+1; piece
<= rook
; piece
++)
1136 piece
== bishop
|| piece
== rook
)
1138 /* check for threat of xside piece */
1139 ptyp
= ptype
[side
][piece
];
1142 u
= first_direction(ptyp
, &d
, square
);
1144 ppos
= (*nextpos
[ptyp
])[square
];
1145 pdir
= (*nextdir
[ptyp
])[square
];
1151 if (color
[u
] == neutral
)
1155 xu
= next_position(ptyp
, &d
, square
, u
);
1157 if (xu
== next_direction(ptyp
, &dd
, square
))
1159 n
= 0; /* oops new direction */
1163 drop_square
[n
++] = u
;
1167 if ((xu
= ppos
[u
]) == pdir
[u
])
1169 n
= 0; /* oops new direction */
1173 drop_square
[n
++] = u
;
1180 if (color
[u
] == xside
&& (unpromoted
[board
[u
]] == piece
))
1182 /* king is threatened by opponents piece */
1185 DropToSquare(side
, xside
, ply
, drop_square
[--n
]);
1193 u
= next_direction(ptyp
, &d
, square
);
1199 while (u
!= square
);
1207 * Add drops that check enemy king.
1211 LinkCheckDrops(short side
, short xside
, short ply
)
1216 unsigned char *ppos
, *pdir
;
1219 short square
, piece
;
1221 if (board
[square
= PieceList
[xside
][0]] != king
)
1224 for (piece
= pawn
; piece
< king
; piece
++)
1226 if (Captured
[side
][piece
])
1229 * "side" has "piece" in hand. Try to make a piece move from
1230 * opponents king square and drop this piece to each reachable
1231 * empty square. This definitely gives check! For a pawn drop
1232 * it must not double pawns and it must not be checkmate!
1235 ptyp
= ptype
[xside
][piece
];
1237 u
= first_direction(ptyp
, &d
, square
);
1239 ppos
= (*nextpos
[ptyp
])[square
];
1240 pdir
= (*nextdir
[ptyp
])[square
];
1245 if (color
[u
] == neutral
)
1247 if (piece
!= pawn
|| DropPossible(pawn
, side
, u
))
1250 f
= NO_SQUARES
+ piece
;
1256 (dropmask
| piece
| check
), xside
, true);
1260 u
= next_position(ptyp
, &d
, square
, u
);
1268 u
= next_direction(ptyp
, &d
, square
);
1274 while (u
!= square
);
1282 * Fill the array Tree[] with all available moves for side to play. Array
1283 * TrPnt[ply] contains the index into Tree[] of the first move at a ply.
1284 * in_check = 0 side is not in check
1285 * in_check > 1 side is in check
1286 * in_check < 0 don't know
1287 * in_check -2 indicates move generation for book moves
1291 MoveList(short side
, short ply
,
1292 short in_check
, bool blockable
)
1295 struct leaf
*firstnode
;
1296 short flag_tsume
, num
;
1299 unsigned short hiHt
= 0, hi0
= 0, hi1
= 0, hi2
= 0, hi3
= 0, hi4
= 0;
1302 flag_tsume
= flag
.tsume
;
1306 sqking
= PieceList
[side
][0];
1307 sqxking
= PieceList
[xside
][0];
1315 InCheck
= (board
[sqking
] == king
)
1316 ? SqAttacked(sqking
, xside
, &blockable
)
1320 GenerateAllMoves
= (in_check
== -2) || generate_move_flags
;
1322 if (InCheck
/* && (ply > 1 || side == computer) */)
1324 /* Own king in check */
1328 TrP
= &TrPnt
[ply
+ 1];
1331 firstnode
= node
= &Tree
[*TrP
];
1334 Swag0
= killr0
[ply
];
1338 Swag1
= killr1
[ply
];
1339 Swag2
= killr2
[ply
];
1340 Swag3
= killr3
[ply
];
1343 Swag4
= killr1
[ply
- 2];
1350 history
[hiHt
= hindex(side
, SwagHt
)] += 5000;
1351 history
[hi0
= hindex(side
, Swag0
)] += 2000;
1352 history
[hi1
= hindex(side
, Swag1
)] += 60;
1353 history
[hi2
= hindex(side
, Swag2
)] += 50;
1354 history
[hi3
= hindex(side
, Swag3
)] += 40;
1355 history
[hi4
= hindex(side
, Swag4
)] += 30;
1359 for (i
= PieceCnt
[side
]; i
>= 0; i
--)
1360 GenMoves(ply
, PieceList
[side
][i
], side
, xside
);
1362 if (!InCheck
|| blockable
)
1366 /* special drop routine for tsume problems */
1368 LinkPreventCheckDrops(side
, xside
, ply
);
1370 LinkCheckDrops(side
, xside
, ply
);
1374 for (u
= 0; u
< NO_SQUARES
; u
++)
1375 DropToSquare(side
, xside
, ply
, u
);
1382 history
[hiHt
] -= 5000;
1383 history
[hi0
] -= 2000;
1391 SwagHt
= 0; /* SwagHt is only used once */
1393 if (flag
.tsume
&& node
== firstnode
)
1396 GenCnt
+= (num
= (TrPnt
[ply
+1] - TrPnt
[ply
]));
1398 #ifdef DONTUSE_HEURISTIC
1399 /* remove some nodes in case of wide spread in depth */
1400 if (!flag
.tsume
&& (i
= MaxNum
[ply
]) > 0 && num
> i
)
1403 DontUseMoves(ply
, i
);
1407 flag
.tsume
= flag_tsume
;
1413 * Fill the array Tree[] with all available captures for side to play. If
1414 * there is a non-promote option, discard the non-promoting move. Array
1415 * TrPnt[ply] contains the index into Tree[] of the first move at a ply.
1416 * If flag.tsume is set, only add captures (but also the non-promoting)
1417 * that threaten the opponents king.
1419 * in_check = 0: side is not in check
1420 * in_check > 1: side is in check
1421 * in_check < 0: we don't know
1425 CaptureList(short side
, short ply
,
1426 short in_check
, bool blockable
)
1432 unsigned char *ppos
, *pdir
;
1434 short i
, piece
, flag_tsume
;
1439 TrP
= &TrPnt
[ply
+ 1];
1443 flag_tsume
= flag
.tsume
;
1445 sqking
= PieceList
[side
][0];
1446 sqxking
= PieceList
[xside
][0];
1454 InCheck
= (board
[sqking
] == king
)
1455 ? SqAttacked(sqking
, xside
, &blockable
)
1459 GenerateAllMoves
= (in_check
== -2);
1461 if (InCheck
&& (ply
> 1 || side
== computer
))
1463 /* Own king is in check */
1467 check_determined
= false;
1469 PL
= PieceList
[side
];
1471 for (i
= 0; i
<= PieceCnt
[side
]; i
++)
1476 ptyp
= ptype
[side
][piece
];
1478 u
= first_direction(ptyp
, &d
, sq
);
1480 ppos
= (*nextpos
[ptyp
])[sq
];
1481 pdir
= (*nextdir
[ptyp
])[sq
];
1486 if (color
[u
] == neutral
)
1489 u
= next_position(ptyp
, &d
, sq
, u
);
1496 if (color
[u
] == xside
&& board
[u
] != king
)
1500 if ((PP
= PromotionPossible(color
[sq
], sq
, u
, piece
)))
1503 sq
, u
, capture
| promote
,
1504 (*value
)[stage
][board
[u
]]
1505 #if !defined SAVE_SVALUE
1508 - relative_value
[piece
]);
1511 if (!PP
|| flag
.tsume
)
1515 (*value
)[stage
][board
[u
]]
1516 #if !defined SAVE_SVALUE
1519 - relative_value
[piece
]);
1524 u
= next_direction(ptyp
, &d
, sq
);
1533 flag
.tsume
= flag_tsume
;
1535 SwagHt
= 0; /* SwagHt is only used once */
1542 * If the king is in check, try to find a move that prevents check.
1543 * If such a move is found, return false, otherwise return true.
1544 * in_check = 0: side is not in check
1545 * in_check > 1: side is in check
1546 * in_check < 0: don't know
1547 * blockable > 0 && check: check can possibly be prevented by a drop
1548 * blockable = 0 && check: check can definitely not be prevented by a drop
1549 * blockable < 0 && check: nothing known about type of check
1553 IsCheckmate(short side
, short in_check
, bool blockable
)
1559 unsigned char *ppos
, *pdir
;
1563 short tempb
, tempc
, ksq
, threat
, sqking
;
1569 sqking
= PieceList
[side
][0];
1572 * Checkmate is possible only if king is in check.
1577 else if (board
[sqking
] == king
)
1578 InCheck
= SqAttacked(sqking
, xside
, &blockable
);
1586 * Try to find a move that prevents check.
1589 PL
= PieceList
[side
];
1591 for (i
= 0; i
<= PieceCnt
[side
]; i
++)
1596 ptyp
= ptype
[side
][piece
];
1598 u
= first_direction(ptyp
, &d
, sq
);
1600 ppos
= (*nextpos
[ptyp
])[sq
];
1601 pdir
= (*nextdir
[ptyp
])[sq
];
1606 if (color
[u
] == neutral
|| color
[u
] == xside
)
1608 GenMakeMove(side
, sq
, u
, &tempb
, &tempc
, false);
1609 ksq
= (sq
== sqking
) ? u
: sqking
;
1610 threat
= SqAttacked(ksq
, xside
, &dummy
);
1611 GenUnmakeMove(side
, sq
, u
, tempb
, tempc
, false);
1618 u
= (color
[u
] == neutral
)
1619 ? next_position(ptyp
, &d
, sq
, u
)
1620 : next_direction(ptyp
, &d
, sq
);
1622 u
= (color
[u
] == neutral
) ? ppos
[u
] : pdir
[u
];
1629 * Couldn't find a move that prevents check.
1630 * Try to find a drop that prevents check.
1635 for (piece
= king
- 1; piece
>= pawn
; piece
--)
1637 if (Captured
[side
][piece
])
1639 for (u
= 0; u
< NO_SQUARES
; u
++)
1641 if (DropPossible(piece
, side
, u
))
1644 f
= NO_SQUARES
+ piece
;
1649 GenMakeMove(side
, f
, u
, &tempb
, &tempc
, false);
1650 threat
= SqAttacked(sqking
, xside
, &dummy
);
1651 GenUnmakeMove(side
, f
, u
, tempb
, tempc
, false);
1659 * If the piece could be dropped at any square, it is
1660 * impossible for any other piece drop to prevent check.
1661 * Drops are restricted for pawns, lances, and knights.
1664 if (piece
>= silver
)