Thu Aug 13 02:04:41 MSZ 1987 - Added option -t to trace the executed moves. > Detected bad problem. In one shinkman variant the generated move list is bad, when the king to move is attacked by an S: wkc4 wda6 wth1 wbd2 bkb2 blh8 bse5 z1w chest -m returns move list move_gen returns 1 Bd2-d3 ?? Th1-f1 ?? Kc4-d4 Kc4-b4 Kc4-c5 Kc4-d5 Kc4-b5 Reason for this: indexed the array "spr_mov" directly with a direction from att_dir, instead to subtract MIN_S_DIR. Thu Aug 13 02:51:00 MSZ 1987 Extended implementation of chk_board() such that it would have detected the above error. Sat Aug 15 21:30:19 MSZ 1987 Depth reduction considerations: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Depth reduction is only possible at the leaves. Currently this means not to execute every legal move as if it could be a 1-mate move. Thus we need a move generator variant, that - in the ideal case - does generate 1-mate moves, only. This means to skip moves which cannot be mate moves, because: (1) They do not check (2) They leave a king escape (3) They can be blocked or beaten These attributes are approximated. The first two attributes may guide the method of move production. (4) When currently in check, this may also guide the move production. (4) is expected to occur in 10% of all cases. (1) and (2) seem to be the more important, and may be combined: all not yet attacked not yet blocked fields of the kings 3*3 square must be attacked either directly or indirectly. Certain patterns of fields of the 3*3 king square (KS) can be very restrictive to the possibilities of moves covering all these. - Castlings are handled specially - e.p. is handled specially - promotions are handled specially This leaves the "simple moves": figure F moves from f to t. Important attributes of KS fields: - border: completely blocked - piece of same colour as K: blocked, except it is t (beaten) - whether A-datt: not yet escape - whether A-iatt: may be attacked indirectly through f. Special case for (3): - when the K has no A-iatt, there cannot be any pinning. ==> any D-datt of SLTD indicates a legal move, except for pinnings uncovered by f or done by t. Maximum possible additional (not yet) active KS attacks: D: 6 T: 4 L: 3 S: 2 B: 2 K: 3 (except central field) Each uncovering can attack at most 3 additional fields. Maximum possible additional (not yet) KS attacks with one uncovering: D: - T: 3 + 3 - 1 = 5 L: 3 + 3 - 1 = 3 + 2 = 5 S: 2 + 3 - 1 = 1 + 3 = 4 B: 2 + 3 - 1 = 1 + 3 = 4 K: 3 + 3 - 1 = 5 (without central attack) 2 + 3 - 1 = 4 (with central field) Problem: maximum of multiple uncovering has to be proven. Sun Aug 16 00:01:49 MSZ 1987 Extracted ep_legal() and gen_castle() from move_gen(). Mon Aug 17 19:07:51 MSZ 1987 Saved Version 2.1. Started to program version 2.2. Main feature is the move generator for mate moves. - Introduced type LegalDelta, preparing tables. - Increased the number of lines such, that any legal delta from any legal position does not reach outside the border. - Made trm_dir and lfr_dir macros true double bound checks. Changed some direction checks for this change. Tue Aug 18 21:29:10 MSZ 1987 - Corrected error in ep_legal() (returned FALSE instead TRUE). Sat Aug 22 00:25:16 MSZ 1987 Added checks for castling rights in debug check. Tue Apr 19 21:51:47 MET DST 1988 Tried first time on clipper/BSD4.3 (without optimizer !!): Tested simple 3-mate: wke4 wdb5 wla5 bkc8 z3w: 20.7u (instead 47.9u) %time cum% secs cumsecs #call ms/call addr name 34.49 34.49 7.16 7.16 74938 0.096 12b8 _add_att 34.20 68.69 7.10 14.26 74934 0.095 14e6 _del_att 8.96 77.65 1.86 16.12 8833 0.211 2169 _move_gen 8.77 86.42 1.82 17.94 37496 0.049 1ac2 _move_execute 7.23 93.64 1.50 19.44 37496 0.040 1992 _move_undo 3.18 96.82 0.66 20.10 5b12 mcount 2.84 99.66 0.59 20.69 1070 0.551 d8 _analyse 0.14 99.81 0.03 20.72 1 30.000 ea0 _ini_extern 0.10 99.90 0.02 20.74 116 0.172 1708 _rep_att Sat Jun 25 17:52:42 MET DST 1988 Compiled with new cc. Simple 3-mate: wke4 wdb5 wla5 bkc8 z3w: Now 17.3u %time cum% secs cumsecs #call ms/call addr name 34.96 34.96 6.07 6.07 74934 0.081 2dfa _del_att 31.73 66.69 5.50 11.57 74938 0.073 29b0 _add_att 9.91 76.60 1.72 13.29 37496 0.046 391e _move_execute 7.95 84.55 1.38 14.67 8833 0.156 46d8 _move_gen 7.20 91.76 1.25 15.92 37496 0.033 36ba _move_undo 4.15 95.91 0.72 16.64 1070 0.673 620 _analyse 3.63 99.54 0.63 17.27 350 mcount 0.17 99.71 0.03 17.30 1 30.000 21a0 _ini_extern 0.12 99.83 0.02 17.32 3684 _move_untrace Added some "register" keywords. Defined special types for registers. Simple 3-mate: wke4 wdb5 wla5 bkc8 z3w: Now 14.4u %time cum% secs cumsecs #call ms/call addr name 33.44 33.44 4.87 4.87 74938 0.065 2860 _add_att 33.44 66.87 4.87 9.73 74934 0.065 2be6 _del_att 9.00 75.88 1.31 11.04 37496 0.035 3578 _move_execute 8.80 84.67 1.28 12.32 37496 0.034 3358 _move_undo 7.63 92.30 1.11 13.43 8833 0.126 3f18 _move_gen 4.54 96.84 0.66 14.09 350 mcount 2.82 99.66 0.41 14.50 1070 0.383 620 _analyse 0.21 99.86 0.03 14.53 1 30.000 2050 _ini_extern With -a: 14.1u %time cum% secs cumsecs #call ms/call addr name 34.77 34.77 4.88 4.88 73815 0.066 2be6 _del_att 34.20 68.97 4.80 9.69 73819 0.065 2860 _add_att 8.04 77.01 1.13 10.82 36956 0.031 3578 _move_execute 7.90 84.91 1.11 11.93 8770 0.127 3f18 _move_gen 6.69 91.60 0.94 12.87 36956 0.025 3358 _move_undo 3.99 95.59 0.56 13.43 350 mcount 3.63 99.22 0.51 13.94 1066 0.478 620 _analyse 0.28 99.50 0.04 13.98 194 0.206 2f50 _rep_att 0.21 99.72 0.03 14.01 1022 0.029 960 _sort_simple 0.14 99.86 0.02 14.03 1 20.000 2050 _ini_extern Tue Jun 28 23:01:10 MET DST 1988 debug.c: Added output flushing before "abort()". Fri Jul 29 16:53:54 MET DST 1988 extern.c: Extended for table initializer tool "mkinited.c" mkinited.c: Define, then print tables as C initializer. Produces "inited.h" version.c: Added. Wed Aug 3 23:21:45 MET DST 1988 move.c: slight changes to move tracing. FFS Implemented first version of "adaptive chess memory" (acm) via the "adaptive fact memory" (afm). Additional: acm, afmc, afm_param. Changed "analyse()" to (a) establish facts, and (b) use them for each recursive call. FFS: could use it to guide the selection of answers. Tested with 4-mate "svbAug02": wkd2 wtb4 wte5 wlh4 wsa2 wbg4 bka5 bda8 bld5 bba3 bba4 bba6 z4w Statistics with 8000 nodes -aM: %time cum% secs cumsecs #call ms/call addr name 25.48 25.48 54.74 54.74 1001622 0.055 2a10 _add_att 24.71 50.19 53.09 107.83 1001610 0.053 2d96 _del_att 10.49 60.67 22.53 130.36 91448 0.246 41a8 _move_gen 8.88 69.55 19.07 149.44 521623 0.037 37fa _move_execute 7.37 76.92 15.84 165.28 521623 0.030 35da _move_undo 5.01 81.93 10.77 176.04 350 mcount 3.70 85.63 7.94 183.99 83272 0.095 3100 _rep_att 3.56 89.19 7.64 191.63 35569 0.215 620 _analyse 2.25 91.44 4.84 196.47 31696 0.153 b90 _sort_simple 2.15 93.59 4.62 201.08 35569 0.130 6fae _acm_pack 1.63 95.22 3.50 204.59 60182 0.058 5b52 _afm_intobucket 1.25 96.47 2.69 207.27 35569 0.075 70f2 _acm_search 0.69 97.16 1.48 208.75 82758 0.018 8690 _bcmp 0.56 97.71 1.20 209.94 37114 0.032 62ec _afm_incvalue 0.36 98.08 0.78 210.72 76275 0.010 5a68 _afm_effbucket 0.35 98.42 0.75 211.47 24917 0.030 747c _acm_note 0.21 98.63 0.45 211.93 b7a0 saved_7 0.21 98.84 0.45 212.37 23164 0.019 60c6 _afm_alloc 0.17 99.01 0.37 212.74 15164 0.024 6e2a _acm_unlink 0.17 99.18 0.35 213.09 35569 0.010 6078 _afm_tick 0.15 99.33 0.32 213.41 12406 0.026 7624 _acm_used 0.13 99.45 0.27 213.69 35569 0.008 73f8 _acm_release 0.13 99.58 0.27 213.96 35316 0.008 6204 _afm_unlocked 0.11 99.69 0.25 214.20 23163 0.011 6452 _afm_enter 0.11 99.80 0.23 214.43 b760 restd_7 0.10 99.90 0.21 214.64 2 105.000 5c84 _afm_rescale Solution: Te5 - h5 acm statistics: 7999 nodes alive 23163 nodes entered 15164 nodes forgotten 5491 steps used ( 0.36) 35569 nodes searched 82758 compared ( 2.33) 38887 steps left ( 1.09) 113929 steps right ( 3.20) 12406 found ( 0.35) medium search square, opt = 1190.467, is = 2029.795 ( 1.71) apx costs: done = 715905, saved = 518648 (72.45%), speed = 1.67 Tried another (slightly more sophisticated) hash code: Solution: Te5 - h5 acm statistics: 7999 nodes alive 22896 nodes entered 14897 nodes forgotten 3973 steps used ( 0.27) 35505 nodes searched 16679 compared ( 0.47) 44959 steps left ( 1.27) 52854 steps right ( 1.49) 12609 found ( 0.36) medium search square, opt = 1186.183, is = 1339.328 ( 1.13) apx costs: done = 706495, saved = 527859 (74.72%), speed = 1.70 %time cum% secs cumsecs #call ms/call addr name 25.79 25.79 54.30 54.30 985259 0.055 2a10 _add_att 24.89 50.67 52.40 106.69 985247 0.053 2d96 _del_att 10.63 61.31 22.39 129.08 90605 0.247 41a8 _move_gen 9.11 70.41 19.17 148.25 513248 0.037 37fa _move_execute 7.40 77.82 15.59 163.84 513248 0.030 35da _move_undo 4.79 82.61 10.09 173.93 350 mcount 3.51 86.12 7.39 181.32 82498 0.090 3100 _rep_att 3.49 89.61 7.35 188.67 35505 0.207 620 _analyse 2.32 91.94 4.89 193.56 31632 0.155 b90 _sort_simple 2.19 94.12 4.61 198.17 35505 0.130 6fae _acm_pack 1.66 95.78 3.49 201.66 59850 0.058 5b52 _afm_intobucket 1.19 96.97 2.50 204.16 35505 0.070 7108 _acm_search 0.49 97.46 1.03 205.19 37047 0.028 62ec _afm_incvalue 0.38 97.84 0.80 205.99 24647 0.032 7492 _acm_note 0.36 98.20 0.76 206.75 75941 0.010 5a68 _afm_effbucket 0.27 98.46 0.56 207.31 16679 0.034 86b0 _bcmp 0.20 98.66 0.41 207.72 14897 0.028 6e2a _acm_unlink 0.17 98.83 0.36 208.09 22897 0.016 60c6 _afm_alloc 0.17 99.01 0.36 208.45 35505 0.010 6078 _afm_tick 0.17 99.18 0.35 208.81 12609 0.028 763a _acm_used 0.17 99.34 0.35 209.16 b7c0 saved_7 0.15 99.49 0.32 209.47 b780 restd_7 0.14 99.63 0.29 209.76 35505 0.008 740e _acm_release 0.13 99.76 0.27 210.03 35252 0.008 6204 _afm_unlocked 0.08 99.84 0.16 210.19 35a4 _move_untrace 0.07 99.91 0.15 210.34 2 75.000 5c84 _afm_rescale 0.05 99.96 0.11 210.46 22896 0.005 6452 _afm_enter Sat Aug 6 00:46:10 MET DST 1988 First time -O successful (without -p): chest -a 257.1 chest -aM 164.4 Tue Aug 9 19:17:06 MET DST 1988 acm.c: Better approximation for "speed". Wed Aug 10 22:33:31 MET DST 1988 input.c: Added 's' as alias for 'b' (schwarz/black) Added '#' as guaranteed comment. Thu Aug 11 21:16:00 MET DST 1988 timing.c: New. Offers "msec_user()" to time in milliseconds. chest.c: Times the total job and prints the time (except I/O). Advantage: is documented in stdout. move.c: Offers "move_trace_samelevel()", now called by analyse.c causing exact numbering of traced moves. Tue Aug 16 23:22:46 MET DST 1988 output.c: Added notion for "no move" in "put_move()". move.c: Added "depth" parameter to "move_trace_level()", printed on trace level 0. Sun Sep 4 19:30:10 MET DST 1988 chest.c, extern.c: Introduced special flag "f_heiner". Caused by "-H". hm_move_gen.c: Similar to earlier experiment: simple mate move generation. Essentially there is done a rough checking test (i.e. moves than cannot check are suppressed). Triggered by -H (in "analyse()"). Serves as basis for evaluation of more sophisticated algorithms still to be implemented. Testing with "Dr. H. Weissauer (SpVoBl #10, 04-Sep-88)": wka6 wtc2 wld1 wld4 wbb2 bka1 bbd5 z3w 9.06 sec chest 2.2 32K -aM (speed 1.24 937 nodes) 8.13 sec supp all K moves when uncovering impossible 3.25 sec supp SLTD that neither indir (via atts) nor direct check (via direction). Not yet anything for B or castling. Now speed = 1.11 -H factor == 2.79 Without -M: 11.12 / 3.60 => -H factor == 3.09 svbAug04 (cf above): -aM 170.76 19555 42% 1.80 -aMH 89.51 19555 42% 1.49 -H factor 1.91 Sun Sep 11 20:28:43 MET DST 1988 hm_move_gen.c: More restrictive for king moves: disallow when not uncovering the only possibility for check. Do not try K moves, when uncovering direction not existant. Effect < 1% Example i.svbSep11: Would like figure counts per color: (1) No mate is possible with just a king to attack. (2) When attacker has just one more figure, it is very good to beat that one (stops analysis immediately). Sun Sep 11 23:04:18 MET DST 1988 chest.c: Added check for maximal analysis depth (move stack !). analyse.c: Additionally fast return for early mates found in tree. Achieved ~ 1.5% Mon Sep 12 01:06:03 MET DST 1988 acm.c: acm_statistics() needs total time in milliseconds, now (or 0). Now more correct speed value ? Sat Sep 24 19:18:25 MET DST 1988 i/i.svbSep24: Found second solution (in 14 seconds) !! chest.c: Seperated "solve()" from "main()". FFS: Wants a "solution()", presenting the complete solution, and because of what answer the other moves do not succeed. Sat Sep 24 22:52:36 MET DST 1988 move_gen.c: When found legal e.p. there were missing the check for no movelist specified (just return move existance). hm_move_gen.c (-H): Improved for D: when target position is attacked by enemy king, and cannot be supported by self, it cannot be a mate. For i/i.svbSep24: 13.89 -> 12.14 (87.4%) Additionally: When not in check, analyse enemy's escape possibilities: + enumerate not yet attacked positions: D: cannot uncover attack, thus those also must be covered actively. 12.14 -> 9.54 + enumerate "escapes" which have just one attack, and no indir: those attacks must not be removed actively by normal moves (non-ep, non-castling). 9.54 -> 9.25 Added simple checking test for B moves (non-ep, non-promotion). Sun Sep 25 02:03:55 MET 1988 hm_move_gen.c (-H): Looked at i/i.bay4 (still > 100 sec). Still too many mate-candidates. Thus: - In general, indirect checks are possible on D-dirs, only. - Indirect checks are possible for L on T-dir, only. - Indirect checks are possible for T on L-dir, only. - For L and T: when no indir possible, and already on an attacking dir to enemy-K, there is just 1 chance: Proceed on this dir and beat a single intermediate enemy. Effect < 10% (sigh). Mon Sep 26 20:27:45 MET 1988 types.h: Introduced "ort_dir()" macro. For a D direction it picks some other direction othogonal to the argument. hm_move_gen.c (-H): Now constructs the directly checking moves of L/T from the opponents K. This ensures that there is not yet anybody in the checking path. Several minor optimizations in this context. i/i.bay4 now < 90 sec. FFS: mate analysis, when in check myself. Because of answer heuristic this is not infrequently (50% ?). When in check myself: Forbid blocking, when the checker will always be able to beat an intervening piece, and that one cannot check indirectly. A K attacked by not yet pinned non-B cannot mate. Wed Sep 28 19:37:23 MET 1988 analyse.c: Added "ana_stat()", which prints statistics about how many moves are excuted for which level. hm_move_gen.c (-H): Added check for "D can be beaten by non-K", with very rough approximation for pinning. (saved 1% on i.svbSep27, sigh) When in check, and eK -> K -> ckpos => no direct check possible K -> ckpos -> eK => direct check by beating, only. (Saved 7% on i.svbSep27, mate moves 6228->2515) Added simple check for standard promotions. Thu Sep 29 16:06:19 MET 1988 solution.c: Is new. Triggered by "-l", prints complete solution tree. chest.c: Extracted "test_movgen()" from "main()". output.c: Extracted "put__move()" (without newline). Sun Oct 2 21:23:07 MET 1988 hm_move_gen.c (-H): Made illegal: mate move generation without any output list. As long as it is an approximation, it does not make any sense. Added simple check test for castlings. Mon Oct 3 16:16:10 MET 1988 *.[hc]: Editing function definition layout for "vgrind(1)". Made printout. Sat Oct 15 13:57:57 MET 1988 acm.c: Made output of statistics more compact (fewer lines). Sat Oct 15 16:54:23 MET 1988 chest.c: Added option -x to analyse chances of the defender. Also extended "solve()". Bug: timing includes lots of "printf()"s. Mon Oct 17 07:05:20 MET 1988 chest.c: Corrected bug where calling procedure for long solution. Tue Oct 18 17:47:54 MET 1988 hm_move_gen.c: Added collection and printing of king escape statistics. chest.c: Added call to "hm_1_statistic()". Wed Oct 19 17:30:10 MET 1988 chest.c & others: Introduced flag -s to increment statistics level. Made statistics outputs conditional. Thu Oct 20 23:58:16 MET 1988 output.c: Added procedure to print the control position of a board. This is used to document the job in the output. chest.c: Print control position before the start of an analysis. Tue Oct 25 12:00:04 MET 1988 types.h & extern.c: Introduced "bitsum", mapping "uint8" into its bit count. Thu Oct 27 02:01:26 MET 1988 input.c: Extracted initialization of empty board from read_board(). Named "empty_board()". types.h: Invented "in_range" macro. Redefined several range checking macros (e.g spr_dir). Fri Nov 4 23:26:19 MET 1988 types.h: Some new types for "move1gen()" support. extern.c: New procedures to initialize the new arrays "cov_esc{_chk}[]". Thu Nov 10 21:24:57 MET 1988 acm.c: Changed the chess memory half-tick initialization to FACTS/8. analyse.c: Changed move list generation such, that a N-mate, doing the 1-mate first, uses the restricted move list, first, and computes the complete move list later. This costs a move generator more, but saved move executions. Sigh: sometimes costs time instead of saving (e.g. i/i.bay4) FFS: how comes ? Tue Nov 22 00:24:43 MET 1988 move1gen.c: First try seems to be ok. Achieves ca. factor 2, should do another factor 2. Sun Nov 27 02:28:59 MET 1988 chest.c: Suppressing long solution when there was no solution. Effectively saves two empty lines. Mon Nov 28 21:20:24 MET 1988 mgsubr.c: Collects subroutines shared among flavors of move generators. Thu Dec 1 00:07:30 MET 1988 move1gen.c: Per figure choice of escapes (indirs); necessary attacks can discard B/S moves; generate LTD from an escape => nearly as good as -H. Missing: beat the checker & self in check. Tue Dec 6 00:44:24 MET 1988 answer.c: sort_simple(): Added to get check moves (near king) first. On i/i.meph22: 37.45 -> 13.25 (!!) Sun Dec 25 21:46:41 MET 1988 extern.c: wrt_cov_esc(): In crunching the "lds[]/ld_[]" array now also sorts each vector and then searches for already existing one (or existing suffix). Reduces size from 1180 -> 680 elements. Although the benefit is marginal (less space, better cache usage), it doesn't do any harm. FFS: One more indirection could reduce the 512 EscInfo array elements to 193 (different) ones. Unclear whether this is worthwile. Sun Jan 8 14:13:55 MET 1989 Started to name the version 2.3 Sun Jan 8 14:55:38 MET 1989 answer.c: Made "sort_simple()" to return 1 as approximate cost for "analyse()". asw.c: Added; "sort_answer()" selects the answer procedure. analyse.c: Now calls "sort_answer()" with analysis depth. Sun Jan 8 17:01:45 MET 1989 answer.c: Started to program more sophisticated sorting features. Mon Jan 9 19:59:53 MET 1989 move_gen.c & move1gen.c: Pinning analysis when piece is near to its king: if on T-dir, it cannot be faked, so we are already sure. Avoids loop. Mon Jan 9 23:41:32 MET 1989 move.c: Added differential apx_cost value to trace lines (is one line too low). answer.c: A new answer heuristic with true sorting. - beaten material is good - material expected to be lost is bad - checking is worth about a T Unfortunately it is often worse than the old one. Better approximation of checking. Lowering penalty of lost material. FFS: - checking could be better - material loss isn't really important - better approx. for forced K-moves Fri Jan 20 00:35:05 MET 1989 move1gen.c: As B attacks are different for the colors, the fig_cov[bauer] is a maximal set, and cannot be used to check against noesc1d0i. Introduced the piece set "does1d0i". Sun Jan 22 18:32:57 MET 1989 board.h add "int8 m_value" into "Move" for the use of answer heuristic. This is needed for the I/O interface. Has to be zero if no special value is assigned. Mon Jan 30 21:43:51 MET 1989 board.h: New "m_attr" for checking attributes. New "l_attr" to their computation. Has to be set zero in move generators. Wed Feb 1 22:31:11 MET 1989 move1gen.c: K-legality when in check used "tpos", but didn't set it ... Wed Feb 8 02:00:44 MET 1989 mlattr.c: ml_ck_attr(): "mask" was used but not set ... Wed Feb 8 08:19:50 MET 1989 acm.c: acm_note() Eliminate a division by zero (when later level is less expensive). Thu Feb 16 22:05:36 MET 1989 chest.c: Changed several flag meanings: -a now disables answer heuristic -m now disables memory -M deleted -f new: disables "fac" (enabled now default) Wed Feb 22 23:56:12 MET 1989 fac.c: Invented "fac_km_dirs()". Saves ca. 10% of the attacker's 2-mate moves by knowing "fac" on K-moves while in check. Thu Feb 23 20:35:40 MET 1989 Reduced memory nodes to 20000, now usable on 4M-Triton. Thu Feb 23 21:47:49 MET 1989 Made move list linked. Now move list generators need "mg_link()". Fri Feb 24 00:25:05 MET 1989 move_gen.c: Faster by avoiding app_move(). Tue Feb 28 19:31:09 MET 1989 extern.c types.h: changed bitsum from 8 bit values to 9 bit values Wed Mar 1 01:44:01 MET 1989 move.c: Changed drastically up/downdate. Slightly faster (0.5%). Prepares more board redundencies and lazy up/downdate. Some minor improvements in loop control (loop over 8 directions). Fri Mar 3 18:06:01 MET 1989 move.c & input.c & debug.c &&& Added more board redundancy: b_bau used to prevent unnecessary mg_app_prom() calls b_cur_piece should be used in answer heuristic. b_packed used in acm, currenly costing more than saving Fri Mar 3 19:57:34 MET 1989 fac.c & analyse.c: Implemented & using "can_naken()". Made "fac" conditional in analyse from existing defender material. Thu Mar 9 17:12:08 MET 1989 extern.c types.h: changed bitsum from 9 bit values to 16 bit values Thu Mar 9 18:32:33 MET 1989 move1gen.c: Fast pre-check for "mg_app_prom()" tested target line for Bs ... Tue Mar 14 23:20:12 MET 1989 mgsubr.c: Better check-test in mg_app_prom(). Now puts only those into movelist, which have appropriate att_dir(). Sat Apr 1 17:32:26 MET DST 1989 fac.c: Corrected error in check-test for B (wrong delta computation). Occurred in i/i.tsp89Mar26 Fri May 18 21:18:22 MET DST 1990 move_gen.c & others: Implemented "ala_move_gen()" for attacker with only one piece. Leaves out what looses that piece (can't be k-mate solution). Feb 1991 move.c & acm.c & analyse.c: Implemented first version of snooping. After answer heuristic check at most the first 11 moves. No success for Bayer, but high success for i/50/i.50 Could be done one level deeper, cutted earlier. Now b_packed should be amortized. Tue Mar 05 04:31:11 MET 1991 answer.c & asw.c: Now using Holger's answer heuristic, which is really better for the Bayer, and at least more stable for e.g. the mate in 50. For large depths (>= 19) it is also better. Mon Mar 11 20:13:32 MET 1991 Hurra, the Bayer 9-mate is solved ! 32.5 hours on a HP9000-835 It is totally clean. Tue Mar 12 fac.c: Corrected bug in fac_km_dirs(). Gave too many dirs. Mon Mar 18 05:01:33 MET 1991 mlsubr.c: Corrected minor bug in ml_ck_attr. Near indir checks with B were missing. bsd.h: Is new. Solves some portability problems. Mon Mar 18 06:26:40 MET 1991 acm.c: As memcmp is really slow on i486 (interactive), it were completely eliminated. Now 8 explicit compares. Mon Mar 18 09:16:17 MET 1991 chest.c & solution.c: Added -L (changed -l) to print restricted depth solution trees. Sun Mar 24 23:14:34 MET 1991 move1gen.c: More exactly analyses indirect checking !(escs & (1< 97504 Sun Feb 6 23:28:53 MET 1994 Added helpmate to analyse.c & solution.c (not yet solopt). h#4 has already acm recall of 90% (speed > 9). Mon Feb 7 20:16:48 MET 1994 += f_solopt Sun May 8 15:31:15 METDST 1994 += f_eguse analyse.c: Using (first version) EG. Still not efficiently enough. Sun May 8 16:01:44 METDST 1994 Current version got symbolic RCS name "nonANSI". Started new version 2.5: using ANSI, now. Mon May 9 21:46:32 METDST 1994 acm.[hc] & analyse.c: acm_node -> AcmNode Mon May 9 22:44:30 METDST 1994 fac.c: BUG detected. Used "bau_left" twice, instead "bau_right", also. Some (rare) FAC recognized, which were not FAC. Grr. Sun May 15 19:33:21 METDST 1994 All files: First complete ANSI-C version, called "3.1". RCS revision is also 3.1. Thu May 19 11:34:09 METDST 1994 move1gen.c: corrected & enabled WITH_PROM (5% faster on i.50 z21) Sun Jun 26 22:19:41 METDST 1994 input.c: Much better input parsing. Now rejects obvious garbage. Completed porting to SunOS/g++. Sun Aug 21 17:13:39 METDST 1994 lang.[hc]: Added. input/output: Using lang & implementing input/output language. New: title lines. chest.c: Accepting input filename. debug.c & board.h: chk_board += wantcore Thu Aug 25 01:15:24 METDST 1994 answer.c: Found & removed bug: K can give direct check with T in 0-0 & 0-0-0. In that case mp->m_to is probably NOT related to enemy K, and the blocker search must start at the new T-position. Fri Aug 26 03:20:33 METDST 1994 Invented Board.b_zhash. New file zhi.h (generated by lrand48(4242)). Used as AcmHash. Is even better than the old hash code. Wed Sep 7 22:31:08 METDST 1994 Unfortunately, with the new ZHASH it is slower overall (10%). Explanation: the b_zhash is maintained at all moves, even inside all the mate in 2, where the bulk of the moves occur, but the b_zhash is not used (yet). When we will have a good move2gen(), this will change: all those 2-mate candidates disappear, and most moves are those, that turn a 3-mate into 2-mates. Then we will re-evaluate the ZHASH. Although move_snoop should be faster with the ZHASH method (allowing for more extensive snooping), its cost must be compared to the expected cost of the total job. When 2-mates become much more efficient, snooping in the 3-mate may become a problem despite the ZHASH. Tue Oct 10 20:59:18 MET 1995 Corrected bug in answer heuristic, which caused sometimes T-promotions to appear to be better than the corresponding D-promotion. Caused by erroneous suppression of D-checks (after promotion), which appeared as possible in a single move (as if the B would have been a D in the first place). Although now nearly every statistics value is better, "cost per sec" went down by 6%, and the overall performance is slightly worse. :-( Nevertheless we stay with the new version 3.7. It probably should be profiled and tuned. Wed Nov 22 21:52:01 MET 1995 New version 3.8: with first version of "mate2". Statistic for EscSet list lengths and the cut down chances by - recognizing maximum (^) - last is equal current (=) - last contains current (<) as done on Bayer-6: CHEST version 3.8, 22-Nov-1995 Options = -s -E 16 Time (user) = 38.06 sec mvx 6: 50 66 [50.000 1.320] mvskip lvskip mvx 5: 486 593 [ 7.364 1.220] 2 mvx 4: 4000 3978 [ 6.745 0.995] 9 mvx 3: 23408 24493 [ 5.884 1.046] mvx 2: 73197 23594 [ 2.988 0.322] mvx 1: 8343 0 [ 0.354 ] mate2: 22648, 206198 cand [ 9.1], 73197 mvx [35.5%] m2e: avg 3.29, cnt = 22648 0+ 2705 11.9%: 2626 79 - - = 11.6 0.3 - - 1+ 1135 5.0%: 626 94 - 415 = 2.8 0.4 - 1.8 2+ 4236 18.7%: 1433 351 270 2182 = 6.3 1.5 1.2 9.6 3+ 6682 29.5%: 2116 195 406 3965 = 9.3 0.9 1.8 17.5 4+ 3788 16.7%: 2220 211 304 1053 = 9.8 0.9 1.3 4.6 5+ 3269 14.4%: 1401 46 158 1664 = 6.2 0.2 0.7 7.3 6+ 457 2.0%: 375 8 11 63 = 1.7 0.0 0.0 0.3 7+ 318 1.4%: 316 - - 2 = 1.4 - - 0.0 8+ 58 0.3%: 58 - - - = 0.3 - - - m2c: 11008 dunno, 0 ep, 565 illf, 10363 illt [ 7.2%] m2c: 107 from, 332 beat, 15917 move, 27 frst m2c: 2895 thru, 31983 rest, 71265 succ [49.3%] m2ll 0 t/m: 25717 30603 [ 23.8% 28.3%] m2ll 1 t/m: 2339 6543 [ 2.2% 6.0%] m2ll 2 t/m: 3574 6088 [ 3.3% 5.6%] cut^=<: 0.89% 4.33% 2.33% m2ll 3 t/m: 2139 11109 [ 2.0% 10.3%] cut^=<: 0.92% 9.61% 1.65% m2ll 4 t/m: 484 4117 [ 0.4% 3.8%] cut^=<: 1.79% 16.19% 6.91% m2ll 5 t/m: 197 3138 [ 0.2% 2.9%] cut^=<: 1.36% 15.46% 3.03% m2ll 6 t/m: 100 2383 [ 0.1% 2.2%] cut^=<: 4.71% 14.21% 16.40% m2ll 7 t/m: 29 1742 [ 0.0% 1.6%] cut^=<: 8.68% 24.16% 24.26% m2ll 8 t/m: 3 2032 [ 0.0% 1.9%] cut^=<: 21.31% 20.22% 17.62% m2ll 9 t/m: 6 1216 [ 0.0% 1.1%] cut^=<: 17.31% 2.88% 26.74% m2ll 10 t/m: 1 1778 [ 0.0% 1.6%] cut^=<: 20.34% 2.67% 19.43% m2ll 11 t/m: 1 756 [ 0.0% 0.7%] cut^=<: 20.88% 3.36% 19.63% m2ll 12 t/m: - 1293 [ 0.0% 1.2%] cut^=<: 24.11% 1.68% 18.52% m2ll 13 t/m: - 374 [ 0.0% 0.3%] cut^=<: 21.99% 3.43% 12.16% m2ll 14 t/m: - 226 [ 0.0% 0.2%] cut^=<: 34.99% 3.57% 7.81% m2ll 15 t/m: - 151 [ 0.0% 0.1%] cut^=<: 27.11% 0.88% 23.80% m2ll 16 t/m: - 24 [ 0.0% 0.0%] cut^=<: 7.03% 4.69% 23.70% m2ll 17 t/m: - 10 [ 0.0% 0.0%] cut^=<: 7.65% 10.59% 34.12% m2ll 18 t/m: - 6 [ 0.0% 0.0%] cut^=<: 0.00% 5.56% 29.63% Clearly, the average list length is so small, that we will not use the bit vector approach to represent sets of EscSets, except perhaps for summarizing purposes. Profiling showed, that testing for supersets in the bit vectors took 13% of all the candidate-test-work, which is a bit high. Recognizing the maximal possible set to exist, does not save much with smaller list lengths, but significantly reduces the larger ones. It also should be used to recognize complete groups of candidates, avoiding further work without chances: - if the plm of piece X can cover E completely, only X is left as a non-2-mate candidate: all others are already "dunno", as they can be combined with X. - if the opening effect of moving X covers E completely, X itself is "dunno". Statistics show a good effect, but the overall time is not as good. Preparation and candidate testing both are in the same class as move generation and move execution. Tue Nov 28 19:51:22 MET 1995 Made M2State hidden in mate2, introduced M2Info. Conditional m2_prep(): bay-6 33.64 -> 33.09 Fri Dec 15 00:45:57 MET 1995 New: "ebc" == EscSet blocked completely. Arrays filled in extern.c Building the ebc-set in mate2: minimal time (cannot measure). Using for LTD-moves: -3% mvx, +1% succ, -1% time Using everywhere in mate2: slightly better, but slower :-( Will need some microtuning. Mon Dec 18 18:24:50 MET 1995 GRR, Corrected bug in "move1gen": ltd_rev did not search through the king to be attacked, while searching for a move target which might attack some (non-central) element of the left EscSet. This bug where there always (since Jan 1989). Occured for "TSP/i.tsp951217a" (Speckmann 3#). Incremented version -> 3.10 Sat Dec 23 17:49:40 MET 1995 GRR, the "optimized" code is not very optimal on "drb4" (HPUX) as well as on "drb3" (IRIX). Multiple fetches of the same byte, funny handling of >> in connection with signed values, and lots of unnecessary sign extensions when caching short locals in registers make some code really bad. Some minimal tweaking in "mate2": 2% (relative). Expanded "is_ep_move". Expanded part of "dir_for_fig". Added several "register". IRIX/R4400: faster (3% overall), HPUX/HPPA: same speed. Grr. But code is smaller in both cases. Sat Dec 30 13:12:52 MET 1995 The reason for "move_undo()" top be slower than "move_exec()" on some machines seems to be bad "switch" code. Grr. Sat Dec 30 23:57:47 MET 1995 Hacked nearly everything for first version with PROD_LEV: all statistics and local debugs are now conditional. Made "dam_fmov[]" also const (inited at compile time). Mon Jan 1 19:41:21 MET 1996 Invented king oriented macros: K_IDX(c), K_POS(bp,c) and K_FP(bp,c). Sun Jan 7 16:16:35 MET 1996 Added 1 line statistics signature. Mon Jan 8 00:57:22 MET 1996 mate2: Significant speed-up by reducing the scanned directions. Thu Feb 1 23:23:23 MET 1996 xatt.h: rearranged macros, avoiding (0, 0, 0, expr) yields better optimization: 5% faster code (!). Mon Jun 3 01:24:46 METDST 1996 mlsubr.c: ml_ck_attr() is wrong for direct checks of promotions! (not yet corrected) Wed Jun 5 01:55:26 METDST 1996 mlsubr.c: ml_ck_attr() corrected for direct checks of promotions. Sun Jun 9 20:41:17 METDST 1996 types.h, board.h, extern.c: Invented "Iconst", to make all arrays in "inited.h" const (or static). FFS: linearized "fig_cov" basis, but does not yet crunch it. Mon Jun 10 00:08:46 METDST 1996 xatt.h & Nearly everything: Invented & using "Xconst", the conditional const for lazy attack information in otherwise constant Board's and Field's. Sun Dec 28 12:47:53 MET 1997 GRR, bug in "move1gen": king moves are excluded even when the "bad" defender (non-bauer, which says check) can be beaten by the king. In the following position the mate in 1 was not found (Kc3:c2++) wkc3 wbh8 bka1 bpa2 bqc2 z1w. move1gen.c: --> 3.15 Incremented version --> 3.11 28-Dec-1997 Sun Jan 11 17:11:32 MET 1998 Added FEN-Output line by explicit call after put_control: put_fen_eng. Note: FEN output is defined to be in english. Mon Jan 12 20:42:05 MET 1998 solopt: added rest-depth to "..." notation Sun Jan 18 17:03:37 MET 1998 chest.c & analyse.c: Added jobtype "helpstalemate" (jH). Incremented version --> 3.12 18-Jan-1998 Sun Jan 18 23:01:00 MET 1998 Added module "refu", used in analyse.c and callers. Tue Jan 20 21:52:14 MET 1998 solution.c: "..." always with depth Tue Jan 20 23:47:36 MET 1998 solopt.c: ++statistics Wed Jan 21 01:32:36 MET 1998 solution.c: += dual suppression (-u & -U) Not yet in solopt. Thu Jan 22 22:40:40 MET 1998 job.h: added (redundant f_jobattr) solopt: using sol_analyse (for f_nodualdep). Not yet optimal (should pick moves at lowest level). Sun Feb 8 14:58:01 MET 1998 extern.c: -= small bug, introduced recently (mkinited did not terminate) Sat Feb 14 22:09:26 MET 1998 analyse.c: += jobtype "stalemate" Sun Feb 15 22:13:58 MET 1998 analyse.c: += jobtype "selfstalemate" GRR: Corrected bug with selfmate, when attacker has no valid move from ala_move_gen: we must not announce an early solution, but a non-solution (since early solution is already checked). Has been there since 1.17 (Apr-1991), since first selfmate version. Occurs only, when do1selfmate() returns without a move list. Probably never occured. Version --> 3.13, 15-Feb-1998 Fri Jul 24 19:33:32 MEST 1998 Added option -p: printing partial positive solutions, when entered into ACM. This may help guessing, sometimes. Sun Oct 25 18:40:11 MET 1998 cost.h, acm.c, trace.c, analyse.c: Using type AnaCost defined to be double. Measured on mendlvr1 (Solaris 2, some Pentium), found to be 1.24% slower: :-( # 24 457.48 15.35 2220968- 7413 # 25 1249.59 2.98 5975663- 1681111 # 24 463.06 15.37 2220968- 7413 # 25 1265.09 16.83 5975663- 1681111 Not yet tried a local cost var of type int. --> version 3.14 Sat Oct 31 17:55:50 MET 1998 analyse.c: Introduced APC_* macros to lower the cost of double AnaCost. Gets hardly any better (measured on drb6(P166) with Bay-6). And the cost in trace output is less intuitive to interpret. Whether to use local variables for cost is FFS, hence. Sun Nov 1 22:00:05 MET 1998 refu.? & analyse.c: Added refu_fail(), noting non-refutations in an additional table. Tue Nov 3 21:34:43 MET 1998 analyse.c: When snooping, mark bad defenders with MA_SKIP. This really happens in "i.50". Wed Nov 11 21:26:05 MET 1998 chest.c: Added -G option (count legal tree width). It happens to be equal to the numbers posted by others. Fine. Fri Nov 13 17:42:41 MET 1998 analyse.c: Flag f_noanti was initialized wrong (disabled anti heuristic). Mon Nov 16 00:13:19 MET 1998 mate2.c: Extended, to allow some castling flags of the attacker. Motivated by "APG/i.91" and its partials, where "mate2" was nearly switched off by the castling rights. Note, that the "no mate in 9" had been computed with castling switched off, which was not really correct. Mon Dec 21 22:34:15 MET 1998 mate2.c: Experimentally, enabled WITH_9E_FINE: completely free is ok, if the defK-target indicates a legal move. Sometimes gives a significant speed up (by avoiding all the computations in "mate2"). i.ktk: 9+ = 43.6% # 10 147.21 33.61 23482- 5 # 10 146.84 33.61 23482- 5 (9E_FINE) .37 = 0.25% APG/i.38: 9+ = 58.7% # 11 34.44 3.43 20905- 0 # 11 30.16 3.44 20905- 0 (9E_FINE) 4.28 = 12.4% CCC/i.ccc02: 9+ = 51.7% # 12 6.47 9.42 3840- 0 # 12 5.86 9.42 3840- 0 .61 = 9.4% This indicates, that a more elaborate study might be well worth it. Mon Dec 28 22:59:03 MET 1998 chest.c: Added -z N. Moved "sum_stats" from "chest.c" into "analyse.c", calling now for all top level results. --> version 3.15 Sat Feb 20 22:52:40 MET 1999 On the "drb6" (P/166) one computation (CCC/i.ccc14) showed some "-NaN" in its output (for "apx_saved"). This was NOT reproducable: the exact same computation repeated showed expected values (like doing it on another system). Also, the result file with the Nan in it has the wrong GID: 20 -r--r----- 1 heiner drb 9243 Feb 11 17:25 i.ccc14-NaN 20 -rw-r----- 1 heiner chest 9247 Feb 20 22:50 i.ccc14 2 drwxrwsr-x 2 heiner chest 512 Feb 20 23:01 ./ ^ forces files to ^^^^^ this group ! The "drb6" is a double processor system. uname -a yields SunOS drb6 5.6 Generic_105182-05 i86pc i386 i86pc This is disturbing! Mon Jun 7 23:59:28 MEST 1999 board.h & move_gen.c: With APG/i.72Q we got a panic: Movelist overflow! FEN: 4k3/qqqqqqqq/8/8/8/8/RRRRRRRR/4K3 w - - Bumped MAX_MOVES 120 -> 150, and extended the panic messages. Sun Jun 13 17:33:53 MEST 1999 i/APG/i.72R: Looked at the played variants (with xic), and found them to be mostly ok, i.e. the answer heuristic is not so bad, even in this rather unusual case. Wed Jun 16 00:11:57 MEST 1999 acm.[hc] & chest.c Added acm_start(), which makes ACM data safe across multiple jobs. --> version 3.16 Sat Jun 19 17:08:13 MEST 1999 move.c: Avoid setting b_ep for pawn double step, when there is no opponent pawn left or right of the target square. Should even be a bit more efficient for moving, while allowing more heuristics which do not want to deal with e.p. Fri Jun 25 19:58:28 MEST 1999 README_LONG: Wrote first version. Tue Jul 20 23:15:01 MEST 1999 allchest.c: Created first version of "compile all at once". Invented manifests Extern, Eximpl and I0static. Used them practically everywhere. Bumped MAX_MOVES 150 --> 222, should always be sufficient. Wed Jul 21 23:10:35 MEST 1999 basdef.h: Extracted from bastyp. basdef can be used in generators. Added CDECL_ (NT portability). chest.c: Added option -V. --> version 3.17 Fri Aug 6 00:57:01 MEST 1999 mklcltyp.c: First version to be used & distributed. Replaces experimental "mklocal.c". Now using "lcltyp.h" in "bastyp.h". Fri Sep 10 00:33:43 MEST 1999 mate2.c: Fixed bug in "m2_prep()", which occured, when the side to mate still has all 16 pieces on board. Stepped over piece array, and ... (pseudo-)random memory accesses may follow. Crash detected by Dann Corbit. Wed Oct 13 00:29:24 MEST 1999 epdio.? Not yet complete. Results are still missing. Added option -Z. --> version 3.18 Sat Nov 20 22:22:11 MET 1999 epdio.c: Added comment copying. Should be rather complete, now. "am" still missing. chest.c: Added CHEST_OPTS. Sat Nov 27 17:33:18 MET 1999 acm.[hc]: Added ACM_DYN. Decided for calloc instead of malloc. chest.c: Added option -M. allchest.c: Sorted by cluster (first manual guess). Sun Dec 5 00:10:20 MET 1999 timing.[hc] & all uses: Switched to (double TimeSecs) instead (unsigned long TimeMsec). Added timing_type() & timing_prec() for abstraction. Added mixed clock()/time(), standard conforming. Sat Dec 18 18:13:02 MET 1999 Preparing packing first release. Using "distcollect", so this is not going to be public, itself. Unpacking on Linux-PC worked, compiled with "Makefile.simple", and correctly did compute "EPD/HMm4.epd" in less than 5 seconds (P/133). --> version 3.19 making public in http://www.drb.insel.de/~heiner/Chess/chest.html