/* * CHEST, chess analyst. For Copyright notice read file "COPYRIGHT". * * $Source: /home/heiner/ca/chest/RCS/fac.c,v $ * $Id: fac.c,v 3.11 1999/07/20 21:01:56 heiner Exp $ * * Answer heuristic "fatal anti-check" */ #include "types.h" #include "board.h" #include "output.h" #include #include "fac.h" #if PROD_LEV # define FAC_STATS 0 #else # ifndef FAC_STATS # define FAC_STATS 1 /* CF: turn on/off statistics */ # endif #endif #undef THIS_STATS #define THIS_STATS FAC_STATS #include "statsupp.h" static Move last_found = {NO_POS, NO_POS, no_figure, -1, 0}; Eximpl Flag fac_has_guess = FALSE; static int8 guess_credit = 0; static int8 guess_newcredit = 1; Eximpl Counter sc_fackm_used; /* incremented in analyse.c */ #if FAC_STATS static Counter sc_fac_called; static Counter sc_fac_scans; static Counter sc_fac_cktests; static Counter sc_fac_success; static Counter sc_fact_called; static Counter sc_fact_cand; static Counter sc_fact_success; static Counter sc_fackm_called; static Counter sc_fackm_chk; static Counter sc_fackm_scans; static Counter sc_fackm_dirs; /* Counter sc_fackm_used; */ static Counter sc_nak_called; static Counter sc_nak_success; static Counter sc_nak_indir; static Counter sc_smtfac_called; static Counter sc_smtfac_success; #endif /* ! FAC_STATS */ Eximpl void /* ARGSUSED */ fac_stats(Bool doprint) { #if FAC_STATS if (doprint && f_stats) { if (sc_fac_called) { printf("fac :"); show_scs(1, 9, sc_fac_called, " calls,"); show_scs(1, 0, sc_fac_scans, " scans,"); show_scs(1, 0, sc_fac_cktests, " ck,"); show_scs(1, 0, sc_fac_success, " success"); printf(" (%.1f%%)\n", percent(sc_fac_success, sc_fac_called)); } if (sc_fact_called) { printf("fact :"); show_scs(1, 9, sc_fact_called, " calls,"); show_scs(1, 0, sc_fact_cand, " candidates,"); show_scs(1, 0, sc_fact_success, " success"); printf(" (%.1f%%)\n", percent(sc_fact_success, sc_fact_called)); } if (sc_fackm_called) { printf("fackm:"); show_scs(1, 9, sc_fackm_called, " calls,"); show_scs(1, 0, sc_fackm_chk, " inchk,"); show_scs(1, 0, sc_fackm_scans, " scans,"); show_scs(1, 0, sc_fackm_dirs, " dirs\n"); show_scs(7, 9, sc_fackm_used, " used"); printf(" [%.2f]\n", fraction(sc_fackm_used, sc_fackm_called)); } if (sc_nak_called) { printf("naked:"); show_scs(1, 9, sc_nak_called, " calls,"); show_scs(1, 0, sc_nak_indir, " indir,"); show_scs(1, 0, sc_nak_success, " success"); printf(" (%.1f%%)\n", percent(sc_nak_success, sc_nak_called)); } if (sc_smtfac_called) { printf("smtfac:"); show_scs(0, 9, sc_smtfac_called, " calls,"); show_scs(1, 0, sc_smtfac_success, " success"); printf(" (%.1f%%)\n", percent(sc_smtfac_success, sc_smtfac_called)); } } sc_fac_called = 0; sc_fac_scans = 0; sc_fac_cktests = 0; sc_fac_success = 0; sc_fact_called = 0; sc_fact_cand = 0; sc_fact_success = 0; sc_fackm_called = 0; sc_fackm_chk = 0; sc_fackm_scans = 0; sc_fackm_dirs = 0; sc_fackm_used = 0; sc_nak_called = 0; sc_nak_success = 0; sc_nak_indir = 0; sc_smtfac_called = 0; sc_smtfac_success = 0; #endif /* FAC_STATS */ last_found.m_from = NO_POS; fac_has_guess = FALSE; guess_credit = 0; guess_newcredit = 1; } #if !PROD_LEV && 0 /* CF: local debugging */ # define XDB(lv,x) if( f_xdebug < (lv) );else { x } #else # define XDB(lv,x) /* empty */ #endif /* * In the specified board there has been computed * the specified list of defender moves. * These are intended as answers for a 2-mate. * Scan those moves and try to find a move for which we here * can guarantee that there will not be possible any 1-mate after it. * * This is the case when the defender has a move that does check, * (which restricts the set of legal reactions of the attacker), * and all possible reactions of the attacker cannot mate * (perhaps not even say check). * * A pointer to a move with the wanted property is returned, or 0. */ Eximpl const Move * find_fac_inlist( register Xconst Board * bp, register const Movelist * lp) { register const Move *p; register Xconst Field *fp; register Xconst Field *tp; register Xconst Field *xp; const Field *orgtp; register int dir; register int delta; Colour def; Colour att; Position defkpos; Position attkpos; register Xconst Field *dkp; Xconst Field *akp; PieceSet amask; PieceSet dmask; PieceSet nonkamask; PieceSet effamask; register rPieceSet atts; int aidx; const Field *dontmove; Figure f; Bool dckunpinnable; scinc(sc_fac_called); XDB(1, printf("> fac: list length = %d\n", list_length(lp)); ) if (empty_list(lp)) { goto fail; /* cannot find a move in empty list */ } /* When checking the attacker, he might well move his king. When such a * king move (which cannot be a castling) can be a mate move, we here * loose. * * It cannot be a mate move, when (a) it can impossibly be a check move, as * there is no relation between the kings. (b) there is a relation, * but not yet any attacker behind the attackers king to be opened for a * check. Opening can involve the attackers K and some defenders piece. * * If being forced to react with beat or block of a checker in order to * achieve a mate, then there are two chances to check: (1) the * beat/block might check directly, possibly because the defender moved * away. (2) the beat/block might check indirectly, by moving away * himself, and possible also by moving away the defender. */ def = bp->b_tomove; att = opp_colour(def); defkpos = K_POS(bp, def); attkpos = K_POS(bp, att); dkp = &(bp->b_f[defkpos]); akp = &(bp->b_f[attkpos]); amask = COLOUR_MASK(att); dmask = COLOUR_MASK(def); /* Consider checks by moving the attackers king away: */ dontmove = (Field *) 0; dir = att_dir(defkpos, attkpos); if (dam_dir(dir)) { if ((F_DATT(akp) | F_IATT(akp)) & amask) { /* Moving the attK may open an check. */ fp = dkp; delta = dam_mov[dir]; while ((fp += delta) != akp) { if (fp->f_c == empty) { continue; } if (fp->f_c == att) { /* There is an attacker between them Ks. This field * cannot be made empty by moving the attK, nor by moving * some defender (except e.p.). */ goto scan; } /* Found a defender between them kings. At most this one and * the K may go away: */ if (F_IATT(fp) & F_DATT(akp) & amask) { dontmove = fp; /* could be better */ } goto scan; } /* Up to the attK there were empty. */ do { fp += delta; } while (fp->f_c == empty); if (fp->f_c == def) { if (F_DATT(fp) & F_IATT(akp) & amask) { dontmove = fp; } goto scan; /* cf. explanation above */ } if (fp->f_c == att) { if (F_IATT(dkp) & SET1(fp->f_idx)) { goto fail; } } } } /* When the defender doesn't move "dontmove", then moving the attackers * king cannot check the defenders king. */ scan:; /* enough info collected, scan the move list: */ scinc(sc_fac_scans); XDB(1, if (dontmove) { printf("= fac: dontmove "); put_position(pos64_pos[dontmove->f_pos64]); printf("\n"); } ) nonkamask = amask & ~BOTH_KINGS; formoves(lp, p) { fp = &(bp->b_f[p->m_from]); if ((fp == dkp) /* too complex for now */ ||(fp == dontmove)) { continue; } XDB(2, printf("- fac: consider "); put_move(bp, p); ) /* Consider indirect checks: */ if (F_IATT(akp) & F_DATT(fp) & dmask) { dir = att_dir(fp, akp); if (dam_dir(dir) && (dir != att_dir(p->m_to, attkpos))) { delta = dam_mov[dir]; tp = fp; do { tp -= delta; } while (tp->f_c == empty); if ((tp->f_c == def) && (F_IATT(akp) & SET1(tp->f_idx))) { if ((fp->f_f == bauer) && ((p->m_to - p->m_from) == (2 * bau_mov[def]))) { continue; /* might enable e.p. */ } goto tst_ckpath; } } } /* Consider direct checks: */ if ((f = fp->f_f) == bauer) { /* must not do e.p. */ if ((p->m_to - bau_mov[def]) == bp->b_ep) { continue; } if ((p->m_to - p->m_from) == (2 * bau_mov[def])) { continue; /* might enable e.p. */ } f = p->m_fig; /* resulting figure */ } switch (f) { case koenig: /* too complex for now */ default: continue; /* not recognized */ case bauer: delta = attkpos - p->m_to; if ((delta != bau_left[def]) && (delta != bau_right[def])) { continue; /* does not check */ } /* "delta" now guaranteed to be a single-step one */ tp = &(bp->b_f[p->m_to]); break; case springer: if (!spr_dir(dir = att_dir(p->m_to, attkpos))) { continue; /* does not check */ } delta = spr_mov[dir - MIN_S_DIR]; tp = &(bp->b_f[p->m_to]); break; /* check back-checks */ case laeufer: if (!lfr_dir(dir = att_dir(p->m_to, attkpos))) { continue; /* does not check */ } goto ltd; case turm: if (!trm_dir(dir = att_dir(p->m_to, attkpos))) { continue; /* does not check */ } goto ltd; case dame: if (!dam_dir(dir = att_dir(p->m_to, attkpos))) { continue; /* does not check */ } ltd: ; delta = dam_mov[dir]; tp = &(bp->b_f[p->m_to]); xp = tp; do { xp += delta; } while (xp->f_c == empty); if (xp != akp) { continue; /* does not check */ } break; /* check back-checks */ } tst_ckpath:; scinc(sc_fac_cktests); /* Now we know, that this defender's move does check. The checker is * at "tp", and the path is scanned by "delta" steps. As moving the * attackers king cannot open a check, his only chance to check is * via beat or block. Thus we scan the check path to assure that such * a reaction is not possible or not fatal. * * When the checking defender (at "tp") is unpinnable, we even know that * blocking moves with direct check only cannot be a mate (as "tp" * could beat the blocker). * * Note: the (attacker's) move to be considered would be executed with * the defenders move already executed. */ XDB(1, printf("= fac: test ck path for "); put_move(bp, p); ) effamask = nonkamask; xp = &(bp->b_f[p->m_to]); if (xp->f_c == att) { effamask &= ~SET1(xp->f_idx); /* beaten */ } dckunpinnable = (!dam_dir(dir = att_dir(dkp, tp)) || (tp[dam_mov[dir]].f_c == border) ); orgtp = tp; do { /* while( (tp += delta) != akp ) */ atts = 0; /* In 'atts' construct the set of pieces, which may move to this * 'tp' field on the check path, thus blocking (or beating) the * checking defender. * * FFS: we should exclude B-attacks except for 'orgtp'. */ /* test for B moves not indicated by attacks: */ if (tp != orgtp) { xp = tp - bau_mov[att]; if ((xp->f_f == bauer) && (xp->f_c == att)) { atts |= SET1(xp->f_idx); /* fake for B-move */ } else if ((xp->f_c == empty) || (xp == fp)) { xp -= bau_mov[att]; if ((xp->f_f == bauer) && (xp->f_c == att) && (LIN64(xp->f_pos64) == BAS_LIN(att)) ) { atts |= SET1(xp->f_idx); /* for B-move */ } } } /* Due to removal of piece at "fp", some attacks can be opened: */ if (dam_dir(att_dir(fp, tp))) { atts |= (F_IATT(tp) & F_DATT(fp)); } atts |= F_DATT(tp); /* datt indicates move possibilities */ atts &= effamask; XDB(1, printf("- fac: atts = %8x @ ", atts); put_position(pos64_pos[tp->f_pos64]); printf("\n"); ) if (atts) { /* Those attackers have a chance to come here and say check * either directly or indirectly. */ dir = att_dir(tp, dkp); /* chances for direct check */ aidx = 0; do { /* while( (aidx += 1), (atts >>= 1) ) */ while (!(atts & 01)) { register int zeroes; zeroes = MIN_LOW_ZERO(atts); atts >>= zeroes; aidx += zeroes; } xp = &(bp->b_f[bp->b_piece[aidx]]); XDB(1, printf(" fac: test check from "); put_position(pos64_pos[xp->f_pos64]); printf("; dir=%d, fig=%d\n", dir, xp->f_f); ) if ((xp->f_f == bauer) && (tp != orgtp) && lfr_dir(att_dir(xp, tp))) { continue; /* B cannot beat to empty field */ } /* xp -> tp checking indirect is fatal */ if ((xp->f_f != dame) && dam_dir(att_dir(xp, dkp))) { if (att_dir(fp, dkp) == att_dir(xp, dkp)) { /* FFS: should be sharper */ goto this_fails; /* might also open; lazy */ } else { if (F_DATT(xp) & F_IATT(dkp) & amask) { goto this_fails; } } } /* xp -> tp checking direct may be fatal */ if ((tp != orgtp) && dckunpinnable) { continue; /* blocker cannot mate directly */ } switch (xp->f_f) { case bauer: /* attack implies beat only */ if (F_DATT(tp) & SET1(aidx)) { if (tp != orgtp) { break; /* cannot beat to empty */ } } else { if (tp == orgtp) { break; /* cannot move to non-empty */ } } if (LIN64(tp->f_pos64) == PROM_LIN(att)) { if (!no_dir(dir)) { goto this_fails; /* some promotion */ } } else { if (lfr_dir(dir) && (((tp + bau_right[att]) == dkp) || ((tp + bau_left[att]) == dkp) ) ) { goto this_fails; } } break; case springer: if (spr_dir(dir)) { goto this_fails; } break; case laeufer: if (lfr_dir(dir)) { goto this_fails; } break; case turm: if (trm_dir(dir)) { goto this_fails; } break; case dame: if (dam_dir(dir)) { goto this_fails; } break; default: goto this_fails; } } while ((aidx += 1), (atts >>= 1)); } } while ((tp += delta) != akp); if (tp == akp) { /* Well, the check path is scanned. No checking chances found, * thus we are happy to announce a "fatal anti-check": */ scinc(sc_fac_success); XDB(1, printf("< fac:+ finds "); put_move(bp, p); ) if ((orgtp + delta) == akp) { /* only near check's */ last_found = *p;/* note this success for later */ fac_has_guess = TRUE; /* to save procedure calls */ guess_credit = guess_newcredit; } return (p); } this_fails:; } /* formoves */ fail:; XDB(1, printf("< fac:-\n"); ) return (Move *) 0; /* failure, nothing found */ } /* * As it turns out, the output of "find_fac_inlist()" tends to * be the same move, again and again. * As the complete move list is computed and scanned for that approach, * here is another one, that gets a guess (based on the recent success), * and tries to verify that the guess is a legal move * and also a fatal anti-check. * If we here do not succeed this may be due to lazyness. * * The situation is the same as above: the defender is to move, * the attacker has just executed his 2-mate candidate. * * Note, that the presented move must either have been generated by * a move generator (has been legal at some time), * or contain a NO_POS as "m_from". * Other values are considered to be in range. * * When a NIL move pointer is handed in, we use the last success * found in a list by "find_fac_inlist()". */ Eximpl Bool is_fac_and_legal( register Xconst Board * bp, register const Move * mp) { register Xconst Field *fp; register Xconst Field *tp; register Xconst Field *xp; register int dir; Colour def; Colour att; register Xconst Field *dkp; register Xconst Field *akp; PieceSet nonkamask; scinc(sc_fact_called); XDB(1, printf("> fact\n"); ) if (mp == (Move *) 0) { mp = &last_found; } if (no_pos(mp->m_from)) { goto fail; } def = bp->b_tomove; fp = &(bp->b_f[mp->m_from]); if ((fp->f_c != def) || (fp->f_idx != mp->m_idx)) { goto fail; /* that piece not there any more */ } scinc(sc_fact_cand); XDB(1, printf(" fact cand "); put_move(bp, mp); ) att = opp_colour(def); dkp = K_FP(bp, def); akp = K_FP(bp, att); nonkamask = COLOUR_MASK(att) & ~SET1(akp->f_idx); if (F_DATT(dkp) & nonkamask) { goto fail; /* currently in check; legality too complex */ } /* Test, whether legal. Test whether checks directly to the attackers * king. */ tp = &(bp->b_f[mp->m_to]); dir = att_dir(tp, akp); { register int delta; switch (fp->f_f) { case bauer: /* FFS, not yet */ case koenig: /* too complex */ default: goto fail; case springer: if (!spr_dir(dir)) { goto fail; } delta = spr_mov[dir - MIN_S_DIR]; break; case laeufer: if (!lfr_dir(dir)) { goto fail; } delta = dam_mov[dir]; break; case turm: if (!trm_dir(dir)) { goto fail; } delta = dam_mov[dir]; break; case dame: if (!dam_dir(dir)) { goto fail; } delta = dam_mov[dir]; break; } if (!(F_DATT(tp) & SET1(fp->f_idx)) || (tp->f_c == def)) { goto fail; } XDB(1, printf(": fact tp ok\n"); ) if ((tp + delta) != akp) { goto fail; } XDB(1, printf(": fact near\n"); ) } if (dam_dir(att_dir(fp, dkp))) { if (F_DATT(fp) & F_IATT(dkp) & nonkamask) { goto fail; /* might be pinned */ } } XDB(1, printf(": fact unpinned\n"); ) /* That piece is still at the old place. It can move to the same target * due to a direct attack and no defender present there. It cannot be * anything special (B and K forbidden here), It cannot be pinned and the * defender's king is not attacked (thus it is a legal move). Currently * it also is a near check, i.e. only beating is considered. * * Test whether a K move of the attacker might open a check: */ dir = att_dir(dkp, akp); if (dam_dir(dir)) { if ((F_DATT(akp) | F_IATT(akp)) & nonkamask) { register int delta; xp = dkp; delta = dam_mov[dir]; while ((xp += delta) != akp) { if (xp->f_c == empty) { continue; } /* There is someone between them kings. Is only bad, when it * is the moving defender. */ if (xp == fp) { if (F_IATT(fp) & F_DATT(akp) & nonkamask) { goto fail; } } goto ak_cannot_ck; } /* Nothing between them kings. */ do { xp += delta; } while (xp->f_c == empty); if (xp->f_c == def) { if ((xp == fp) && (F_DATT(xp) & F_IATT(akp) & nonkamask)) { goto fail; } } else if (xp->f_c == att) { if (F_IATT(dkp) & SET1(xp->f_idx)) { goto fail; } } } } ak_cannot_ck:; XDB(1, printf(": fact ak no ck\n"); ) { register rPieceSet atts; register int aidx; atts = F_DATT(tp) & nonkamask; if (atts) { dir = att_dir(tp, dkp); /* chances for direct check */ aidx = 0; do { while (!(atts & 01)) { register int zeroes; zeroes = MIN_LOW_ZERO(atts); atts >>= zeroes; aidx += zeroes; } xp = &(bp->b_f[bp->b_piece[aidx]]); XDB(1, printf(" fact: test check from "); put_position(pos64_pos[xp->f_pos64]); printf("; dir=%d, fig=%d\n", dir, xp->f_f); ) /* xp -> tp checking indirect is fatal */ if ((xp->f_f != dame) && dam_dir(att_dir(xp, dkp))) { if (att_dir(fp, dkp) == att_dir(xp, dkp)) { goto fail; /* might also open; lazy */ } else { if (F_DATT(xp) & F_IATT(dkp) & nonkamask) { goto fail; } } } /* xp -> tp checking direct is fatal */ switch (xp->f_f) { case bauer: /* attack implies beat only */ if (LIN64(tp->f_pos64) == PROM_LIN(att)) { if (!no_dir(dir)) { goto fail; } } else { if (lfr_dir(dir) && (((tp + bau_right[att]) == dkp) || ((tp + bau_left[att]) == dkp) ) ) { goto fail; } } break; case springer: if (spr_dir(dir)) { goto fail; } break; case laeufer: if (lfr_dir(dir)) { goto fail; } break; case turm: if (trm_dir(dir)) { goto fail; } break; case dame: if (dam_dir(dir)) { goto fail; } break; default: goto fail; } } while ((aidx += 1), (atts >>= 1)); } } /* Well, now we have no more objections, thus ... */ scinc(sc_fact_success); XDB(1, printf("< fact+ "); put_move(bp, mp); ) return TRUE; fail:; XDB(1, printf("< fact-\n"); ) if (mp == &last_found) { if (--guess_credit <= 0) { last_found.m_from = NO_POS; /* forget, do not frequently retry */ fac_has_guess = FALSE; guess_credit = 0; /* FFS: "guess_newcredit" could be changed according to the * current success rate. */ } } return FALSE; /* sorry */ } /* * fac_km_dirs() * The specified board is a 2-mate job. * Return the set of those directions, from which we here are sure, * that moving the attackers king into such * will result in a fatal anti-check. * * Method: If the attacker is already in check by some LTD, * in many cases there can follow the move onto the current K-pos. * Such is often a fatal anti-check. */ Eximpl DirSet fac_km_dirs(register Xconst Board * bp) { register Xconst Field *akp; register Xconst Field *dkp; register Xconst Field *fp; register Xconst Field *tp; Colour att; Colour def; Position defkpos; Position attkpos; register rPieceSet amask; PieceSet dmask; register rPieceSet atts; register int dix; int zeroes; int pos; int result; register int i; int imax; scinc(sc_fackm_called); att = bp->b_tomove; def = opp_colour(att); attkpos = K_POS(bp, att); akp = &(bp->b_f[attkpos]); dmask = COLOUR_MASK(def); if (!(atts = (F_DATT(akp) & dmask))) { return (0); /* attacker currently not in check */ } scinc(sc_fackm_chk); /* Attacker in check => no castling allowed. */ defkpos = K_POS(bp, def); dkp = &(bp->b_f[defkpos]); amask = COLOUR_MASK(att); /* Consider the attK steps aside, and one of the checking defender's * steps to the just left attkpos. Below we enumerate those defenders * and verify that they say check. Also, only LTD is allowed (S FFS). * Such a defender's check is a fatal anti check, e.g. if the attacker * cannot answer with any check, again. There are several possibilities * for such a back-check of the attacker (possibly a mate), which are to * be excluded: * * (A) Move K again and open a check. (a1) from attK target position (tp) to * defK position is a D dir and (a2) only the attK moving again opens the * check. This needs an iatt in defK (dkp) which is datt in tp. Also, * attK moving to tp must beat. or (a3) only the defender is opening the * check, as fp blocks it, then the attK blocks also at tp, then both * leave it. For this, the attK walks to an empty field at tp, and there * is a datt in fp which is iatt in defK (dkp), and datt or iatt in tp. * Also D-dir tp=>dkp == fp=>dkp. or (a4) both, the defender at fp and * the attk at tp open the attack. For this, the attK beats at tp, and * there is an datt in fp being iatt in tp, or iatt in fp being datt in * tp. Also D-dir tp=>dkp == fp=>dkp. * * (B) Beat the checking defender and give a direct check. (b1) a direct * attack already in attK, which might attack defK from there. This might * be a D or S direct check. or (b2) such an attack be opened by moving * the defender. This needs a datt in fp and a iatt in akp, already, and * a D relation akp=>dkp. * * (C) Beat the checking defender and open an indirect check. (c1) An iatt * already in defK may be opened by that back-beat. or (c2) A datt or * iatt in fp might be opened together with the back-beater. Blocking is * already excluded by construction. Generally, in order for a defender * to go to attkpos (D) attK must not beat the checking defender at fp. * (E) the defender at fp must not be pinned, before. If the attK opens a * new pinning, moving to attkpos doesn't leave it Note, that the attK * cannot open a direct attack to the left field. */ if (!no_dir(att_dir(attkpos, defkpos)) && (F_DATT(akp) & amask)) { return (0); /* (b1) attacker might check back */ } /* Enumerate the checking defenders: */ scinc(sc_fackm_scans); result = 0; dix = 0; do { /* find def's at fp, attacking akp */ while (!(atts & 01)) { dix += (zeroes = MIN_LOW_ZERO(atts)); atts >>= zeroes; } fp = &(bp->b_f[pos = bp->b_piece[dix]]); if ((F_DATT(fp) & F_IATT(dkp) & amask) && dam_dir(att_dir(pos, defkpos))) { continue; /* (E) may be pinned */ } /* Ok, that defender on "fp" is not yet pinned. A possibly opened * pinning by the K-move is not intended to be left. */ if ((amask & (F_DATT(akp) | (F_IATT(akp) & F_DATT(fp))))) { /* (B|C) The defender at the attK position might be beaten back. */ if (amask & F_IATT(dkp)) { continue; /* (c1) indir check to defK might happen */ } if ((amask & (F_IATT(fp) | F_DATT(fp))) && dam_dir(att_dir(pos, defkpos))) { continue; /* (c2) opening fp may create a F_IATT(dkp) */ } if ((amask & F_DATT(fp) & F_IATT(akp)) && dam_dir(att_dir(attkpos, defkpos))) { continue; /* (b2) direct back-check might be possible */ } } /* Get direction for attK moves range such that moving "fp"->"akp" * would say check. */ switch (fp->f_f) { default: /* LTD can follow its f_datt; S is FFS */ continue; case laeufer: i = MIN_L_DIR; imax = MAX_L_DIR; break; case turm: i = MIN_T_DIR; imax = MAX_T_DIR; break; case dame: i = MIN_D_DIR; imax = MAX_D_DIR; break; } do { tp = akp + dam_mov[i]; if ((tp != fp) /* (D) not beating the defender */ &&(tp->f_c != border) /* else impossible move */ &&(tp->f_c != att) /* else impossible move */ &&!(F_DATT(tp) & dmask) /* else illegal move */ ) { /* Check this K-escape for condition (A) [K-move indir chk]: */ if (dam_dir(att_dir(tp, dkp))) { /* (a1) */ if (tp->f_c == empty) { if ((amask & F_DATT(fp) & F_IATT(dkp) & (F_DATT(tp) | F_IATT(tp)) ) && (att_dir(tp, dkp) == att_dir(fp, dkp)) ) { continue; /* (a3) */ } } else if (tp->f_c == def) { if (amask & F_DATT(tp) & F_IATT(dkp)) { continue; /* (a2) */ } if ((amask & ((F_DATT(fp) & F_IATT(tp)) | (F_IATT(fp) & F_DATT(tp)) ) ) && (att_dir(tp, dkp) == att_dir(fp, dkp)) ) { continue; /* (a4) */ } } } result |= (1 << i); scinc(sc_fackm_dirs); } } while (++i < imax); } while ((dix += 1), (atts >>= 1)); return result; } /* * can_naken() * Return, whether we are sure that the side to move * can naken the opponent (beat its last piece). * If a defender can do so, this is fatal for the attacker. * * This should be called only with piece count 2 for opponent (efficiency). * When we return FALSE, we may just not know. * FFS: must be ok to patt the attacker */ #if 0 /* Generalized setup: - The side to move is called "def", the defender. - * The other side is called "att", the attacker. - It is fatal for the * attacker to have a naked king. - It is fatal for the attacker to have no * more legal moves, whether it is mate or stalemate. - "att" has exactly 2 * pieces, named attK and attX. - We return, whether something is fatal for * the attacker, i.e. whether we are sure, that he will be nakened, or is * forced to have no legal moves, before that happens to the defender. This * is termed "success". Consider these conditions to be asserted. * * There are several considerations: (A) The defender can immediately and * legally beat the attX. ==> success This is indicated by a datt of def in * attX, which immediately implies a legal move if from non-K (as any * existing check or pinning is removed), and which indicates a legal "defK * beats attX", iff there is no datt from the attK in attX, too. if( * attX.datt & defmask & ~bothking ) success if( attX.datt & defmask & * bothking && ! attX.datt & attmask ) success * * (B) The defender has another (non-K) piece Y, which just now has a legal * move Y:f->t, such that we can guarantee a later beat of attX. There are * three different methods exploited: (1) t --d--> attX --d--> attK * [pinning attX] (2) t --d--> attK --d--> attX [check & beat] (3) t * --d--> attK [fork] --e--> attX Legality of f->t: - If Y@f * is pinned, moving to t must not leave the pinning. But if Y cannot yet * beat attX, such a move does not enable another possibility to beat attX * later. Hence, while (A) failed, any pinned Y is ignored. - Currently * defK cannot be in double check (only attX there). - If currently defK is * in single check (i.e. by attX), this attack must be removed. While not * moving defK and not beating attX at t (would have been case (A)), this * implies to block the attack with Y@t. Now, attX may beat Y@t, in which * case it is lost iff there is a back-beat by def. This back-beat may be * done by defK if t is not supported by attK, or by any other defZ, which * has already some datt in t. Moving Y:f->t s.t. check from attX is * blocked, is legal if non-B Y has datt in t (i.e. Y cannot be pinned). * (B1) t --d--> attX --d--> attK [pinning attX] - Y:f->t must be * checked to be legal - Y must be LTD, and be capable to walk dir d, or * Y:f->t must be promotion (FFS: not yet considered) - attK has no attack * in t (by construction) - if attX has no datt in t, + either attK moves * (attX does not move): ==> next move Y:t->attX is legal + or attX moves, * but cannot leave pinning ==> next move Y:t->attX is legal + or att has no * move: succ (B2) t --d--> attK --d--> attX [check & beat] - Y:f->t must * be checked to be legal - Y must be LTD, and be capable to walk dir d, or * Y:f->t must be promotion (FFS: not yet considered) - if attK has datt in * t, we must support Y@t by another defender datt in t (may be from defK), * else we fail. - attX can neither move to t, nor block t-->attK. - ==> * attK must move, but this move cannot be check. - ==> either att has no * move ==> succ or next Y:f->attX is legal ==> succ (B3) t --d--> attK * fork] --e--> attX - Y:f->t must be checked to be legal - Y must be LTD, * and be capable to walk dirs d and e, or Y:f->t must be promotion (FFS: * not yet considered) - if attK has datt@t: if also def has non-Y datt@t, * attK cannot beat@t, else failure - if attX has datt@t: if also def has * non-Y, non-K datt@t, then attX must not beat@t, as else def beats back * (naken) else if defK has datt@t but attK not, then attX must not beat@t, * as else defK beats back (naken) else failure - if the above is checked * ==> att must not beat@t ==> either att has no move ==> succ or attK * moves ==> Y:t->attX is legal ==> succ or attX moves between t and * attK (blocks check) ==> Y:t->attX is legal ==> succ */ static const Field * find_some_nonK_piece( register const Board * bp, register rColour att) { register const Position *posp; register const Field *tp; if (bp->b_cur_piece[att] <= 1) { return 0; /* no chance */ } posp = &(bp->b_piece[COLOUR_IDX(att) + bp->b_max_piece[att]]); for (;;) { --posp; if (!no_pos(*posp)) { tp = &(bp->b_f[*posp]); if ((KING_IDX == 0) || (tp->f_f != koenig)) { break; } } } return tp; } #endif Eximpl Bool can_naken( register Xconst Board * bp, Bool mateok) { /* ok to mate attacker */ register rColour att; /* opponent */ register Xconst Field *tp; scinc(sc_nak_called); if (!mateok) { return FALSE; /* sorry, not yet, FFS */ } att = opp_colour(bp->b_tomove); if (bp->b_cur_piece[att] != 2) { return FALSE; /* too hard to think about */ } /* Determine position of the non-king attacker. */ { register const Position *posp; posp = &(bp->b_piece[COLOUR_IDX(att) + bp->b_max_piece[att]]); while (no_pos(*--posp)) /* empty */ ; tp = &(bp->b_f[*posp]); } /* This is the one (non-K) piece of "att". When it can be beaten (as * indicated by a direct attack), the "att" is naked. Note, that pinning * cannot be involved, as nobody is left. Just beating by the king can be * inhibited by the other king. */ { register rPieceSet atts; if ((atts = (F_DATT(tp) & COLOUR_MASK(bp->b_tomove))) && ((atts != (atts & BOTH_KINGS)) /* non-K attack */ ||!(F_DATT(tp) & ~atts) /* not prevented */ ) ) { scinc(sc_nak_success); return (TRUE); } } /* Well, we cannot yet beat at "tp". BUT ... */ #if 1 /* May be we can pin it in a way that a beat in the next move by the * pinning piece is unavoidable. The pinned piece can either not move at * all, or stay in the pinning, or beat the pinner. (a) pinned (attacker) * piece does not move (i.e. king moves) It may even be that the attacker * has no move at all. This is mate or stalemate, which is also * considered a success. If the attacker has a legal (king) move, after * it we can beat. Note, that the pinning piece cannot be beaten by the * king. (b) pinned (attacker) piece moves, but inside pinning It will * then be beaten. (c) pinned (attacker) piece beats the pinner When the * pinner is defended by a non-K, the beat will happen. If the pinner is * defended by its own K, only, but not yet attacked by the other K, the * beat will also happen. By construction the other K is at least 2 steps * away. Hence also the defender K is sufficient. FFS: open the pinning * by another piece. */ if (bp->b_cur_piece[bp->b_tomove] >= 2) { register int dir; register Xconst Field *p; register rPieceSet atts; register rPieceSet dmask; register int delta; register int dix; register Xconst Field *fp; register int zeroes; register rPieceSet pinmask; /* att that may pin */ p = K_FP(bp, att); /* attK */ dir = att_dir(p, tp); /* attK -> attX */ if (!dam_dir(dir)) { goto cantpin; } if (!bp->b_fig_cnt[bp->b_tomove][dame] && !bp->b_fig_cnt[bp->b_tomove][trm_dir(dir) ? turm : laeufer]) { goto cantpin; /* no capable figure */ } /* is free between attK and tp ? */ delta = dam_mov[dir]; do { p += delta; } while (p->f_c == empty); if (p != tp) { goto cantpin; } /* search a target for the pinner */ dmask = COLOUR_MASK(bp->b_tomove); /* we defenders */ fp = K_FP(bp, bp->b_tomove); if (F_DATT(fp) & ~dmask) { /* def currently in check */ goto cantpin; /* move legality nontrivial */ } pinmask = F_IATT(fp); while ((p += delta)->f_c == empty) { if (!(atts = (F_DATT(p) & dmask))) continue; /* Enumerate these pieces, to find those that would pin ... */ dix = 0; do { while (!(atts & 01)) { dix += (zeroes = MIN_LOW_ZERO(atts)); atts >>= zeroes; } fp = &(bp->b_f[bp->b_piece[dix]]); /* When this is L or T it might be pinned on the other type * of direction, which hinders us to move. A D would have * been able to naken directly. */ switch (fp->f_f) { case dame: break; case turm: if (!trm_dir(dir)) continue; /* wouldn't pin */ if (pinmask & F_DATT(fp)) continue; break; case laeufer: if (!lfr_dir(dir)) continue; /* wouldn't pin */ if (pinmask & F_DATT(fp)) continue; break; default: continue; /* sorry */ } /* Now, a move fp->p were possible and would pin the last * piece at tp to its K. The only thing that hinders total * success might be the attacker at tp to beat in p, without * a possible back-beat. */ if (F_DATT(p) & SET1(tp->f_idx)) { /* can beat */ if (!(F_DATT(p) & dmask & ~SET1(dix))) { continue; /* no back beat */ } /* Even if it is only our K that beats back at p, this is * ok, since the only further attacker piece is his king, * from which we know that it is at least 2 steps away by * construction, and hence cannot guard his piece at p. */ } /* Hurra ! */ scinc(sc_nak_success); scinc(sc_nak_indir); return (TRUE); } while ((dix += 1), (atts >>= 1)); } /* scan pinner targets */ cantpin:; } #endif #if 0 /* When there is a defender piece, which can do a forking move to the two * left attackers: - attack the attK, i.e. say check - attack the attX, * i.e. establish a beat-threat and the attK cannot beat back the * checking defender piece, then - either the attK must move, - or the * attX must block. When attX blocks the check, we have gained a pinning * as above, and when the attK walks away, but cannot defend the attX * immediately, the attX can be beaten after that move. FFS: for the move * to be legal, the defender must not be in check. * * Most chances to establish a fork are with a D. Most easy to think about * free pathes is with two defenders, only. * * Consider dK+dD to move, aK+aX to be nakened: - if dD (to move) is pinned * ==> dD can beat aX immediately - find target field z, such that dD can * move to z (pinning already checked, aK & aX cannot be on path, so just * dK must not be between dD and z) - z has D-relation to both, aX and aK * (possibly the same) such that dK is neither between z and aX nor z and * aK - aX cannot beat onto z, and aK cannot beat onto z (no direct * attack, already) - then moving dD->z either pinnes the aX, or checks * the aK. - if aX is pinned, aK must move and dD can beat aX: hurra - if * aK is in check, he must move, or aX must block (beat already avoided) * To find z, search in D-dirs from aK for a direct attack bit of a dD, * such that there is no a-attack in z, already, there is is a D-relation * between z and aX, and verify the path between z and aX to be empty. * * FFS: bp->b_fig_set[bp->b_tomove][dame] hilft weiter * * aX is at tp. It can not yet be beaten. */ if (bp->b_fig_cnt[bp->b_tomove][dame] && (bp->b_cur_piece[bp->b_tomove] == 2) ) { register rColour def; register const Field *damep; register const Field *akp; register rPieceSet amask; def = opp_colour(att); akp = K_FP(bp, att); amask = COLOUR_MASK(att); /* Determine position of the defender D. */ { register Position *posp; posp = &(bp->b_piece[COLOUR_IDX(def) + bp->b_max_piece[def]]); while (no_pos(*--posp)) /* empty */ ; damep = &(bp->b_f[*posp]); } for (dir = MAX_D_DIR; --dir >= MIN_D_DIR;) { delta = dam_mov[dir]; zp = akp + delta; if (zp->f_c != empty) continue; /* FFS: if def attacks zp, too, akp may do it */ for (zp += delta; zp->f_c == empty; zp += delta) { if (F_DATT(zp) & amask) continue; if (!dam_dir(d = att_dir(zp, tp))) continue; { register const Position *p; p = zp; do { p += dam_mov[d]; } while (f->f_c == empty); if (p == tp) { /* path zp-->tp empty */ } } } /* FFS */ } /* FFS */ } #endif return FALSE; } /* * sm_has_tfac() * In the specified board is the defender of a "selfmate" to move. * We analyse and return, whether he has a totally fatal check move. * If so, there is no chance for the attacker to solve in any number * of moves. The idea is, if * (a) the defender has just one more piece than his K, * (then this piece must not be beaten, as else the defender is * not able to mate, any more), * (b) and the defender piece is a D (queen), * (c) and the D can say check, such that * (d) the D is not pinned after the move even if the attK were missing, * and * (e) the attackers K cannot open a check to the defenders K, * after the D said check (castling excluded by check), and * (f) the check is not mate, and * (g) the attacker cannot block the check, * then we know the following: * (r) the D can infinitely follow the K to where it were before, * until the attacker beats the D (what makes the job unsolvable * also), because * (w) all further attacker moves must be K escapes (blocking cannot * happen by construction, beat would have the desired result), * (x) all the D moves do not beat (the attK were there before), * (y) no such K move can open a check, as such implies that earlier * there were a situation such that the defK could be beaten. * (z) no such D move can be mate, as the support of the own K cannot * be where the other K just were. * Selfmate jobs with the defender having just K & D are not frequent, * but also not rare. Also, this might evolve in an analysis. */ Eximpl Bool sm_has_tfac(register Xconst Board * bp) { register Xconst Field *tp; register Xconst Field *akp; register int def; /* defenders colour (to move) */ register rPieceSet mask; register rPosition kpos; register rPosition pos; register rPosition akpos; scinc(sc_smtfac_called); def = bp->b_tomove; if ((bp->b_cur_piece[def] != 2) || (bp->b_fig_cnt[def][dame] != 1)) { return FALSE; /* missing entry condition, need K&D material */ } mask = COLOUR_MASK(opp_colour(def)); /* Ok, we have a K and a D (conditions (a) and (b)). Search the position * of the D: */ { register int minifig; register int ifig; minifig = COLOUR_IDX(def); kpos = bp->b_piece[minifig + KING_IDX]; if (F_DATT(&(bp->b_f[kpos])) & mask) { return FALSE; /* we are in check, sorry */ } akpos = K_POS(bp, opp_colour(def)); ifig = minifig + bp->b_max_piece[def]; do { --ifig; #if 1 if (ifig < minifig) panic("sm_has_tfac: can't find piece"); #endif pos = bp->b_piece[ifig]; /* skip empty slot (beaten piece) and K */ } while (no_pos(pos) || (pos == kpos)); } /* Now we test (d) and (e) by the following: If both, the D and the attK * were not present, were the defK then in check ? If not, hurra ! When * both, the D and the attK are in the same D-direction as seen from the * defK, then there must be a piece between them, as else the D could * beat the K !. */ akp = &(bp->b_f[akpos]); if (dam_dir(att_dir(kpos, pos))) { /* A missing D might harm */ if (F_IATT(&(bp->b_f[kpos])) & F_DATT(&(bp->b_f[pos])) & mask) { return FALSE; /* sorry, looks like pinned */ } } if (dam_dir(att_dir(kpos, akpos))) { /* A missing K might harm */ if (F_IATT(&(bp->b_f[kpos])) & F_DATT(akp) & mask) { return FALSE; /* sorry, looks like indir check possible */ } } /* Now we know for sure, that the D is not pinned. Hence a pseudo-legal * D-move will be legal. Hence, to find a legal checking move it * suffices to scan the D dirs from the attK and find a direct attack of * the D. We still need conditions (c) check, (f) not mate, and (g) no * block. (c) is implied by construction, (f) is possible only far from * the attK, or near the attK, with the defK supporting. Hence, the * near-attK case is the most simple. */ mask = COLOUR_MASK(def); { register int dir; for (dir = MAX_D_DIR; --dir >= MIN_D_DIR;) { tp = akp + dam_mov[dir]; if ((F_DATT(tp) & mask) /* some defender */ &&!(F_DATT(tp) & mask & BOTH_KINGS) /* but not a K */ ) { scinc(sc_smtfac_success); return TRUE; /* Hurra */ } } #if 0 /* FFS missing block test */ for (dir = MAX_D_DIR; --dir >= MIN_D_DIR;) { register int delta; tp = akp; delta = dam_mov[dir]; do { tp += delta; if (tp->f_c == def) break; if ((F_DATT(tp) & mask) /* some defender */ &&!(F_DATT(tp) & mask & BOTH_KINGS) /* but not a K */ ) { scinc(sc_smtfac_success); return TRUE;/* Hurra */ } } while (tp->f_c == empty); } #endif } /* FFS: indir check by moving the defK */ return FALSE; /* sorry, not yet */ }