Only build pat2inc and declare it as dep for pattern.inc when not cross-compiling.
[gnushogi.git] / gnushogi / genmove.c
blob208966d3a0fccb8bd4b0118c15186bdca7dfa54d
1 /*
2 * FILE: genmove.c
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
24 * for more details.
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 * ----------------------------------------------------------------------
33 #include "gnushogi.h"
35 /* #define DONTUSE_HEURISTIC */
37 short *TrP;
39 static struct leaf *node;
40 static short sqking, sqxking;
41 static short InCheck = false, GenerateAllMoves = false;
42 static short check_determined = false;
44 short deepsearchcut = true;
45 short tas = false, taxs = false, ssa = false;
47 short 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,
76 #endif
78 #ifdef HASHKEYTEST
79 extern int CheckHashKey();
80 extern char mvstr[4][6];
81 #endif
85 * Update Arrays board[] and color[] to reflect the new board
86 * position obtained after making the move pointed to by node.
89 inline static void
90 GenMakeMove(short side,
91 short f,
92 short t,
93 short *tempb, /* piece at to square */
94 short *tempc, /* color of to square */
95 short promote_piece)
97 short piece, upiece, n;
99 t = t & 0x7f;
101 if (f > NO_SQUARES)
103 piece = f - NO_SQUARES;
105 if (piece > NO_PIECES)
106 piece -= NO_PIECES;
108 board[t] = piece;
109 color[t] = side;
110 n = (Captured[side][piece])--;
111 UpdateDropHashbd(side, piece, n);
112 UpdateHashbd(side, piece, -1, t);
113 UpdatePieceList(side, t, ADD_PIECE);
115 else
117 *tempb = board[t];
118 *tempc = color[t];
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);
128 piece = board[f];
129 Pindex[t] = Pindex[f];
130 PieceList[side][Pindex[t]] = t;
131 color[f] = neutral;
132 board[f] = no_piece;
133 color[t] = side;
135 if (promote_piece)
137 UpdateHashbd(side, piece, f, -1);
138 board[t] = promoted[piece];
139 UpdateHashbd(side, board[t], -1, t);
141 else
143 board[t] = piece;
144 UpdateHashbd(side, piece, f, t);
148 #ifdef HASHKEYTEST
149 if (CheckHashKey())
151 algbr(f, t, 0);
152 printf("error in GenMakeMove: %s\n", mvstr[0]);
153 exit(1);
155 #endif
161 * Take back a move.
164 static void
165 GenUnmakeMove(short side,
166 short f,
167 short t,
168 short tempb,
169 short tempc,
170 short promote_piece)
172 short piece, upiece, n;
174 t = t & 0x7f;
176 if (f > NO_SQUARES)
178 piece = f - NO_SQUARES;
180 if (piece > NO_PIECES)
181 piece -= NO_PIECES;
183 board[t] = no_piece;
184 color[t] = neutral;
185 n = ++Captured[side][piece];
186 UpdateDropHashbd(side, piece, n);
187 UpdateHashbd(side, piece, -1, t);
188 UpdatePieceList(side, t, REMOVE_PIECE);
190 else
192 piece = board[t];
193 color[t] = tempc;
194 board[t] = tempb;
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);
207 color[f] = side;
209 if (promote_piece)
211 UpdateHashbd(side, piece, -1, t);
212 board[f] = unpromoted[piece];
213 UpdateHashbd(side, board[f], f, -1);
215 else
217 board[f] = piece;
218 UpdateHashbd(side, piece, f, t);
222 #ifdef HASHKEYTEST
223 if (CheckHashKey())
225 algbr(f, t, 0);
226 printf("error in GenUnmakeMove: %s\n", mvstr[0]);
227 exit(1);
229 #endif
234 static void
235 gives_check_flag(unsigned short *flags, short side, short f, short t)
237 short tempb, tempc, blockable, promote_piece;
238 promote_piece = (*flags & promote) != 0;
239 GenMakeMove(side, f, t, &tempb, &tempc, promote_piece);
241 if (SqAttacked(sqxking, side, &blockable))
242 *flags |= check;
244 GenUnmakeMove(side, f, t, tempb, tempc, promote_piece);
248 inline static void
249 Link(short side,
250 short from, short to, unsigned short local_flag, short s)
252 if (*TrP == TREE)
254 dsp->ShowMessage("TREE overflow\n");
256 else
258 node->f = from;
259 node->t = (local_flag & promote) ? (to | 0x80) : to;
260 node->reply = 0;
261 node->flags = local_flag;
262 node->score = s;
263 node->INCscore = INCscore;
265 if (GenerateAllMoves)
267 /* FIXME: gimme a break! */
268 (*TrP)++, node++;
270 else if (InCheck)
272 /* only moves out of check */
273 short tempb, tempc, sq, threat, blockable, promote_piece;
274 promote_piece = (node->flags & promote) != 0;
275 GenMakeMove(side, node->f, node->t,
276 &tempb, &tempc, promote_piece);
277 sq = (from == sqking) ? to : sqking;
278 threat = SqAttacked(sq, side ^ 1, &blockable);
279 GenUnmakeMove(side, node->f, node->t,
280 tempb, tempc, promote_piece);
282 if (!threat)
284 /* FIXME! Gimme a break! */
285 (*TrP)++, node++;
288 else if (flag.tsume)
290 /* only moves that give check */
291 if (!(node->flags & check) && !check_determined)
293 /* determine check flag */
294 gives_check_flag(&node->flags, side, node->f, node->t);
297 if (node->flags & check)
299 /* FIXME! Gimme a break! */
300 (*TrP)++, node++;
303 else
305 /* FIXME! Gimme a break! */
306 (*TrP)++, node++;
312 inline int
313 PromotionPossible(short color, short f, short t, short p)
315 if (color == black)
317 if ((!InWhiteCamp(f)) && (!InWhiteCamp(t)))
318 return false;
320 else
322 if ((!InBlackCamp(f)) && (!InBlackCamp(t)))
323 return false;
326 /* FIXME: this can be simplified... */
327 switch (p)
329 case pawn:
330 #ifndef MINISHOGI
331 case lance:
332 case knight:
333 #endif
334 case silver:
335 case bishop:
336 case rook:
337 return true;
340 return false;
344 static inline int
345 NonPromotionPossible(short color,
346 short t, short p)
348 switch (p)
350 case pawn :
351 if (color == black)
353 return ((t < 72)
354 ? true
355 : (generate_move_flags ? ILLEGAL_TRAPPED : false));
357 else
359 return ((t > 8)
360 ? true
361 : (generate_move_flags ? ILLEGAL_TRAPPED : false));
364 #ifndef MINISHOGI
365 case lance:
366 if (color == black)
368 return ((t < 72)
369 ? true
370 : (generate_move_flags ? ILLEGAL_TRAPPED : false));
372 else
374 return ((t > 8)
375 ? true
376 : (generate_move_flags ? ILLEGAL_TRAPPED : false));
379 case knight:
380 if (color == black)
382 return ((t < 63)
383 ? true
384 : (generate_move_flags ? ILLEGAL_TRAPPED : false));
386 else
388 return ((t > 17)
389 ? true
390 : (generate_move_flags ? ILLEGAL_TRAPPED : false));
392 #endif
395 return true;
399 #if defined FIELDBONUS || defined DROPBONUS
401 /* bonus for possible next moves */
403 inline static short
404 field_bonus(short side, short piece,
405 short f, short t, unsigned short *local_flag)
407 short s, u, ptyp;
408 unsigned char *ppos, *pdir;
409 short c1, c2;
411 #ifdef SAVE_NEXTPOS
412 short d;
413 #endif
415 c1 = side;
416 c2 = side ^ 1;
417 s = 0;
418 check_determined = true;
420 ptyp = ptype[side][piece];
422 #ifdef SAVE_NEXTPOS
423 u = first_direction(ptyp, &d, t);
424 #else
425 ppos = (*nextpos[ptyp])[t];
426 pdir = (*nextdir[ptyp])[t];
427 u = ppos[t];
428 #endif
432 short coloru = color[u];
434 if (piece != king && GameCnt > 40)
436 if (distance(u, EnemyKing) <= 1)
438 /* can reach square near own king */
439 s += 2;
440 *local_flag |= kingattack;
442 else if (distance(u, OwnKing) <= 1)
444 /* can reach square near enemy king */
445 s++;
446 *local_flag |= kingattack;
450 if (coloru == side)
452 /* impossible next move */
453 #ifdef SAVE_NEXTPOS
454 u = next_direction(ptyp, &d, t);
455 #else
456 u = pdir[u];
457 #endif
459 else
461 /* possible next move */
462 if (PromotionPossible(side, t, u, piece))
464 /* possible promotion in next move */
465 if (piece == pawn)
467 s += 2;
468 #ifdef TESUJIBONUS
469 if (!InPromotionZone(side, t))
471 *local_flag |= tesuji; /* The dangling pawn */
472 s++;
474 #endif
476 else
478 s++;
482 if (coloru == neutral)
484 /* next move to an empty square */
485 if (u == FROMsquare)
487 /* opponent has just left this square */
488 s++;
491 #ifdef SAVE_NEXTPOS
492 u = next_position(ptyp, &d, t, u);
493 #else
494 u = ppos[u];
495 #endif
497 else
499 /* attack opponents piece */
500 #ifdef TESUJIBONUS
501 short boardu, upiece, rvupiece, rvuboard;
502 #endif
503 s++;
505 if (u == TOsquare) /* opponent has moved to TOsquare */
506 s++;
508 if ((boardu = board[u]) == king)
510 s += 20; INCscore -= 18;
511 *local_flag |= check; /* move threatens
512 * opponents king */
515 #ifdef TESUJIBONUS
516 upiece = unpromoted[piece];
517 rvupiece = relative_value[upiece];
518 rvuboard = relative_value[unpromoted[boardu]];
520 if ((upiece == pawn) && (Captured[side][pawn] > 1))
522 *local_flag |= tesuji; /* The joining pawn attack */
523 s++;
526 if (rvupiece <= rvuboard)
528 *local_flag |= tesuji; /* The striking pawn
529 * (piece) attack */
531 if (f > NO_SQUARES)
532 s += 2;
533 else
534 s++;
536 if (upiece == pawn)
537 s++;
539 /* CHECKME: is this right? */
540 if (((rvupiece == rvuboard) && (upiece == pawn))
541 || (upiece == bishop)
542 #ifndef MINISHOGI
543 || (upiece == knight)
544 #endif
547 s++; /* The opposing pawn (piece) */
549 if (upiece == pawn)
550 s++;
553 #endif
555 #ifdef SAVE_NEXTPOS
556 u = next_direction(ptyp, &d, t);
557 #else
558 u = pdir[u];
559 #endif
563 while (u != t);
565 INCscore += s;
567 return s;
570 #endif
576 * Add a move to the tree. Assign a bonus to order the moves as follows:
577 * 1. Principle variation 2. Capture of last moved piece 3. Other captures
578 * (major pieces first) 4. Killer moves 5. Tesuji drops 6. Other Moves
579 * 7. Other drops. 8. Non-promoting moves
580 * If the flag.tsume is set, assign a high bonus for checks.
583 /* inline */ void
584 LinkMove(short ply, short f,
585 short t,
586 unsigned short local_flag,
587 short xside,
588 short score_if_impossible)
590 short s = 0;
591 short side, piece, mv;
592 short flag_tsume, try_link = true;
593 short c1, c2, ds, is_drop = f > NO_SQUARES;
594 unsigned long as = 0;
596 flag_tsume = flag.tsume;
598 c1 = side = xside ^ 1;
599 c2 = xside;
602 * Is it determined whether the move gives check ?
605 check_determined = ((local_flag & check) != 0);
607 mv = (f << 8) | ((local_flag & promote) ? (t | 0x80) : t);
609 if (f > NO_SQUARES)
611 piece = f - NO_SQUARES;
613 if (piece > NO_PIECES)
614 piece -= NO_PIECES;
616 else
618 piece = board[f];
621 if (score_if_impossible < 0)
623 /* The move is flagged as illegal. */
624 Link(side,
625 f, t, local_flag, score_if_impossible);
627 return;
630 INCscore = 0;
632 #ifdef HISTORY
633 s += history[hindex(side, mv)];
634 #endif
636 /* If we're running short of tree nodes, go into tsume mode. */
638 if (!(local_flag & capture))
640 if (*TrP > (TREE - 300))
642 /* too close to tree table limit */
643 flag.tsume = true;
647 /* Guess strength of move and set flags. */
649 if ((piece != king) && (!in_opening_stage))
651 if (distance(t, EnemyKing) <= 1)
653 /* bonus for square near enemy king */
654 s += 15;
655 INCscore += 2;
656 local_flag |= kingattack;
658 else if (distance(t, OwnKing) <= 1)
660 /* bonus for square near own king */
661 s += 10;
662 INCscore++;
663 local_flag |= kingattack;
667 if (tas) /* own attack array available */
669 /* square t defended by own piece (don't count piece to move) ? */
670 if (is_drop
671 ? (as = attack[side][t])
672 : (as = ((attack[side][t] & CNT_MASK) > 1)))
673 s += (ds = in_endgame_stage ? 100 : 10);
676 if (taxs) /* opponents attack array available */
678 /* square t not threatened by opponent or
679 * defended and only threatened by opponents king ?
681 unsigned long axs;
683 if (!(axs = attack[xside][t])
684 || (tas && as && (axs & control[king]) && (axs & CNT_MASK) == 1))
686 /* FIXME: this is a mess; clean up. */
687 s += (ds = in_endgame_stage
688 ? 200
689 : (is_drop
690 ? (InPromotionZone(side, t)
691 ? 40 + relative_value[piece]
692 : 10)
693 : 20));
697 /* target square near area of action */
699 if (TOsquare >= 0)
700 s += (9 - distance(TOsquare, t));
702 if (FROMsquare >= 0)
703 s += (9 - distance(FROMsquare, t)) / 2;
705 /* target square near own or enemy king */
707 if (!in_opening_stage && piece != king)
709 if (balance[c1] < 50)
710 s += (9 - distance(EnemyKing, t)) * (50 - balance[c1]) / 20;
711 else
712 s += (9 - distance(OwnKing, t)) * (balance[c1] - 50) / 20;
715 if (f > NO_SQUARES)
717 /* bonus for drops, in order to place
718 * drops before questionable moves */
719 s += in_endgame_stage ? 25 : 10;
721 if (t == FROMsquare)
723 /* drop to the square the opponent has just left */
724 s += 5;
727 if (piece == gold)
728 s -= 32 / Captured[side][gold];
729 else if (piece == silver)
730 s -= 16 / Captured[side][silver];
732 #if defined DROPBONUS
733 s += field_bonus(side, piece, f, t, &local_flag);
735 if (s == 10 && piece != pawn)
736 local_flag |= questionable;
737 #endif
739 else
741 /* bonus for moves (non-drops) */
742 int consider_last = false;
744 if (in_endgame_stage && Captured[side][gold])
745 s += 10;
747 s += 20;
749 if (t == FROMsquare)
751 /* move to the square the opponent has just left */
752 s += in_endgame_stage ? 10 : 1;
755 if (color[t] != neutral)
757 /* Captures */
758 if (in_endgame_stage)
760 s += relative_value[board[t]] - relative_value[piece];
762 else
764 s += (*value)[stage][board[t]] - relative_value[piece];
767 if (t == TOsquare) /* Capture of last moved piece */
768 s += in_endgame_stage ? 5 : 50;
771 if (local_flag & promote)
773 /* bonus for promotions */
774 s++;
775 INCscore += value[stage][promoted[piece]] - value[stage][piece];
777 else
779 /* bonus for non-promotions */
780 if (PromotionPossible(side, f, t, piece))
782 #ifdef TESUJIBONUS
783 /* Look at non-promoting silver or knight */
784 if (piece == silver
785 #ifndef MINISHOGI
786 || piece == knight
787 #endif
790 local_flag |= tesuji; /* Non-promotion */
791 s++;
793 else
794 #endif
796 consider_last = true;
798 if (piece == pawn || piece == bishop || piece == rook)
800 local_flag |= stupid;
801 INCscore -= 20;
803 else
805 local_flag |= questionable;
806 INCscore -= 10;
812 if (consider_last)
814 if (local_flag & stupid)
815 s = 0;
816 else
817 s = s % 20;
819 else
821 #if defined FIELDBONUS
822 s += field_bonus(side, piece, f, t, &local_flag);
823 #endif
827 #if defined CHECKBONUS
828 /* determine check flag */
829 if (!(local_flag & check) && !check_determined)
831 gives_check_flag(&local_flag, side, f, t);
833 if (local_flag & check)
834 s += 20;
836 #endif
838 /* check conditions for deep search cut (flag.tsume = true) */
840 #ifdef DEEPSEARCHCUT
841 if (!flag.tsume && deepsearchcut)
843 if ((ply > BEYOND_STUPID) && (local_flag & stupid))
845 try_link = flag.force || ((ply == 1) && (side != computer));
847 else if (hard_time_limit && (ply > BEYOND_TIMEOUT) && flag.timeout)
849 flag.tsume = true;
851 else if ((ply > BEYOND_KINGATTACK) && !(local_flag & kingattack))
853 flag.tsume = true;
855 else if ((ply > BEYOND_QUESTIONABLE) && (local_flag & questionable))
857 flag.tsume = true;
858 #ifdef TESUJIBONUS
860 else if ((ply > BEYOND_TESUJI) && !(local_flag & tesuji))
862 flag.tsume = true;
863 #endif
865 else if ((ply > BEYOND_DROP) && (f > NO_SQUARES))
867 flag.tsume = true;
870 #endif
872 if (try_link || GenerateAllMoves)
874 Link(side, f, t, local_flag,
875 s - ((SCORE_LIMIT + 1000) * 2));
878 flag.tsume = flag_tsume;
883 short
884 DropPossible(short piece, short side, short sq)
886 short r = row(sq), possible = true;
888 if (board[sq] != no_piece)
890 possible = false;
892 else if (piece == pawn)
894 if ((side == black) && (r == 8))
896 possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
898 else if ((side == white) && (r == 0))
900 possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
902 else if (PawnCnt[side][column(sq)])
904 possible = (generate_move_flags ? ILLEGAL_DOUBLED : false);
907 /* Pawn drops are invalid if they mate the opponent. */
908 if (possible)
910 short f, tempb, tempc;
911 f = pawn + NO_SQUARES;
913 if (side == white)
914 f += NO_PIECES;
916 GenMakeMove(side, f, sq, &tempb, &tempc, false);
918 if (IsCheckmate(side^1, -1, -1))
919 possible = (generate_move_flags ? ILLEGAL_MATE : false);
921 GenUnmakeMove(side, f, sq, tempb, tempc, false);
924 #ifndef MINISHOGI
925 else if (piece == lance)
927 if ((side == black) && (r == 8))
928 possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
929 else if ((side == white) && (r == 0))
930 possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
932 else if (piece == knight)
934 if ((side == black) && (r >= 7))
935 possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
936 else if ((side == white) && (r <= 1))
937 possible = (generate_move_flags ? ILLEGAL_TRAPPED : false);
939 #endif
941 return possible;
945 #if defined DONTUSE_HEURISTIC
946 static void
947 SortMoves(short ply)
949 short p;
951 for (p = TrPnt[ply]; p < TrPnt[ply+1]; p++)
952 pick(p, TrPnt[ply+1] - 1);
954 #endif /* DONTUSE_HEURISTIC */
957 #ifdef DONTUSE_HEURISTIC
959 static void
960 DontUseMoves(short ply, short n)
962 struct leaf *p;
963 short i, k;
965 /* k = number of check moves + number of captures */
966 for (i = TrPnt[ply], k = 0; i < TrPnt[ply+1]; i++)
968 p = &Tree[i];
970 if ((p->flags & check) || (p->flags & capture))
972 if (++k >= n)
973 return;
977 /* use n moves */
978 for (i = TrPnt[ply]; i < TrPnt[ply+1]; i++)
980 p = &Tree[i];
982 if (!((p->flags & check) || (p->flags & capture)))
984 if (k < n)
985 k++;
986 else
988 p->score = DONTUSE;
994 #endif
999 * Generate moves for a piece. The moves are taken from the precalculated
1000 * array nextpos/nextdir. If the board is free, next move is chosen from
1001 * nextpos else from nextdir.
1004 inline void
1005 GenMoves(short ply, short sq, short side,
1006 short xside)
1008 short u, piece;
1009 short ptyp, possible;
1010 #ifdef SAVE_NEXTPOS
1011 short d;
1012 #else
1013 unsigned char *ppos, *pdir;
1014 #endif
1016 piece = board[sq];
1017 ptyp = ptype[side][piece];
1019 #ifdef SAVE_NEXTPOS
1020 u = first_direction(ptyp, &d, sq);
1021 #else
1022 ppos = (*nextpos[ptyp])[sq];
1023 pdir = (*nextdir[ptyp])[sq];
1024 u = ppos[sq];
1025 #endif
1029 unsigned short local_flag;
1030 short c;
1032 if ((c = color[u]) == xside)
1033 local_flag = capture;
1034 else
1035 local_flag = 0;
1037 if (c != side && board[u] != king)
1039 if (PromotionPossible(color[sq], sq, u, piece))
1041 LinkMove(ply, sq, u, local_flag | promote, xside, true);
1043 if ((possible
1044 = NonPromotionPossible(color[sq], u, piece)))
1046 LinkMove(ply, sq, u, local_flag, xside, possible);
1049 else
1051 LinkMove(ply, sq, u, local_flag, xside, true);
1055 if (c == neutral)
1056 #ifdef SAVE_NEXTPOS
1058 u = next_position(ptyp, &d, sq, u);
1060 else
1062 u = next_direction(ptyp, &d, sq);
1064 #else
1066 u = ppos[u];
1068 else
1070 u = pdir[u];
1072 #endif
1074 while (u != sq);
1081 * Drop each piece in hand of "side" to square "u" (if allowed).
1084 static void
1085 DropToSquare(short side, short xside, short ply, short u)
1087 short i, possible;
1089 for (i = pawn; i < king; i++)
1091 if (Captured[side][i])
1093 if ((possible = DropPossible(i, side, u)))
1095 short f;
1096 f = NO_SQUARES + i;
1098 if (side == white)
1099 f += NO_PIECES;
1101 LinkMove(ply, f, u, (dropmask | i), xside, possible);
1110 * Add drops of side that prevent own king from being in check
1111 * from xside's sweeping pieces.
1114 static void
1115 LinkPreventCheckDrops(short side, short xside, short ply)
1117 #ifdef SAVE_NEXTPOS
1118 short d, dd;
1119 #else
1120 unsigned char *ppos, *pdir;
1121 #endif
1122 short piece, u, xu, square, ptyp;
1123 short n, drop_square[9];
1125 if (board[square = PieceList[side][0]] != king)
1126 return;
1128 for (piece = pawn+1; piece <= rook; piece++)
1130 if (
1131 #ifndef MINISHOGI
1132 piece == lance ||
1133 #endif
1134 piece == bishop || piece == rook)
1136 /* check for threat of xside piece */
1137 ptyp = ptype[side][piece];
1138 n = 0;
1139 #ifdef SAVE_NEXTPOS
1140 u = first_direction(ptyp, &d, square);
1141 #else
1142 ppos = (*nextpos[ptyp])[square];
1143 pdir = (*nextdir[ptyp])[square];
1144 u = ppos[square];
1145 #endif
1149 if (color[u] == neutral)
1151 #ifdef SAVE_NEXTPOS
1152 dd = d;
1153 xu = next_position(ptyp, &d, square, u);
1155 if (xu == next_direction(ptyp, &dd, square))
1157 n = 0; /* oops new direction */
1159 else
1161 drop_square[n++] = u;
1163 #else
1165 if ((xu = ppos[u]) == pdir[u])
1167 n = 0; /* oops new direction */
1169 else
1171 drop_square[n++] = u;
1173 #endif
1174 u = xu;
1176 else
1178 if (color[u] == xside && (unpromoted[board[u]] == piece))
1180 /* king is threatened by opponents piece */
1181 while (n > 0)
1183 DropToSquare(side, xside, ply, drop_square[--n]);
1186 else
1188 n = 0;
1190 #ifdef SAVE_NEXTPOS
1191 u = next_direction(ptyp, &d, square);
1192 #else
1193 u = pdir[u];
1194 #endif
1197 while (u != square);
1205 * Add drops that check enemy king.
1208 static void
1209 LinkCheckDrops(short side, short xside, short ply)
1211 #ifdef SAVE_NEXTPOS
1212 short d;
1213 #else
1214 unsigned char *ppos, *pdir;
1215 #endif
1216 short u, ptyp;
1217 short square, piece;
1219 if (board[square = PieceList[xside][0]] != king)
1220 return;
1222 for (piece = pawn; piece < king; piece++)
1224 if (Captured[side][piece])
1227 * "side" has "piece" in hand. Try to make a piece move from
1228 * opponents king square and drop this piece to each reachable
1229 * empty square. This definitely gives check! For a pawn drop
1230 * it must not double pawns and it must not be checkmate!
1233 ptyp = ptype[xside][piece];
1234 #ifdef SAVE_NEXTPOS
1235 u = first_direction(ptyp, &d, square);
1236 #else
1237 ppos = (*nextpos[ptyp])[square];
1238 pdir = (*nextdir[ptyp])[square];
1239 u = ppos[square];
1240 #endif
1243 if (color[u] == neutral)
1245 if (piece != pawn || DropPossible(pawn, side, u))
1247 short f;
1248 f = NO_SQUARES + piece;
1250 if (side == white)
1251 f += NO_PIECES;
1253 LinkMove(ply, f, u,
1254 (dropmask | piece | check), xside, true);
1257 #ifdef SAVE_NEXTPOS
1258 u = next_position(ptyp, &d, square, u);
1259 #else
1260 u = ppos[u];
1261 #endif
1263 else
1265 #ifdef SAVE_NEXTPOS
1266 u = next_direction(ptyp, &d, square);
1267 #else
1268 u = pdir[u];
1269 #endif
1272 while (u != square);
1280 * Fill the array Tree[] with all available moves for side to play. Array
1281 * TrPnt[ply] contains the index into Tree[] of the first move at a ply.
1282 * in_check = 0 side is not in check
1283 * in_check > 1 side is in check
1284 * in_check < 0 don't know
1285 * in_check -2 indicates move generation for book moves
1288 void
1289 MoveList(short side, short ply,
1290 short in_check, short blockable)
1292 short i, xside, u;
1293 struct leaf *firstnode;
1294 short flag_tsume, num;
1296 #ifdef HISTORY
1297 unsigned short hiHt = 0, hi0 = 0, hi1 = 0, hi2 = 0, hi3 = 0, hi4 = 0;
1298 #endif
1300 flag_tsume = flag.tsume;
1302 xside = side ^ 1;
1304 sqking = PieceList[side][0];
1305 sqxking = PieceList[xside][0];
1307 if (in_check >= 0)
1309 InCheck = in_check;
1311 else
1313 InCheck = (board[sqking] == king)
1314 ? SqAttacked(sqking, xside, &blockable)
1315 : false;
1318 GenerateAllMoves = (in_check == -2) || generate_move_flags;
1320 if (InCheck /* && (ply > 1 || side == computer) */)
1322 /* Own king in check */
1323 flag.tsume = true;
1326 TrP = &TrPnt[ply + 1];
1327 *TrP = TrPnt[ply];
1329 firstnode = node = &Tree[*TrP];
1331 if (!PV)
1332 Swag0 = killr0[ply];
1333 else
1334 Swag0 = PV;
1336 Swag1 = killr1[ply];
1337 Swag2 = killr2[ply];
1338 Swag3 = killr3[ply];
1340 if (ply > 2)
1341 Swag4 = killr1[ply - 2];
1342 else
1343 Swag4 = 0;
1345 #ifdef HISTORY
1346 if (use_history)
1348 history[hiHt = hindex(side, SwagHt)] += 5000;
1349 history[hi0 = hindex(side, Swag0)] += 2000;
1350 history[hi1 = hindex(side, Swag1)] += 60;
1351 history[hi2 = hindex(side, Swag2)] += 50;
1352 history[hi3 = hindex(side, Swag3)] += 40;
1353 history[hi4 = hindex(side, Swag4)] += 30;
1355 #endif
1357 for (i = PieceCnt[side]; i >= 0; i--)
1358 GenMoves(ply, PieceList[side][i], side, xside);
1360 if (!InCheck || blockable)
1362 if (flag.tsume)
1364 /* special drop routine for tsume problems */
1365 if (InCheck)
1366 LinkPreventCheckDrops(side, xside, ply);
1367 else
1368 LinkCheckDrops(side, xside, ply);
1370 else
1372 for (u = 0; u < NO_SQUARES; u++)
1373 DropToSquare(side, xside, ply, u);
1377 #ifdef HISTORY
1378 if (use_history)
1380 history[hiHt] -= 5000;
1381 history[hi0] -= 2000;
1382 history[hi1] -= 60;
1383 history[hi2] -= 50;
1384 history[hi3] -= 40;
1385 history[hi4] -= 30;
1387 #endif
1389 SwagHt = 0; /* SwagHt is only used once */
1391 if (flag.tsume && node == firstnode)
1392 (*TrP)++;
1394 GenCnt += (num = (TrPnt[ply+1] - TrPnt[ply]));
1396 #ifdef DONTUSE_HEURISTIC
1397 /* remove some nodes in case of wide spread in depth */
1398 if (!flag.tsume && (i = MaxNum[ply]) > 0 && num > i)
1400 SortMoves(ply);
1401 DontUseMoves(ply, i);
1403 #endif
1405 flag.tsume = flag_tsume;
1411 * Fill the array Tree[] with all available captures for side to play. If
1412 * there is a non-promote option, discard the non-promoting move. Array
1413 * TrPnt[ply] contains the index into Tree[] of the first move at a ply.
1414 * If flag.tsume is set, only add captures (but also the non-promoting)
1415 * that threaten the opponents king.
1417 * in_check = 0: side is not in check
1418 * in_check > 1: side is in check
1419 * in_check < 0: we don't know
1422 void
1423 CaptureList(short side, short ply,
1424 short in_check, short blockable)
1426 short u, sq, xside;
1427 #ifdef SAVE_NEXTPOS
1428 short d;
1429 #else
1430 unsigned char *ppos, *pdir;
1431 #endif
1432 short i, piece, flag_tsume;
1433 small_short *PL;
1435 xside = side ^ 1;
1437 TrP = &TrPnt[ply + 1];
1438 *TrP = TrPnt[ply];
1439 node = &Tree[*TrP];
1441 flag_tsume = flag.tsume;
1443 sqking = PieceList[side][0];
1444 sqxking = PieceList[xside][0];
1446 if (in_check >= 0)
1448 InCheck = in_check;
1450 else
1452 InCheck = (board[sqking] == king)
1453 ? SqAttacked(sqking, xside, &blockable)
1454 : false;
1457 GenerateAllMoves = (in_check == -2);
1459 if (InCheck && (ply > 1 || side == computer))
1461 /* Own king is in check */
1462 flag.tsume = true;
1465 check_determined = false;
1467 PL = PieceList[side];
1469 for (i = 0; i <= PieceCnt[side]; i++)
1471 short ptyp;
1472 sq = PL[i];
1473 piece = board[sq];
1474 ptyp = ptype[side][piece];
1475 #ifdef SAVE_NEXTPOS
1476 u = first_direction(ptyp, &d, sq);
1477 #else
1478 ppos = (*nextpos[ptyp])[sq];
1479 pdir = (*nextdir[ptyp])[sq];
1480 u = ppos[sq];
1481 #endif
1484 if (color[u] == neutral)
1486 #ifdef SAVE_NEXTPOS
1487 u = next_position(ptyp, &d, sq, u);
1488 #else
1489 u = ppos[u];
1490 #endif
1492 else
1494 if (color[u] == xside && board[u] != king)
1496 short PP;
1498 if ((PP = PromotionPossible(color[sq], sq, u, piece)))
1500 Link(side,
1501 sq, u, capture | promote,
1502 (*value)[stage][board[u]]
1503 #if !defined SAVE_SVALUE
1504 + svalue[board[u]]
1505 #endif
1506 - relative_value[piece]);
1509 if (!PP || flag.tsume)
1511 Link(side,
1512 sq, u, capture,
1513 (*value)[stage][board[u]]
1514 #if !defined SAVE_SVALUE
1515 + svalue[board[u]]
1516 #endif
1517 - relative_value[piece]);
1521 #ifdef SAVE_NEXTPOS
1522 u = next_direction(ptyp, &d, sq);
1523 #else
1524 u = pdir[u];
1525 #endif
1528 while (u != sq);
1531 flag.tsume = flag_tsume;
1533 SwagHt = 0; /* SwagHt is only used once */
1540 * If the king is in check, try to find a move that prevents check.
1541 * If such a move is found, return false, otherwise return true.
1542 * in_check = 0: side is not in check
1543 * in_check > 1: side is in check
1544 * in_check < 0: don't know
1545 * blockable > 0 && check: check can possibly be prevented by a drop
1546 * blockable = 0 && check: check can definitely not be prevented by a drop
1547 * blockable < 0 && check: nothing known about type of check
1550 short
1551 IsCheckmate(short side, short in_check, short blockable)
1553 short u, sq, xside;
1554 #ifdef SAVE_NEXTPOS
1555 short d;
1556 #else
1557 unsigned char *ppos, *pdir;
1558 #endif
1559 short i, piece;
1560 small_short *PL;
1561 short tempb, tempc, ksq, threat, dummy, sqking;
1562 short InCheck;
1564 xside = side ^ 1;
1566 sqking = PieceList[side][0];
1569 * Checkmate is possible only if king is in check.
1572 if (in_check >= 0)
1573 InCheck = in_check;
1574 else if (board[sqking] == king)
1575 InCheck = SqAttacked(sqking, xside, &blockable);
1576 else
1577 InCheck = false;
1579 if (!InCheck)
1580 return false;
1583 * Try to find a move that prevents check.
1586 PL = PieceList[side];
1588 for (i = 0; i <= PieceCnt[side]; i++)
1590 short ptyp;
1591 sq = PL[i];
1592 piece = board[sq];
1593 ptyp = ptype[side][piece];
1594 #ifdef SAVE_NEXTPOS
1595 u = first_direction(ptyp, &d, sq);
1596 #else
1597 ppos = (*nextpos[ptyp])[sq];
1598 pdir = (*nextdir[ptyp])[sq];
1599 u = ppos[sq];
1600 #endif
1603 if (color[u] == neutral || color[u] == xside)
1605 GenMakeMove(side, sq, u, &tempb, &tempc, false);
1606 ksq = (sq == sqking) ? u : sqking;
1607 threat = SqAttacked(ksq, xside, &dummy);
1608 GenUnmakeMove(side, sq, u, tempb, tempc, false);
1610 if (!threat)
1611 return false;
1614 #ifdef SAVE_NEXTPOS
1615 u = (color[u] == neutral)
1616 ? next_position(ptyp, &d, sq, u)
1617 : next_direction(ptyp, &d, sq);
1618 #else
1619 u = (color[u] == neutral) ? ppos[u] : pdir[u];
1620 #endif
1622 while (u != sq);
1626 * Couldn't find a move that prevents check.
1627 * Try to find a drop that prevents check.
1630 if (blockable != 0)
1632 for (piece = king - 1; piece >= pawn; piece--)
1634 if (Captured[side][piece])
1636 for (u = 0; u < NO_SQUARES; u++)
1638 if (DropPossible(piece, side, u))
1640 short f;
1641 f = NO_SQUARES + piece;
1643 if (side == white)
1644 f += NO_PIECES;
1646 GenMakeMove(side, f, u, &tempb, &tempc, false);
1647 threat = SqAttacked(sqking, xside, &dummy);
1648 GenUnmakeMove(side, f, u, tempb, tempc, false);
1650 if (!threat)
1651 return false;
1656 * If the piece could be dropped at any square, it is
1657 * impossible for any other piece drop to prevent check.
1658 * Drops are restricted for pawns, lances, and knights.
1661 if (piece >= silver)
1662 break;
1667 return true;