/* * 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 $ * * 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 #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 * m 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 (!(flags & (F_tryanti | F_no_anti)) && ((dep >= 4) || ((dep >= 3) && (attlength >= 12)) ) ) { flags |= F_tryanti; } } 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 */ 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; }