WAC.163: 662 node search tree

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

WAC.163: 662 node search tree

Post by sje » Tue May 01, 2007 4:04 am

Here's WAC.163 (a mate in eleven):
[D] 5rk1/2p4p/2p4r/3P4/4p1b1/1Q2NqPp/PP3P1K/R4R2 b - - 0 1
And here's the 662 node search tree:

Code: Select all

1... Qg2+ 2. Nxg2 hxg2+ 3. Kxg2
    3... Bf3+ 4. Qxf3
      4... Rh2+ 5. Kxh2
      4... exf3+ 5. Kg1 Rh1+ 6. Kxh1
    3... Bh3+ 4. Kg1
    3... Rh2+ 4. Kxh2 Rxf2+ 5. Rxf2
    3... Rxf2+ 4. Rxf2
      4... Bf3+ 5. Qxf3 Rh2+ 6. Kxh2
      4... Bh3+ 5. Kg1
      4... Rh2+ 5. Kxh2
1... Qh1+ 2. Rxh1 Rxf2+ 3. Kg1
    3... Rf1+ 4. Rxf1 h2+ 5. Kg2
        5... Bf3+ 6. Rxf3 exf3+ 7. Kf2
        5... Bh3+ 6. Kxh2
          6... Bc8+ 7. Kg1 Rxh1+ 8. Kxh1
          6... Bd7+ 7. Kg1 Rxh1+ 8. Kxh1
          6... Be6+ 7. Kg1 Rxh1+ 8. Kxh1
          6... Bf5+ 7. Kg1 Rxh1+ 8. Kxh1
          6... Bg2+ 7. Kxg2 Rh2+ 8. Kxh2
          6... Bg4+ 7. Kg1 Rxh1+ 8. Kxh1
          6... Bxf1+ 7. Kg1 Rxh1+ 8. Kxh1
    3... Rg2+ 4. Nxg2 h2+ 5. Kf1
        5... Be2+ 6. Kxe2
        5... Rf6+ 6. Nf4 Bh3+ 7. Ke1
    3... h2+ 4. Kxf2 Rf6+ 5. Nf5
1... Qxf2+
 2. Kh1 Bf3+ 3. Ng2 hxg2#
 2. Ng2 Qxg2#
 2. Rxf2 Rxf2+
   3. Kg1
    3... Rf1+ 4. Rxf1 h2+ 5. Kh1 Bf3+ 6. Rxf3
    3... Rg2+ 4. Nxg2 h2+ 5. Kh1
    3... h2+
     4. Kh1 Bf3+ 5. Ng2
        5... Bxg2#
        5... Rf1+ 6. Rxf1 Bxg2+ 7. Kxg2
     4. Kxf2 Rf6+
       5. Ke1
        5... h1=Q+
         6. Kd2
          6... Qc1+ 7. Kxc1
          6... Rf2+ 7. Kc3
         6. Nf1
          6... Qxf1+ 7. Kd2
            7... Qc1+ 8. Kxc1
            7... Qe2+
             8. Kc1
              8... Qd1+ 9. Qxd1
              8... Rf1+ 9. Qd1
                9... Qc2+ 10. Kxc2
                9... Qxb2+ 10. Kxb2
                9... Qxd1#
                9... Rxd1#
             8. Kc3
              8... Qd2+ 9. Kxd2
              8... Qd3+ 9. Kb4
              8... Rf3+
               9. Kb4 Qb5+ 10. Ka3
                  10... Qa4+ 11. Kxa4
                  10... Qa5#
                  10... Qa6+ 11. Kb4
                    11... Qb5+ 12. Ka3
                      12... Qa4+ 13. Kxa4
                      12... Qa5#
                      12... Qa6+ 13. Kb4 Qb5+ 14. Ka3 Qa5#
                      12... Qb4+ 13. Kxb4
                      12... Qc5+ 13. Ka4
                        13... Qa5+ 14. Kxa5
                        13... Qa7+ 14. Kb4
                      12... Qxb3+ 13. axb3
                      12... Rxb3+ 13. axb3
                        13... Qa5#
                        13... Qa6+ 14. Kb4
                        13... Qxb3+ 14. Kxb3
                    11... c5+ 12. Kxc5
                  10... Qb4+ 11. Kxb4
                  10... Qc5+ 11. Ka4
                    11... Qa5+ 12. Kxa5
                    11... Qa7+ 12. Kb4
                  10... Qxb3+ 11. axb3
                  10... Rxb3+ 11. axb3
                    11... Qa5#
                    11... Qa6+ 12. Kb4
                    11... Qxb3+ 12. Kxb3
               9. Kd4
            7... Qf2+
             8. Kc1
              8... Qc2+ 9. Kxc2
              8... Qd2+ 9. Kxd2
              8... Qe1+
               9. Kc2 Rf2#
               9. Qd1 Qxd1#
              8... Qxb2+ 9. Kxb2
             8. Kc3
              8... Qc5+ 9. Qc4
              8... Qd2+ 9. Kxd2
              8... Qd4+ 9. Kxd4
              8... Rf3+ 9. Kb4
            7... Rf2+ 8. Ke3
              8... Qd3+ 9. Qxd3
              8... Qe1+ 9. Rxe1
              8... Qe2+ 9. Kd4
              8... Re2+ 9. Kd4
          6... Rxf1+ 7. Kd2
            7... Qg2+ 8. Ke3
              8... Qd2+ 9. Kxd2
              8... Qe2+ 9. Kd4
              8... Qf2+ 9. Kxe4
                9... Bf5+ 10. Ke5 Qd4+ 11. Kxd4
                9... Qd4+ 10. Kxd4
              8... Qf3+ 9. Kd2
                9... Qd3+ 10. Qxd3
                9... Qe2+ 10. Kc3 Qd3+ 11. Kb4
                9... Qf2+ 10. Kc3
              8... Qg1+ 9. Kxe4
                9... Bf5+ 10. Ke5 Qd4+ 11. Kxd4
                9... Qd4+ 10. Kxd4
              8... Rf3+ 9. Kxe4
            7... Qh2+ 8. Ke3
              8... Qd2+ 9. Kxd2
              8... Qe2+ 9. Kd4
              8... Qf2+ 9. Kxe4
                9... Bf5+ 10. Ke5 Qd4+ 11. Kxd4
                9... Qd4+ 10. Kxd4
              8... Qg1+ 9. Kxe4
                9... Bf5+ 10. Ke5 Qd4+ 11. Kxd4
                9... Qd4+ 10. Kxd4
              8... Qh6+ 9. Kxe4
              8... Rf3+ 9. Kxe4
            7... Rf2+ 8. Ke3
              8... Qe1+ 9. Rxe1
              8... Qf3+ 9. Kd4
              8... Re2+ 9. Kd4
        5... h1=R+ 6. Nf1
          6... Rfxf1+ 7. Kd2
            7... Rf2+ 8. Ke3 Re2+ 9. Kd4
            7... Rh2+ 8. Ke3
              8... Re2+ 9. Kd4
              8... Rf3+ 9. Kxe4
          6... Rhxf1+ 7. Kd2 R6f2+ 8. Ke3 Re2+ 9. Kd4
       5. Kg2
        5... Rf2+ 6. Kxf2
        5... h1=Q+ 6. Kxh1
       5. Nf5 Rxf5+
         6. Ke1
          6... Rf1+ 7. Kxf1
            7... h1=Q+ 8. Kf2
              8... Qg1+ 9. Kxg1
              8... e3+ 9. Kxe3 Qf3+ 10. Kd2
            7... h1=R+ 8. Kf2
          6... h1=Q+ 7. Kd2
            7... Qc1+ 8. Kxc1
            7... Rf2+ 8. Ke3
              8... Qe1+ 9. Rxe1
              8... Qf3+ 9. Kd4
              8... Re2+ 9. Kd4
          6... h1=R+ 7. Kd2 Rf2+ 8. Ke3 Re2+ 9. Kd4
         6. Ke3
         6. Kg2
          6... Rf2+ 7. Kxf2
          6... h1=Q+ 7. Kxh1 Rh5+ 8. Kg1
         6. Qf3 Rxf3+
           7. Ke1
            7... Rf1+ 8. Kxf1
              8... h1=Q+ 9. Kf2 e3+ 10. Kxe3
              8... h1=R+ 9. Kf2
            7... h1=Q+ 8. Kd2
              8... Qd1+ 9. Kxd1 Rf1+ 10. Kc2
              8... Rd3+ 9. Kc2 Qd1+ 10. Rxd1
              8... Rf2+ 9. Ke3 Qf3+ 10. Kd4
            7... h1=R+
             8. Kd2
              8... Rd3+ 9. Kc2
                9... Rc1+ 10. Kxc1 Rd1+ 11. Kc2
                9... Rh2+
                 10. Kb1
                  10... Rd1#
                  10... Rh1+ 11. Kc2
                 10. Kc1
                  10... Rd1#
                  10... Rh1+ 11. Kc2
              8... Rf2+ 9. Ke3 Re2+ 10. Kd4
             8. Ke2
              8... Ra3+
               9. Kd2
                9... Rd3+ 10. Kc2
                9... e3+ 10. Kc2 Bf5#
               9. Kf2 e3+ 10. Kg2 Bf3+ 11. Kxf3
              8... Rb3+ 9. Kd2
                9... Rd3+ 10. Kc2
                9... e3+ 10. Kc2 Bf5+ 11. Kxb3
              8... Rc3+ 9. Kd2
                9... Rd3+ 10. Kc2
                9... e3+ 10. Kxc3
              8... Rd3+ 9. Kf2
                9... Rd2+ 10. Ke3
                9... e3+ 10. Kg2
                  10... Bf3+ 11. Kxf3
                  10... Rd2+ 11. Kxh1 Bf3+ 12. Kg1
              8... Rf2+ 9. Kxf2
              8... Rf4+ 9. Ke3
              8... Rf5+ 9. Ke3
              8... Rf6+ 9. Ke3
              8... Rf7+ 9. Ke3
              8... Rf8+ 9. Ke3
              8... Rff1+ 9. Ke3
              8... Rh2+
               9. Kd1
                9... Ra3+ 10. Kc1
                9... Rb3+ 10. Kc1
                9... Rc3+ 10. Ke1
                  10... Rc1+ 11. Rxc1
                  10... Re3+ 11. Kf1 Bh3+ 12. Kg1 Rxg3+ 13. Kxh2
                9... Rd3+
                 10. Kc1
                  10... Rd1#
                  10... Rh1+ 11. Kc2
                 10. Ke1
                  10... Rd1+ 11. Rxd1 Re2+ 12. Kf1
                  10... Re2+ 11. Kf1 Rd1+ 12. Rxd1
                  10... Re3+ 11. Kf1 Bh3+ 12. Kg1 Rxg3+ 13. Kxh2
                  10... Rh1+ 11. Kf2
                    11... Rd2+ 12. Ke3
                    11... e3+ 12. Kg2
                      12... Bf3+ 13. Kxf3
                      12... Rd2+ 13. Kxh1 Bf3+ 14. Kg1
                9... Re3+ 10. Kc1 Re1#
                9... Rf1#
                9... Rf4+
                 10. Kc1 Rf1#
                 10. Ke1
                  10... Re2+ 11. Kd1 Rf1#
                  10... Rf1+ 11. Kxf1
                  10... Rh1+ 11. Kd2
                9... Rf5+
                 10. Kc1 Rf1#
                 10. Ke1
                  10... Re2+ 11. Kd1
                    11... Rf1#
                    11... Rxd5+ 12. Kc1
                      12... Rd1+ 13. Kxd1
                      12... Re1+ 13. Kc2
                  10... Rf1+ 11. Kxf1
                  10... Rh1+ 11. Kd2
                9... Rf6+
                 10. Kc1 Rf1#
                 10. Ke1
                  10... Re2+ 11. Kd1 Rf1#
                  10... Rf1+ 11. Kxf1
                  10... Rh1+ 11. Kd2
                9... Rf7+
                 10. Kc1 Rf1#
                 10. Ke1
                  10... Re2+ 11. Kd1 Rf1#
                  10... Rf1+ 11. Kxf1
                  10... Rh1+ 11. Kd2
                9... Rf8+
                 10. Kc1 Rf1#
                 10. Ke1
                  10... Re2+ 11. Kd1 Rf1#
                  10... Rf1+ 11. Kxf1
                  10... Rh1+ 11. Kd2
               9. Ke1
                9... Re2+ 10. Kxe2
                9... Re3+ 10. Kf1 Bh3+ 11. Kg1 Rxg3+ 12. Kxh2
                9... Rf1+ 10. Kxf1
                9... Rh1+ 10. Kd2 Rd3+ 11. Kc2
              8... Rxg3+
               9. Kd2
                9... Rd1+ 10. Rxd1
                9... Rd3+ 10. Kc2
                9... Rg2+ 10. Ke3
                9... Rh2+
                 10. Kc1 Rg1#
                 10. Ke1
                  10... Re3+ 11. Kf1 Bh3+ 12. Kg1 Rg3+ 13. Kxh2
                  10... Rg1#
               9. Kf2
                9... Rf3+ 10. Ke2
                  10... Rd3+ 11. Kf2
                  10... Rf2+ 11. Kxf2
                9... Rg2+ 10. Kxg2
                9... e3+ 10. Kxg3
           7. Ke2
           7. Kg2
            7... Rf2+ 8. Kxf2
            7... h1=Q+ 8. Kxh1
   3. Kh1
    3... Bf3+ 4. Kg1 h2+ 5. Kxf2
    3... Rh2+ 4. Kxh2
   3. Ng2
    3... Rxg2+ 4. Kh1 Rh2+ 5. Kxh2
    3... hxg2+ 4. Kg1
      4... Rf1+ 5. Rxf1
        5... Rh1+ 6. Kxg2
        5... gxf1=Q+ 6. Kxf1
        5... gxf1=R+ 6. Kxf1
      4... Rh1+ 5. Kxf2 g1=Q+ 6. Rxg1
1... Qxg3+ 2. fxg3 Rf2+ 3. Rxf2

Pradu
Posts: 287
Joined: Sat Mar 11, 2006 2:19 am
Location: Atlanta, GA
Contact:

Re: WAC.163: 662 node search tree

Post by Pradu » Tue May 01, 2007 5:40 am

How does your "cognitive" search algorithm work?

Dann Corbit
Posts: 8518
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: WAC.163: 662 node search tree

Post by Dann Corbit » Tue May 01, 2007 6:19 am

Solving a mate in 11 with 662 nodes is utterly astounding. I would have been prepared to say probably impossible for a position such as the one posted.

Chest takes quite a long time and other engines solve fairly fast, but chug through a lot more nodes than 662. Rybka (which is generally considered to under-report node counts) takes 1.3 million nodes to solve it.

Code: Select all

Analysis from c:\mtest.epd   
4/30/2007 11:09:32 PM Level: 300 Seconds
Analyzing engine: Rybka v1.2.w32

1)                      
    Avoid move: 
    Best move (Rybka v1.2.w32): Qf3-g2
    Not found in: 05:00
      2	00:01	         368	5.888	+0.49	c6c5
      2	00:01	         416	5.324	+0.67	c6xd5
      3	00:01	         728	6.715	+0.48	c6xd5
      3	00:01	         976	9.003	+0.51	c6c5
      4	00:01	       3.384	15.750	+0.50	c6c5 Qb3c4
      5	00:01	       9.312	28.895	+0.60	c6c5 Qb3c3 Rf8b8
      6	00:01	      12.608	32.935	+0.29	c6c5 Qb3c3 Rf8b8 Ra1b1
      6	00:01	      13.896	33.639	+0.48	c6xd5 Qb3xd5+ Bg4e6 Qd5d1 Qf3f7
      7	00:01	      24.824	42.722	+0.22	c6xd5 Qb3xd5+ Bg4e6 Qd5d1 Qf3f6 Ne3g4
      7	00:01	      44.224	51.695	+0.48	c6c5 a2a4 Bg4c8 Qb3d1 Qf3f7
      8	00:02	      64.336	57.688	+0.52	c6c5 a2a4 Bg4c8 Qb3d1 Qf3f7 Ra1c1
      9	00:02	      84.304	63.429	+0.45	c6c5 a2a4 Bg4c8 Qb3d1 Qf3f7 Ra1c1 Qf7e7
     10	00:02	     141.912	73.171	+0.48	c6c5 a2a4 Bg4c8 Qb3d1 Qf3f7 Ra1c1 Qf7e7 Kh2h1
     11	00:04	     254.096	80.406	+0.45	c6c5 a2a4 Bg4c8 Qb3d1 Qf3f7 Ra1c1 Qf7e7 a4a5 Bc8d7
     12	00:17	   1.269.584	79.160	+0.44	c6c5 a2a4 Bg4c8 Ra1c1 Rh6b6 Qb3d1 Rb6xb2 Qd1xf3 Rf8xf3 Ne3d1 Rb2d2
     12	00:17	   1.292.176	79.883	+M11	Qf3g2+ Ne3xg2 h3xg2+ Kh2xg2 Bg4f3+ Qb3xf3 e4xf3+ Kg2g1 Rf8f5 Ra1e1 Rf5h5 Re1e8+ Kg8f7 Re8e7+ Kf7xe7 Rf1e1+ Ke7f8 Re1e8+ Kf8xe8
Hiarcs takes eons, and WinFinder gets it pretty fast, but far, far more than 662 nodes are needed:

Code: Select all

Analysis from c:\mtest.epd   
4/30/2007 11:11:40 PM Level: 300 Seconds
Analyzing engine: Hiarcs11.1UCI

1)                      
    Avoid move: 
    Best move (Hiarcs11.1UCI): Qf3-g2
    Not found in: 05:00
     8/23	00:01	     159.112	307.760	+0.84	Rf8f7
     8/23	00:01	     190.113	311.660	+0.84	Rf8f7 Ra1d1
     9/23	00:02	     381.162	300.838	+0.84	Rf8f7 Ra1d1 Bg4c8 d5xc6 Bc8a6 Rd1d8+ Kg8g7 Qb3b8 Rh6xc6 Qb8a8 Ba6xf1
     9/24	00:02	     505.468	291.336	+0.85	c6c5
     9/24+	00:02	     546.979	291.566	+1.09	c6c5
     9/24	00:02	     552.950	292.256	+1.09	c6c5 Qb3c3 c7c6 d5xc6 Rh6xc6 Ra1c1 Rc6f6 Qc3xc5 Bg4e6 Qc5g5+ Rf6g6
    10/25-	00:03	     766.085	302.561	+0.84	c6c5
    10/25	00:03	     866.370	299.574	+0.82	c6c5 Ra1c1 Rh6f6 Qb3c2 c7c6 d5xc6 Rf6xc6 b2b4 Rc6f6 Qc2xc5 Bg4e6
    11/28	00:08	   2.082.992	287.269	+0.88	c6c5 Ra1c1 Rh6b6 Qb3c3 Bg4c8 Rc1c2
    12/33	00:17	   5.020.063	305.096	+0.65	c6c5 Ra1d1 Bg4c8 Rd1d2 Bc8a6 Rf1e1 Ba6d3 Qb3c3 Rf8f7 Qc3xc5 Rh6g6 Qc5c3 Rg6f6
    12/33	00:20	   6.033.314	305.221	+0.66	c6xd5
    12/33	00:21	   6.361.454	304.041	+0.66	c6xd5 Qb3xd5+ Kg8g7 Qd5g5+ Rh6g6 Qg5e5+ Kg7g8 Ra1c1 c7c6 Rc1c4
    12/33	00:29	   8.634.442	301.629	+0.67	Rh6f6
    12/33	00:32	   9.427.529	300.020	+0.95	Rh6f6 Ra1c1 c6c5 a2a3 h7h5 Rc1c2 Bg4c8 Rc2xc5 h5h4 Rc5c2 Rf6f7 Rf1g1
    13/39+	00:46	  13.746.304	304.202	+1.20	Rh6f6
    13/40	00:54	  16.947.458	314.745	+1.20	Rh6f6 d5xc6+ Bg4e6 Qb3c2 Qf3xf2+ Rf1xf2 Rf6xf2+ Kh2g1 Rf2xc2 Ne3xc2 h3h2+ Kg1h1 Rf8f2 Nc2e3 Rf2xb2 a2a4 Rb2e2 Ne3g2 Be6h3
    14/40	01:12	  22.789.778	320.626	+1.05	Rh6f6 d5xc6+ Bg4e6 Qb3d1 Qf3xd1 Ne3xd1 e4e3 Nd1xe3 Rf6xf2+ Kh2h1 Rf2e2 Rf1xf8+ Kg8xf8 Ra1f1+
    15/41	02:06	  40.628.901	324.825	+0.98	Rh6f6 d5xc6+ Bg4e6 Qb3d1 Qf3xd1 Ne3xd1 e4e3 Nd1xe3 Rf6xf2+ Kh2h1 Rf2e2 Rf1xf8+ Kg8xf8 Ra1f1+ Kf8e8 Rf1f3 h7h5 a2a4 Re2xb2 a4a5 Rb2a2
    15/45	03:57	  76.635.161	324.681	+0.99	Qf3g2+
    15/45+	03:57	  77.003.960	324.952	+1.30	Qf3g2+
    15/45	03:59	  77.746.735	325.916	+M12	Qf3g2+
    15/45	04:00	  78.238.461	326.502	+M11	Qf3g2+ Ne3xg2 h3xg2+ Kh2xg2 Bg4f3+ Qb3xf3 e4xf3+ Kg2g1 Rf8f5 Ra1e1 Rf5h5 Re1e8+ Kg8f7 Re8e7+
    16/45	04:01	  78.688.741	326.868	+M11	Qf3g2+ Ne3xg2 h3xg2+ Kh2xg2 Bg4f3+ Qb3xf3 e4xf3+ Kg2g1 Rf8f5 Ra1e1 Rf5h5 Re1e8+ Kg8f7 Re8e7+ Kf7xe7 Rf1e1+ Ke7f8 Re1e8+ Kf8xe8
    17/45	04:02	  79.106.540	327.265	+M11	Qf3g2+ Ne3xg2 h3xg2+ Kh2xg2 Bg4f3+ Qb3xf3 e4xf3+ Kg2g1 Rf8f5 Ra1e1 Rf5h5 Re1e8+ Kg8f7 Re8e7+ Kf7xe7 Rf1e1+ Ke7f8 Re1e8+ Kf8xe8
    18/45	04:02	  79.127.838	327.289	+M11	Qf3g2+ Ne3xg2 h3xg2+ Kh2xg2 Bg4f3+ Qb3xf3 e4xf3+ Kg2g1 Rf8f5 Ra1e1 Rf5h5 Re1e8+ Kg8f7 Re8e7+ Kf7xe7 Rf1e1+ Ke7f8 Re1e8+ Kf8xe8
    19/45	04:02	  79.129.345	327.295	+M11	Qf3g2+ Ne3xg2 h3xg2+ Kh2xg2 Bg4f3+ Qb3xf3 e4xf3+ Kg2g1 Rf8f5 Ra1e1 Rf5h5 Re1e8+ Kg8f7 Re8e7+ Kf7xe7 Rf1e1+ Ke7f8 Re1e8+ Kf8xe8
    20/45	04:02	  79.130.918	327.282	+M11	Qf3g2+ Ne3xg2 h3xg2+ Kh2xg2 Bg4f3+ Qb3xf3 e4xf3+ Kg2g1 Rf8f5 Ra1e1 Rf5h5 Re1e8+ Kg8f7 Re8e7+ Kf7xe7 Rf1e1+ Ke7f8 Re1e8+ Kf8xe8
    21/45	04:02	  79.133.516	327.292	+M11	Qf3g2+ Ne3xg2 h3xg2+ Kh2xg2 Bg4f3+ Qb3xf3 e4xf3+ Kg2g1 Rf8f5 Ra1e1 Rf5h5 Re1e8+ Kg8f7 Re8e7+ Kf7xe7 Rf1e1+ Ke7f8 Re1e8+ Kf8xe8
   4/30/2007 11:15:49 PM, Time for this analysis: 00:04:03, Rated time: 05:00

0 of 1 matching moves
4/30/2007 11:15:50 PM, Total time: 12:04:09 AM
Rated time: 05:00 = 300 Seconds

--------------------------------------------------------------------------------

Analysis from c:\mtest.epd   
4/30/2007 11:11:40 PM Level: Infinite
Analyzing engine: Rybka WinFinder 1.0.w32

1)                      
    Avoid move: 
    Best move (Rybka WinFinder 1.0.w32): Qf3-g2
    Not found in: 05:00
      3	00:01	      13.576	73.554	+1.01	c6xd5
      4	00:01	      16.344	76.073	+0.87	c6xd5
      4	00:01	      23.504	85.046	+0.94	Kg8g7
      5	00:01	       6.648	17.366	+0.78	Kg8g7 d5xc6
      5	00:01	       6.864	17.930	+0.88	c6xd5 Qb3xd5+ Bg4e6
      6	00:01	      11.789	24.095	+0.62	c6xd5 Qb3xd5+ Bg4e6 Qd5d1
      6	00:01	      21.401	31.084	+0.72	Rh6g6 d5xc6+ Bg4e6 Qb3d1
      7	00:01	      29.294	36.141	+0.57	Rh6g6 d5xc6+ Bg4e6 Qb3d1 Qf3f6
      7	00:02	      37.370	38.810	+0.59	c6xd5 Qb3xd5+ Kg8g7 Qd5g5+ Rh6g6 Qg5e7+ Kg7g8
      7	00:02	      49.109	41.732	+0.72	c6c5 Ra1c1 Rh6b6 Qb3a3
      8	00:02	      80.426	49.672	+0.86	c6c5 Ra1c1 Rh6b6 Qb3c3 Bg4d7
      8	00:02	      88.151	51.551	+M0	Qf3g2+ Ne3xg2 h3xg2+ Kh2xg2 Bg4f3+ Qb3xf3 e4xf3+ Kg2g1 Rf8f5 Rf1e1 Rf5h5
      9	00:02	      88.247	51.607	+M0	Qf3g2+ Ne3xg2 h3xg2+ Kh2xg2 Bg4f3+ Qb3xf3 e4xf3+ Kg2g1 Rf8f5 Rf1e1 Rf5h5
     10	00:02	      88.159	51.556	+M0	Qf3g2+ Ne3xg2 h3xg2+ Kh2xg2 Bg4f3+ Qb3xf3 e4xf3+ Kg2g1 Rf8f5 Rf1e1 Rf5h5
   4/30/2007 11:16:35 PM, Time for this analysis: 00:00:36, Rated time: 05:00

Does whatever you are doing work for best moves also, and not just won/loss/draw solutions?

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: WAC.163: 662 node search tree

Post by sje » Tue May 01, 2007 11:25 am

Pradu wrote:How does your "cognitive" search algorithm work?
See the status report for 2007.04.25.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: WAC.163: 662 node search tree

Post by sje » Tue May 01, 2007 11:27 am

Dann Corbit wrote: Does whatever you are doing work for best moves also, and not just won/loss/draw solutions?
Not yet, and not soon. It's still a long road ahead.

Pradu
Posts: 287
Joined: Sat Mar 11, 2006 2:19 am
Location: Atlanta, GA
Contact:

Re: WAC.163: 662 node search tree

Post by Pradu » Tue May 01, 2007 3:32 pm

sje wrote:
Pradu wrote:How does your "cognitive" search algorithm work?
See the status report for 2007.04.25.
Search algorithm looks very alpha-betaish eg attacker/defender. The implementation of attack and defense metrics will be rather interesting though.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: WAC.163: 662 node search tree

Post by sje » Tue May 01, 2007 6:37 pm

Pradu wrote:Search algorithm looks very alpha-betaish eg attacker/defender. The implementation of attack and defense metrics will be rather interesting though.
Well, there aren't any position scores, so there's no alpha and beta. And there isn't any real symmetry, as threats are generated via global selection while refutations are generated along a single variation. Each side has a different search, and both are best first and not depth first.

The attack and defense do take turns as they would in a traditional A/B searcher. But there's no particular "current position" or "current expectation window."

--------

I took another look at the first cut source and plenty of omissions have come to light, including the lack of draw recognition other than stalemates. All draws are correctly marked when a node is generated and inserted into the tree, but the metrics productions don't use this data at the present. The same can be said for a lot of other attributes, so there's lots of room for improvement here.

Somewhat annoyingly, the PV returned by the mate search is almost always not the theoretically best PV but rather a PV with suboptimal moves. It turns out that both sides tend to try the worst moves last, and this is what comes back as a result. It doesn't matter too much for actual play as the attacker's first move in the final result is always correct in the sense that it leads to some forced mate, if not the fastest one.

Dann Corbit
Posts: 8518
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: WAC.163: 662 node search tree

Post by Dann Corbit » Tue May 01, 2007 10:18 pm

sje wrote:
Dann Corbit wrote: Does whatever you are doing work for best moves also, and not just won/loss/draw solutions?
Not yet, and not soon. It's still a long road ahead.
Whatever it is you have done here (and even if it is only for proof search) is -- fundamentally -- very, very interesting.

It seems almost miraculous and perhaps a new paradigm altogether.

If you could spend some time explaining it, it might be a breakthrough for proof search ideas.

I mean, 662 nodes for a depth 11 mate is borderline ridiculous!
;-)

User avatar
Steve Maughan
Posts: 1024
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: WAC.163: 662 node search tree

Post by Steve Maughan » Tue May 01, 2007 11:33 pm

Dann Corbit wrote:Solving a mate in 11 with 662 nodes is utterly astounding.
This may be a stupid question but where is the mate in 11 in the search? The key move is Qg2+ and the tree seems to focus on Qxf2. I cannot see the mating line in the tree.

What am I missing?

Steve

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: WAC.163: 662 node search tree

Post by sje » Tue May 01, 2007 11:59 pm

Dann Corbit wrote:I mean, 662 nodes for a depth 11 mate is borderline ridiculous!
Some might say that spending tens to hundreds of milliseconds at a node is just as ridiculous.

From what I know of Paradise, it was never tried on WAC.163, but I'm fairly sure that it could have solved the problem with under 500 nodes and maybe only 250 or less. And I think that a strong human with the assistance of paper and pencil (or the electronic equivalent) could do the same. Remember that nearly all of the problems in WAC and BWTC came from human games in the first place.

Consider the human correspondence chess player. With several days to a week or so for each move, there's plenty of time for leisurely analysis. One way of doing the analysis is to get a big piece of paper and start to draw a search tree with the nodes labeled with active attack and defend issues. The human extends the tree one node at a time with a different algorithm based on which side is on the move. The player adds a node for his/her choice based on which of all the lines seems the most promising. For the opponent's choice, the node added is the one that best refutes the current threat at any level of the threat. In both cases there's a slight bias for shorter threats and faster/early refutations.

Now add a simple computer program that replaces the paper and pencil and keeps track of the tree. Add to the program a set of functions (productions) that measures the relative nastiness and speed of a threat along with a sorting routine that picks the best one. Then add a set of defensive productions that measure at all levels of a threat the relative power of possible refutations and a companion sorting routine. Wrap all of this together and you've got the basics behind Symbolic's mate search.

Post Reply