Lest the new Chess In Lisp toolkit receive unnecessary criticism (vs necessary criticism), let me point out that some serious performance problems in the demo forced mate finder have been fixed.
[d]1N2k3/6r1/3pP3/p2P1p1P/PpBpP2b/1PP2b2/2K5/B3R1q1 b - - 1 42
Old analysis:
Code: Select all
[MateIn4/7/17.269/111,573/0] 42... Rg2+ 43 Be2 Bxe4+ 44 Kc1 Qxe1+ 45 Bd1 Bg5#
New analysis:
Code: Select all
[MateIn4/7/0.108/633/0] 42... Rg2+ 43 Be2 Bxe4+ 44 Kc1 Qxe1+ 45 Bd1 Bg5#
A speed-up factor of about 160. The actual Lisp call in both cases:
Code: Select all
(matefinder "1N2k3/6r1/3pP3/p2P1p1P/PpBpP2b/1PP2b2/2K5/B3R1q1 b - - 1 42" 4)
When running the matefinder routine on the 100,000 position matein3 FEN file, the toolkit solved all the problems with an average speed of about 16.1 Hz (period of about 62.1 msec). For the easier 100,000 position matein2 FEN file, the frequency was about 162 Hz (a period of about 6.16 msec). The matein1 problems zipped by at about 839 Hz with nearly all of the time eaten by I/O and decoding/encoding.
Why is this important? Consider a knowledge-based program with a time budget of (on average) 100 seconds per move and a node budget of (also on average) 1,000 nodes per search; this is 100 milliseconds total per node. To keep the program from making really dumb blunders due to gaps in the knowledge base, perhaps ten percent of each node time allocation can be spent on brute force calculation to help avoid stepping into obvious traps and mates. Therefore, there are about ten milliseconds per node that can be expended on, uh, cheating with brute force. These budget numbers are admittedly a bit arbitrary.
Anyway, with the above figures a mate-in-two search cheat at each node would be permissible, but not a mate in three search.
Code snippet:
Code: Select all
;; ---------- Simple mate finding routines
(defun matefinder-node (my-pos my-window my-ply my-depth)
"Search for a mate attack/defend at the given ply and depth for the given position; return an analysis."
(let
(
(result (make-analysis :draft my-depth :nodecount 1 :score (window-alfa my-window) :fgpair (pos->fgpair my-pos)))
)
(if (zero? my-depth)
(setf (analysis-score result) (if (pos-is-checkmate? my-pos) checkmated-score even-score))
(let*
(
(atkflag (even? my-ply))
(d1flag (one? my-depth))
(newply (1+ my-ply))
(newdepth (1- my-depth))
(moves (if d1flag (generate-checkers my-pos) (generate my-pos)))
(basket
(new-basket
(if d1flag
(movelist-assign-order-simple-est-gain moves)
(if atkflag
(movelist-assign-order-negative-mobility moves my-pos)
(movelist-assign-order-simple-est-gain moves)))))
(atleast1 nil)
)
(dowhile
(and
(basket-has-moves? basket)
(not (is-window-cutoff? my-window))
(if atkflag
(not (is-score-mating? (window-alfa my-window)))
(negative? (window-alfa my-window))))
(let
(
(desc-analysis nil)
(newbest nil)
(move (basket-pick-best basket))
)
(setf atleast1 t)
(pos-execute my-pos move)
(setf desc-analysis (matefinder-node my-pos (downshift-window my-window) newply newdepth))
(setf newbest (combine-node-desc-analyses move result desc-analysis))
(when newbest
(setf (window-alfa my-window) (analysis-score result)))
(pos-retract my-pos)))
(unless atleast1
(setf (analysis-score result) (if (pos-inch my-pos) checkmated-score even-score)))))
result))
(defun matefinder-root (my-pos my-fmvc)
"Search for a mate in N for the given position at the root; return an analysis."
(matefinder-node my-pos (new-full-window) 0 (1- (2* my-fmvc))))
(defun matefinder (my-fen my-fmvc)
"Search for a mate in N for the given position; return an analysis."
(let ((result nil) (pos (string->pos my-fen)) (st (new-cu-simpletimer t)))
(setf result (matefinder-root pos my-fmvc))
(setf (analysis-usage result) (simpletimer->msec st))
(movelist-notate-sequence (analysis-pv result) pos)
(if (is-score-mating? (analysis-score result))
(format t "Found a mate in ~R: ~A~%"
(calc-mate-distance (analysis-score result))
(analysis-pv->string result))
(setf result nil))
result))
(defun matehammer (my-fen my-fmnc-upper)
"Repeatedly search for a mate in full move number increments."
(let ((result nil) (fmvc 1))
(dowhile (and (not result) (<= fmvc my-fmnc-upper))
(format t "Searching for a mate in ~R...~%" fmvc)
(setf result (matefinder my-fen fmvc))
(incf fmvc))
result))
