/*
* 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 $ [corrected 10-Dec-2004]
* [corrected 08-Mar-2011]
*
* Answer heuristic "fatal anti-check"
*/
#include "types.h"
#include "board.h"
#include "output.h"
#include <stdio.h>
#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 0 /* original version */
if( (fp->f_f == bauer)
&& ((p->m_to - p->m_from) == (2 * bau_mov[def])) ) {
continue; /* might enable e.p. */
}
#else /* corrected 2011-03-08 */
if( fp->f_f == bauer ) {
if( (p->m_to - p->m_from) == (2 * bau_mov[def]) ) {
continue; /* might enable e.p. */
}
/*
* We also must not accept e.p. moves by the defender,
* since the code below does not know about the
* missing attacker pawn, which may open up
* possibilities to perform a mate move.
*/
if( (p->m_to - bau_mov[def]) == bp->b_ep ) {
continue;
}
}
#endif
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) | (F_IATT(tp) & F_DATT(fp))) & 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 */
}