/*
* CHEST, chess analyst. For Copyright notice read file "COPYRIGHT".
*
* $Source: /home/heiner/ca/chest/RCS/analyse.c,v $
* $Id: analyse.c,v 3.38 1999/12/04 23:07:17 heiner Exp $ [corrected 3-May-2005]
*
* solve (sub-) problems
*
* Ideas:
* - when A has K+F, defender strategy: move just K:
* try to show K+F cannot cover K-escapes [normal only]
*/
#include "types.h"
#include "board.h"
#include "acm.h"
#include "asw.h"
#include "fac.h"
#include "trace.h"
#include "output.h"
#include "stats.h"
#include "mgsubr.h"
#include "mlsubr.h"
#include "move.h"
#include "move_gen.h"
#include <stdio.h>
#include "job.h"
#include "spana.h"
#include "mate2.h"
#include "refu.h"
#include "analyse.h"
#ifndef ANA_STATS
# define ANA_STATS 1 /* CF */
#endif
#ifndef ATTL_STATS
# define ATTL_STATS 1 /* CF */
#endif
#ifndef SHOW_ATTMVX
# define SHOW_ATTMVX 0 /* CF: show freq(att mv exec) */
#endif
#if PROD_LEV >= 1
# undef ANA_STATS
# undef ATTL_STATS
# undef SHOW_ATTMVX
#endif
#if ATTL_STATS && ! ANA_STATS
# undef ATTL_STATS
# define ATTL_STATS 0
#endif
#undef THIS_STATS
#define THIS_STATS ANA_STATS
#include "statsupp.h"
/* For declaration of the flags see "job.h" */
Eximpl int f_jobtype = JT_normal;
Eximpl int f_jobattr = JTA__normal;
Eximpl int f_jobprog = JTP__normal;
Eximpl int f_bulkmode = 0;
Eximpl int f_Qallowed = 999;
Eximpl int f_acmflags = 0;
Eximpl int f_noanti = FALSE;
#if WITH_EG
Eximpl int f_eguse = TRUE;
#endif
Eximpl AnaCost apx_cost = 0; /* approximate cost of analysis */
Eximpl AnaCost apx_ovhd = 0; /* approximate overhead cost of acm */
#if ANA_STATS
/* Moves executed by attacker and defender,
* indexed by depth of current analysis (bottom distance).
*/
static Counter sc_movx[ 2*(MAX_ANA_DEPTH+1) ];
#define mvx_att(dep) (sc_movx[((dep)<<1) - 1])
#define mvx_def(dep) (sc_movx[((dep)<<1) - 2])
static Counter sc_mvskipped[ MAX_ANA_DEPTH + 1 ];
static Counter sc_lvskipped[ MAX_ANA_DEPTH + 1 ];
static Counter sc_m2; /* mate in 2 to solve */
static Counter sc_m2sum; /* sum(move cands) */
static Counter sc_m2mvx; /* executed cands */
static Counter sc_anti_tries; /* called move1gen for anti */
static Counter sc_anti_lists; /* non-empty move lists */
static Counter sc_anti_moves; /* moves executed for anti */
static Counter sc_anti_succ; /* were mate moves */
static Counter sc_att_pieces[17]; /* [piececnt] how often */
static Counter sc_def_pieces[17]; /* [piececnt] how often */
/* snooping: */
static Counter sc_snp_list [ANA_MANY]; /* [subdep] lists */
static Counter sc_snp_step [ANA_MANY]; /* [subdep] steps */
static Counter sc_snp_lsum [ANA_MANY]; /* [subdep] list length sum */
static Counter sc_snp_list_succ[ANA_MANY]; /* [subdep] lists */
static Counter sc_snp_step_succ[ANA_MANY]; /* [subdep] steps */
static Counter sc_snp_lsum_succ[ANA_MANY]; /* [subdep] list length sum */
static Counter sc_sm1_mv;
static Counter sc_sm1_mvesc;
static Counter sc_sm1_mvsucc;
static Counter sc_res_1m [2]; /* [succ] do1mate */
static Counter sc_res_1p [2]; /* [succ] do1stale */
static Counter sc_res_1sm[2]; /* [succ] do1selfmate */
static Counter sc_res_1sp[2]; /* [succ] do1selfstale */
#endif /* ANA_STATS */
#if ! ATTL_STATS
# define note_attl_1(x) /*empty*/
# define note_attl_N(x) /*empty*/
#else /* ATTL_STATS */
static Counter attl_1[MAX_MOVES];
static Counter attl_N[MAX_MOVES];
# define note_attl_1(x) (attl_1[x] += 1)
# define note_attl_N(x) (attl_N[x] += 1)
#endif /* ATTL_STATS */
#if WITH_EG
# include "../include/egask.h"
# ifndef egc_used
# define egc_used(q) /*empty*/ /*FFS*/
# endif
#endif /* WITH_EG */
/*
* Optionally print, then initialize analysis statistics gathered here.
*/
static void
stat1res( char* txt, Counter arr[2] )
{
if( arr[0] || arr[1] ) {
printf("%s:", txt);
show_scs(1,10, arr[0]+arr[1], ",");
show_scs(1,10, arr[1], " succ");
printf(" [%5.1f%%]\n", percent(arr[1], arr[0]+arr[1]));
}
}
Eximpl void
ana_stats( Bool withprint )
{
#if ANA_STATS
register int dep;
register int i;
if( withprint && (f_stats > 0) ) {
register Counter m1;
register Counter m2;
register Counter m0;
register Counter skmv;
register Counter sklv;
Bool topline = TRUE;
m0 = 1; /* entering globally once */
for( dep=MAX_ANA_DEPTH ; dep >= 1 ; --dep ) {
m1 = mvx_att(dep);
m2 = mvx_def(dep);
skmv = sc_mvskipped[dep];
sklv = sc_lvskipped[dep];
if( m1 || m2 || skmv || sklv ) {
/* mvx 12: 123456789 123456789 [12.456 12.456]1234567 1234567
*/
printf("mvx %2d:", dep);
show_sc(1,9, m1);
show_sc(1,9, m2);
printf(" [");
if( m0 && m1 ) {
printf("%6.3f", ((double)m1) / (double)m0);
}else {
printf("%6c", ' ');
}
printf(" ");
if( m1 && m2 ) {
printf("%6.3f", ((double)m2) / (double)m1);
}else {
printf("%6c", ' ');
}
printf("]");
if( skmv | sklv ) {
show_nz(0,7, '-', skmv);
if( sklv ) {
show_nz(1,7, '-', sklv);
}
}else {
if( topline && (dep > 1) ) {
printf("%7s %7s", "mvskip", "lvskip");
}
}
printf("\n");
topline = FALSE;
}
if( m2 ) {
m0 = m2;
}else {
m0 = 1;
}
}
if( sc_m2 ) {
printf("mate2:");
show_scs(1,8, sc_m2, ",");
show_scs(1,8, sc_m2sum, " cand");
printf(" [%4.1f],", fraction(sc_m2sum, sc_m2));
show_scs(1,8, sc_m2mvx, " mvx");
printf(" [%4.1f%%]", percent(sc_m2mvx, sc_m2sum));
printf("\n");
}
if( sc_anti_tries ) {
printf("anti: %lu", (unsigned long) sc_anti_tries);
if( sc_anti_lists ) {
printf(", lists %lu [%4.2f%%]", (unsigned long) sc_anti_lists,
percent(sc_anti_lists, sc_anti_tries));
printf(", moves %lu [%4.2f%%]", (unsigned long) sc_anti_moves,
percent(sc_anti_moves, sc_anti_tries));
printf(", succ %lu [%4.2f%%]", (unsigned long) sc_anti_succ,
percent(sc_anti_succ, sc_anti_tries));
}
printf("\n");
}
{ /* snooping */
sc_snp_list [0] = 0;
sc_snp_step [0] = 0;
sc_snp_lsum [0] = 0;
sc_snp_list_succ[0] = 0;
sc_snp_step_succ[0] = 0;
sc_snp_lsum_succ[0] = 0;
for( i=1 ; i<ANA_MANY ; ++i ) {
sc_snp_list [0] += sc_snp_list [i];
sc_snp_step [0] += sc_snp_step [i];
sc_snp_lsum [0] += sc_snp_lsum [i];
sc_snp_list_succ[0] += sc_snp_list_succ[i];
sc_snp_step_succ[0] += sc_snp_step_succ[i];
sc_snp_lsum_succ[0] += sc_snp_lsum_succ[i];
}
if( sc_snp_list[0] ) {
printf("%6s %9s %10s %10s %9s %10s %10s\n", "subdep",
"lists", "steps", "lsum", "lists+", "steps+", "lsum+");
for( i=ANA_MANY-1 ; i>=0 ; --i ) {
if( ! sc_snp_list[i] ) continue;
if( i ) {
printf("%6d", i);
}else {
printf("%6s", "tot");
}
show_sc(1, 9, sc_snp_list [i]);
show_sc(1,10, sc_snp_step [i]);
show_sc(1,10, sc_snp_lsum [i]);
show_sc(1, 9, sc_snp_list_succ[i]);
show_sc(1,10, sc_snp_step_succ[i]);
show_sc(1,10, sc_snp_lsum_succ[i]);
printf("\n");
}
}
} /* snooping */
stat1res("m1" , sc_res_1m );
stat1res("p1" , sc_res_1p );
stat1res("sm1", sc_res_1sm);
stat1res("sp1", sc_res_1sp);
if( sc_sm1_mv ) {
printf("sm1tst:");
show_scs(1,9, sc_sm1_mv , ",");
show_scs(1,9, sc_sm1_mvesc , " esc,");
show_scs(1,9, sc_sm1_mvsucc, " succ");
printf(" (%.1f%%)\n", percent(sc_sm1_mvsucc, sc_sm1_mv));
}
for( i=0 ; i<17 ; ++i ) {
if( sc_att_pieces[i] || sc_def_pieces[i] ) {
printf("%2d pieces:", i);
show_nz(0,11, '-', sc_att_pieces[i]);
show_nz(1,11, '-', sc_def_pieces[i]);
printf("\n");
}
}
#if ATTL_STATS
if( f_stats > 1 ) {
Counter sums[2];
double wsums[2];
sums [0] = sums [1] = 0;
wsums[0] = wsums[1] = 0;
for( i=0 ; i<MAX_MOVES ; ++i ) {
sums[0] += attl_N[i];
sums[1] += attl_1[i];
wsums[0] += i * (double) attl_N[i];
wsums[1] += i * (double) attl_1[i];
}
for( i=0 ; i<MAX_MOVES ; ++i ) {
m1 = attl_N[i];
m2 = attl_1[i];
if( m1 || m2 ) {
printf("attl%3d:", i);
show_nz(0,11, '-', m1);
if( m1 && sums[0] ) {
printf(" [%5.1f]", percent(m1, sums[0]));
}else {
printf(" ");
}
show_nz(1,11, '-', m2);
if( m2 && sums[1] ) {
printf(" [%5.1f]\n", percent(m2, sums[1]));
}else {
printf("\n");
}
}
}
if( sums[0] || sums[1] ) {
printf("attlavg: %10.2f %19.2f\n",
(sums[0] ? wsums[0] / (double)sums[0] : 0.0),
(sums[1] ? wsums[1] / (double)sums[1] : 0.0)
);
}
}
#endif /* ATTL_STATS */
}
for( dep=MAX_ANA_DEPTH ; dep >= 1 ; --dep ) {
mvx_att(dep) = 0;
mvx_def(dep) = 0;
sc_mvskipped[dep] = 0;
sc_lvskipped[dep] = 0;
}
sc_m2 = 0;
sc_m2sum = 0;
sc_m2mvx = 0;
sc_anti_tries = 0;
sc_anti_lists = 0;
sc_anti_moves = 0;
sc_anti_succ = 0;
for( i=0 ; i<17 ; ++i ) {
sc_att_pieces[i] = 0;
sc_def_pieces[i] = 0;
}
for( i=0 ; i<ANA_MANY ; ++i ) {
sc_snp_list [i] = 0;
sc_snp_step [i] = 0;
sc_snp_lsum [i] = 0;
sc_snp_list_succ[i] = 0;
sc_snp_step_succ[i] = 0;
sc_snp_lsum_succ[i] = 0;
}
sc_sm1_mv = 0;
sc_sm1_mvesc = 0;
sc_sm1_mvsucc = 0;
for( i=0 ; i<2 ; ++i ) {
sc_res_1m [i] = 0;
sc_res_1p [i] = 0;
sc_res_1sm[i] = 0;
sc_res_1sp[i] = 0;
}
# if ATTL_STATS
for( i=0 ; i<MAX_MOVES ; ++i ) {
attl_1[i] = 0;
attl_N[i] = 0;
}
# endif /* ATTL_STATS */
#endif /* ANA_STATS */
m2_stats (withprint);
spana_stats(withprint);
#if WITH_EG
if( withprint && (f_stats > 0) ) {
eg_stat_print(stdout);
}
eg_stat_clear();
#endif
}
Eximpl void
ana_sol_stats(void)
{
#if WITH_EG
eg_stat_print(stdout);
#endif
}
Eximpl void /*ARGSUSED*/
sum_stats( int depth, TimeSecs secs )
{
#if ! PROD_LEV
if( f_stats > 0 ) {
/*
* Print a single line, containing the most significant statistics.
* - leading comment sign #
* - (demanded) depth of analysis
* - time in seconds
* - speed (of acm)
* - nodes in/out (of acm)
* FFS: version/options
* FFS: timing_prec()
*/
printf("# %2d %8.2f", depth, (double)secs);
printf(" %5.2f", acm_speed());
printf(" %10lu-%9lu",
(unsigned long) acm_cnt_in(),
(unsigned long) acm_cnt_out());
printf("\n");
fflush(stdout);
}
#endif /* ! PROD_LEV */
}
Eximpl void
set_jobtype( int jobtype )
{
f_jobtype = jobtype;
switch( f_jobtype ) {
case JT_normal: f_jobattr = JTA__normal; break;
case JT_stalemate: f_jobattr = JTA__stalemate; break;
case JT_selfmate: f_jobattr = JTA__selfmate; break;
case JT_selfstalemate: f_jobattr = JTA__selfstalemate; break;
case JT_helpmate: f_jobattr = JTA__helpmate; break;
case JT_helpstalemate: f_jobattr = JTA__helpstalemate; break;
default: f_jobattr = 0; break;
}
}
typedef struct AnaOut AnaOut; /* collected output of analysis */
struct AnaOut
{
Movelist* resp; /* all solutions */
Move* movp; /* one solution */
RefuList* refup; /* all (known) refutations */
};
/*
* Collection of "apx_cost" by incrementing a global variable
* can be expensive, when that global variable is of type (double).
* This is decided by "cost.h": COST_AS_DOUBLE.
* [ If the following macros are to be used outside this module,
* they have to go into "cost.h". ]
* We make conditional macros for the typical operations within
* an analyse-function, and use a local variable, when the global is (double).
*
* Basic Localized
*
* AnaCost cost0; AnaCost cost0;
* uint32 lcl_cost = 0;
*
* cost0 = apx_cost; =
*
* apx_cost += E; lcl_cost += E;
* apx_ovhd += E; = [FFS]
*
* ...(apx_cost-cost0)... ...(apx_cost-cost0+lcl_cost)...
*
* return E; apx_cost += lcl_cost; [ lcl_cost = 0 ];
* return E;
*
* NOTE: We have to insert code before any return (when some cost
* may have been collected.
* Hence it is good style to use "goto out" to concentrate on
* one return statement per function.
* FFS: Benfit of this is small. Cf. LOG. FFS.
*/
#ifndef COST_COLL_LOCAL /* whether to use a local var */
# define COST_COLL_LOCAL COST_AS_DOUBLE
#endif
#define APC_DCL_0() AnaCost cost0; /* locally saved value */
#define APC_SET_0() (cost0 = apx_cost) /* assign saved value */
#define APC_OADD(val) (apx_ovhd += (val)) /* FFS: no caching */
#if COST_COLL_LOCAL /* use a local var */
# define APC_DCL_LCL() uint32 lcl_cost = 0;
# define APC_CADD(val) (lcl_cost += (val))
# define APC_UPTO() (apx_cost - cost0 + lcl_cost)
# define APC_SYNC() (apx_cost += lcl_cost);
#else /* ! COST_COLL_LOCAL : use global var directly */
# define APC_DCL_LCL() /*empty*/
# define APC_CADD(val) (apx_cost += (val))
# define APC_UPTO() (apx_cost - cost0)
# define APC_SYNC() /*empty*/
#endif /* ! COST_COLL_LOCAL */
#define APC_DCL_0_LCL() APC_DCL_0() \
APC_DCL_LCL()
#define APC_CINC() APC_CADD(1)
#define APC_OINC() APC_OADD(1)
#define APC_CO_ADD(val) (APC_CADD(val), APC_OADD(val)) /* cost & ovhd */
#define APC_CO_INC() APC_CO_ADD(1) /* cost & ovhd */
/*
* analyse()
* Analyse the specified board in the specified depth.
* Put all solutions (moves) into the specified movelist (when present).
* Return success (whether solution found).
* Only minimally deap solutions are generated by progressive deepening.
*
* In the memory are also only minimally deep solutions, by which we
* know that everything of smaller depth is unsolvable.
*
* analyse() exported interface
* do_ana() local recursive function
* do1mate() special for depth==1
* do1stale() depth==1, stalemate version
* do1selfmate() depth==1, selfmate version
* do1selfstale() depth==1, selfstalemate version
*/
static int /* constructed by ANARES() */
do1mate(
register Board* bp,
AnaOut* outp) /* collected results */
{
register Move* ap;
register int result;
Movelist attacks; /* inited by move generator */
TRC_INTO_ANALYSE(bp, 1);
if( outp && outp->resp ) {
clear_list(outp->resp);
}
{ register rColour att;
att = bp->b_tomove;
if( f_stats > 1 ) {
scinc(sc_att_pieces[bp->b_cur_piece[ att ]]);
scinc(sc_def_pieces[bp->b_cur_piece[opp_colour(att)]]);
}
if( bp->b_cur_piece[att] <= 1 ) { /* naked king cannot win */
result = ANARES(ANA_MANY,FALSE); /* in any depth */
goto out;
}
}
result = ANARES(1, FALSE); /* to stuff in the FALSE */
apx_cost += 2; /* for ourselves + the move generator */
if( ! move1gen(bp, &attacks) ) { /* there are no mate move candidates */
note_attl_1(0);
goto out;
}
note_attl_1(list_length(&attacks));
#if 1
ml_ck_attr(bp, &attacks);
#endif
TRC_ATT_START(1);
TRC_ATT_MOVES(bp, &attacks);
formoves( &attacks, ap ) {
register Bool solution;
if( attacks.l_attr & LA_CK ) {
/* We know already checking properties ... */
if( ! (ap->m_attr & MA__CK) ) { /* not even a check move */
continue;
}
}
move_execute(bp, ap); ++apx_cost; scinc(mvx_att(1));
if( in_check(bp) ) {
solution = ! move_gen(bp, (Movelist*)0); ++apx_cost;
}else {
solution = FALSE; /* not even a checking move */
}
move_undo(bp);
if( solution ) { /* this attacker move is a solution */
result = ANARES(1,TRUE);
if( outp && outp->movp ) {
*(outp->movp) = *ap;
}
if( ! (outp && outp->resp) ) {
break; /* ready with those moves */
}
app_move(ap, outp->resp);
}
} /* for attacks */
TRC_ATT_END();
if( outp && outp->resp && ! empty_list(outp->resp) ) {
mg_link(outp->resp);
}
out:;
scinc(sc_res_1m[ANASUC(result)]);
TRC_OUTOF_ANALYSE(bp, result, (outp ? outp->resp : (MoveList*)0));
return(result);
}
static int /* constructed by ANARES() */
do1stale(
register Board* bp,
AnaOut* outp) /* collected results */
{
register Move* ap;
register int result;
Movelist attacks; /* inited by move generator */
APC_DCL_LCL()
TRC_INTO_ANALYSE(bp, 1);
if( outp && outp->resp ) {
clear_list(outp->resp);
}
{ register rColour att;
att = bp->b_tomove;
if( f_stats > 1 ) {
scinc(sc_att_pieces[bp->b_cur_piece[ att ]]);
scinc(sc_def_pieces[bp->b_cur_piece[opp_colour(att)]]);
}
if( (bp->b_cur_piece[ att ] <= 1) /* two naked Ks */
&& (bp->b_cur_piece[opp_colour(att)] <= 1) ) {
result = ANARES(ANA_MANY,FALSE); /* cannot in any depth */
goto out;
}
}
result = ANARES(1, FALSE); /* to stuff in the FALSE */
APC_CADD(2); /* for ourselves + the move generator */
if( ! move_gen(bp, &attacks) ) { /* there are no move candidates */
note_attl_1(0);
goto out;
}
note_attl_1(list_length(&attacks));
ml_ck_attr(bp, &attacks); /* checking moves to be discarded */
TRC_ATT_START(1);
TRC_ATT_MOVES(bp, &attacks);
formoves( &attacks, ap ) {
register Bool solution;
if( ap->m_attr & MA__CK ) { /* check move cannot yield stalemate */
continue;
}
move_execute(bp, ap); APC_CINC(); scinc(mvx_att(1));
if( in_check(bp) ) {
panic("do1stale: in_check (%d)", __LINE__); /*NOTREACHED*/
}
solution = ! move_gen(bp, (Movelist*)0); APC_CINC();
move_undo(bp);
if( solution ) { /* this attacker move is a solution */
result = ANARES(1,TRUE);
if( outp && outp->movp ) {
*(outp->movp) = *ap;
}
if( ! (outp && outp->resp) ) {
break; /* ready with those moves */
}
app_move(ap, outp->resp);
}
} /* for attacks */
TRC_ATT_END();
if( outp && outp->resp && ! empty_list(outp->resp) ) {
mg_link(outp->resp);
}
out:;
scinc(sc_res_1p[ANASUC(result)]);
APC_SYNC()
TRC_OUTOF_ANALYSE(bp, result, (outp ? outp->resp : (MoveList*)0));
return(result);
}
#define SM1_ACM 1 /* whether to use "acm" in 1-selfmate */
static int /* constructed by ANARES() */
do1selfmate(
register Board* bp,
AnaOut* outp, /* collected results */
Movelist* outatts, /* fill attacks here */
int* candepp, /* fill dep of attacks here */
AcmNode** outacmp) /* fill memory node here */
{
register Move* dp;
register Move* ap;
register int result;
register int flags;
register Xconst Field* tp;
register Xconst Field* dkp;
register Xconst Field* akp;
register rPieceSet attmask;
register int dir;
register rEscSet e; /* actual defender escapes */
register rEscSet escs; /* current defender escapes */
register rEscSet escs_i; /* but has indirect attacks */
register rPieceSet escs_doesi; /* those make escs_i */
register rEscSet escs_1d0i; /* no esc, but only 1 dir-att */
register rPieceSet escs_does1d0i; /* those make escs_i */
#if SM1_ACM
register AcmNode* acmp;
APC_DCL_0() /* cost0 */
#endif
APC_DCL_LCL() /* lcl_cost */
Movelist* attsp;
Movelist attacks; /* inited by move generator */
Movelist defends; /* inited by move generator */
TRC_INTO_ANALYSE(bp, 1);
if( outp && outp->resp ) {
clear_list(outp->resp);
}
flags = 0;
#define SMF_nobeat 0x01
{ register rColour att;
att = bp->b_tomove;
if( f_stats > 1 ) {
scinc(sc_att_pieces[bp->b_cur_piece[ att ]]);
scinc(sc_def_pieces[bp->b_cur_piece[opp_colour(att)]]);
}
switch( bp->b_cur_piece[opp_colour(att)] ) {
case 1: /* naked defender king cannot mate */
result = ANARES(ANA_MANY,FALSE); /* in any depth */
goto out;
case 2:
flags |= SMF_nobeat;
break;
}
}
result = ANARES(1, FALSE); /* to stuff in the FALSE */
#if SM1_ACM
APC_SET_0(); /* cost0 */
#endif
APC_CINC(); /* we cost ourselves */
#if SM1_ACM
if( f_acmflags & F_ACM_DO ) {
acmp = acm_search(bp); APC_CO_INC();
if( outacmp ) {
*outacmp = acmp;
}
if( acmp && (f_acmflags & F_ACM_USE) ) {
register int ndep;
ndep = ACM_IDEP(acmp->mn_info);
if( ndep > 1 ) { /* knows even bigger depth */
acm_used(acmp, ACM_INFO(1,FALSE));
result = ANARES(ndep-ACM_IRES(acmp->mn_info), FALSE);
acm_release(acmp);
goto out; /* so no solution here */
}
if( ndep == 1 ) { /* known depth matches needs */
if( (!outp || (!outp->resp && !outp->movp))
|| (!ACM_IRES(acmp->mn_info)) ) {
/*
* Result is either empty (no solution)
* or is not wanted outside, so:
*/
acm_used(acmp, acmp->mn_info);
result = ANARES(1, ACM_IRES(acmp->mn_info));
acm_release(acmp);
goto out;
}
}
}
}else {
acmp = (AcmNode*)0; /* no such animal here */
}
#endif
APC_CINC(); /* for the move generator */
if( ! (attsp = outatts) ) {
attsp = &attacks;
}else {
if( candepp ) {
*candepp = 9999;
}
}
if( ! move_gen(bp, attsp) ) { /* there are no move candidates */
note_attl_1(0);
/*
* No legal move left: this immediately decides the outcome.
* mate ==> is solution in 0 moves
* stalemate ==> is not solution for any depth
*/
if( in_check(bp) ) { /* already mate: early solution */
result = ANARES(0, TRUE);
}else {
result = ANARES(ANA_MANY, FALSE);
}
#if SM1_ACM
if( acmp ) {
acm_note(acmp, ACM_INFO(ANADEP(result),ANASUC(result)), APC_UPTO());
acm_release(acmp);
}
#endif
goto out;
}
note_attl_1(list_length(attsp));
#if 1
ml_ck_attr(bp, attsp);
#endif
TRC_ATT_START(1);
TRC_ATT_MOVES(bp, attsp);
/*
* An attacker move is a "solution", iff the defender after it is forced
* to mate the attacker. This needs the following assertions:
* (a) there must be legal moves (at least one)
* (b) all legal moves must be mate moves
* Hence:
* (c) there must be mate moves (as produced by move1gen)
* (d) there must not be more moves produces by move_gen
* Different approaches are possible. Currently it seems to be best
* to call "move_gen", attributize with "ml_ck_attr" and hope to find
* a non-checking move. Normally, in 99.8% this is the case. Another
* approach is to call "move1gen", first, and verify that its ouput is
* non-empty and all are really mate moves. This is sometimes the case
* and hence considered more expensive than the first approach.
* Even better were a special move generator.
*
* Anyhow, nearly all of the moves executed in a selfmate analysis
* are these attacker moves. We want to work against that and
* detect - before move execution - that it cannot be a solution.
* The easiest approach is to find a legal defender K move which
* cannot even say check (success = 10% .. 40%).
*/
escs = 0;
escs_i = 0;
escs_doesi = 0;
escs_1d0i = 0;
escs_does1d0i = 0;
{
register rColour def;
register rPieceSet atts;
def = bp->b_tomove;
akp = K_FP(bp, def);
def = opp_colour(def);
dkp = K_FP(bp, def);
attmask = COLOUR_MASK(bp->b_tomove); /* attackers */
for( dir=MIN_D_DIR ; dir<MAX_D_DIR ; ++dir ) {
tp = dkp + dam_mov[dir];
if( (tp->f_c == border) || (tp->f_c == def) ) continue;
atts = ( F_IATT(tp)
| ( F_IATT(dkp)
& ( F_IATT(&(dkp[dam_mov[opp_dir(dir)]]))
| F_DATT(&(dkp[dam_mov[opp_dir(dir)]]))
)
)
)
& attmask;
if( F_DATT(tp) & attmask ) {
if( !atts && max1elems(F_DATT(tp) & attmask) ) {
escs_does1d0i |= (F_DATT(tp) & attmask);
escs_1d0i |= (1 << dir);
}
continue;
}
escs |= (1 << dir); /* currently */
if( atts ) { /* might be opened */
escs_i |= (1 << dir);
escs_doesi |= atts;
}
}
#if 0
{
put_packed(&bp->b_packed, "\t");
printf("escs = %2x, dkp@%2o [%3x]\n",
escs, dkp->f_pos64, dkp-bp->b_f
);
}
#endif
}
formoves( attsp, ap ) {
register Xconst Field* fp;
register Bool solution;
tp = &(bp->b_f[ ap->m_to ]);
if( (flags & SMF_nobeat) && (tp->f_c != empty) ) {
/* REFU(ap): def naked */
continue;
}
fp = &(bp->b_f[ ap->m_from ]);
scinc(sc_sm1_mv);
switch( ap->m_fig ) {
case koenig: /* beware of castling */
if( ! (F_DATT(tp) & BOTH_KINGS) ) {
break; /* is a castling */
}
if( (e = escs) ) {
scinc(sc_sm1_mvesc);
if( F_DATT(fp) & escs_doesi ) {
e &= ~(escs_i & fig_cov[dame][fp-dkp]);
}
}
if( escs_does1d0i & SET1(ap->m_idx) ) {
for( dir=MIN_D_DIR ; dir<MAX_D_DIR ; ++dir ) {
if( (escs_1d0i & (1 << dir))
&& (F_DATT(&(dkp[dam_mov[dir]])) & SET1(ap->m_idx))
) {
e |= (1 << dir);
}
}
}
if( (e & ~fig_cov[koenig][tp-dkp]) /* exists defK move */
&& ( !dam_dir(dir=att_dir(tp, dkp)) /* cannot check */
|| (dkp[dam_mov[dir]].f_c == border)
|| !(F_DATT(dkp) & (F_IATT(tp)|F_IATT(fp)) & ~attmask)
)
) {
scinc(sc_sm1_mvsucc);
/* REFU(ap): SM1 */
continue;
}
break;
case bauer: /* beware of e.p. */
if( (tp->f_c == empty)
&& lfr_dir(att_dir(ap->m_from, ap->m_to))
) {
break; /* is an e.p. */
}
default: /* non-K normal move (may be promotion) */
e = 0;
if( (e |= escs) ) {
scinc(sc_sm1_mvesc);
if( F_DATT(fp) & escs_doesi ) {
e &= ~(escs_i & fig_cov[dame][fp-dkp]);
}
}
if( (F_DATT(tp) & BOTH_KINGS & ~attmask) /* defK attacks */
&& ! (F_DATT(tp) & ~SET1(ap->m_idx) & attmask) /* no support */
&& ! (F_IATT(tp) & F_DATT(fp) & attmask)
) {
e |= (1 << att_dir(dkp, tp)); /* may beat back */
}
if( escs_does1d0i & SET1(ap->m_idx) ) {
for( dir=MIN_D_DIR ; dir<MAX_D_DIR ; ++dir ) {
if( (escs_1d0i & (1 << dir))
&& (F_DATT(&(dkp[dam_mov[dir]])) & SET1(ap->m_idx))
) {
e |= (1 << dir);
}
}
}
if( (e & ~fig_cov[ap->m_fig][tp-dkp])
&& ( !dam_dir(dir=att_dir(akp, dkp)) /* cannot check */
|| (dkp[dam_mov[dir]].f_c == border)
|| ( !(F_DATT(dkp) & F_IATT(akp) & ~attmask)
&& (att_dir(akp, fp) != dir)
)
)
) {
scinc(sc_sm1_mvsucc);
/* REFU(ap): SM1 */
continue;
}
break;
}
move_execute(bp, ap); APC_CINC(); scinc(mvx_att(1));
if( ! move_gen(bp, &defends) ) { /* defender mate/stalemate */
solution = FALSE;
/* REFU(ap): no move */
}else {
solution = TRUE; /* except we find a defense */
ml_ck_attr(bp, &defends);
formoves( &defends, dp ) {
if( ! (dp->m_attr & MA__CK) ) {
/* REFU(ap,dp) */
solution = FALSE; /* not even a check move */
break;
}
}
if( solution ) { /* all def moves are check moves */
formoves( &defends, dp ) {
move_execute(bp, dp); APC_CINC(); scinc(mvx_def(1));
if( move_gen(bp, (Movelist*)0) ) { /* not mate */
/* REFU(ap,dp) */
solution = FALSE;
}
move_undo(bp);
if( ! solution ) {
break;
}
}
}
}
move_undo(bp);
if( solution ) { /* this attacker move is a solution */
#if SM1_ACM
if( acmp && ! ANASUC(result) ) {
acm_note(acmp, ACM_INFO(ANADEP(result), TRUE), APC_UPTO());
}
#endif
result = ANARES(1,TRUE);
/* REFU(ap): none */
if( outp && outp->movp ) {
*(outp->movp) = *ap;
}
if( ! (outp && outp->resp) ) {
break; /* ready with those moves */
}
app_move(ap, outp->resp);
}
} /* for attacks */
TRC_ATT_END();
if( outp && outp->resp && ! empty_list(outp->resp) ) {
mg_link(outp->resp);
}
#if SM1_ACM
if( acmp ) {
if( ! ANASUC(result) ) {
acm_note(acmp, ACM_INFO(ANADEP(result), FALSE), APC_UPTO());
}
acm_release(acmp);
}
#endif
out:; /* no memory node any more, here */
scinc(sc_res_1sm[ANASUC(result)]);
APC_SYNC()
TRC_OUTOF_ANALYSE(bp, result, (outp ? outp->resp : (MoveList*)0));
return(result);
}
#if 1
static int /* constructed by ANARES() */
do1selfstale(
register Board* bp,
AnaOut* outp, /* collected results */
Movelist* outatts, /* fill attacks here */
int* candepp, /* fill dep of attacks here */
AcmNode** outacmp) /* fill memory node here */
{
register Move* dp;
register Move* ap;
register int result;
register int flags;
register Xconst Field* tp;
#if SM1_ACM
register AcmNode* acmp;
APC_DCL_0() /* cost0 */
#endif
APC_DCL_LCL() /* lcl_cost */
Movelist* attsp;
Movelist attacks; /* inited by move generator */
Movelist defends; /* inited by move generator */
TRC_INTO_ANALYSE(bp, 1);
if( outp && outp->resp ) {
clear_list(outp->resp);
}
flags = 0;
#define SMF_nobeat 0x01 /* att must not beat */
{ register rColour att;
att = bp->b_tomove;
if( f_stats > 1 ) {
scinc(sc_att_pieces[bp->b_cur_piece[ att ]]);
scinc(sc_def_pieces[bp->b_cur_piece[opp_colour(att)]]);
}
/*
* No stalemate is possible, if just both K are left.
*/
if( bp->b_cur_piece[att] <= 1 ) { /* att is naked, already */
switch( bp->b_cur_piece[opp_colour(att)] ) {
case 1: /* naked defender king cannot stalemate */
result = ANARES(ANA_MANY,FALSE); /* in any depth */
goto out;
case 2:
flags |= SMF_nobeat; /* att must not beat that */
break;
}
}
}
result = ANARES(1, FALSE); /* to stuff in the FALSE */
#if SM1_ACM
APC_SET_0(); /* cost0 */
#endif
APC_CINC(); /* we cost ourselves */
#if SM1_ACM
if( f_acmflags & F_ACM_DO ) {
acmp = acm_search(bp); APC_CO_INC();
if( outacmp ) {
*outacmp = acmp;
}
if( acmp && (f_acmflags & F_ACM_USE) ) {
register int ndep;
ndep = ACM_IDEP(acmp->mn_info);
if( ndep > 1 ) { /* knows even bigger depth */
acm_used(acmp, ACM_INFO(1,FALSE));
result = ANARES(ndep-ACM_IRES(acmp->mn_info), FALSE);
acm_release(acmp);
goto out; /* so no solution here */
}
if( ndep == 1 ) { /* known depth matches needs */
if( (!outp || (!outp->resp && !outp->movp))
|| (!ACM_IRES(acmp->mn_info)) ) {
/*
* Result is either empty (no solution)
* or is not wanted outside, so:
*/
acm_used(acmp, acmp->mn_info);
result = ANARES(1, ACM_IRES(acmp->mn_info));
acm_release(acmp);
goto out;
}
}
}
}else {
acmp = (AcmNode*)0; /* no such animal here */
}
#endif
APC_CINC(); /* for the move generator */
if( ! (attsp = outatts) ) {
attsp = &attacks;
}else {
if( candepp ) {
*candepp = 9999;
}
}
if( ! move_gen(bp, attsp) ) { /* there are no move candidates */
note_attl_1(0);
/*
* No legal move left: this immediately decides the outcome.
* stalemate ==> is solution in 0 moves
* mate ==> is not solution for any depth
*/
if( ! in_check(bp) ) { /* already stalemate: early solution */
result = ANARES(0, TRUE);
}else {
result = ANARES(ANA_MANY, FALSE);
}
#if SM1_ACM
if( acmp ) {
acm_note(acmp, ACM_INFO(ANADEP(result),ANASUC(result)), APC_UPTO());
acm_release(acmp);
}
#endif
goto out;
}
note_attl_1(list_length(attsp));
#if 0
ml_ck_attr(bp, attsp);
#endif
TRC_ATT_START(1);
TRC_ATT_MOVES(bp, attsp);
/*
* An attacker move is a "solution", iff the defender after it is forced
* to stalemate the attacker. This needs the following assertions:
* (a) there must be legal (defender) moves (at least one)
* (b) all legal (defender) moves must be stalemate moves
* Hence:
* (c) there must not be any checking moves produced by move_gen (for def)
* While we have no special move generator, we use the normal one,
* and check for the existence of checking moves, before we execute
* any of the defender moves.
*
* FFS: some attacking environment analysis should help a lot.
*/
formoves( attsp, ap ) {
register Bool solution;
tp = &(bp->b_f[ ap->m_to ]);
if( (flags & SMF_nobeat) && (tp->f_c != empty) ) {
/* REFU(ap): def naked */
continue;
}
move_execute(bp, ap); APC_CINC(); scinc(mvx_att(1));
if( ! move_gen(bp, &defends) ) { /* defender mate/stalemate */
solution = FALSE;
/* REFU(ap): no move */
}else {
solution = TRUE; /* except we find a defense */
ml_ck_attr(bp, &defends);
formoves( &defends, dp ) {
if( dp->m_attr & MA__CK ) {
/* REFU(ap,dp) */
solution = FALSE; /* is a check move */
break;
}
}
if( solution ) { /* no def move is a check move */
formoves( &defends, dp ) {
move_execute(bp, dp); APC_CINC(); scinc(mvx_def(1));
if( move_gen(bp, (Movelist*)0) ) { /* not stalemate */
/* REFU(ap,dp) */
solution = FALSE;
}
move_undo(bp);
if( ! solution ) {
break;
}
}
}
}
move_undo(bp);
if( solution ) { /* this attacker move is a solution */
#if SM1_ACM
if( acmp && ! ANASUC(result) ) {
acm_note(acmp, ACM_INFO(ANADEP(result), TRUE), APC_UPTO());
}
#endif
result = ANARES(1,TRUE);
/* REFU(ap): none */
if( outp && outp->movp ) {
*(outp->movp) = *ap;
}
if( ! (outp && outp->resp) ) {
break; /* ready with those moves */
}
app_move(ap, outp->resp);
}
} /* for attacks */
TRC_ATT_END();
if( outp && outp->resp && ! empty_list(outp->resp) ) {
mg_link(outp->resp);
}
#if SM1_ACM
if( acmp ) {
if( ! ANASUC(result) ) {
acm_note(acmp, ACM_INFO(ANADEP(result), FALSE), APC_UPTO());
}
acm_release(acmp);
}
#endif
out:; /* no memory node any more, here */
scinc(sc_res_1sp[ANASUC(result)]);
APC_SYNC()
TRC_OUTOF_ANALYSE(bp, result, (outp ? outp->resp : (MoveList*)0));
return(result);
}
#endif
/*
* Due to the mutual recursive nature of our functions,
* we need some forward declarations ...
*/
static int do_help_rest (Board* bp, int plies, AnaOut* outp);
static int do_help_full (Board* bp, int plies, AnaOut* outp);
static int /* constructed by ANARES() */
do_ana(
register Board* bp,
int depth, /* wanted depth of analysis */
AnaOut* outp) /* collected results */
{
register Move* ap;
register Move* dp;
register Bool solution;
register int result; /*ffs 0*/
register int dep; /* current depth in progress */
int listcandep;
Movelist attacks; /* inited by move generator */
Movelist defends; /* inited by move generator */
int defsarefor; /* for which attacker */
DirSet km_dirs;
Position akpos;
register AcmNode* acmp;
APC_DCL_0_LCL() /* cost0, lcl_cost */
int ndep;
register ruint32 flags;
register rColour att;
register int aidx;
int attlength;
int thiscant;
int mincant;
int aisprom; /* whether 'ap' is promotion */
uint8 cantprom; /* know a promotion 'cant' value */
Move aprom; /* for this promotion move */
int8 d_pieces; /* piece count of defender to move */
uint8 cant[MAX_MOVES];
#if SHOW_ATTMVX
short attmvx[ANA_MANY+1];
#endif
/* Snooping is important: try to detect that selecting a defenders
* move results in a position, which we know in ACM, and which
* is sufficient to decide. This spares the full execution of the
* move (only an updated packed board is done in ACM), and may
* find answers the answer heuristic consideres bad, but we just
* know, it is sufficient.
* But, we must not do too much of it. To snoop one move is
* expected to cost as much as executing a full move.
* If successful we save executing and undoing a defender move,
* and a subanalysis, which does at least another ACM search,
* but may cost a hole tree.
* When the subanalyis depth is large enough, we snoop all defender
* moves, anyhow. If the subdepth is not large, but the attacker
* has many moves, we snoop all or a part of the defender list,
* after it has been sorted according to the answer heuristic.
*/
/* min # att-mov to snoop sub-depth */
static int8 attlsnoop[] ={ 0, 99, /* sub-depth 0 & 1 */
20, /* sub-depth 2 */
4, /* sub-depth 3 */
2, /* sub-depth 4 */
};
/* max # moves snooped for sub-depth */
static int8 stopsnoop[] ={ 0, 0, /* sub-depth 0 & 1 */
2, /* sub-depth 2 */
4, /* sub-depth 3 */
12, /* sub-depth 4 */
59, /* sub-depth 5 */
};
M2Info m2info;
att = bp->b_tomove;
dep = 1; /* start iterative deepening here */
APC_SET_0(); /* cost0 */
acmp = (AcmNode*)0; /* not yet memory node found */
listcandep = -1; /* not yet any move list generated */
defsarefor = -1; /* aidx has no interpretation */
attlength = -1; /* shuts off warning */
/*
* Level-1 self[stale]mate is always to be done via special function ...
* Cf. call of ala_move_gen(), below.
*/
if( f_jobattr & JTA_self ) {
AcmNode* myacmp;
myacmp = (AcmNode*)0;
if( f_jobtype == JT_selfmate ) {
result = do1selfmate (bp, outp, &attacks, &listcandep, &myacmp);
}else {
result = do1selfstale(bp, outp, &attacks, &listcandep, &myacmp);
}
/* we have not yet collected cost locally */
if( ANASUC(result) ) {
return result; /* we know a success */
}
dep = ANADEP(result); /* known to be successless */
if( dep >= depth ) {
return result; /* this is sufficient */
}
if( (acmp = myacmp) ) { /* we are going to use it */
acm_attach(acmp);
}
++dep; /* first to be done */
if( listcandep >= dep ) { /* he did it for us, already */
attlength = list_length(&attacks);
if( (aidx = attlength) > 0 ) {
while( --aidx >= 0 ) {
cant[aidx] = dep-1; /* that is for sure */
}
if( ! (attacks.l_attr & LA_CK) ) {
#if 1
ml_ck_attr(bp, &attacks);
#else
if( f_Qallowed < (depth-1) ) {
ml_ck_attr(bp, &attacks);
}
#endif
}
}
defsarefor = -1; /* aidx has new interpretation */
}
}else {
if( outp && outp->resp ) {
clear_list(outp->resp);
}
if( f_stats > 1 ) {
scinc(sc_att_pieces[bp->b_cur_piece[ att ]]);
scinc(sc_def_pieces[bp->b_cur_piece[opp_colour(att)]]);
}
}
TRC_INTO_ANALYSE(bp, depth);
flags = 0;
#define F_tryfac (1<< 0) /* try fac heuristic */
#define F_tryanti (1<< 1) /* try anti-mate heuristic */
#define F_didanti (1<< 2) /* did anti-mate heuristic */
#define F_anakedfails (1<< 3) /* nakened attacker looses */
#define F_a1_mg_full (1<< 4) /* attacker needs all moves in dep 1 */
#define F_no_anti (1<< 5) /* attacker mate doesn't make him loose */
#define F_ok_fac (1<< 6) /* fac heuristic is ok */
#define F_normal (1<< 7) /* normal: dep==1 must mate */
#define F_nodef_fails (1<< 8) /* no defender move fails for attacker */
#define F_dnakedfails (1<< 9) /* nakened defender makes attacker loose */
#define F_a_no_beat (1<<10) /* nakened defender makes attacker loose */
#define F_try_smtfac (1<<11) /* try use fac version for selfmate */
#define F_help (1<<12) /* helpmate: att to be [stale]mated */
#define F_m2 (1<<13) /* tmp: do 2-mate analysis */
#define F_refu (1<<14) /* fill RefuList */
#define F_stalem (1<<15) /* stalemate: dep==1 must stalemate */
#define F_a_kxk (1<<16) /* try kxk analysis for attacker */
#define F_top (1<<17) /* we are top level (not yet exact) */
switch( f_jobtype ) {
default: panic("do_ana: jobtype %d (%d)", f_jobtype, __LINE__);
/*NOTREACHED*/
case JT_normal:
flags |= F_anakedfails | F_ok_fac | F_normal | F_a_kxk;
flags |= F_refu;
break;
case JT_stalemate:
flags |= F_a1_mg_full | F_refu | F_stalem | F_a_kxk;
/*both naked fails*/
break;
case JT_selfmate: /* att to be mated, def forced to mate */
flags |= F_a1_mg_full | F_no_anti | F_nodef_fails | F_dnakedfails;
flags |= F_refu;
break;
case JT_selfstalemate: /* att to be stalemated, def forced to do it */
flags |= F_a1_mg_full | F_no_anti | F_nodef_fails;
flags |= F_refu;
break;
case JT_helpmate: /* att to be mated, def tries to mate */
flags |= F_help;
flags |= F_a1_mg_full | F_no_anti | F_nodef_fails | F_dnakedfails;
break;
case JT_helpstalemate: /* att to be stalemated, def tries to do it */
flags |= F_help;
flags |= F_a1_mg_full | F_no_anti | F_nodef_fails;
break;
}
if( f_jobattr & JTA_stalemate ) { /* both naked: cannot stalemate */
if( bp->b_cur_piece[opp_colour(att)] == 1 ) {
flags |= F_anakedfails; /* both naked fails */
}else if( bp->b_cur_piece[att] == 1 ) {
flags |= F_dnakedfails; /* both naked fails */
}
}
if( flags & F_refu ) {
if( (depth < 2) || !(outp && outp->refup) ) {
flags &= ~F_refu;
}
}
if( outp && outp->refup ) { /* FFS: guess work */
flags |= F_top;
}
#define REFUnote(ap,t,dep) if(flags&F_refu) refu_note(outp->refup,ap,t,dep);
#define REFUmove(ap,dp,sub) if(flags&F_refu) refu_move(outp->refup,ap,dp,sub);
#define REFUfail(ap,dp,sub) if(flags&F_refu) refu_fail(outp->refup,ap,dp,sub);
/*
* Check some theoretical knowledge, cheap enough to test,
* that we will not enter it into ACM.
*/
if( flags & F_anakedfails ) {
switch( bp->b_cur_piece[att] ) {
case 0: /* huh ? */
case 1: /* naked king cannot win */
/* TRC att is naked */
result = ANARES(ANA_MANY,FALSE); /* in any depth */
goto out;
}
}
if( flags & F_dnakedfails ) {
switch( bp->b_cur_piece[opp_colour(att)] ) {
case 1:
/* TRC def is naked */
result = ANARES(ANA_MANY,FALSE); /* in any depth */
goto out;
case 2:
flags |= F_a_no_beat;
if( f_jobtype == JT_selfmate ) {
flags |= F_try_smtfac;
}
break;
}
}
if( flags & F_a_kxk ) {
if( (1 == bp->b_cur_piece[opp_colour(att)])
&& (2 == bp->b_cur_piece[ att ]) ) {
ndep = kxk_mindep(bp);
if( ndep > dep ) {
dep = ndep;
if( dep > depth ) {
/* TRC theory/material */
result = ANARES(dep-1,FALSE);
goto out;
}
}
/* FFS: ndep < 0 */
}
}
result = ANARES(depth,FALSE); /* to stuff in the FALSE */
APC_CINC(); /* we cost ourselves */
#if WITH_EG
if( (flags & F_normal)
&& f_eguse
&& EGA_CAN_CNTS(bp->b_cur_piece[white], bp->b_cur_piece[black])
&& !(bp->b_castle[white] | bp->b_castle[black])
&& no_pos(bp->b_ep) /* FFS*/
) {
EgHandle* hp;
# define MKmat(bp,c) EG_MK_ONEMAT( (bp)->b_fig_cnt[c][dame], \
(bp)->b_fig_cnt[c][turm], \
(bp)->b_fig_cnt[c][laeufer], \
(bp)->b_fig_cnt[c][springer], \
(bp)->b_fig_cnt[c][bauer] )
# define MK64xy(p64) EG_MKXY(COL64(p64), LIN64(p64))
# define MKxy(bp,pos) MK64xy((bp)->b_f[pos].f_pos64)
hp = eg_find_handle( MKmat(bp,white), MKmat(bp,black) );
if( hp ) {
EgMat mat;
rPosition pos;
Field* p;
int c;
int ifig;
int minifig;
uint8 ibeg[2][MAX_FIGURES]; /* [C][F] */
EgQual q;
mat.m_tom = (att == black); /* EG: w=0, b=1 */
ibeg[0][bauer ] = bp->b_fig_cnt[white][springer]
+ (ibeg[0][springer] = bp->b_fig_cnt[white][laeufer ]
+ (ibeg[0][laeufer ] = bp->b_fig_cnt[white][turm ]
+ (ibeg[0][turm ] = bp->b_fig_cnt[white][dame ]
+ (ibeg[0][dame ] = 0))));
ibeg[1][bauer ] = bp->b_fig_cnt[black][springer]
+ (ibeg[1][springer] = bp->b_fig_cnt[black][laeufer ]
+ (ibeg[1][laeufer ] = bp->b_fig_cnt[black][turm ]
+ (ibeg[1][turm ] = bp->b_fig_cnt[black][dame ]
+ (ibeg[1][dame ] = 0))));
for( c=0 ; c<2 ; ++c ) {
minifig = COLOUR_IDX(c==black);
for( ifig = minifig + bp->b_max_piece[c==black]
; ifig >= minifig
; --ifig
) {
pos = bp->b_piece[ifig];
if( no_pos(pos) )
continue;
p = &(bp->b_f[pos]);
if( p->f_f == koenig ) {
mat.m_kpos[c] = MK64xy(p->f_pos64);
}else {
mat.m_fpos[c][ibeg[c][p->f_f]++] = MK64xy(p->f_pos64);
}
}
}
q = eg_val(hp, &mat);
#if 0
printf("eg_val = %2d\n", (int)q);
#endif
if( q == EGQ_DRAW ) {
egc_used(q);
result = ANARES(ANA_MANY, FALSE);
goto rdy;
}else if( EGQ_IS_LW(q) ) {
dep = EGQ_PLY(q); /* plies: #1 == 3; #2 == 5 */
if( EGQ_PLY_IS_WINS(dep) ) {
dep >>= 1; /* can mate is this many */
if( dep > depth ) {
if( --dep > ANA_MANY ) {
dep = ANA_MANY;
}
egc_used(EGQ_LW(1 + 2*dep));
result = ANARES(dep, FALSE);
goto rdy;
}else {
egc_used(q);
if( !outp || (!outp->resp && !outp->movp) ) {
result = ANARES(dep, TRUE);
goto rdy;
}
depth = dep; /* bigger ones are impossible */
goto doit;
}
}else { /* attacker looses */
egc_used(EGQ_DRAW); /*FFS*/
result = ANARES(ANA_MANY, FALSE);
goto rdy;
}
}
}
# undef MK64xy
# undef MKxy
# undef MKmat
}
#endif /* WITH_EG */
/*
* Now eventually check adaptive memory.
* If that decides, set 'result' and goto 'out'.
* If not decided, set "dep" to the first depth to be analysed.
*/
if( !acmp
&& (f_acmflags & F_ACM_DO)
&& (depth >= (1 + !(flags & F_help))) /*FFS*/
) {
acmp = acm_search(bp); APC_CO_INC();
}
if( acmp && (f_acmflags & F_ACM_USE) ) {
ndep = ACM_IDEP(acmp->mn_info);
if( ndep > 0 ) { /* something known */
if( ndep > depth ) { /* knows even bigger depth */
/* TRC ACM */
acm_used(acmp, ACM_INFO(depth,FALSE));
result = ANARES(ndep-ACM_IRES(acmp->mn_info), FALSE);
acm_release(acmp);
goto out; /* so no solution here */
}
if( ndep == depth ) { /* known depth matches needs */
if( (!outp || (!outp->resp && !outp->movp))
|| (!ACM_IRES(acmp->mn_info)) ) {
/*
* Result is either empty (no solution)
* or is not wanted outside, so:
*/
/* TRC ACM */
acm_used(acmp, acmp->mn_info);
result = ANARES(ndep,ACM_IRES(acmp->mn_info));
acm_release(acmp);
goto out;
}
if( dep < ndep ) {
acm_used(acmp, ACM_INFO(ndep-1, FALSE));
dep = ndep;
}
}else { /* ndep < depth */
if( ! ACM_IRES(acmp->mn_info) ) {
if( dep < ++ndep ) {
acm_used(acmp, acmp->mn_info);
dep = ndep;
}
}else { /* will succeed with smaller depth */
if( !outp || (!outp->resp && !outp->movp) ) {
/* and result is not wanted */
/* TRC ACM */
acm_used(acmp, acmp->mn_info);
result = ANARES(ndep,TRUE);
acm_release(acmp);
goto out;
}
acm_used(acmp, ACM_INFO(ndep-1, FALSE));
dep = ndep;
depth = ndep; /* bigger ones are impossible */
}
}
}
}
#if 1
/*
* Check special chess knowledge, if attacker has K and B, only ...
*/
if( (flags & F_normal)
&& (depth >= 2) /* else it does not pay off */
&& (dep < 2) /* else we assume, we did this, already */
&& (dep < BEST_MINDEP_BBB) /* currently best achievable FFS: ANA_MANY? */
&& (bp->b_fig_cnt[att][bauer] == (bp->b_cur_piece[att] - 1)) ) {
#if ! PROD_LEV
static int cnt2ana = 0;
if( (o_heiner & 04) && (--cnt2ana <= 0) ) {
put_packed(&bp->b_packed, "a2b\t");
printf("%d,%d ", depth, dep);
ndep = mate_mindep_bbb(bp, dep, 2);
printf("\n"); oflush();
cnt2ana = 888;
}else
#endif
{
ndep = mate_mindep_bbb(bp, dep, 0);
}
if( ndep > dep ) { /* improves lower bound */
if( ndep > depth ) { /* proves impossible */
--ndep; /* in so many moves */
/* TRC MDB */
result = ANARES(ndep, FALSE);
if( acmp ) {
acm_note(acmp, ACM_INFO(ndep, FALSE), APC_UPTO());
}
goto rdy;
}
dep = ndep;
}
}
#endif
doit:;
/*
* This job is not (completely) known, so do it the standard way.
* For this increment the effective depth "dep", until it reaches "depth".
* This is called `progressive deepening'.
* In order to avoid unnecessary move executions we remember what we
* know for each of the attacker moves:
* cant[aidx] the analysis depth for which the attacker move with
* index aidx cannot be a solution.
* mincant minimum over all 'thiscant', i.e. after each level
* the effective depth we have proven to be impossible.
*/
#if SHOW_ATTMVX
{ register int i;
for( i=0 ; i<dep ; ++i ) attmvx[i] = -1;
for( ; i<=depth ; ++i ) attmvx[i] = 0;
}
#endif
do {
TRC_ATT_START(dep);
if( dep > listcandep ) { /* need another move list */
APC_CINC(); /* for the move generator */
if( (dep == 1) && !(flags & F_a1_mg_full) ) {
(void) move1gen(bp, &attacks);
listcandep = 1;
attlength = list_length(&attacks);
note_attl_1(attlength);
}else {
if( (flags & F_anakedfails) && !(flags & F_help)
&& (bp->b_cur_piece[att] == 2) ) {
(void) ala_move_gen(bp, &attacks); /* cf. below */
}else {
(void) move_gen(bp, &attacks);
}
listcandep = 9999; /* "all moves" can all depths */
attlength = list_length(&attacks);
note_attl_N(attlength);
if( 0 == attlength ) { /* no legal attacker move */
/* Careful: when we have a restricted move list,
* we cannot announce a short solution, only a quick
* non-solution.
* - help[stale]mate: got full list
* - normal/stale: derive non-solution
* - self[stale]mate: checked 1-result, already,
* i.e. there is no early solution!
*/
switch( f_jobtype ) {
default:
panic("do_ana: jobtype %d (%d)", f_jobtype, __LINE__);
/*NOTREACHED*/
case JT_normal:
case JT_stalemate:
case JT_selfmate:
case JT_selfstalemate:
/* TRC no att move */
result = ANARES(dep=ANA_MANY,FALSE);
note_and_rdy: ;
if( acmp ) {
acm_note(acmp, ACM_INFO(dep, ANASUC(result)),
APC_UPTO());
}
goto rdy;
case JT_helpmate: /* have full list */
if( in_check(bp) ) { /* early solution */
result = ANARES(dep=0 , TRUE);
}else { /* stalemate */
/* TRC stalemate */
result = ANARES(dep=ANA_MANY, FALSE);
}
goto note_and_rdy;
case JT_helpstalemate: /* have full list */
if( ! in_check(bp) ) { /* early solution */
result = ANARES(dep=0 , TRUE);
}else { /* mate */
/* TRC mate */
result = ANARES(dep=ANA_MANY, FALSE);
}
goto note_and_rdy;
}
}
}
if( (aidx = attlength) > 0 ) {
while( --aidx >= 0 ) {
cant[aidx] = dep-1; /* that is for sure */
}
#if 1
ml_ck_attr(bp, &attacks);
#else
if( f_Qallowed < (depth-1) ) {
ml_ck_attr(bp, &attacks);
}
#endif
}
defsarefor = -1; /* aidx has new interpretation */
} /* new attacker move list */
if( !(flags & (F_tryanti|F_no_anti))
&& ( (dep >= 4)
|| ((dep >= 3) && (attlength >= 12))
)
) {
flags |= F_tryanti;
}
flags &= ~F_tryfac;
if( (dep == 2) && f_fac && (flags & F_ok_fac)
&& (bp->b_cur_piece[opp_colour(att)] > 1) ) {
flags |= F_tryfac;
km_dirs = fac_km_dirs(bp); APC_CINC();
akpos = K_POS(bp, att);
}else {
km_dirs = 0;
akpos = NO_POS; /* shuts off warning */
}
if( flags & F_m2 ) {
m2_leave(); flags &= ~F_m2;
}else if( (dep == 2) && (flags & F_normal) ) {
scadd(sc_m2 , 1);
scadd(sc_m2sum, list_length(&attacks));
if( f_mate2 ) {
m2_enter(bp, &attacks, &m2info);
flags |= F_m2; /* wanted & entered */
}
}
TRC_ATT_MOVES(bp, &attacks);
cantprom = 0; /* don't know such a thing (yet) */
aprom.m_from = NO_POS;
aprom.m_to = NO_POS;
mincant = ((listcandep < ANA_MANY) ? listcandep : ANA_MANY);
aidx = -1;
formoves( &attacks, ap ) {
++aidx; /* (logical) index of attacker move */
thiscant = cant[aidx]; /* what we know, already */
if( thiscant >= dep ) { /* already known: no solution */
if( thiscant < mincant ) {
mincant = thiscant;
}
scinc(sc_mvskipped[dep]);
continue;
}
if( attacks.l_attr & LA_CK ) {
/*
* We know already checking properties ...
*/
if( (dep <= 1) && (flags & (F_normal|F_stalem)) ) {
if( (flags & F_normal)
? ! (ap->m_attr & MA__CK) /* not even a check move */
: (ap->m_attr & MA__CK) /* is a check move */
) {
REFUnote(ap,
((flags & F_normal)?REFUT_NOTCHECK:REFUT_CHECK), 1)
cant[aidx] = 1;
if( 1 < mincant ) {
mincant = 1;
}
continue;
}
}
#if 0
if( (f_Qallowed <= 0)
&& ! (ap->m_attr & MA__CK) ) { /* not even a check move */
/* REFU: ? */
cant[aidx] = ANA_MANY;
continue;
}
#endif
}
if( (flags & F_a_no_beat) && (bp->b_f[ap->m_to].f_c != empty) ) {
/* TRC move would naken def */
REFUnote(ap, REFUT_DNAKED, ANA_MANY)
cant[aidx] = ANA_MANY;
continue;
}
aisprom = (bp->b_f[ap->m_from].f_f != ap->m_fig);
if( cantprom >= (unsigned)dep ) { /* know a good enough prom */
if( aisprom
&& (ap->m_from == aprom.m_from)
&& (ap->m_to == aprom.m_to ) ) {
REFUnote(ap, REFUT_DITO, (int)cantprom)
cant[aidx] = thiscant = cantprom;
if( thiscant < mincant ) {
mincant = thiscant;
}
continue;
}
cantprom = 0; /* forget it, proms are dense */
}
if( km_dirs
&& (ap->m_from == akpos)
&& (km_dirs & (1 << att_dir(ap->m_from, ap->m_to)))
) {
scinc(sc_fackm_used);
/* TRC K-move fac */
IF_HEINER_SET(02,
printf("fackm %02x skips\t", km_dirs); put_move(bp, ap);
)
cant[aidx] = thiscant = dep;
if( thiscant < mincant ) {
mincant = thiscant;
}
REFUnote(ap, REFUT_FACKM, dep)
continue;
}
if( flags & F_m2 ) { /* we did enter */
#if 1
if( ! (m2info.m2_apsdunno & SET1(ap->m_idx)) ) {
if( ! (m2info.m2_apscands & SET1(ap->m_idx)) ) {
thiscant = dep;
REFUnote(ap, REFUT_M2PIECE, dep)
}else {
APC_CINC();
if( ! m2_cand(bp, ap, &m2info) ) {
REFUnote(ap, REFUT_M2MOVE, dep)
thiscant = dep;
}
}
if( thiscant >= dep ) {
IF_HEINER_SET(0x20,
printf("m2 skips\t"); put_move(bp, ap);
)
cant[aidx] = thiscant;
if( thiscant < mincant ) {
mincant = thiscant;
}
continue;
}
}
#endif
}
scadd(sc_m2mvx, ((dep == 2) && (flags & F_normal)));
/*
* Analyse this attacker move at 'ap' for depth 'dep'.
* solution whether this attacker move is a solution
* thiscant if !solution: for which depth it is no solution
*/
#if SHOW_ATTMVX
attmvx[dep] += 1;
#endif
move_execute(bp, ap); APC_CINC(); scinc(mvx_att(dep));
if( flags & F_help ) {
register int subres; /* in odd plies */
subres = do_help_rest(bp, 2*dep-1, (AnaOut*)0);
solution = ANASUC(subres);
thiscant = (ANADEP(subres)+1)/2 - solution;
}else if( dep <= 1 ) {
if( flags & F_normal ) {
if( in_check(bp) ) {
solution = ! move_gen(bp, (Movelist*)0); APC_CINC();
thiscant = 1 - solution;
}else {
solution = FALSE; /* not even a checking move */
thiscant = 1;
}
}else if( flags & F_stalem ) {
if( ! in_check(bp) ) {
solution = ! move_gen(bp, (Movelist*)0); APC_CINC();
thiscant = 1 - solution;
}else {
solution = FALSE; /* is a checking move */
thiscant = 1;
}
}else { /* FFS: must be self[stale]mate */
/*
* This move is a "solution", if the defender now is forced
* to [stale]mate the attacker.
*/
defsarefor = aidx;
if( ! move_gen(bp, &defends) ) { /* def mate/stalemate */
solution = FALSE;
thiscant = ANA_MANY;
}else {
solution = TRUE; /* except we find a defense */
ml_ck_attr(bp, &defends);
if( f_jobattr & JTA_mate ) { /* all must be check */
formoves( &defends, dp ) {
if( ! (dp->m_attr & MA__CK) ) {
solution = FALSE; /* not even a check */
thiscant = 1;
break;
}
}
}else { /* none must be check */
formoves( &defends, dp ) {
if( dp->m_attr & MA__CK ) {
solution = FALSE; /* is a check */
thiscant = 1;
break;
}
}
}
if( solution ) { /* all moves say check */
formoves( &defends, dp ) {
move_execute(bp, dp);
APC_CINC(); scinc(mvx_def(1));
if( move_gen(bp, (Movelist*)0) ) { /* ! mate */
solution = FALSE;
thiscant = 1;
}
move_undo(bp);
if( ! solution ) {
break;
}
} /* for defends */
} /* all moves say check */
} /* has moves */
} /* s#1 */
}else { /* dep>=2 : Search for a defending move: */
#if 1
if( (flags & F_anakedfails) /* && !(flags & F_help) */
&& (bp->b_cur_piece[att] == 2) ) {
if( can_naken(bp, TRUE) ) {
/* TRC can naken att */
REFUnote(ap, REFUT_ANAKED, ANA_MANY)
solution = FALSE; /* for arbitrary depth */
thiscant = ANA_MANY;
goto after_defends;
}
}
#endif
d_pieces = bp->b_cur_piece[opp_colour(att)];
#if 1
/*
* The defender may even have a mate move, which is
* really fatal for all depthes. If we expect to be
* expensive, test explicitly for them:
*/
if( ((flags & (F_tryanti|F_didanti)) == F_tryanti)
&& (d_pieces > 1)
&& ! f_noanti
) {
Movelist mdefends; /* inited by move1gen */
APC_CINC(); scinc(sc_anti_tries);
if( move1gen(bp, &mdefends) ) { /* move exists */
scinc(sc_anti_lists);
TRC_DEF_START();
TRC_DEF_MOVES(bp, &mdefends);
solution = TRUE; /* unless we find one */
formoves( &mdefends, dp ) {
move_execute(bp, dp);
APC_CINC(); scinc(mvx_def(dep));
scinc(sc_anti_moves);
if( in_check(bp) ) {
APC_CINC();
if( ! move_gen(bp, (Movelist*)0) ) {
scinc(sc_anti_succ);
solution = FALSE;
}
}
move_undo(bp);
if( ! solution ) {
/* TRC can mate att */
REFUmove(ap, dp, ANARES(ANA_MANY,0))
thiscant = ANA_MANY;
goto defends_done;
}
}
TRC_DEF_END();
}
}
#endif
if( (flags & F_tryfac) && (d_pieces > 1) ) {
if( fac_has_guess ) { /* too fast for apx_cost */
if( is_fac_and_legal(bp, (Move*)0) ) {
/* TRC fact */
REFUnote(ap, REFUT_FACT, dep)
solution = FALSE;
thiscant = dep;
goto after_defends;
}
}
}
if( (flags & F_try_smtfac) && (d_pieces == 2) ) {
if( bp->b_fig_cnt[bp->b_tomove][dame] == 1 ) {
if( sm_has_tfac(bp) ) {
/* TRC sm-fact */
REFUnote(ap, REFUT_SMFACT, ANA_MANY)
solution = FALSE;
thiscant = ANA_MANY;
goto after_defends;
}
}
}
if( defsarefor != aidx ) {
(void) move_gen(bp, &defends); APC_CINC();
defsarefor = aidx; /* remember */
}
if( empty_list(&defends) ) { /* Early mate or stalemate: */
if( flags & F_nodef_fails ) {
solution = FALSE;
}else {
solution = !! in_check(bp);
if( flags & F_stalem ) solution ^= 1;
}
if( ! solution ) {
/* TRC stalemate */
REFUnote(ap, REFUT_NOMOVE, ANA_MANY)
thiscant = ANA_MANY; /* normal: stalemate */
}
}else { /* There are defending moves. Check them: */
int deflen; /* don't init: g++ bug */
TRC_DEF_START();
deflen = list_length(&defends);
solution = TRUE; /* except we find a good answer */
if( (flags & F_tryfac) && (d_pieces > 1) ) {
APC_CINC();
if( find_fac_inlist(bp, &defends) ) {
/* TRC fac */
REFUnote(ap, REFUT_FAC, dep)
solution = FALSE;
thiscant = dep;
goto defends_done;
}
}
if( f_danswer && (deflen > 1) ) {
APC_CADD( sort_answer(dep, bp, &defends) );
}
/*
* If the relative cost appears to be small enough
* test the moves first, whether we know one of them
* from the chess fact memory. If so, we turn
* "solution" to FALSE, and stop defender analysis.
*/
if( (deflen > 1) /* have a choice */
&& (f_acmflags & F_ACM_DO)
&& ( ((dep-1) >= NELEMS(attlsnoop))
|| (attlength >= attlsnoop[dep-1])
) ) {
register int cnt = 0;
register Bool chained = TRUE;
TRC_DEF_MOVES(bp, &defends);
scadd(sc_snp_list[dep-1], 1);
scadd(sc_snp_lsum[dep-1], deflen);
formoves( &defends, dp ) {
register AcmNode* acmq;
++cnt;
if( (dep-1) < NELEMS(stopsnoop) ) {
if( cnt > stopsnoop[dep-1] ) {
break; /* defends */
}
}
scinc(sc_snp_step[dep-1]); APC_CO_INC();
acmq = acm_snoop(bp,dp);
if( ! acmq ) {
continue;
}
/*
* When the info is completely zero,
* we do not yet know anything.
*/
if( (f_acmflags & F_ACM_USE)
&& (acmq->mn_info != 0) ) {
ndep = ACM_IDEP(acmq->mn_info)
- ACM_IRES(acmq->mn_info);
if( ndep >= (dep-1) ) {
/* TRC snoop */
REFUmove(ap, dp, ANARES(ndep,0))
solution = FALSE;
thiscant = ndep + 1;
scadd(sc_snp_list_succ[dep-1], 1);
scadd(sc_snp_step_succ[dep-1], cnt);
scadd(sc_snp_lsum_succ[dep-1], deflen);
if( ndep > (depth-1) ) {
ndep = depth-1;
}
acm_used(acmq, ACM_INFO(ndep,FALSE));
if( aisprom && (dp->m_to == ap->m_to) ) {
/*
* Remember prom defeated by beat
*/
aprom = *ap;
cantprom = thiscant;
}
}else if( ACM_IRES(acmq->mn_info) ) {
/* The info says, it will yield a
* solution! We mark the defender move
* and not use it below. We also
* note this as refutation failure.
*/
dp->m_attr |= MA_SKIP;
REFUfail(ap, dp, (int)acmq->mn_info)
if( chained ) { /* FFS */
acm_used(acmq, acmq->mn_info);
}
}else {
chained = FALSE;
}
}
acm_release(acmq);
if( ! solution ) {
goto defends_done;
}
} /* for defends */
} /* try snooping */
TRC_DEF_MOVES(bp, &defends);
formoves( &defends, dp ) {
register int subres;
if( dp->m_attr & MA_SKIP ) {
continue; /* snooping said "bad" */
}
move_execute(bp, dp); APC_CINC(); scinc(mvx_def(dep));
if( dep <= 2 ) {
switch( f_jobtype ) {
default:
panic("do_ana: jobtype %d (%d)",
f_jobtype, __LINE__);
/*NOTREACHED*/
case JT_normal:
subres = do1mate(bp, (AnaOut*)0);
break;
case JT_stalemate:
subres = do1stale(bp, (AnaOut*)0);
break;
case JT_selfmate:
subres = do1selfmate(bp, (AnaOut*)0,
(Movelist*)0, (int*)0, (AcmNode**)0);
break;
case JT_selfstalemate:
subres = do1selfstale(bp, (AnaOut*)0,
(Movelist*)0, (int*)0, (AcmNode**)0);
break;
}
}else {
subres = do_ana(bp, dep-1, (AnaOut*)0);
}
if( ! ANASUC(subres) ) { /* good defender */
REFUmove(ap, dp, subres)
solution = FALSE;
thiscant = ANADEP(subres) + 1;
}else {
REFUfail(ap, dp, subres)
}
move_undo(bp); /* defender move back */
if( ! solution ) {
if( aisprom && (dp->m_to == ap->m_to) ) {
aprom = *ap; /* remember prom */
cantprom = thiscant; /* defeated by beat */
}
break; /* defends */
}
} /* for defends */
defends_done: ;
TRC_DEF_END();
} /* non-empty defender move list */
after_defends: ;
} /* dep >= 2 */
move_undo(bp); /* attacker move back */
if( solution ) { /* this attacker move is a solution */
result = ANARES(dep,TRUE);
if( outp && outp->movp ) {
*(outp->movp) = *ap;
}
if( outp && outp->resp ) {
app_move(ap, outp->resp);
}else {
if( acmp ) {
acm_note(acmp, ACM_INFO(dep,TRUE), APC_UPTO());
acm_release(acmp);
}
goto out;
}
}else { /* this attacker move is no solution */
cant[aidx] = thiscant;
if( thiscant < mincant ) {
mincant = thiscant;
}
}
} /* for attacks */
dep_scanned:;
if( ANASUC(result) ) {
if( acmp ) {
acm_note(acmp, ACM_INFO(dep,TRUE), APC_UPTO());
}
}else {
if( flags & F_tryanti ) {
flags |= F_didanti; /* did it in this level */
}
if( mincant < dep ) {
panic("depth %d, dep %d, mincant %d\n", depth, dep, mincant);
}
if( acmp ) {
acm_note(acmp, ACM_INFO(mincant,FALSE), APC_UPTO());
}
while( (dep < mincant) && (dep < depth) ) {
++dep;
scinc(sc_lvskipped[dep]);
}
}
if( flags & F_m2 ) {
m2_leave(); flags &= ~F_m2;
}
if( (flags & F_top) && (f_stats > 0) ) {
sum_stats(dep, gtimer_now());
}
TRC_ATT_END();
}while( (++dep <= depth) && !ANASUC(result) );
--dep;
if( ANASUC(result) ) {
result = ANARES(dep, TRUE);
}else {
if( mincant < dep ) {
panic("depth %d, dep %d, mincant %d\n", depth, dep, mincant);
}
result = ANARES(mincant, FALSE);
#if SHOW_ATTMVX
{ register int i;
printf("attmvx[%2d %c%2d](%2d)",
depth, (depth<mincant)?'<':' ', mincant, attlength);
for( i=depth ; i>=1 ; --i ) {
if( attmvx[i] < 0 ) {
printf(" -");
}else {
printf(" %2d", attmvx[i]);
}
}
printf("\n");
}
#endif
}
rdy:;
if( acmp ) {
acm_release(acmp);
}
out:;
if( flags & F_m2 ) {
m2_leave(); flags &= ~F_m2;
}
if( outp && outp->resp ) {
mg_link(outp->resp);
}
APC_SYNC()
TRC_OUTOF_ANALYSE(bp, result, (outp ? outp->resp : (MoveList*)0));
return(result);
#undef REFUnote
#undef REFUmove
#undef REFUfail
}
static int /* constructed by ANARES(), in plies */
do_help_rest(
register Board* bp,
int plies, /* wanted depth of analysis */
AnaOut* outp) /* collected results */
{
/*
* The party to [stale]mate is to move, "plies" is odd (and >= 1).
* We do not enter this into ACM, nor do we search this job.
* No progressive deepening is considered, here.
* If we have no legal move, the job just fails.
* If we are naked (or a [stale]mate cannot be constructed anymore)
* the job may fail immediately.
*/
register int result;
register int subres;
register int thiscant;
register int mincant;
register int maxplies;
register int deepfail;
register rColour tom;
register Move* mp;
register Bool mustmate;
APC_DCL_LCL() /* lcl_cost */
Movelist mlist; /* inited by move generator */
maxplies = (ANA_MANY-1) | 1; /* force odd */
deepfail = ANARES(maxplies, FALSE); /* no solution in any depth */
mincant = maxplies;
if( outp && outp->resp ) {
clear_list(outp->resp);
}
mustmate = (f_jobtype == JT_helpmate); /* otherwise: stalemate */
tom = bp->b_tomove;
switch( bp->b_cur_piece[tom] ) {
case 0: /* huh ? */
case 1: /* naked king cannot mate */
if( mustmate || (bp->b_cur_piece[opp_colour(tom)] <= 1) ) {
/* TRC att is naked | theory/material */
result = deepfail;
goto out;
}
break;
case 2: /* [stale]mater has just K+X */
if( mustmate ) {
switch( bp->b_cur_piece[opp_colour(tom)] ) {
case 1: /* to be mated has just K (naked) */
if( bp->b_fig_cnt[tom][springer] /* KSK */
|| bp->b_fig_cnt[tom][laeufer] /* KLK */
) {
/* TRC theory/material */
result = deepfail; /* can't mate */
goto out;
}
/* FFS: KTK/KDK minimum depth */
}
}
}
APC_CADD(2); /* for ourselves + the move generator */
if( mustmate && (plies <= 1) ) { /* like mate in 1 */
if( ! move1gen(bp, &mlist) ) { /* no mate move exists */
result = ANARES(plies, FALSE);
goto out;
}
}else {
if( ! move_gen(bp, &mlist) ) { /* wrong party [stale]mate */
result = deepfail;
goto out;
}
}
result = ANARES(plies, FALSE); /* expected: no solution */
TRC_DEF_START();
TRC_DEF_MOVES(bp, &mlist);
formoves( &mlist, mp ) {
/*
* Before we execute the move, we may want to snoop in ACM.
*/
#if 1
if( (o_heiner & 8) && (plies >= 3) && (f_acmflags & F_ACM_DO) ) {
register AcmNode* acmp;
APC_CO_INC();
acmp = acm_snoop(bp, mp);
if( acmp ) {
/*
* When the info is completely zero,
* we do not yet know anything.
*/
if( (f_acmflags & F_ACM_USE) && (acmp->mn_info != 0) ) {
int depwant;
int dephave;
int suchave;
depwant = (plies-1)/2;
dephave = ACM_IDEP(acmp->mn_info);
suchave = ACM_IRES(acmp->mn_info);
if( dephave >= depwant ) { /* that is enough */
if( dephave > depwant ) {
dephave -= suchave;
suchave = FALSE;
subres = ANARES(dephave*2, suchave);
acm_used(acmp, ACM_INFO(depwant,suchave));
}else {
subres = ANARES(dephave*2, suchave);
acm_used(acmp, ACM_INFO(dephave,suchave));
}
acm_release(acmp);
goto have_subres;
}
} /* try use node info */
acm_release(acmp);
} /* found node */
} /* try snoop */
#endif
move_execute(bp, mp); APC_CINC(); scinc(mvx_def((plies+1)/2));
if( plies > 1 ) {
subres = do_help_full(bp, plies-1, (AnaOut*)0);
}else { /* plies==1: must be [stale]mate, now */
if( (!!in_check(bp)) == mustmate ) {
APC_CINC();
subres = ANARES(0, !move_gen(bp, (Movelist*)0));
}else {
subres = ANARES(0, FALSE);
}
}
move_undo(bp); /* move back */
have_subres:;
if( ANASUC(subres) ) { /* solution ! */
result = ANARES(ANADEP(subres)+1, TRUE);
if( outp && outp->movp ) {
*(outp->movp) = *mp; /* remember this solution */
}
if( outp && outp->resp ) {
app_move(mp, outp->resp);
}else { /* no more solutions wanted */
goto rdy_pos;
}
}else { /* this move is no solution */
thiscant = ANADEP(subres);
if( thiscant < mincant ) {
mincant = thiscant;
}
}
}
if( ! ANASUC(result) && (plies > 1) ) {
++mincant; /* we collected subres minimum */
if( mincant > ANA_MANY ) {
mincant = ANA_MANY;
}
if( ! (mincant & 01) ) {
--mincant; /* force odd */
}
if( mincant > ANADEP(result) ) {
result = ANARES(mincant, FALSE);
}
}
rdy_pos:;
TRC_DEF_END();
out:;
if( outp && outp->resp ) {
mg_link(outp->resp);
}
APC_SYNC()
/* FFS: ANADEP(result) > ANA_MANY */
return result;
}
static int /* constructed by ANARES(), in plies */
do_help_full(
Board* bp,
register int plies, /* wanted depth of analysis */
AnaOut* outp) /* collected results */
{
/*
* The party to be [stale]mated is to move, "plies" is even (and >= 2).
* The other side must not be made naked (if helpmate).
* If there is no legal move, we either have a mate or a stalemate:
* - if mate/stalemate matches the job: solution in 0 plies
* - if mate/stalemate does not match: no solution in any depth
* Here we want to perform the progressive deepening,
* and therefore use ACM, here.
* All this is done via the standard "do_ana()",
* which will call "do_help_rest()" after one ply.
*/
register int result;
result = do_ana(bp, plies/2, outp);
plies = 2*ANADEP(result);
if( (plies > ANA_MANY) && !ANASUC(result) ) {
plies = ANA_MANY;
if( plies & 01 ) {
--plies; /* force even */
}
}
result = ANARES(plies, ANASUC(result));
return result;
}
static int /* constructed by ANARES() */
ana_0_dep( /* shall be already [stale]mate */
Board* bp,
Movelist* resp, /* all solutions */
Move* movp) /* one solution */
{
int result;
result = ANARES(0,FALSE);
if( ! (f_jobattr & (JTA_mate | JTA_stalemate)) ) {
panic("jobtype %d", f_jobtype); /*NOTREACHED*/
}
if( resp ) {
clear_list(resp);
}
if( movp ) {
movp->m_from = NO_POS;
}
if( (!!in_check(bp)) == !!(f_jobattr & JTA_mate) ) {
++apx_cost; /* for move_gen [uncached] */
if( ! move_gen(bp, (Movelist*)0) ) { /* no legal move */
result = ANARES(0,TRUE);
}
}
return result;
}
Eximpl int /* constructed by ANARES(), in plies */
ana_help(
Board* bp,
int plies, /* wanted depth of analysis */
Movelist* resp, /* all solutions */
Move* movp) /* one solution */
{
int result;
switch( f_jobtype ) {
case JT_helpmate:
case JT_helpstalemate:
break; /* ok */
default:
panic("jobtype %d", f_jobtype);
/*NOTREACHED*/ result = 0; /* shut off warning */
}
if( plies <= 0 ) { /* need be [stale]mate, already */
result = ana_0_dep(bp, resp, movp);
}else { /* plies >= 1 */
/* FFS: plies > ANA_MANY */
AnaOut anaout;
AnaOut* outp;
if( resp || movp ) {
anaout.resp = resp;
anaout.movp = movp;
anaout.refup = (RefuList*)0;
outp = &anaout;
}else {
outp = 0;
}
if( plies & 01 ) {
result = do_help_rest(bp, plies, outp);
}else {
result = do_help_full(bp, plies, outp);
}
}
return result;
}
Eximpl int /* constructed by ANARES() */
analyse(
Board* bp,
int depth, /* wanted depth of analysis */
Movelist* resp, /* all solutions */
Move* movp, /* one solution */
RefuList* refup) /* collect refutations */
{
int result;
AnaOut anaout;
AnaOut* outp;
if( resp || movp /* || refup FFS */ ) {
anaout.resp = resp;
anaout.movp = movp;
anaout.refup = refup;
outp = &anaout;
}else {
outp = 0;
}
switch( f_jobtype ) {
case JT_helpmate:
case JT_helpstalemate:
result = ana_help(bp, depth*2, resp, movp);
result = ANARES(ANADEP(result)/2, ANASUC(result));
break;
case JT_selfmate:
if( depth <= 0 ) {
result = ana_0_dep(bp, resp, movp);
}else if( depth <= 1 ) {
result = do1selfmate(bp, outp, (Movelist*)0,(int*)0,(AcmNode**)0);
}else {
result = do_ana(bp, depth, outp);
}
break;
case JT_selfstalemate:
if( depth <= 0 ) {
result = ana_0_dep(bp, resp, movp);
}else if( depth <= 1 ) {
result = do1selfstale(bp, outp, (Movelist*)0,(int*)0,(AcmNode**)0);
}else {
result = do_ana(bp, depth, outp);
}
break;
case JT_normal:
if( depth <= 1 ) {
result = do1mate(bp, outp);
}else {
result = do_ana(bp, depth, outp);
}
break;
case JT_stalemate:
if( depth <= 1 ) {
result = do1stale(bp, outp);
}else {
result = do_ana(bp, depth, outp);
}
break;
default:
panic("jobtype %d", f_jobtype);
/*NOTREACHED*/ result = 0; /* shut off warning */
}
return result;
}