X-Git-Url: http://winboard.nl/cgi-bin?a=blobdiff_plain;f=gnushogi%2Fgenmove.c;fp=gnushogi%2Fgenmove.c;h=6490319f1859cdc2fd7e12304a0adf3c761b398f;hb=8ae7e7d1b257ef36d8a9fd1cd88807954ef10764;hp=0000000000000000000000000000000000000000;hpb=e597a4014df46fbc2b8cacc74f8f176c194872a0;p=gnushogi.git diff --git a/gnushogi/genmove.c b/gnushogi/genmove.c new file mode 100644 index 0000000..6490319 --- /dev/null +++ b/gnushogi/genmove.c @@ -0,0 +1,1654 @@ +/* + * FILE: genmove.c + * + * ---------------------------------------------------------------------- + * Copyright (c) 1993, 1994, 1995 Matthias Mutz + * Copyright (c) 1999 Michael Vanier and the Free Software Foundation + * + * GNU SHOGI is based on GNU CHESS + * + * Copyright (c) 1988, 1989, 1990 John Stanback + * Copyright (c) 1992 Free Software Foundation + * + * This file is part of GNU SHOGI. + * + * GNU Shogi is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 1, or (at your option) any + * later version. + * + * GNU Shogi is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * for more details. + * + * You should have received a copy of the GNU General Public License along + * with GNU Shogi; see the file COPYING. If not, write to the Free + * Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. + * ---------------------------------------------------------------------- + * + */ + +#include "gnushogi.h" + +/* #define DONTUSE_HEURISTIC */ + +short *TrP; + +static struct leaf *node; +static short sqking, sqxking; +static short InCheck = false, GenerateAllMoves = false; +static short check_determined = false; + +static short INCscore = 0; + +short deepsearchcut = true; +short tas = false, taxs = false, ssa = false; + +short generate_move_flags = false; + + +/* + * Ply limits for deep search cut. No moves or drops flagged with "stupid" + * are considered beyond ply BEYOND_STUPID. Only moves or drops flagged + * with "kingattack" are considered beyond ply BEYOND_KINGATTACK. No moves + * or drops flagged with "questionable" are considered beyond ply + * BEYOND_QUESTIONABLE. Only moves or drops flagged with "tesuji" are + * considered beyond ply BEYOND_TESUJI. No drops are considered beyond ply + * BEYOND_DROP. Exceptions: moves or drops that prevent check or give + * check are always considered. + */ + +#define BEYOND_STUPID 0 +#define BEYOND_TIMEOUT 2 +#define BEYOND_KINGATTACK 6 +#define BEYOND_QUESTIONABLE 8 +#define BEYOND_TESUJI 8 +#define BEYOND_DROP 10 + +#ifdef DONTUSE_HEURISTIC +static short MaxNum[MAXDEPTH] = +{ + -1, 40, 80, 20, 40, 10, 5, 5, 5, 5, + 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, + 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, + 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, +}; +#endif + +#ifdef HASHKEYTEST +extern int CheckHashKey(); +extern char mvstr[4][6]; +#endif + + +/* + * Update Arrays board[] and color[] to reflect the new board + * position obtained after making the move pointed to by node. + */ + +inline static void +GenMakeMove(short side, + short f, + short t, + short *tempb, /* piece at to square */ + short *tempc, /* color of to square */ + short promote_piece) +{ + short piece, upiece, n; + + t = t & 0x7f; + + if (f > NO_SQUARES) + { + piece = f - NO_SQUARES; + + if (piece > NO_PIECES) + piece -= NO_PIECES; + + board[t] = piece; + color[t] = side; + n = (Captured[side][piece])--; + UpdateDropHashbd(side, piece, n); + UpdateHashbd(side, piece, -1, t); + UpdatePieceList(side, t, ADD_PIECE); + } + else + { + *tempb = board[t]; + *tempc = color[t]; + + if (*tempb != no_piece) + { + n = ++Captured[side][upiece = unpromoted[*tempb]]; + UpdateDropHashbd(side, upiece, n); + UpdateHashbd(*tempc, *tempb, -1, t); + UpdatePieceList(*tempc, t, REMOVE_PIECE); + } + + piece = board[f]; + Pindex[t] = Pindex[f]; + PieceList[side][Pindex[t]] = t; + color[f] = neutral; + board[f] = no_piece; + color[t] = side; + + if (promote_piece) + { + UpdateHashbd(side, piece, f, -1); + board[t] = promoted[piece]; + UpdateHashbd(side, board[t], -1, t); + } + else + { + board[t] = piece; + UpdateHashbd(side, piece, f, t); + } + } + +#ifdef HASHKEYTEST + if (CheckHashKey()) + { + algbr(f, t, 0); + printf("error in GenMakeMove: %s\n", mvstr[0]); + exit(1); + } +#endif +} + + + +/* + * Take back a move. + */ + +static void +GenUnmakeMove(short side, + short f, + short t, + short tempb, + short tempc, + short promote_piece) +{ + short piece, upiece, n; + + t = t & 0x7f; + + if (f > NO_SQUARES) + { + piece = f - NO_SQUARES; + + if (piece > NO_PIECES) + piece -= NO_PIECES; + + board[t] = no_piece; + color[t] = neutral; + n = ++Captured[side][piece]; + UpdateDropHashbd(side, piece, n); + UpdateHashbd(side, piece, -1, t); + UpdatePieceList(side, t, REMOVE_PIECE); + } + else + { + piece = board[t]; + color[t] = tempc; + board[t] = tempb; + Pindex[f] = Pindex[t]; + PieceList[side][Pindex[f]] = f; + + if (tempb != no_piece) + { + /* FIXME: make this next line a bit more reasonable... */ + n = (Captured[side][upiece = unpromoted[tempb]])--; + UpdateDropHashbd(side, upiece, n); + UpdateHashbd(tempc, tempb, -1, t); + UpdatePieceList(tempc, t, ADD_PIECE); + } + + color[f] = side; + + if (promote_piece) + { + UpdateHashbd(side, piece, -1, t); + board[f] = unpromoted[piece]; + UpdateHashbd(side, board[f], f, -1); + } + else + { + board[f] = piece; + UpdateHashbd(side, piece, f, t); + } + } + +#ifdef HASHKEYTEST + if (CheckHashKey()) + { + algbr(f, t, 0); + printf("error in GenUnmakeMove: %s\n", mvstr[0]); + exit(1); + } +#endif +} + + + +static void +gives_check_flag(unsigned short *flags, short side, short f, short t) +{ + short tempb, tempc, blockable, promote_piece; + promote_piece = (*flags & promote) != 0; + GenMakeMove(side, f, t, &tempb, &tempc, promote_piece); + + if (SqAttacked(sqxking, side, &blockable)) + *flags |= check; + + GenUnmakeMove(side, f, t, tempb, tempc, promote_piece); +} + + +inline static void +Link(short side, short piece, + short from, short to, unsigned short local_flag, short s) +{ + if (*TrP == TREE) + { + ShowMessage("TREE overflow\n"); + } + else + { + node->f = from; + node->t = (local_flag & promote) ? (to | 0x80) : to; + node->reply = 0; + node->flags = local_flag; + node->score = s; + node->INCscore = INCscore; + + if (GenerateAllMoves) + { + /* FIXME: gimme a break! */ + (*TrP)++, node++; + } + else if (InCheck) + { + /* only moves out of check */ + short tempb, tempc, sq, threat, blockable, promote_piece; + promote_piece = (node->flags & promote) != 0; + GenMakeMove(side, node->f, node->t, + &tempb, &tempc, promote_piece); + sq = (from == sqking) ? to : sqking; + threat = SqAttacked(sq, side ^ 1, &blockable); + GenUnmakeMove(side, node->f, node->t, + tempb, tempc, promote_piece); + + if (!threat) + { + /* FIXME! Gimme a break! */ + (*TrP)++, node++; + } + } + else if (flag.tsume) + { + /* only moves that give check */ + if (!(node->flags & check) && !check_determined) + { + /* determine check flag */ + gives_check_flag(&node->flags, side, node->f, node->t); + } + + if (node->flags & check) + { + /* FIXME! Gimme a break! */ + (*TrP)++, node++; + } + } + else + { + /* FIXME! Gimme a break! */ + (*TrP)++, node++; + } + } +} + + +inline int +PromotionPossible(short color, short f, short t, short p) +{ + if (color == black) + { + if ((f < 54) && (t < 54)) + return false; + } + else + { + if ((f > 26) && (t > 26)) + return false; + } + + /* FIXME: this can be simplified... */ + switch (p) + { + case pawn: + case lance: + case knight: + case silver: + case bishop: + case rook: + return true; + }; + + return false; +} + + +inline int +NonPromotionPossible(short color, short f, + short t, short p) +{ + switch (p) + { + case pawn : + if (color == black) + { + return ((t < 72) + ? true + : (generate_move_flags ? ILLEGAL_TRAPPED : false)); + } + else + { + return ((t > 8) + ? true + : (generate_move_flags ? ILLEGAL_TRAPPED : false)); + } + + case lance: + if (color == black) + { + return ((t < 72) + ? true + : (generate_move_flags ? ILLEGAL_TRAPPED : false)); + } + else + { + return ((t > 8) + ? true + : (generate_move_flags ? ILLEGAL_TRAPPED : false)); + } + + case knight: + if (color == black) + { + return ((t < 63) + ? true + : (generate_move_flags ? ILLEGAL_TRAPPED : false)); + } + else + { + return ((t > 17) + ? true + : (generate_move_flags ? ILLEGAL_TRAPPED : false)); + } + } + + return true; +} + + +#if defined FIELDBONUS || defined DROPBONUS + +/* bonus for possible next moves */ + +inline static short +field_bonus(short ply, short side, short piece, + short f, short t, unsigned short *local_flag) +{ + short s, u, ptyp; + unsigned char *ppos, *pdir; + short c1, c2; + +#ifdef SAVE_NEXTPOS + short d; +#endif + + c1 = side; + c2 = side ^ 1; + s = 0; + check_determined = true; + + ptyp = ptype[side][piece]; + +#ifdef SAVE_NEXTPOS + u = first_direction(ptyp, &d, t); +#else + ppos = (*nextpos[ptyp])[t]; + pdir = (*nextdir[ptyp])[t]; + u = ppos[t]; +#endif + + do + { + short coloru = color[u]; + + if (piece != king && GameCnt > 40) + { + if (distance(u, EnemyKing) <= 1) + { + /* can reach square near own king */ + s += 2; + *local_flag |= kingattack; + } + else if (distance(u, OwnKing) <= 1) + { + /* can reach square near enemy king */ + s++; + *local_flag |= kingattack; + } + } + + if (coloru == side) + { + /* impossible next move */ +#ifdef SAVE_NEXTPOS + u = next_direction(ptyp, &d, t); +#else + u = pdir[u]; +#endif + } + else + { + /* possible next move */ + if (PromotionPossible(side, t, u, piece)) + { + /* possible promotion in next move */ + if (piece == pawn) + { + s += 2; +#ifdef TESUJIBONUS + if (!InPromotionZone(side, t)) + { + *local_flag |= tesuji; /* The dangling pawn */ + s++; + } +#endif + } + else + { + s++; + } + } + + if (coloru == neutral) + { + /* next move to an empty square */ + if (u == FROMsquare) + { + /* opponent has just left this square */ + s++; + } + +#ifdef SAVE_NEXTPOS + u = next_position(ptyp, &d, t, u); +#else + u = ppos[u]; +#endif + } + else + { + /* attack opponents piece */ +#ifdef TESUJIBONUS + short boardu, upiece, rvupiece, rvuboard; +#endif + s++; + + if (u == TOsquare) /* opponent has moved to TOsquare */ + s++; + + if ((boardu = board[u]) == king) + { + s += 20; INCscore -= 18; + *local_flag |= check; /* move threatens + * opponents king */ + } + +#ifdef TESUJIBONUS + upiece = unpromoted[piece]; + rvupiece = relative_value[upiece]; + rvuboard = relative_value[unpromoted[boardu]]; + + if ((upiece == pawn) && (Captured[side][pawn] > 1)) + { + *local_flag |= tesuji; /* The joining pawn attack */ + s++; + } + + if (rvupiece <= rvuboard) + { + *local_flag |= tesuji; /* The striking pawn + * (piece) attack */ + + if (f > NO_SQUARES) + s += 2; + else + s++; + + if (upiece == pawn) + s++; + + /* CHECKME: is this right? */ + if (((rvupiece == rvuboard) && (upiece == pawn)) + || (upiece == bishop) || (upiece == knight)) + { + s++; /* The opposing pawn (piece) */ + + if (upiece == pawn) + s++; + } + } +#endif + +#ifdef SAVE_NEXTPOS + u = next_direction(ptyp, &d, t); +#else + u = pdir[u]; +#endif + } + } + } + while (u != t); + + INCscore += s; + + return s; +} + +#endif + + + + +/* + * Add a move to the tree. Assign a bonus to order the moves as follows: + * 1. Principle variation 2. Capture of last moved piece 3. Other captures + * (major pieces first) 4. Killer moves 5. Tesuji drops 6. Other Moves + * 7. Other drops. 8. Non-promoting moves + * If the flag.tsume is set, assign a high bonus for checks. + */ + +/* inline */ void +LinkMove(short ply, short f, + short t, + unsigned short local_flag, + short xside, + short score_if_impossible) +{ + short s = 0; + short side, piece, mv; + short flag_tsume, try_link = true; + short c1, c2, ds, is_drop = f > NO_SQUARES; + unsigned long as = 0; + + flag_tsume = flag.tsume; + + c1 = side = xside ^ 1; + c2 = xside; + + /* + * Is it determined whether the move gives check ? + */ + + check_determined = ((local_flag & check) != 0); + + mv = (f << 8) | ((local_flag & promote) ? (t | 0x80) : t); + + if (f > NO_SQUARES) + { + piece = f - NO_SQUARES; + + if (piece > NO_PIECES) + piece -= NO_PIECES; + } + else + { + piece = board[f]; + } + + if (score_if_impossible < 0) + { + /* The move is flagged as illegal. */ + Link(side, piece, + f, t, local_flag, score_if_impossible); + + return; + } + + INCscore = 0; + +#ifdef HISTORY + s += history[hindex(side, mv)]; +#endif + + /* If we're running short of tree nodes, go into tsume mode. */ + + if (!(local_flag & capture)) + { + if (*TrP > (TREE - 300)) + { + /* too close to tree table limit */ + flag.tsume = true; + } + } + + /* Guess strength of move and set flags. */ + + if ((piece != king) && (!in_opening_stage)) + { + if (distance(t, EnemyKing) <= 1) + { + /* bonus for square near enemy king */ + s += 15; + INCscore += 2; + local_flag |= kingattack; + } + else if (distance(t, OwnKing) <= 1) + { + /* bonus for square near own king */ + s += 10; + INCscore++; + local_flag |= kingattack; + } + } + + if (tas) /* own attack array available */ + { + /* square t defended by own piece (don't count piece to move) ? */ + if (is_drop + ? (as = attack[side][t]) + : (as = ((attack[side][t] & CNT_MASK) > 1))) + s += (ds = in_endgame_stage ? 100 : 10); + } + + if (taxs) /* opponents attack array available */ + { + /* square t not threatened by opponent or + * defended and only threatened by opponents king ? + */ + unsigned long axs; + + if (!(axs = attack[xside][t]) + || (tas && as && (axs & control[king]) && (axs & CNT_MASK) == 1)) + { + /* FIXME: this is a mess; clean up. */ + s += (ds = in_endgame_stage + ? 200 + : (is_drop + ? (InPromotionZone(side, t) + ? 40 + relative_value[piece] + : 10) + : 20)); + } + } + + /* target square near area of action */ + + if (TOsquare >= 0) + s += (9 - distance(TOsquare, t)); + + if (FROMsquare >= 0) + s += (9 - distance(FROMsquare, t)) / 2; + + /* target square near own or enemy king */ + + if (!in_opening_stage && piece != king) + { + if (balance[c1] < 50) + s += (9 - distance(EnemyKing, t)) * (50 - balance[c1]) / 20; + else + s += (9 - distance(OwnKing, t)) * (balance[c1] - 50) / 20; + } + + if (f > NO_SQUARES) + { + /* bonus for drops, in order to place + * drops before questionable moves */ + s += in_endgame_stage ? 25 : 10; + + if (t == FROMsquare) + { + /* drop to the square the opponent has just left */ + s += 5; + }; + + if (piece == gold) + s -= 32 / Captured[side][gold]; + else if (piece == silver) + s -= 16 / Captured[side][silver]; + +#if defined DROPBONUS + s += field_bonus(ply, side, piece, f, t, &local_flag); + + if (s == 10 && piece != pawn) + local_flag |= questionable; +#endif + } + else + { + /* bonus for moves (non-drops) */ + int consider_last = false; + + if (in_endgame_stage && Captured[side][gold]) + s += 10; + + s += 20; + + if (t == FROMsquare) + { + /* move to the square the opponent has just left */ + s += in_endgame_stage ? 10 : 1; + } + + if (color[t] != neutral) + { + /* Captures */ + if (in_endgame_stage) + { + s += relative_value[board[t]] - relative_value[piece]; + } + else + { + s += (*value)[stage][board[t]] - relative_value[piece]; + } + + if (t == TOsquare) /* Capture of last moved piece */ + s += in_endgame_stage ? 5 : 50; + } + + if (local_flag & promote) + { + /* bonus for promotions */ + s++; + INCscore += value[stage][promoted[piece]] - value[stage][piece]; + } + else + { + /* bonus for non-promotions */ + if (PromotionPossible(side, f, t, piece)) + { +#ifdef TESUJIBONUS + /* Look at non-promoting silver or knight */ + if (piece == silver || piece == knight) + { + local_flag |= tesuji; /* Non-promotion */ + s++; + } + else +#endif + { + consider_last = true; + + if (piece == pawn || piece == bishop || piece == rook) + { + local_flag |= stupid; + INCscore -= 20; + } + else + { + local_flag |= questionable; + INCscore -= 10; + } + } + } + } + + if (consider_last) + { + if (local_flag & stupid) + s = 0; + else + s = s % 20; + } + else + { +#if defined FIELDBONUS + s += field_bonus(ply, side, piece, f, t, &local_flag); +#endif + } + } + +#if defined CHECKBONUS + /* determine check flag */ + if (!(local_flag & check) && !check_determined) + { + gives_check_flag(&local_flag, side, f, t); + + if (local_flag & check) + s += 20; + } +#endif + + /* check conditions for deep search cut (flag.tsume = true) */ + +#ifdef DEEPSEARCHCUT + if (!flag.tsume && deepsearchcut) + { + if ((ply > BEYOND_STUPID) && (local_flag & stupid)) + { + try_link = flag.force || ((ply == 1) && (side != computer)); + } + else if (hard_time_limit && (ply > BEYOND_TIMEOUT) && flag.timeout) + { + flag.tsume = true; + } + else if ((ply > BEYOND_KINGATTACK) && !(local_flag & kingattack)) + { + flag.tsume = true; + } + else if ((ply > BEYOND_QUESTIONABLE) && (local_flag & questionable)) + { + flag.tsume = true; +#ifdef TESUJIBONUS + } + else if ((ply > BEYOND_TESUJI) && !(local_flag & tesuji)) + { + flag.tsume = true; +#endif + } + else if ((ply > BEYOND_DROP) && (f > NO_SQUARES)) + { + flag.tsume = true; + } + } +#endif + + if (try_link || GenerateAllMoves) + { + Link(side, piece, f, t, local_flag, + s - ((SCORE_LIMIT + 1000) * 2)); + } + + flag.tsume = flag_tsume; +} + + + +short +DropPossible(short piece, short side, short sq) +{ + short r = row(sq), possible = true; + + if (board[sq] != no_piece) + { + possible = false; + } + else if (piece == pawn) + { + if ((side == black) && (r == 8)) + { + possible = (generate_move_flags ? ILLEGAL_TRAPPED : false); + } + else if ((side == white) && (r == 0)) + { + possible = (generate_move_flags ? ILLEGAL_TRAPPED : false); + } + else if (PawnCnt[side][column(sq)]) + { + possible = (generate_move_flags ? ILLEGAL_DOUBLED : false); + } + + /* Pawn drops are invalid if they mate the opponent. */ + if (possible) + { + short f, tempb, tempc; + f = pawn + NO_SQUARES; + + if (side == white) + f += NO_PIECES; + + GenMakeMove(side, f, sq, &tempb, &tempc, false); + + if (IsCheckmate(side^1, -1, -1)) + possible = (generate_move_flags ? ILLEGAL_MATE : false); + + GenUnmakeMove(side, f, sq, tempb, tempc, false); + } + } + else if (piece == lance) + { + if ((side == black) && (r == 8)) + possible = (generate_move_flags ? ILLEGAL_TRAPPED : false); + else if ((side == white) && (r == 0)) + possible = (generate_move_flags ? ILLEGAL_TRAPPED : false); + } + else if (piece == knight) + { + if ((side == black) && (r >= 7)) + possible = (generate_move_flags ? ILLEGAL_TRAPPED : false); + else if ((side == white) && (r <= 1)) + possible = (generate_move_flags ? ILLEGAL_TRAPPED : false); + } + + return possible; +} + + +#if defined DONTUSE_HEURISTIC +static void +SortMoves(short ply) +{ + short p; + + for (p = TrPnt[ply]; p < TrPnt[ply+1]; p++) + pick(p, TrPnt[ply+1] - 1); +} +#endif /* DONTUSE_HEURISTIC */ + + +#ifdef DONTUSE_HEURISTIC + +static void +DontUseMoves(short ply, short n) +{ + struct leaf *p; + short i, k; + + /* k = number of check moves + number of captures */ + for (i = TrPnt[ply], k = 0; i < TrPnt[ply+1]; i++) + { + p = &Tree[i]; + + if ((p->flags & check) || (p->flags & capture)) + { + if (++k >= n) + return; + } + } + + /* use n moves */ + for (i = TrPnt[ply]; i < TrPnt[ply+1]; i++) + { + p = &Tree[i]; + + if (!((p->flags & check) || (p->flags & capture))) + { + if (k < n) + k++; + else + { + p->score = DONTUSE; + } + } + } +} + +#endif + + + +/* + * Generate moves for a piece. The moves are taken from the precalculated + * array nextpos/nextdir. If the board is free, next move is chosen from + * nextpos else from nextdir. + */ + +inline void +GenMoves(short ply, short sq, short side, + short xside) +{ + short u, piece; + short ptyp, possible; +#ifdef SAVE_NEXTPOS + short d; +#else + unsigned char *ppos, *pdir; +#endif + + piece = board[sq]; + ptyp = ptype[side][piece]; + +#ifdef SAVE_NEXTPOS + u = first_direction(ptyp, &d, sq); +#else + ppos = (*nextpos[ptyp])[sq]; + pdir = (*nextdir[ptyp])[sq]; + u = ppos[sq]; +#endif + + do + { + unsigned short local_flag; + short c; + + if ((c = color[u]) == xside) + local_flag = capture; + else + local_flag = 0; + + if (c != side && board[u] != king) + { + if (PromotionPossible(color[sq], sq, u, piece)) + { + LinkMove(ply, sq, u, local_flag | promote, xside, true); + + if ((possible + = NonPromotionPossible(color[sq], sq, u, piece))) + { + LinkMove(ply, sq, u, local_flag, xside, possible); + } + } + else + { + LinkMove(ply, sq, u, local_flag, xside, true); + } + } + + if (c == neutral) +#ifdef SAVE_NEXTPOS + { + u = next_position(ptyp, &d, sq, u); + } + else + { + u = next_direction(ptyp, &d, sq); + } +#else + { + u = ppos[u]; + } + else + { + u = pdir[u]; + } +#endif + } + while (u != sq); +} + + + + +/* + * Drop each piece in hand of "side" to square "u" (if allowed). + */ + +static void +DropToSquare(short side, short xside, short ply, short u) +{ + short i, possible; + + for (i = pawn; i < king; i++) + { + if (Captured[side][i]) + { + if ((possible = DropPossible(i, side, u))) + { + short f; + f = NO_SQUARES + i; + + if (side == white) + f += NO_PIECES; + + LinkMove(ply, f, u, (dropmask | i), xside, possible); + } + } + } +} + + + +/* + * Add drops of side that prevent own king from being in check + * from xside's sweeping pieces. + */ + +static void +LinkPreventCheckDrops(short side, short xside, short ply) +{ +#ifdef SAVE_NEXTPOS + short d, dd; +#else + unsigned char *ppos, *pdir; +#endif + short piece, u, xu, square, ptyp; + short n, drop_square[9]; + + if (board[square = PieceList[side][0]] != king) + return; + + for (piece = lance; piece <= rook; piece++) + { + if (piece == lance || piece == bishop || piece == rook) + { + /* check for threat of xside piece */ + ptyp = ptype[side][piece]; + n = 0; +#ifdef SAVE_NEXTPOS + u = first_direction(ptyp, &d, square); +#else + ppos = (*nextpos[ptyp])[square]; + pdir = (*nextdir[ptyp])[square]; + u = ppos[square]; +#endif + + do + { + if (color[u] == neutral) + { +#ifdef SAVE_NEXTPOS + dd = d; + xu = next_position(ptyp, &d, square, u); + + if (xu == next_direction(ptyp, &dd, square)) + { + n = 0; /* oops new direction */ + } + else + { + drop_square[n++] = u; + } +#else + + if ((xu = ppos[u]) == pdir[u]) + { + n = 0; /* oops new direction */ + } + else + { + drop_square[n++] = u; + } +#endif + u = xu; + } + else + { + if (color[u] == xside && (unpromoted[board[u]] == piece)) + { + /* king is threatened by opponents piece */ + while (n > 0) + { + DropToSquare(side, xside, ply, drop_square[--n]); + } + } + else + { + n = 0; + } +#ifdef SAVE_NEXTPOS + u = next_direction(ptyp, &d, square); +#else + u = pdir[u]; +#endif + } + } + while (u != square); + } + } +} + + + +/* + * Add drops that check enemy king. + */ + +static void +LinkCheckDrops(short side, short xside, short ply) +{ +#ifdef SAVE_NEXTPOS + short d; +#else + unsigned char *ppos, *pdir; +#endif + short u, ptyp; + short square, piece; + + if (board[square = PieceList[xside][0]] != king) + return; + + for (piece = pawn; piece < king; piece++) + { + if (Captured[side][piece]) + { + /* + * "side" has "piece" in hand. Try to make a piece move from + * opponents king square and drop this piece to each reachable + * empty square. This definitely gives check! For a pawn drop + * it must not double pawns and it must not be checkmate! + */ + + ptyp = ptype[xside][piece]; +#ifdef SAVE_NEXTPOS + u = first_direction(ptyp, &d, square); +#else + ppos = (*nextpos[ptyp])[square]; + pdir = (*nextdir[ptyp])[square]; + u = ppos[square]; +#endif + do + { + if (color[u] == neutral) + { + if (piece != pawn || DropPossible(pawn, side, u)) + { + short f; + f = NO_SQUARES + piece; + + if (side == white) + f += NO_PIECES; + + LinkMove(ply, f, u, + (dropmask | piece | check), xside, true); + } + +#ifdef SAVE_NEXTPOS + u = next_position(ptyp, &d, square, u); +#else + u = ppos[u]; +#endif + } + else + { +#ifdef SAVE_NEXTPOS + u = next_direction(ptyp, &d, square); +#else + u = pdir[u]; +#endif + } + } + while (u != square); + } + } +} + + + +/* + * Fill the array Tree[] with all available moves for side to play. Array + * TrPnt[ply] contains the index into Tree[] of the first move at a ply. + * in_check = 0 side is not in check + * in_check > 1 side is in check + * in_check < 0 don't know + * in_check -2 indicates move generation for book moves + */ + +void +MoveList(short side, short ply, + short in_check, short blockable) +{ + short i, xside, u; + struct leaf *firstnode; + short flag_tsume, num; + +#ifdef HISTORY + unsigned short hiHt = 0, hi0 = 0, hi1 = 0, hi2 = 0, hi3 = 0, hi4 = 0; +#endif + + flag_tsume = flag.tsume; + + xside = side ^ 1; + + sqking = PieceList[side][0]; + sqxking = PieceList[xside][0]; + + if (in_check >= 0) + { + InCheck = in_check; + } + else + { + InCheck = (board[sqking] == king) + ? SqAttacked(sqking, xside, &blockable) + : false; + } + + GenerateAllMoves = (in_check == -2) || generate_move_flags; + + if (InCheck /* && (ply > 1 || side == computer) */) + { + /* Own king in check */ + flag.tsume = true; + } + + TrP = &TrPnt[ply + 1]; + *TrP = TrPnt[ply]; + + firstnode = node = &Tree[*TrP]; + + if (!PV) + Swag0 = killr0[ply]; + else + Swag0 = PV; + + Swag1 = killr1[ply]; + Swag2 = killr2[ply]; + Swag3 = killr3[ply]; + + if (ply > 2) + Swag4 = killr1[ply - 2]; + else + Swag4 = 0; + +#ifdef HISTORY + if (use_history) + { + history[hiHt = hindex(side, SwagHt)] += 5000; + history[hi0 = hindex(side, Swag0)] += 2000; + history[hi1 = hindex(side, Swag1)] += 60; + history[hi2 = hindex(side, Swag2)] += 50; + history[hi3 = hindex(side, Swag3)] += 40; + history[hi4 = hindex(side, Swag4)] += 30; + } +#endif + + for (i = PieceCnt[side]; i >= 0; i--) + GenMoves(ply, PieceList[side][i], side, xside); + + if (!InCheck || blockable) + { + if (flag.tsume) + { + /* special drop routine for tsume problems */ + if (InCheck) + LinkPreventCheckDrops(side, xside, ply); + else + LinkCheckDrops(side, xside, ply); + } + else + { + for (u = 0; u < NO_SQUARES; u++) + DropToSquare(side, xside, ply, u); + } + } + +#ifdef HISTORY + if (use_history) + { + history[hiHt] -= 5000; + history[hi0] -= 2000; + history[hi1] -= 60; + history[hi2] -= 50; + history[hi3] -= 40; + history[hi4] -= 30; + } +#endif + + SwagHt = 0; /* SwagHt is only used once */ + + if (flag.tsume && node == firstnode) + (*TrP)++; + + GenCnt += (num = (TrPnt[ply+1] - TrPnt[ply])); + +#ifdef DONTUSE_HEURISTIC + /* remove some nodes in case of wide spread in depth */ + if (!flag.tsume && (i = MaxNum[ply]) > 0 && num > i) + { + SortMoves(ply); + DontUseMoves(ply, i); + } +#endif + + flag.tsume = flag_tsume; +} + + + +/* + * Fill the array Tree[] with all available captures for side to play. If + * there is a non-promote option, discard the non-promoting move. Array + * TrPnt[ply] contains the index into Tree[] of the first move at a ply. + * If flag.tsume is set, only add captures (but also the non-promoting) + * that threaten the opponents king. + * + * in_check = 0: side is not in check + * in_check > 1: side is in check + * in_check < 0: we don't know + */ + +void +CaptureList(short side, short ply, + short in_check, short blockable) +{ + short u, sq, xside; +#ifdef SAVE_NEXTPOS + short d; +#else + unsigned char *ppos, *pdir; +#endif + short i, piece, flag_tsume; + small_short *PL; + + xside = side ^ 1; + + TrP = &TrPnt[ply + 1]; + *TrP = TrPnt[ply]; + node = &Tree[*TrP]; + + flag_tsume = flag.tsume; + + sqking = PieceList[side][0]; + sqxking = PieceList[xside][0]; + + if (in_check >= 0) + { + InCheck = in_check; + } + else + { + InCheck = (board[sqking] == king) + ? SqAttacked(sqking, xside, &blockable) + : false; + } + + GenerateAllMoves = (in_check == -2); + + if (InCheck && (ply > 1 || side == computer)) + { + /* Own king is in check */ + flag.tsume = true; + } + + check_determined = false; + + PL = PieceList[side]; + + for (i = 0; i <= PieceCnt[side]; i++) + { + short ptyp; + sq = PL[i]; + piece = board[sq]; + ptyp = ptype[side][piece]; +#ifdef SAVE_NEXTPOS + u = first_direction(ptyp, &d, sq); +#else + ppos = (*nextpos[ptyp])[sq]; + pdir = (*nextdir[ptyp])[sq]; + u = ppos[sq]; +#endif + do + { + if (color[u] == neutral) + { +#ifdef SAVE_NEXTPOS + u = next_position(ptyp, &d, sq, u); +#else + u = ppos[u]; +#endif + } + else + { + if (color[u] == xside && board[u] != king) + { + short PP; + + if ((PP = PromotionPossible(color[sq], sq, u, piece))) + { + Link(side, piece, + sq, u, capture | promote, + (*value)[stage][board[u]] +#if !defined SAVE_SVALUE + + svalue[board[u]] +#endif + - relative_value[piece]); + } + + if (!PP || flag.tsume) + { + Link(side, piece, + sq, u, capture, + (*value)[stage][board[u]] +#if !defined SAVE_SVALUE + + svalue[board[u]] +#endif + - relative_value[piece]); + } + } + +#ifdef SAVE_NEXTPOS + u = next_direction(ptyp, &d, sq); +#else + u = pdir[u]; +#endif + } + } + while (u != sq); + } + + flag.tsume = flag_tsume; + + SwagHt = 0; /* SwagHt is only used once */ +} + + + + +/* + * If the king is in check, try to find a move that prevents check. + * If such a move is found, return false, otherwise return true. + * in_check = 0: side is not in check + * in_check > 1: side is in check + * in_check < 0: don't know + * blockable > 0 && check: check can possibly be prevented by a drop + * blockable = 0 && check: check can definitely not be prevented by a drop + * blockable < 0 && check: nothing known about type of check + */ + +short +IsCheckmate(short side, short in_check, short blockable) +{ + short u, sq, xside; +#ifdef SAVE_NEXTPOS + short d; +#else + unsigned char *ppos, *pdir; +#endif + short i, piece; + small_short *PL; + short tempb, tempc, ksq, threat, dummy, sqking; + short InCheck; + + xside = side ^ 1; + + sqking = PieceList[side][0]; + + /* + * Checkmate is possible only if king is in check. + */ + + if (in_check >= 0) + InCheck = in_check; + else if (board[sqking] == king) + InCheck = SqAttacked(sqking, xside, &blockable); + else + InCheck = false; + + if (!InCheck) + return false; + + /* + * Try to find a move that prevents check. + */ + + PL = PieceList[side]; + + for (i = 0; i <= PieceCnt[side]; i++) + { + short ptyp; + sq = PL[i]; + piece = board[sq]; + ptyp = ptype[side][piece]; +#ifdef SAVE_NEXTPOS + u = first_direction(ptyp, &d, sq); +#else + ppos = (*nextpos[ptyp])[sq]; + pdir = (*nextdir[ptyp])[sq]; + u = ppos[sq]; +#endif + do + { + if (color[u] == neutral || color[u] == xside) + { + GenMakeMove(side, sq, u, &tempb, &tempc, false); + ksq = (sq == sqking) ? u : sqking; + threat = SqAttacked(ksq, xside, &dummy); + GenUnmakeMove(side, sq, u, tempb, tempc, false); + + if (!threat) + return false; + } + +#ifdef SAVE_NEXTPOS + u = (color[u] == neutral) + ? next_position(ptyp, &d, sq, u) + : next_direction(ptyp, &d, sq); +#else + u = (color[u] == neutral) ? ppos[u] : pdir[u]; +#endif + } + while (u != sq); + } + + /* + * Couldn't find a move that prevents check. + * Try to find a drop that prevents check. + */ + + if (blockable != 0) + { + for (piece = king - 1; piece >= pawn; piece--) + { + if (Captured[side][piece]) + { + for (u = 0; u < NO_SQUARES; u++) + { + if (DropPossible(piece, side, u)) + { + short f; + f = NO_SQUARES + piece; + + if (side == white) + f += NO_PIECES; + + GenMakeMove(side, f, u, &tempb, &tempc, false); + threat = SqAttacked(sqking, xside, &dummy); + GenUnmakeMove(side, f, u, tempb, tempc, false); + + if (!threat) + return false; + } + } + + /* + * If the piece could be dropped at any square, it is + * impossible for any other piece drop to prevent check. + * Drops are restricted for pawns, lances, and knights. + */ + + if (piece > knight) + break; + } + } + } + + return true; + +} + +