Movepath enumeration (perft) record breaker (?)

[sje]

Consider:
[d]7k/8/8/8/8/8/8/K7 w - - 0 1
If your program can do movepath enumeration (perft) and if it has 64 bit unsigned counters, you should be able to verify:

(perft "7k/8/8/8/8/8/8/K7 w - - 0 1" 24) ; 24 ply deep

Ka2 2543510336852458578
Kb1 2543510336852458578
Kb2 4555171376957742544

Total path count for depth twenty-four: 9642192050662659700
Descriptive: nine quintillion, six hundred and forty-two quadrillion, one hundred and ninety-two trillion, fifty billion, six hundred and sixty-two million, six hundred and fifty-nine thousand, seven hundred

But can you verify:

(perft "7k/8/8/8/8/8/8/K7 w - - 0 1" 64) ; 64 ply deep

Ka2 6014758645580371240454075970327082449514766427868000
Kb1 6014758645580371240454075970327082449514766427868000
Kb2 10766048221894048840311950043044869834072791312416556

Total path count for depth sixty-four: 22795565513054791321220101983699034733102324168152556
Descriptive: twenty-two sexdecillion, seven hundred and ninety-five quindecillion, five hundred and sixty-five quattuordecillion, five hundred and thirteen tredecillion, fifty-four duodecillion, seven hundred and ninety-one undecillion, three hundred and twenty-one decillion, two hundred and twenty nonillion, one hundred and one octillion, nine hundred and eighty-three septillion, six hundred and ninety-nine sextillion, thirty-four quintillion, seven hundred and thirty-three quadrillion, one hundred and two trillion, three hundred and twenty-four billion, one hundred and sixty-eight million, one hundred and fifty-two thousand, five hundred and fifty-six

[sje]

(perft "7k/8/8/8/8/8/8/K7 w - - 0 1" 100) ; 100 ply deep

Ka2 6483391819812966265301327210604415991150205380553703683640938433619496741378891273
Kb1 6483391819812966265301327210604415991150205380553703683640938433619496741378891273
Kb2 11604865389712919261745423181879079463176931058791407264500561685233384707452354616

Total path count for depth one hundred: 24571649029338851792348077603087911445477341819898814631782438552472378190210137162

Alas, the big number dictionary only goes so far, so no descriptive name.

[sje]

(perft "7k/8/8/8/8/8/8/K7 w - - 0 1" 256) ; 256 ply deep

Ka2 89739959111555760601875157522163171611479782966995387045190567392432538486177650829016545038696350743521233767128067650015306301992399865826963886714827355541640277355594812075620175790936507730408883345043365459
Kb1 89739959111555760601875157522163171611479782966995387045190567392432538486177650829016545038696350743521233767128067650015306301992399865826963886714827355541640277355594812075620175790936507730408883345043365459
Kb2 160628907492493035382127946337452665019972493099771369555778239050185396228502733478491483520445722874015237122420463168777892685415549388777020762452270028841342013968059618618330170809939179556306336970463058146

Total path count for depth two hundred and fifty-six: 340108825715604556585878261381779008242932059033762143646159373835050473200858035136524573597838424361057704656676598468808505289400349120430948535881924739924622568679249242769570522391812195017124103660549789064

[Zach Wegner]

256? All I can say is DAMN! Did that really take just 15 minutes to calculate?

That's when Lisp integers can come in real handy!

[sje]

256? All I can say is DAMN! Did that really take just 15 minutes to calculate?

That's when Lisp integers can come in real handy!

Yes; Lisp's BIGNUM facility is also known as "the calculator of the gods".

That last perft number is about 3.4*10^212, more than a trillion times a googol squared.

[Pradu]

Very impressive! How is it done?

[sje]

Very impressive! How is it done?

http://en.wikipedia.org/wiki/Bignum

[Pradu]

Very impressive! How is it done?

http://en.wikipedia.org/wiki/Bignum

I meant the algorithm that calculates the perft.

[sje]

Code: Select all

;;; Count terminal nodes with transpositions (movepath enumeration)

(defun create-transtable-vec (my-ply-limit)
  (let ((result (make-array my-ply-limit)))
    (dotimes (ply my-ply-limit)
      (setf (svref result ply) (make-hash-table :test #'equal)))
    result))

(defun cwt-movepaths-aux (my-pos my-rcv my-ply my-depth my-tt-vec)
  "Return a count of distinct movepaths using a transposition table vector."
  (let ((result nil) (trans-flag (< my-ply (array-total-size my-tt-vec))))
    (when trans-flag
      (setf result (gethash (pos-main-hash my-pos) (svref my-tt-vec my-ply))))
    (when (not result)
      (cond
        ((zero? my-depth)
          (setf result 1))
        ((one? my-depth)
          (setf result (count-moves my-pos)))
        (t
          (setf result 0)
          (dolist (move (if (zero? my-ply) (generate-canonical my-pos) (generate my-pos)))
            (let ((saved-posenv (clone-posenv (pos-posenv my-pos))))
              (execute-move move my-pos)
              (incf result
                (cwt-movepaths-aux my-pos (cons move my-rcv) (1+ my-ply) (1- my-depth) my-tt-vec))
              (setf (pos-posenv my-pos) saved-posenv)
              (retract-move move my-pos)))))
      (when trans-flag
        (setf (gethash (pos-main-hash my-pos) (svref my-tt-vec my-ply)) result)))
    (when (one? my-ply)
      (format t "~A ~D~%" (first my-rcv) result))
    result))

(defun cwt-movepaths (my-pos my-depth)
  "Count the distinct movepaths from the given position to the given ply depth."
  (let ((result nil))
    (setf result (cwt-movepaths-aux my-pos nil 0 my-depth (create-transtable-vec 256)))
    (format t "Total path count for depth ~R: ~D~%" my-depth result)
    (format t "Descriptive: ~R~%" result)
    result))

[hgm]

I guess al these perfts are wrong. They should be zero as the position is draw by rule. If you do a perft from the opening, you also don't continue branches after they reach a stalemate or checkmate position?

There are no legal moves in this position, as the game is finished.