Fine #70, once again

[sje]

Fine #70, useful for testing transposition tables:
[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

I fed this into the new CIL Toolkit just to see what would happen. This may be the first time that a Lisp program solved Fine #70. Some output:

Code: Select all

[si] Starting iteration twenty-five
[pv] 1 Ka2 Kb8 2 Kb3 Kc7 3 Kc4 Kb6 4 Kd3 Kc7 5 Ke3 Kd8 6 Kf3 Ke8 7 Kg3 Kf7 8 Kh4 Kg6 9 Kh3 Kh7 10 Kg3 Kh6 11 Kf3 Kg6 12 Ke3 Kf7 13 Kf3   score: +1.160
[pv] 1 Kb1 Kb8 2 Kc2 Kb7 3 Kc3 Kc7   score: +2.288
[si] Starting iteration twenty-six
[st] Resource exhaustion (time)   Elapsed: 000.00:16:40.000

Search statistics summary report at 2011.04.10 20:47:32
  Root position FEN: 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
  Root moves (three):
    (Ka2 Kb1 Kb2)
  PV: 1 Kb1 Kb8 2 Kc2 Kb7 3 Kc3 Kc7
  Predicted score: +2.288
  Node counts:
   Total: 10,507,415   Capture: 2,349,062   Evasion: 754,823   General: 1,814,142   PlyZero: 26   
  Elapsed time: 000.00:16:40.000
  Termination status: Resource exhaustion (time)
  Transposition table statistics (general position tables by color):
    (white) limit: 65,536   usage: 64,188   match: 1,330,395   probe: 1,880,628   store: 1,214,730
    (black) limit: 65,536   usage: 65,533   match: 6,075,452   probe: 8,205,491   store: 3,703,292
  Transposition table statistics (pawn structure tables by color):
    (white) limit: 4,096   usage: 597   match: 640,722   probe: 641,485   store: 763
    (black) limit: 4,096   usage: 629   match: 1,706,723   probe: 1,707,577   store: 854
  Transposition pruning:
    Attempts: 10,086,119   Matches: 7,405,847   Sufficient drafts: 5,774,482   Successes: 5,168,092

[+2.288/6/1000.000/10,507,415/0] 1 Kb1 Kb8 2 Kc2 Kb7 3 Kc3 Kc7

[bob]

Fine #70, useful for testing transposition tables:
[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

I fed this into the new CIL Toolkit just to see what would happen. This may be the first time that a Lisp program solved Fine #70. Some output:

Code: Select all

[si] Starting iteration twenty-five
[pv] 1 Ka2 Kb8 2 Kb3 Kc7 3 Kc4 Kb6 4 Kd3 Kc7 5 Ke3 Kd8 6 Kf3 Ke8 7 Kg3 Kf7 8 Kh4 Kg6 9 Kh3 Kh7 10 Kg3 Kh6 11 Kf3 Kg6 12 Ke3 Kf7 13 Kf3   score: +1.160
[pv] 1 Kb1 Kb8 2 Kc2 Kb7 3 Kc3 Kc7   score: +2.288
[si] Starting iteration twenty-six
[st] Resource exhaustion (time)   Elapsed: 000.00:16:40.000

Search statistics summary report at 2011.04.10 20:47:32
  Root position FEN: 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
  Root moves (three):
    (Ka2 Kb1 Kb2)
  PV: 1 Kb1 Kb8 2 Kc2 Kb7 3 Kc3 Kc7
  Predicted score: +2.288
  Node counts:
   Total: 10,507,415   Capture: 2,349,062   Evasion: 754,823   General: 1,814,142   PlyZero: 26   
  Elapsed time: 000.00:16:40.000
  Termination status: Resource exhaustion (time)
  Transposition table statistics (general position tables by color):
    (white) limit: 65,536   usage: 64,188   match: 1,330,395   probe: 1,880,628   store: 1,214,730
    (black) limit: 65,536   usage: 65,533   match: 6,075,452   probe: 8,205,491   store: 3,703,292
  Transposition table statistics (pawn structure tables by color):
    (white) limit: 4,096   usage: 597   match: 640,722   probe: 641,485   store: 763
    (black) limit: 4,096   usage: 629   match: 1,706,723   probe: 1,707,577   store: 854
  Transposition pruning:
    Attempts: 10,086,119   Matches: 7,405,847   Sufficient drafts: 5,774,482   Successes: 5,168,092

[+2.288/6/1000.000/10,507,415/0] 1 Kb1 Kb8 2 Kc2 Kb7 3 Kc3 Kc7

I ran this on Crafty a few months back and without EGTBs was quite surprised to see it find a forced mate... Don't remember the depth. But think it took something under 2 minutes to find...

programs are getting quite good in these positions where hashing runs efficiency way up there...

[sje]

I ran this on Crafty a few months back and without EGTBs was quite surprised to see it find a forced mate... Don't remember the depth. But think it took something under 2 minutes to find...

programs are getting quite good in these positions where hashing runs efficiency way up there...

In the above example, the toolkit has allocated a pawn structure transposition table of 4K entries per color and managed to use only a fraction of that space. On the other hand, the general transposition table at 64K entries per color could certainly be larger. (See the statistics report.) The toolkit zips through the iterations quite rapidly until it sees the pawn win, and then the near-exhaustion of the general table slows progress.

At the moment, the toolkit knows nothing about pawn structure except for a simple color/square score table that credits pawn advancement. This was just enough to prove that the evaluator and the pawn transposition table subsystem works.

I'll have to work on copying some pawn knowledge from Symbolic into the toolkit.

I'm claiming the name "Simpleton" for the simple minded A/B search inside the toolkit. This will not be the final version of the search, but it does serve to help test the rest of the code and can serve to fill cracks in an advanced cognitive search.

Code: Select all

(defun simpleton (my-pos)
  "Perform a simpleton move selection for the given position; return an analysis."
  (let ((scs (new-scs my-pos)))
    (encode-board-graphic-color (scs-trstream scs) my-pos)
    (simpleton-analyze scs)
    (when (is-acof-set? (acs-acofbits *acs*) acof-sssr)
      (scs-report-statistics scs))
    (scs->analysis scs)))

(defun simpleton-test-game ()
  "Produce a simpleton test game."
  (let*
    (
      (result  (make-game))
      (ostream (acs-ostream *acs*))
      (pos     (game-pos result))
      (ptp-vec (game-ptp-vec result))
    )
    (setf (svref ptp-vec ptn-event) "Simpleton autoplay test")
    (setf (svref ptp-vec ptn-site)  "Autoplay test site")
    (setf (svref ptp-vec ptn-white) "Simpleton")
    (setf (svref ptp-vec ptn-black) "Simpleton")
    (dowhile (pos-is-game-going? pos)
      (let* ((analysis (simpleton pos)) (move (first (analysis-pv analysis))))
        (format ostream "~A~%" (analysis->string analysis))
        (pos-execute pos move)
        (format ostream "~A~%" (pos->string pos))))
    (encode-board-graphic-color ostream pos)
    (game-set-gsr result (pos->gsr pos))
    result))

[sje]

A sample CIL toolkit blitz game:

Code: Select all

[Event "Simpleton autoplay test"]
[Site "Autoplay test site"]
[Date "2011.04.11"]
[Round "-"]
[White "Simpleton"]
[Black "Simpleton"]
[Result "0-1"]
[UTC "2011.04.11 04:20:07"]

1 Nc3 Nc6 2 Nf3 Nf6 3 e4 e5 4 Bc4 Bb4 5 d3 Bxc3+ 6 bxc3 d5 7 exd5 Nxd5 8 Bg5 f6
9 Bxd5 Qxd5 10 c4 Qd6 11 Be3 Be6 12 Rb1 O-O-O 13 Qc1 h5 14 h4 Qe7 15 Ke2 e4 16
Nd2 exd3+ 17 cxd3 Bf5 18 Ne4 Bxe4 19 dxe4 Qxe4 20 f3 Nd4+ 21 Kf2 Qd3 22 Rb2 c5
23 Rd1 Qf5 24 Kf1 Nc6 25 a4 Rxd1+ 26 Qxd1 Re8 27 Qe2 Kc7 28 Qd2 b6 29 Bf4+ Ne5
30 g3 g5 31 hxg5 fxg5 32 Bxe5+ Rxe5 33 Kg2 Re8 34 Qc3 Qd7 35 Rd2 Qxa4 36 Qg7+
Kb8 37 Qxg5 Qxc4 38 Qxh5 Re2+ 39 Rxe2 Qxe2+ 40 Kh1 Qd1+ 41 Kg2 Qe2+ 42 Kh1 Qd1+
43 Kg2 Qc2+ 44 Kh3 a5 45 Qe5+ Ka7 46 Qc7+ Ka6 47 Qc8+ Kb5 48 Qe8+ Kb4 49 Qe4+
Qxe4 50 fxe4 c4 51 e5 Kc5 52 e6 Kd6 53 g4 c3 54 g5 Kxe6 55 Kg3 c2 56 g6 c1=Q 57
Kf3 Kf6 58 Ke2 Kxg6 59 Kd3 a4 60 Kd4 a3 61 Kd3 a2 62 Ke2 a1=Q 63 Kd3 Qa6+ 64
Kd4 Kf5 65 Kd5 Qc5# 0-1

There's a long way to go.

[Jouni]

From current top engines only Rybka (!) found mate in reasonable time in dual Pentium with or without tablebases:

Analysis by Rybka 4.1

1.Kb1 Kb7 2.Kc1 Kc7 3.Kd1 Kd7 4.Kc2 Kc7 5.Kd3 Kb7 6.Ke3 Kc7 7.Kf2 Kd7 8.Kg3 Ke7 9.Kh4 Kf6 10.Kh5 Kf7 11.Kg5 Kg7 12.Kxf5 Kf7 13.Kg5 Kg7 14.f5 Kf7 15.f6 Kf8 16.Kf4
+- (#32) Depth: 33 00:00:44 16816kN

Jouni

[bob]

From current top engines only Rybka (!) found mate in reasonable time in dual Pentium with or without tablebases:

Analysis by Rybka 4.1

1.Kb1 Kb7 2.Kc1 Kc7 3.Kd1 Kd7 4.Kc2 Kc7 5.Kd3 Kb7 6.Ke3 Kc7 7.Kf2 Kd7 8.Kg3 Ke7 9.Kh4 Kf6 10.Kh5 Kf7 11.Kg5 Kg7 12.Kxf5 Kf7 13.Kg5 Kg7 14.f5 Kf7 15.f6 Kf8 16.Kf4
+- (#32) Depth: 33 00:00:44 16816kN

Jouni

I believe it took Crafty about 1.5 minutes on the 8-core box. Tracy first reported this to me (no egtbs). I was surprised and tested it and bam. I posted the output here in CCC when it happened, as a curiosity. I'd suspect it could be found easily enough. It found a forced mate. I remember Monty's program "peasant" which was a K+P ending only program (in Frey's Chess Skill in ... book) where he thought this would take a ton of time just to see the win of a pawn. 30+ years later, the things see all the way to checkmate. What is impossible today is hard in a few years, then easy a few years later, then it becomes instantaneous.

[sje]

I remember Monty's program "peasant" which was a K+P ending only program (in Frey's Chess Skill in ... book) where he thought this would take a ton of time just to see the win of a pawn. 30+ years later, the things see all the way to checkmate. What is impossible today is hard in a few years, then easy a few years later, then it becomes instantaneous.

I remember Peasant and it was a groundbreaking program at the time because no one else had done an endgame specific searcher. Back in the early 1990s when I was doing the tablebases, I sent an email to Monty and to let him know that he was welcome to use my KPK and KPPK if he ever wanted to revise Peasant to replace its ONEPAWN and TWOPAWN routines. But too many years had gone by at that point and he had understandably moved onto better topics.

It's a bit sad that the use of big transposition tables and big tablebases has apparently taken away the motivation to work on intelligent endgame play. We have been spoiled by the simple stuff because today's hardware make it perform too well.

[UncombedCoconut]

Congrats, Steven. In addition to probably breaking a record, your program actually prints the word "three". Is that as notable as I think?

(I posted that earlier with an INTERCAL joke... but I guess it was stupid, since that was in the program's output rather than its input.)

Stockfish is funny to watch in this position. In general it seems hard to reproduce such fast mate resolutions with even strong (general purpose) engines, but hard to doubt they could solve it on a fast 8-CPU box.

[sje]

Congrats, Steven. In addition to probably breaking a record, your program actually prints the word "three". Is that as notable as I think?.

It depends on what you think. Here's the source if you'd like to change the output to use Roman numerals:

Code: Select all

;;; Search statistics summary report

(defun scs-report-statistics (my-scs)
  "Produce a statistics report summary of a search."
  (let ((ostream (acs-ostream *acs*)))
    (format ostream "Search statistics summary report at ~A~%" (current-ltz->string))
    ;;
    (format ostream "  Root position FEN: ~A~%" (scs-rootpos my-scs))
    (format ostream "  Root moves (~R):~%" (scs-rootmc my-scs))
    (format ostream "    ~A~%" (scs-rootmoves my-scs))
    ;;
    (format ostream "  PV: ~A~%" (fgpair+moves->string (scs-rootfgpair my-scs) (scs-lastpv my-scs)))
    (format ostream "  Expectation: ~A~%" (score->string (scs-lastscore my-scs)))
    ;;
    (format ostream "  Node counts:~%")
    (format ostream "   Total: ~:D   Capture: ~:D   Evasion: ~:D   General: ~:D   PlyZero: ~:D   ~%"
      (scs-nc        my-scs)
      (scs-nccapture my-scs)
      (scs-ncevasion my-scs)
      (scs-ncgeneral my-scs)
      (scs-ncplyzero my-scs))
    ;;
    (format ostream "  Elapsed time: ~A~%" (scs-stcu my-scs))
    ;;
    (format ostream "  Termination status: ~A~%" (sts->string (scs-sts my-scs)))
    ;;
    (format ostream "  Transposition table statistics (general position tables by color):~%")
    (gttpair-dumpstats (scs-gttpair my-scs))
    ;;
    (format ostream "  Transposition table statistics (pawn structure tables by color):~%")
    (pttpair-dumpstats (scs-pttpair my-scs))
    ;;
    (format ostream "  Transposition pruning:~%")
    (format ostream "    Attempts: ~:D   Matches: ~:D   Sufficient drafts: ~:D   Successes: ~:D~%"
      (scs-ttprune0 my-scs)
      (scs-ttprune1 my-scs)
      (scs-ttprune2 my-scs)
      (scs-ttprune3 my-scs)))
  (values))

[UncombedCoconut]

Ah... of course Common Lisp, of all languages, would have that feature built in. Does it only work in English?