/* * CHEST, chess analyst. For Copyright notice read file "COPYRIGHT". * * $Source: /home/heiner/ca/chest/RCS/answer.c,v $ * $Id: answer.c,v 3.13 1999/07/20 20:59:03 heiner Exp $ * * implement answer heuristics * * Ideas: when total material of attacker is low, beating it is better */ #include "bsd.h" #include "types.h" #include "board.h" #include "mgsubr.h" #include "mlsubr.h" #include "move.h" #include "move_gen.h" #include "trace.h" #include "analyse.h" #include "answer.h" /* * Deleted when changing RCS revision 1.5 -> 2.1: * sort_simple() * copy_movelist() * sort_movelist() * sort_weighted_simple() */ /* * GENERAL: * This module tries to select from all legal defender moves * those, which should be used first, as we expect them to * lead to a cheaper overall analysis. * * While the first objective of the defender is to avoid a mate, * this is in almost all occurring positions no problem. * As most of the legal attacker moves are analysed, anyhow, * in most cases the defender cannot be mated regardless * of his move. * * But, the different defender moves tend to lead to sub-analysis * of different cost. The effort needed to show the attacker * to be incapable of mating tends to be larger, when he has more * legal moves. * * Hence, the real objective of the defender is: * (A) to cut down the move possibilities of the attacker, and * (B) to make a mate combination more absurd. * * Methods to achieve such (in approximate order of importance) are: * (a) Beat attacker pieces: those cannot have have any legal * move in any further depth. In extreme cases this may * lead to a naked attacker king, which then cannot mate * anymore. * (b) Say 'check' to the attacker. He cannot ignore it, * and is severly restricted in his move possibilies * in the directly following level. * (c) Restrict the move possibilities of the attacker king. * King moves are a not so small percentage of all attacker moves. * Bayer 9-mate: 3.57 per mg, 34.4% of all moves. * att in check: 75.4% of mg-calls * (d) Pinning attacker pieces. Restricts its moving capabilities * for one or more further levels. Prepares beat. * (e) Move the defender K to a less dangerous field. * Where it is restricted by less border, and by less actual * attacker threats. * (f) Prepare some of the above by unpinning a defender piece. * (g) Prepare some of the above by promotion. * (h) Prepare promotion by advancing (promising) pawns. * (i) Block attacker promotions. * * Statistics from Bayer 9-mate: * - when defender is in check: 2.09 K-moves / mg-call * - attacker is in check: 75.4% of mg-calls * - attacker K-moves: 3.57 / mg-call * 34.4% of all attacker moves * - average # of moves per piece: FFS * * MRFC = missing reason for constant */ static int8 mat_val[MAX_FIGURES] = { /* [ Figure ] */ /* B S L T D K */ 1, 3, 3, 5, 9, 0 /* material in B units */ }; /* FFS: typical # of moves per piece */ /* ============================================================================ * Level 2 heuristic. * */ #define LEV2_PROM_BLOCK 0 /* CF: too expensive */ Eximpl int /* ARGSUSED */ sort_2_weighted( int depth, /* is 2, ignored here */ register Xconst Board * bp, /* defender to move */ register Movelist * lp) { /* all legal defender moves */ register Move *mp; register Xconst Field *tp; register Xconst Field *fp; register rPieceSet emask; /* enemies (attackers) */ register Xconst Field *dkp; /* defender's king (ours) */ register int v; register rColour enemy; PieceSet dkatt; int kescs; /* # def-K escapes */ #if LEV2_PROM_BLOCK int epromlin; /* enemies promotion line */ #endif if (list_length(lp) <= 1) { return 0; /* nothing to be sorted */ } if (!(lp->l_attr & LA_CK)) { ml_ck_attr(bp, lp); /* get checking attributes */ } enemy = opp_colour(bp->b_tomove); dkp = K_FP(bp, bp->b_tomove); emask = COLOUR_MASK(enemy); /* all enemies */ dkatt = BOTH_KINGS & ~emask;/* our king */ kescs = -1; /* not yet computed */ #if LEV2_PROM_BLOCK epromlin = PROM_LIN(enemy); #endif formoves(lp, mp) { fp = &(bp->b_f[mp->m_from]); tp = &(bp->b_f[mp->m_to]); v = 0; /* collect value in "v" */ if (mp->m_attr & MA__CK) { /* says 'check' */ PieceSet eatts; eatts = F_DATT(tp) & emask; if (eatts & ~BOTH_KINGS) { v -= 1 /* MRFC */ ; /* non K may beat back */ } switch (mp->m_attr & MA__CK) { /* MRFC... */ case MA_DCK: v += 6; break; /* direct */ case MA_ICK: v += 6; break; /* indirect */ case MA_DCK | MA_ICK: v += 9; break; /* double */ case MA_DCK | MA_NCK: v += 7; break; /* direct near */ case MA_ICK | MA_NCK: v += 7; break; /* indirect near */ case MA_DCK | MA_ICK | MA_NCK: v += 10; break; /* double near */ } } if (tp->f_c != empty) { /* beats attacker piece */ v += mat_val[tp->f_f]; /* beaten material */ if (F_IATT(dkp) & SET1(tp->f_idx)) { v += 2 /* MRFC */ ; /* destroys pinning */ } } #if LEV2_PROM_BLOCK else { if (LIN64(tp->f_pos64) == epromlin) { register const Field *xp; xp = tp - bau_mov[enemy]; if ((xp->f_f == bauer) && (xp->f_c == enemy)) { v += 5; /* mat_val[turm] */ } } } #endif if (F_DATT(dkp) & emask) { /* defender is in check */ /* analyse king escape situation */ if (mp->m_fig == koenig) { /* K move while in check */ register Xconst Field *xp; register rPieceSet mask; register int i; mask = emask; if (tp->f_c != empty) { mask &= ~SET1(tp->f_idx); /* without the beaten one */ } if (kescs < 0) {/* not yet computed */ kescs = 0; for (i = MIN_D_DIR; i < MAX_D_DIR; ++i) { xp = fp + dam_mov[i]; if (!(F_DATT(xp) & emask) && ((xp->f_c == enemy) || (xp->f_c == empty))) { kescs += 1; } } } v -= kescs; /* those before the move */ for (i = MIN_D_DIR; i < MAX_D_DIR; ++i) { xp = tp + dam_mov[i]; if (((xp == fp) || (xp->f_c == enemy) || (xp->f_c == empty)) && !(F_DATT(xp) & mask)) { v += 1; } } /* FFS: integrate the following into the above? */ i = pos64_borders[fp->f_pos64] - pos64_borders[tp->f_pos64]; if (i) { if (i > 0) {/* more border around K before move */ v++; } else { v--; } } } else { /* non-K move while in check */ if (F_DATT(fp) & dkatt) { v += 1; /* MRFC adds potential new K escape */ } if (F_DATT(tp) & dkatt) { v -= 1; /* MRFC destroys potential K escape */ } } } mp->m_value = v; mp->m_value2 = 0; } /* The following sort takes ca 28% of the total time of this function. * Mostly the first (best) of the moves is used, only. FFS: do not sort * before needed. */ ml_sort_rdx(lp); return 2; } /* ============================================================================ * For depth >= 3 */ /* * ana_att_moves() * This is a special version of the normal move generator. * While the defender is really to move, we pretend the attacker * being to move, and count what he could do, in order to use it * as a basis to differentiate between the defender moves, * according to how they change what the attacker will be able to do. * * We do not generate the moves themselves, but rather count them, * separately for each piece. The counter vector "mlp" * is indexed by the piece index and incremented. * Hence, the counter array should be cleared, before. * Restrictions: * - the attacker must not be in check (else defender could beat K) * - castling moves are not yet considered * * Returns the number of all counted moves. */ static int /* total number of moves found */ ana_att_moves( register Xconst Board * bp, /* count opponents moves * in */ register int *mlp) { /* here [idx] */ register Xconst Field *tp; register int tpos; register int delta; register int i; register int imax; register Xconst Field *p; register int *mp; /* points to element in mlp[] */ Position pos; Colour self; Colour enemy; Position kpos; int8 ifig; int8 minifig; int pindir; PieceSet iatts; PieceSet atts; PieceSet enemymask; int nmoves; nmoves = 0; self = opp_colour(bp->b_tomove); /* attacker, would not be to move */ enemy = opp_colour(self); /* defender, normally to move now */ kpos = K_POS(bp, self); /* Analyse the checking situation of our king: */ enemymask = COLOUR_MASK(enemy); iatts = F_IATT(&(bp->b_f[kpos])) & enemymask; /* those may pin someone */ atts = F_DATT(&(bp->b_f[kpos])) & enemymask; if (atts) { /* enemy would be able to beat K */ panic("ana_att_moves: check.\n"); } /* decide type of move enumeration */ /* We are not in check. Thus our pieces can move relatively freely, as * they are not forced to defend against a check. Thus enumerate the move * possibilities by the capable figures: */ minifig = COLOUR_IDX(self); for (ifig = minifig + bp->b_max_piece[self] - 1 ; ifig >= minifig ; --ifig) { /* enumerate non-K pieces */ pos = bp->b_piece[ifig]; if (no_pos(pos)) continue; /* skip empty slot (beaten piece) */ p = &(bp->b_f[pos]); mp = &mlp[ifig]; /* increment here for every move */ /* Analyse the pinning of this piece: */ pindir = NO_DIR; if ((atts = (iatts & F_DATT(p)))) { i = att_dir(pos, kpos); if (dam_dir(i)) { delta = dam_mov[i]; if ((pos + delta) != kpos) { if (atts & F_IATT(&(p[delta]))) { pindir = i; } } else { /* Piece to be checked is near to its king. Therefore * there is only one f_iatt, which alone is not * sufficient for check of direction. If T-dir, we are * already sure to be pinned. */ if (trm_dir(i)) { pindir = i; } else { /* L-dir, search: */ tp = p; do { tp -= delta; } while (tp->f_c == empty); if ((tp->f_c == enemy) && (atts & SET1(tp->f_idx))) { pindir = i; } } } } } switch (p->f_f) { case bauer: /* Try single and double step: */ delta = bau_mov[self]; if (no_dir(pindir) || (delta == dam_mov[pindir]) || (delta == dam_mov[opp_dir(pindir)])) { /* Not pinned or staying in pinning */ tpos = pos; for (i = 0; i < 2; ++i) { if (i && (LIN64(p->f_pos64) != BAS_LIN(self))) break; tpos += delta; if (bp->b_f[tpos].f_c != empty) break; if (LIN64(p->f_pos64) == BAS_LIN(enemy)) { *mp += 4; nmoves += 4; } else { *mp += 1; nmoves += 1; } } } /* Try to beat in both directions: */ for (i = 0; i < 2; ++i) { delta = (i ? bau_right : bau_left)[self]; if (!no_dir(pindir) && (delta != dam_mov[pindir]) && (delta != dam_mov[opp_dir(pindir)])) { continue; } /* Not pinned or staying in pinning */ tpos = pos + delta; tp = &(bp->b_f[tpos]); if ((tp->f_c == border) || (tp->f_c == self)) continue; if (tp->f_c == empty) { /* try e.p.: */ if (bp->b_ep == (tpos - bau_mov[self])) { if (!ep_legal(bp, pos, tpos, kpos)) continue; *mp += 1; nmoves += 1; } } else { /* try normal beat: */ if (LIN64(p->f_pos64) == BAS_LIN(enemy)) { *mp += 4; nmoves += 4; } else { *mp += 1; nmoves += 1; } } } break; case springer: if (!no_dir(pindir)) break; /* pinning always left by S */ for (i = 0; i < 8; ++i) { tp = &bp->b_f[pos + spr_mov[i]]; if ((tp->f_c != border) && (tp->f_c != self)) { *mp += 1; nmoves += 1; } } break; case laeufer: if (no_dir(pindir)) { i = MIN_L_DIR; imax = MAX_L_DIR; } else if (lfr_dir(pindir)) { i = pindir & ~1; imax = i + 2; } else { break; } goto ltd; case turm: if (no_dir(pindir)) { i = MIN_T_DIR; imax = MAX_T_DIR; } else if (trm_dir(pindir)) { i = pindir & ~1; imax = i + 2; } else { break; } goto ltd; case dame: if (no_dir(pindir)) { i = MIN_D_DIR; imax = MAX_D_DIR; } else { i = pindir & ~1; imax = i + 2; } ltd: /* When pinned, we here already have restricted the directions to * pindir and its complement. */ for (; i < imax; ++i) { tp = &(bp->b_f[pos]); delta = dam_mov[i]; do { tp += delta; if ((tp->f_c == border) || (tp->f_c == self)) break; *mp += 1; nmoves += 1; } while (tp->f_c == empty); } break; case koenig: /* is handled below */ break; default: panic("ana_att_moves: figure %d", p->f_f); break; } } /* enumerate non-K pieces */ /* Now add the king moves: */ p = &(bp->b_f[kpos]); mp = &mlp[p->f_idx]; for (i = MIN_D_DIR; i < MAX_D_DIR; ++i) { tp = p + dam_mov[i]; if ((tp->f_c == border) || (tp->f_c == self)) continue; if (F_DATT(tp) & enemymask) continue; /* Note, that we are not in check */ *mp += 1; nmoves += 1; } #if 0 /* not yet */ /* Try to castle: */ if (bp->b_castle[self]) { gen_castle(bp, kpos, lp); } #endif return nmoves; } static Bool fig__can_dir( const Board * bp, /* whether in this Board */ register rPieceSet att, /* one of these SLTD * pieces */ int dir) { /* might go in this direction */ register int zeroes; register int i; i = 0; while (att) { while (!(att & 01)) { zeroes = MIN_LOW_ZERO(att); i += zeroes; att >>= zeroes; } switch (bp->b_f[bp->b_piece[i]].f_f) { case springer: if (spr_dir(dir)) return 1; break; case laeufer: if (lfr_dir(dir)) return 1; break; case turm: if (trm_dir(dir)) return 1; break; case dame: if (dam_dir(dir)) return 1; break; } att >>= 1; ++i; } return 0; /* not found */ } /* * fig__type() * In the given Board, return the figure type of the lowest bit * found in the given piece set. */ static Figure fig__type( const Board * bp, register rPieceSet att) { register int zeroes; register int i; if (!att) { return no_figure; } i = 0; while (!(att & 01)) { zeroes = MIN_LOW_ZERO(att); i += zeroes; att >>= zeroes; } return bp->b_f[bp->b_piece[i]].f_f; } static const Field * fig__pos( const Board * bp, register rPieceSet att) { register int zeroes; register int i; if (!att) { return 0; } i = 0; while (!(att & 01)) { zeroes = MIN_LOW_ZERO(att); i += zeroes; att >>= zeroes; } return &(bp->b_f[bp->b_piece[i]]); } static Bool fig_can_move( Figure fig, register const Field * fp, register const Field * tp) { register const Field *p; register int delta; int dir; dir = att_dir(fp, tp); if (no_dir(dir)) { return FALSE; } switch (fig) { case laeufer: if (!lfr_dir(dir)) return FALSE; break; case turm: if (!trm_dir(dir)) return FALSE; break; case dame: if (!dam_dir(dir)) return FALSE; break; /* heim FFS: default ? */ } /* test path from fp to tp */ delta = dam_mov[dir]; for (p = fp + delta; p != tp; p += delta) { if (p->f_c != empty) { return FALSE; } } /* heim FFS: tp->f_c ? (empty, enemy) */ return TRUE; } #define LOW_BIT(x) ((x) ^ ((x) & ((x)-1))) #define CLR_LOW_BIT(x) ((x) &= ((x)-1)) #define OWN_VALUE(fig,depth) (mat_val[(fig)] / ((depth)>=5 ? 2 : 3)) /* MRFC */ #define ATT_VALUE(fig,depth) (mat_val[(fig)] / ((depth)>=5 ? 2 : 3)) /* MRFC */ #define V2_VAL(n) ((n) - ((n) >> 3)) /* * 0.875 */ /* MRFC */ #define BIT_SUM32(v) ( bitsum[((unsigned char *) &(v))[0]] \ + bitsum[((unsigned char *) &(v))[1]] \ + bitsum[((unsigned char *) &(v))[2]] \ + bitsum[((unsigned char *) &(v))[3]] \ ) #define OWN_V_RES 0 /* whether own value on result of promotion */ #if (PROD_LEV == 0) && 0 /* CF: local debugging */ # define VV(x) x #else # define VV(x) /* empty */ #endif static void find_chk_nxt( int depth, Xconst Board * bp, /* defender's board */ Movelist * lp, /* and his legal moves */ const int *fig_moves, /* [f_idx] how many can * it (def&att) */ PieceSet ck_figs, /* lp->l_hasckmv FFS */ EscSet escs, /* curr K-escapes of * attacker */ EscSet noescs1d, PieceSet does1d) { register const Field *ekp; register rPieceSet emask; register Move *mp; register Xconst Field *p; register Xconst Field *tp; Xconst Field *fp; const Field *dkp; int ma; int beat_fig; int back_ck; int mov_dir; int nxt_dir; int v; int v2; int bestv; int bestv2; int havebest; int tries; Xconst Field *sav_p; PieceSet nxt_ck_fig_set; emask = COLOUR_MASK(opp_colour(bp->b_tomove)); dkp = K_FP(bp, bp->b_tomove); ekp = K_FP(bp, opp_colour(bp->b_tomove)); nxt_ck_fig_set = 0; /* Look for a move that may say check one move later */ formoves(lp, mp) { if (mp->m_attr & MA__CK) continue; /* says check itself */ tp = &(bp->b_f[mp->m_to]); if ((F_DATT(tp) & emask) && (ck_figs & SET1(mp->m_idx)) ) { continue; } if ((mp->m_fig == laeufer) && (pos64_dark[tp->f_pos64] != pos64_dark[ekp->f_pos64]) ) { continue; } bestv = 127; /* really large */ bestv2 = 127; /* really large */ havebest = FALSE; tries = 1; if (dam_dir(att_dir(tp, dkp)) && (F_DATT(tp) & emask & ~BOTH_KINGS) && fig_can_move(fig__type(bp, F_DATT(tp) & emask & ~BOTH_KINGS), tp, dkp) ) { back_ck = 1; } else { back_ck = 0; } fp = &(bp->b_f[mp->m_from]); if (mp->m_fig == springer) { /* also S-promotion */ /* FFS: darkness test */ for (nxt_dir = 0; nxt_dir < 8; ++nxt_dir) { p = tp + spr_mov[nxt_dir]; if ((p->f_c != border) && (p->f_c != bp->b_tomove) && (spr_dir(att_dir(p, ekp))) ) { goto found_ck; } } continue; } /* check from tp --> ekp There has to be exactly one piece on that * blocks the path. (expect beat or uncovering) */ nxt_dir = att_dir(tp, ekp); if (dam_dir(nxt_dir)) { switch (mp->m_fig) { case laeufer: if (!lfr_dir(nxt_dir)) { break; } goto indir_by_ltd; case turm: if (!trm_dir(nxt_dir)) { break; } goto indir_by_ltd; case dame: indir_by_ltd: { int fig_cnt; LegalDelta delta; fig_cnt = 0; delta = dam_mov[nxt_dir]; sav_p = 0; for (p = tp + delta; p != ekp; p += delta) { if (p->f_c != empty) { if (p->f_c == bp->b_tomove) { if (!fig_moves[p->f_idx]) { break; } if (p->f_f == bauer && (COL64(tp->f_pos64) == COL64(ekp->f_pos64)) ) { break; } } if (fig_cnt > 0) break; fig_cnt++; sav_p = p; } } if (p == ekp) { p = sav_p; goto found_ck; } } break; default: break; } continue; /* consider next move *//* FFS: D */ } switch (mp->m_fig) { default: /* FFS: B without prom? */ continue; case laeufer: nxt_dir = MIN_L_DIR; ma = MAX_L_DIR; break; case turm: nxt_dir = MIN_T_DIR; ma = MAX_T_DIR; break; case dame: nxt_dir = MIN_D_DIR; ma = MAX_D_DIR; break; } /* For the rest of the analysis of this move, the resulting piece is * one of LTD (multi-step figure). */ tries = 4; /* try this one harder */ mov_dir = att_dir(fp, tp); VV(printf("Cd %d..%d\n", nxt_dir, ma - 1); ) for (; nxt_dir < ma; ++nxt_dir) { int delta; if ((nxt_dir == opp_dir(mov_dir)) /* don't move back */ ||(tp->f_c == empty && nxt_dir == mov_dir) ) { continue; } beat_fig = 0; delta = dam_mov[nxt_dir]; /* find a move from tp to a field p, where the defender may say * check. */ for (p = tp; beat_fig == 0;) { p += delta; if ((p->f_c == bp->b_tomove) || (p->f_c == border) ) { break; /* next dir */ } else if (p->f_c != empty) { /* enemy */ beat_fig++; } if (!fig_can_move(mp->m_fig, p, ekp)) /* try to say check! */ continue; /* If there is a direct way from fp to p, don't move * indirect! */ if ((fp->f_f == mp->m_fig) && fig_can_move(mp->m_fig, fp, p)) { continue; /* D only */ } found_ck:; /* entered by S and B-proms, also */ { int bad; int king_moves; int ck_block; PieceSet s; nxt_ck_fig_set |= SET1(mp->m_idx); bad = 0; s = escs; if (SET1(mp->m_idx) & does1d) { /* Consider escapes, what is covered before by only * this piece. */ s |= fig_cov[fp->f_f][fp - ekp] & noescs1d; } VV(printf("Cc cov[%d][%2o->%2o] = %3x\n", mp->m_fig, p->f_pos64, ekp->f_pos64, fig_cov[mp->m_fig][p - ekp]); ) s &= ~fig_cov[mp->m_fig][p - ekp]; /* -= covered from p */ king_moves = bitsum[s]; switch (mp->m_fig) { case dame: case turm: case laeufer: ck_block = 1; break; default: /* should not happen */ case koenig: case bauer: case springer: ck_block = 0; break; } if (king_moves < 1) { king_moves = 1; /* FFS */ } if (ck_block) { register Xconst Field *xp; int xdelta; PieceSet eatts; eatts = emask & ~BOTH_KINGS; xdelta = dam_mov[att_dir(tp, p)]; for (xp = tp + xdelta; xp != p; xp += xdelta) { if (F_DATT(xp) & eatts) bad++; } xdelta = dam_mov[att_dir(p, ekp)]; for (xp = p + xdelta; xp != ekp; xp += xdelta) { if (F_DATT(xp) & eatts) bad++; } } if (F_DATT(p) & emask) { #if OWN_V_RES bad += 1 + OWN_VALUE(mp->m_fig, depth - 1); /* FFS */ #else bad += 1; if (mp->m_fig == fp->f_f) { /* no promotion */ bad += OWN_VALUE(mp->m_fig, depth - 1); } /* FFS: promotion: always B value? always D value? */ #endif } if (F_DATT(tp) & emask) { bad++; /* FFS */ } bad += back_ck * 2; /* MRFC */ VV(printf("C> %2o-%2o %d->%d: v=%3d, v2=%3d\n", fp->f_pos64, tp->f_pos64, fp->f_f, mp->m_fig, mp->m_value, mp->m_value2); ) VV(printf("C back_ck=%d, bad=%d, k_moves=%d, fig_moves=%d, escs=%3x, s=%3x\n", back_ck, bad, king_moves, fig_moves[p->f_idx], escs, s); ) v = mp->m_value; v2 = mp->m_value2; v += back_ck; /* MRFC */ v2 = (((v - (bad)) * king_moves) + (bad * v) ) / v; if ((depth >= 4) && (p->f_c != empty)) { VV(printf("C1\n"); ) v2 -= fig_moves[p->f_idx] >> 2; /* MRFC */ } if (tp->f_c != empty) { if ((depth >= 4) && (F_DATT(tp) & nxt_ck_fig_set & ~SET1(mp->m_idx)) ) { VV(printf("C2\n"); ) /* ??? FFS, Hinterstellung; Bayer-Magie */ v2 -= 3; v /= 2; if (mp->m_fig == springer) { v--; } if (v < 1) v = 1; } } if (v2 < 1) v2 = 1; v++; if (depth <= 3) { VV(printf("C3\n"); ) v += 1; v2 += 3; } else if (depth == 4) { VV(printf("C4\n"); ) v += 1; v2 += 1; } VV(printf("C: %2o-%2o %d->%d: v=%3d, v2=%3d\n", fp->f_pos64, tp->f_pos64, fp->f_f, mp->m_fig, v, v2); ) if (!havebest || ((v * v2) < (bestv * bestv2))) { bestv = v; bestv2 = v2; havebest = TRUE; } if (--tries <= 0) { goto rdy_move; } } } /* scan p in nxt_dir */ } rdy_move:; if (havebest) { mp->m_value = bestv; mp->m_value2 = bestv2; VV(printf("C< %2o-%2o %d->%d: v=%3d, v2=%3d\n", fp->f_pos64, tp->f_pos64, fp->f_f, mp->m_fig, mp->m_value, mp->m_value2); ) } } /* formoves */ } static void /* ARGSUSED */ try_promotion( int depth, const Board * bp, /* defender's board */ Movelist * lp, /* and his legal moves */ const int *fig_moves, /* [f_idx] how many can * it (def&att) */ PieceSet ck_figs, /* lp->l_hasckmv FFS */ EscSet escs, /* curr K-escapes of * attacker */ EscSet noescs1d, PieceSet does1d) { /* Try to push promising promotions. */ register Move *mp; register Move *nearest; int promotion_line; int mindist; int nearcnt; promotion_line = PROM_LIN(bp->b_tomove); nearest = 0; mindist = 999; /* far far away */ nearcnt = 0; formoves(lp, mp) { register int dist; if (mp->m_fig != bauer) { continue; } dist = promotion_line - LIN(mp->m_to); if (dist < 0) dist = -dist; if (dist < mindist) { mindist = dist; nearest = mp; nearcnt = 1; } else if (dist == mindist) { nearcnt += 1; } } if (nearest) { /* That one would need (1+mindist) moves to promote, leaving a subjob * of depth-(1+mindist). When that one is at least a 2-mate, we * expect the promotion to help the defender. FFS: do experiment */ register int subdep; subdep = depth - (1 + mindist); /* subjob left after promotion */ if (subdep >= 2) { register int decr; switch (subdep) { case 2: decr = 1; break; case 3: decr = 3; break; default: /* larger values */ case 4: decr = 5; break; } if (nearcnt == 1) { nearest->m_value2 -= decr; if (nearest->m_value2 <= 0) nearest->m_value2 = 1; } else { /* need rescan */ formoves(lp, mp) { register int dist; if (mp->m_fig != bauer) { continue; } dist = promotion_line - LIN(mp->m_to); if (dist < 0) dist = -dist; if (dist == mindist) { mp->m_value2 -= decr; if (mp->m_value2 <= 0) mp->m_value2 = 1; } } } } } } Eximpl int sort_weighted( int depth, /* depth of current * analysis */ register Xconst Board * bp, /* in this board the * defender */ Movelist * lp) { /* to move has these legal moves */ #define CHK_B_BLOCK 0 register Move *mp; register Xconst Field *tp; register Xconst Field *fp; register rPieceSet emask; register Xconst Field *dkp; /* pointer to self king (defender) */ register int v; PieceSet dkatt; PieceSet self_mask; Xconst Field *ekp; /* pointer to enemy king (attacker) */ register rColour enemy; int v2; /* width of next att depth */ int have_good_ck; int att_moves; int fig_moves[32]; PieceSet ck_fig_set; int ck_figs; EscSet escs; EscSet cur_king_escs; EscSet noescs1d; PieceSet does1d; #if CHK_B_BLOCK int ebaumov; int epromlin; #endif if (list_length(lp) <= 1) { /* <= one move: no choice */ return 0; /* no choice: no sort, no cost */ } if (!(lp->l_attr & LA_CK)) { ml_ck_attr(bp, lp); /* we want the checking attributes */ } /* Fill the counter array 'fig_moves' (indexed by piece index) with the * move possibilities of the attacker, if he were to move now (although * he is not to move, now). */ bzero(fig_moves, 32 * sizeof(int)); att_moves = ana_att_moves(bp, fig_moves); enemy = opp_colour(bp->b_tomove); dkp = K_FP(bp, bp->b_tomove); ekp = K_FP(bp, enemy); emask = COLOUR_MASK(enemy); self_mask = COLOUR_MASK(bp->b_tomove); dkatt = BOTH_KINGS & self_mask; /* our king */ #if CHK_B_BLOCK ebaumov = bau_mov[enemy]; epromlin = PROM_LIN(enemy); #endif have_good_ck = 0; ck_fig_set = lp->l_hasckmv; ck_figs = BIT_SUM32(ck_fig_set); /* king escapes for attackers king */ escs = 0; noescs1d = 0; does1d = 0; for (v = MIN_E_DIR; v < MAX_E_DIR; ++v) { tp = ekp + dam_mov[v]; /* escape candidate */ if ((tp->f_c == border) || ((tp->f_c == ekp->f_c) && !zero_dir(v))) { continue; /* blocked */ } if (F_DATT(tp) & self_mask) { /* forbidden by direct att */ if (max1elems(F_DATT(tp) & self_mask)) { noescs1d |= (1 << v); /* no escape, 1 dir-att */ does1d |= F_DATT(tp); } continue; } escs |= (1 << v); /* is an escape for enemy K */ } does1d &= self_mask; /* those attacks are singly to enemy K */ /* Now we are prepared to scan the move list of the defender. Into the * two components "m_value" and "m_value2" we fill what we think will be * the attackers move list lengths in the next two moves. These are later * multiplied, which is a good guess of the width of the analysis. As * we, the defender, like the tree to be small, this product is then * negated and sorted descending. */ formoves(lp, mp) { fp = &(bp->b_f[mp->m_from]); /* from, move source */ tp = &(bp->b_f[mp->m_to]); /* to , move destination */ fig_moves[mp->m_idx]++; /* count defender, too */ /* First, use 'att_moves' as a basis, and compute 'v', the number of * attacker moves after this defender move at 'mp'. If 'mp' beats a * piece, it will not move any more. The enemy's king escapes may * change by doing 'mp'. */ v = att_moves; if (tp->f_c != empty) { v -= fig_moves[tp->f_idx]; /* beaten piece cannot move */ } #if CHK_B_BLOCK else { register const Field *xp; xp = tp - ebaumov; if ((xp->f_f == bauer) && (xp->f_c == enemy)) { /* B-block */ if (v2 = fig_moves[xp->f_idx]) { if (LIN64(tp->f_pos64) == epromlin) { v -= ((v2 >= 4) ? 4 : v2); } else { v -= 1; } } } } #endif cur_king_escs = escs; v -= bitsum[escs]; if (SET1(mp->m_idx) & does1d) { /* take away singly covered */ cur_king_escs |= fig_cov[fp->f_f][fp - ekp] & noescs1d; } cur_king_escs &= ~fig_cov[mp->m_fig][tp - ekp]; v += bitsum[cur_king_escs]; /* # of att king moves */ if (v <= 0) v = 1; v2 = v; #if CHK_B_BLOCK { register const Field *xp; xp = fp - ebaumov; if ((xp->f_f == bauer) && (xp->f_c == enemy)) { if (LIN64(fp->f_pos64) == epromlin) { v += 4; /* 4 promotions enabled */ v2 += 38 / v; /* MRFC */ } else { v += 1; /* ca 1 B-move enabled */ v2 = v; } } } #endif /* Ok, this 'v' is the basis for the next two levels. */ v2 = V2_VAL(v2); VV(printf("> %2o-%2o %d->%d: v=%3d, v2=%3d\n", fp->f_pos64, tp->f_pos64, fp->f_f, mp->m_fig, v, v2); ) if (mp->m_attr & MA__CK) { /* move says 'check' */ /* A checking move is potentially good, as it severely handicaps * the attacker. But, we want to distinguish carefully between * good and not so good or even foolish checking moves. * * We start off with the 'cur_king_escs'. We test, whether the enemy * can beat back. Then, if not in double check, we enumerate * blocking moves, and beating moves, and compute a weighted * average. */ int dir_dkp_tp; int beat_fig_val; int risk; /* how risky is this move? */ int in_ck; int k_moves; int beat_cnt; int block_cnt; int k_beat_cnt; int sav_v2; sav_v2 = v2; beat_fig_val = 0; in_ck = 0; risk = 0; beat_cnt = 0; block_cnt = 0; k_beat_cnt = 0; k_moves = v = bitsum[cur_king_escs]; /* # of att king moves */ if (k_moves <= 0) k_moves = 1; if ((F_DATT(tp) & emask & BOTH_KINGS) && ((F_DATT(tp) & self_mask & ~SET1(mp->m_idx)) == 0) ) { ++v; /* K beat back */ ++beat_cnt; k_beat_cnt = 1; } if ((mp->m_attr & (MA_ICK | MA_DCK)) != (MA_ICK | MA_DCK)) { register Xconst Field *xp; register int xdelta; register rPieceSet eatts; int xxx; /* check blocking moves: on tp --> ekp */ if ((mp->m_attr & MA_DCK) && (mp->m_fig != springer) ) { eatts = emask & ~BOTH_KINGS; xp = tp; if (mp->m_fig == koenig) { /* 0-0 or 0-0-0 */ xdelta = (mp->m_from - mp->m_to) / 2; xp += xdelta; /* here T gives check */ } xdelta = dam_mov[att_dir(xp, ekp)]; while ((xp += xdelta) != ekp) { if (F_DATT(xp) & eatts) { v++; block_cnt++; } } } /* analyse non K beat back */ eatts = F_DATT(tp) & emask & ~BOTH_KINGS; dir_dkp_tp = att_dir(dkp, tp); for (; eatts; CLR_LOW_BIT(eatts)) { const Field *ap; PieceSet s; ++v; ++beat_cnt; /* test if defender can beat back with check. */ if (!in_ck && ((s = ck_fig_set & F_DATT(tp) & ~SET1(mp->m_idx))) && fig__can_dir(bp, s, att_dir(tp, ekp)) ) { continue; } ap = fig__pos(bp, LOW_BIT(eatts)); xxx = bitsum[fig_cov[ap->f_f][tp - dkp]] - bitsum[fig_cov[ap->f_f][ap - dkp]]; if (depth >= 5) { v += xxx * 2; risk += xxx * 2; } else { v += xxx * 2; risk += xxx; } if (no_dir(dir_dkp_tp)) continue; /* analyse if there is a check from tp --> dkp */ switch (ap->f_f) { case springer: if (spr_dir(dir_dkp_tp)) { beat_fig_val += ATT_VALUE(ap->f_f, depth - 1); in_ck++; } break; case laeufer: if (lfr_dir(dir_dkp_tp)) { goto ltd_dir; } break; case turm: if (trm_dir(dir_dkp_tp)) { goto ltd_dir; } break; case dame: ltd_dir: /* test dkp --> tp */ xdelta = dam_mov[dir_dkp_tp]; xp = dkp; do { xp += xdelta; } while ((xp->f_c == empty || xp == fp) && xp != tp); if (xp == tp) { in_ck++; beat_fig_val += ATT_VALUE(ap->f_f, depth - 1); } break; } } /* end "for ( ; eatts ; )" */ } /* end if (say singly check) */ # define SET_MOVES_ON_V2(max_esc,ck_again,nxt_esc) \ if( ck_figs > 1 ) { \ v2 = (nxt_esc); \ }else { \ v2 = (( ((ck_again)*(nxt_esc)) \ + (((max_esc)-(ck_again))*sav_v2) \ ) / (max_esc)); \ } switch (mp->m_fig) { case dame: v2 = 3; break; case turm: v2 = 5; break; case laeufer: SET_MOVES_ON_V2(k_moves, 2, 7); break; case springer: SET_MOVES_ON_V2(k_moves, 3, 7); break; default: v2 = 8; } if (!in_ck) { if (risk <= 2) { have_good_ck = 1; } } else { if (F_DATT(tp) & self_mask & ~SET1(mp->m_idx)) { /* covered */ beat_fig_val = beat_fig_val / in_ck; } else { beat_fig_val = 0; } } v2 = ((k_moves * v2) + ((beat_cnt - in_ck - k_beat_cnt) * ((ck_figs > 1 && !in_ck) ? k_moves : sav_v2)) + (in_ck * att_moves) + (k_beat_cnt * sav_v2) + (block_cnt * (k_moves - 1)) #if OWN_V_RES + (beat_cnt * (OWN_VALUE(mp->m_fig, depth) + 1)) #else + (beat_cnt * (OWN_VALUE(fp->f_f, depth) + 1)) #endif ) / (k_moves + beat_cnt + block_cnt); if (tp->f_c != empty) { v2 -= ATT_VALUE(tp->f_f, depth - 1); } v -= beat_fig_val; v2 -= beat_fig_val; } /* end if (say check) */ if (tp->f_c != empty) { /* beats some attacker */ if (F_IATT(dkp) & SET1(tp->f_idx)) { v -= 1; /* which pins someone to defender K */ if (F_DATT(fp) & SET1(tp->f_idx)) { v -= 2; } } } { register rPieceSet mask; mask = F_DATT(tp) & emask; if (mask) { /* beat back */ /* king may only beat back if fig not covered */ if ((mask & ~BOTH_KINGS) == 0) { if ((F_DATT(tp) & self_mask & ~SET1(mp->m_idx)) == 0) { #if OWN_V_RES v2 += OWN_VALUE(mp->m_fig, depth); #else v2 += OWN_VALUE(fp->f_f, depth); #endif } } else { #if OWN_V_RES v2 += OWN_VALUE(mp->m_fig, depth); #else v2 += OWN_VALUE(fp->f_f, depth); #endif } } #if 0 /* doesn't improve, FFS */ if (mp->m_fig != fp->f_f) { /* promotion */ v2 -= 1 + OWN_VALUE(mp->m_fig, depth); v2 += OWN_VALUE(fp->f_f, depth); v -= 1; } #endif /* analyse escape situation of defenders king */ if (!have_good_ck) { if (mp->m_fig == koenig) { register int b; register int i; mask = emask; if (tp->f_c != empty) { mask &= ~SET1(tp->f_idx); } for (i = MIN_D_DIR; i < MAX_D_DIR; ++i) { register Xconst Field *xp; xp = fp + dam_mov[i]; if (!(F_DATT(xp) & emask) && ((xp->f_c == enemy) || (xp->f_c == empty))) { v += 1; } xp = tp + dam_mov[i]; if (((xp == fp) || (xp->f_c == enemy) || (xp->f_c == empty)) && !(F_DATT(xp) & mask)) { v -= 1; } } b = pos64_borders[fp->f_pos64] - pos64_borders[tp->f_pos64]; if (b) { if (b > 0) v--; else v++; } } else { if (F_DATT(fp) & dkatt) { v -= 1; } if (F_DATT(tp) & dkatt) { v += 1; } } } } if (v <= 0) v = 1; if (v2 <= 0) v2 = 1; mp->m_value = v; mp->m_value2 = v2; VV(printf("< %2o-%2o %d->%d: v=%3d, v2=%3d\n", fp->f_pos64, tp->f_pos64, fp->f_f, mp->m_fig, v, v2); ) } /* end formoves */ /* 'fig_moves' is now complete for both sides. */ if (!have_good_ck || (depth >= 6)) { /* We suspect, that the analysis up to now is not good enough, or we * have just time enough to continue... */ find_chk_nxt(depth, bp, lp, fig_moves, ck_fig_set, escs, noescs1d, does1d); VV( formoves(lp, mp) { fp = &(bp->b_f[mp->m_from]); /* from, move source */ tp = &(bp->b_f[mp->m_to]); /* to , move destination */ printf("C %2o-%2o %d->%d: v=%3d, v2=%3d\n", fp->f_pos64, tp->f_pos64, fp->f_f, mp->m_fig, mp->m_value, mp->m_value2); } ) try_promotion(depth, bp, lp, fig_moves, ck_fig_set, escs, noescs1d, does1d); } /* Scan the move list again, compute the value product, negate it, and * normalise it. */ v = att_moves * V2_VAL(att_moves); /* sort of average */ formoves(lp, mp) { mp->m_value = v - (mp->m_value * mp->m_value2); } ml_sort_rdx(lp); #if 0 if (!have_good_ck) { int last = 0; int v; int vv; int i; int max; int min; int a[100]; register Move *p; double d; v = lp->l_m[0].m_value; vv = v / 3; if (vv < 2) vv = 2; v -= vv; if (v >= 6) v = 6; formoves(lp, p) { if (p->m_value >= v) last++; else break; } if ((last == 1) && (lp->l_m[1].m_value >= 3)) last = 2; if (last > 1) { if (last > 6) last = 6; for (i = 0, p = lp->l_m; i < last; i++, ++p) { Movelist ml; clear_list(&ml); move_execute(bp, p); move_gen(bp, &ml); a[i] = list_length(&ml); move_undo(bp); } max = 0; min = 9999; for (i = 0; i < last; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } /* give 5 points for the best. */ #define PKT 5.0 if (max != min) { Move *sav_free; d = PKT / (double) (max - min); for (i = 0, p = lp->l_m; i < last; ++i, ++p) { p->m_value += (int) (PKT - (double) (a[i] - min) * d); } sav_free = lp->l_free; lp->l_free = &lp->l_m[last]; ml_sort_rdx(lp); lp->l_free = sav_free; } } } #endif #if 0 && HAS_INTERFACE if (f_ic && (f_no_trc == 0) && !f_ic_skip) { /* For the first 5 moves enter the real effort (in moves) into * "value2" */ Counter sav_mov; int i; i = 0; f_no_trc = 1; formoves(lp, mp) { mp->m_value2 = 0; if (i < 5 && mp->m_value) { int res; move_execute(bp, mp); sav_mov = sc_move_exec; res = ANASUC(analyse(bp, depth - 1, (Movelist *) 0, (Move *) 0, (RefuList *) 0)); move_undo(bp); mp->m_value2 = sc_move_exec - sav_mov; if (res) { mp->m_value2 = -mp->m_value2; } } ++i; } f_no_trc = 0; } #endif return 4; /* apx. cost */ }