# Computer Chess Club Archives

## Messages

### Subject: Re: Mate that every program will solve...

Author: leonid

Date: 15:06:54 04/17/01

Go up one level in this thread

```On April 17, 2001 at 13:57:35, Heiner Marxen wrote:

>On April 17, 2001 at 13:12:22, leonid wrote:
>
>>On April 17, 2001 at 11:13:02, Heiner Marxen wrote:
>>
>>>On April 17, 2001 at 07:43:30, leonid wrote:
>>>
>>>>Hello!
>>>>
>>>>If you like to solve very "regular" mate position, then you have one.
>>>>
>>>>[D]R7/4P1Pq/1rR5/2pb1rnk/1Q3B2/4Nn2/1PB2Np1/2K1b1Q1 w - -
>>>>
>>>>
>>>>Thanks,
>>>>Leonid.
>>>
>>>According to Chest there are two key moves for mate in 7 moves:
>>>
>>>Qxg2 Bd2+ Qxd2   Bxc6 g8=Q   Qxg8  Rxg8   Bd5  e8=Q+  Bf7  Nxf5   Nd4  Rxg5#
>>>Rh8  Bd2+ Qxd2   Be4  e8=Q+  Rf7   Qxf7+  Nxf7 Qd5+   Bf5  Rxh7+  Nh6  Rhxh6#
>>>
>>>(K7/600, 350MB hash, 9.3 minutes)
>>>
>>>Heiner
>>
>>Thanks, Heiner! My program demonstrate the worst possible branching factor for
>>this position. Even for seeing the 6 moves by brute force it took already 38 min
>>(Celeron 600. No hash). Only after your indication I went to see  7 moves by
>>brute force. It took for mine hefly 1 hours 5 min. And this is after my last
>>improvement that cut 6 moves brute force search already by 48%.
>>
>>Previously this position my solved by selective search in 10 moves.
>>
>>Leonid.
>
>Hi Leonid,
>
>From depth=6 in 38 minutes to depth=7 in 1h5min is a factor of less than 2.
>Even with the 48% improvement, the factor is just 4.  That is quite
>different from Chest's timing (see below), and is unexpectedly low (for me).

This is not how I see branching factor. At depth 7 mate already found, so I
don't see that much correspondence between 6 and 7 moves. Bad branching factor I
looked this way:

4 moves - 1.86 sec
branching factor = 37
5 moves - 1 min 9 sec.
branching factor = 33.1
6 moves - 38 min 6 sec.
-------------------
7 moves - 1 hour 5 min 6 sec.

After writing this message, I went to see what was the time of solution for my
previous version. I waited for 3 hours (7 moves brute froce) and just
disconnected. Had no more patience to wait.

I went also to see the branching factor on Genius 2. Had only time for 4 moves
and 5.

4 moves - 7 sec.
branching factor 37
5 moves 4 min 25 sec.

Felt me in good company when I found that Genius have exactly the same branching
factor for four an five moves. Did not went to see his time for 6 moves. If he
will mimic my branching factor for 5 and 6, then it will be too long for me to
wait.

>My program shows a branching factor significantly larger than usual, but
>not "worst possible".  Here is the timing info for increasing depths:
>
>depth  seconds speed   hash in    hash out
>#  1      0.00  0.87          1-         0
>#  2      0.01  1.00          1-         0
>#  3      0.03  0.97         83-         0
>#  4      0.26  1.06        907-         0
>#  5      2.59  1.30      13215-         0
>#  6     31.77  1.58     184695-         0
>#  7    559.19  1.81    3425552-      2347
>
>559.19 / 31.77 = 17.60  which is much smaller than 79 (initial legal moves).
>
>Here is statistics over remaining depth:
>
>                 moves              quotient
>depth     attacker   defender     att     def
>mvx  7:         79        192  [ 79.000  2.430]    mvskip     lvskip
>mvx  6:       1167       1863  [  6.078  1.596]          5
>mvx  5:      22875      25690  [ 12.279  1.123]        679
>mvx  4:     299329     334138  [ 11.652  1.116]       7313          4
>mvx  3:    3752287    3769416  [ 11.230  1.005]
>mvx  2:   22524391    7352320  [  5.976  0.326]
>mvx  1:    2394158          0  [  0.326       ]
>
>The "refutation table" shows which defender moves were chosen top level.
>Selecting the "right" defender moves is important for small search trees:
>
>refu  1: e8=Q+   Bf7     [  6-]
>solu          4: Nf7     [  5+]
>solu          5: Kh4     [  1+]
>refu  2: e8=B+   Bf7     [  6-]
>solu          6: Nf7     [  5+]
>solu          7: Kh4     [  1+]
>refu  3: Rh6+    Qxh6    [  6-]
>refu  4: Qh1+    gxh1=Q  [  6-]
>refu  5: Qh2+    Nxh2    [  6-]
>refu  6: g8=Q    Bd2+    [  6-]
>refu  7: g8=N    Bd2+    [  6-]
>refu  8: g8=R    Bd2+    [  6-]
>refu  9: g8=B    Bd2+    [  6-]
>refu 10: e8=N    Bd2+    [  6-]
>refu 11: e8=R    Bd2+    [  6-]
>refu 12: b3      Bd2+    [  6-]
>refu 13: Nd3     Bd2+    [  6-]
>refu 14: Nfd1    Bd2+    [  6-]
>refu 15: Ne4     Bd2+    [  6-]
>refu 16: Nfg4    Bd2+    [  6-]
>refu 17: Nh3     Bd2+    [  6-]
>refu 18: Nh1     Bd2+    [  6-]
>refu 19: Nc4     Bd2+    [  6-]
>refu 20: Nxd5    Bd2+    [  6-]
>refu 21: Ned1    Bd2+    [  6-]
>refu 22: Nxf5    Bxf2    [  6-]
>solu          9: Bd2+    [  6+]
>solu         10: Nxg1    [  3+]
>solu         11: Nd2     [  2+]
>solu         12: Nd4     [  2+]
>solu         13: Ne5     [  2+]
>solu         14: Qxf5    [  5+]
>solu         15: Ra6     [  3+]
>solu         16: Qxg7    [  3+]
>solu         17: cxb4    [  5+]
>solu         18: Rxb4    [  5+]
>solu         19: Bxb4    [  5+]
>solu         20: Rxc6    [  6+]
>solu         21: Bxc6    [  6+]
>refu 23: Nf1     Bd2+    [  6-]
>refu 24: Neg4    Bd2+    [  6-]
>refu 25: Nxg2    Bd2+    [  6-]
>refu 26: Bxg5    Rxb4    [  6-]
>solu         22: Bd2+    [  6+]
>solu         23: Nxg1    [  1+]
>solu         24: Ne5     [  1+]
>solu         25: Nd2     [  1+]
>solu         26: Nd4     [  3+]
>solu         27: Qxg7    [  1+]
>solu         28: Ra6     [  1+]
>solu         29: cxb4    [  6+]
>refu 27: Bg3     Bd2+    [  6-]
>refu 28: Bh2     Bd2+    [  6-]
>refu 29: Be5     Bd2+    [  6-]
>refu 30: Bd6     Bd2+    [  6-]
>refu 31: Bc7     Bd2+    [  6-]
>refu 32: Bb8     Bd2+    [  6-]
>refu 33: Bd3     Bd2+    [  6-]
>refu 34: Be4     Bd2+    [  6-]
>refu 35: Bxf5    Rxc6    [  6-]
>solu         30: Bd2+    [  6+]
>solu         31: Nxg1    [  4+]
>solu         32: Nd4     [  2+]
>solu         33: Nd2     [  2+]
>solu         34: Ne5     [  2+]
>solu         35: Rxb4    [  2+]
>solu         36: Qxf5    [  5+]
>solu         37: Qxg7    [  2+]
>solu         38: Ra6     [  2+]
>solu         39: cxb4    [  2+]
>solu         40: Bxb4    [  2+]
>refu 36: Bb1     Bd2+    [  6-]
>refu 37: Bd1     Bd2+    [  6-]
>refu 38: Bb3     Bd2+    [  6-]
>refu 39: Ba4     Bd2+    [  6-]
>refu 40: Rd6     Bd2+    [  6-]
>refu 41: Re6     Bd2+    [  6-]
>refu 42: Rf6     Bd2+    [  6-]
>refu 43: Rg6     Bd2+    [  6-]
>refu 44: Rxb6    Bd2+    [  6-]
>refu 45: Rc7     Bd2+    [  6-]
>refu 46: Rcc8    Bd2+    [  6-]
>refu 47: Rxc5    Bd2+    [  6-]
>refu 48: Rb8     Bd2+    [  6-]
>refu 49: Rac8    Bd2+    [  6-]
>refu 50: Rd8     Bd2+    [  6-]
>refu 51: Re8     Bd2+    [  6-]
>refu 52: Rf8     Bd2+    [  6-]
>refu 53: Rg8     Bd2+    [  6-]
>refu 54: Rh8     Bd2+    [  5-]
>solu         41: Bd2+    [  6+]
>solu         42: Nxg1    [  5+]
>solu         43: Nd2     [  2+]
>solu         44: Nd4     [  2+]
>solu         45: Ne5     [  2+]
>solu         46: Ra6     [  4+]
>solu         47: cxb4    [  4+]
>solu         48: Rxb4    [  2+]
>solu         49: Bxb4    [  4+]
>solu         50: Rxc6    [  6+]
>solu         51: Bxc6    [  6+]
>solu         52: Qxh8    [  2+]
>solu         53: Rxf4    [  4+]
>solu         54: Bxf2    [  5+]
>solu         55: c4      [  4+]
>solu         56: Ba2     [  4+]
>solu         57: Rb7     [  2+]
>solu         58: Bb3     [  4+]
>solu         59: Be4     [  5+]
>solu         60: Nf7     [  2+]
>solu         61: Nh4     [  5+]
>solu         62: Bf7     [  4+]
>solu         63: Rf7     [  2+]
>solu         64: Kh4     [  2+]
>solu         65: Rb8     [  2+]
>solu         66: Rb5     [  2+]
>solu         67: Ne6     [  2+]
>solu         68: Ne4     [  1+]
>solu         69: Nh3     [  1+]
>solu         70: Nh2     [  2+]
>solu         71: Bc3     [  4+]
>solu         72: Be6     [  5+]
>solu         73: Bg8     [  5+]
>solu         74: Bc4     [  4+]
>solu         75: Re5     [  2+]
>solu         76: Rf6     [  5+]
>solu         77: Rf8     [  2+]
>solu         78: Qh6     [  1+]
>refu 55: Ra7     Bd2+    [  6-]
>refu 56: Ra6     Bd2+    [  6-]
>refu 57: Ra5     Bd2+    [  6-]
>refu 58: Ra4     Bd2+    [  6-]
>refu 59: Ra3     Bd2+    [  6-]
>refu 60: Ra2     Bd2+    [  6-]
>refu 61: Ra1     Bd2+    [  6-]
>refu 62: Qf1     Bd2+    [  6-]
>refu 63: Qgxe1   g1=Q    [  6-]
>refu 64: Qxg2    Bd2+    [  5-]
>solu         79: Bd2+    [  6+]
>solu         80: Ng1     [  1+]
>solu         81: Nd2     [  1+]
>solu         82: Nd4     [  1+]
>solu         83: Ne5     [  2+]
>solu         84: Qxg7    [  1+]
>solu         85: Ra6     [  1+]
>solu         86: cxb4    [  1+]
>solu         87: Rxb4    [  1+]
>solu         88: Bxb4    [  1+]
>solu         89: Rxc6    [  6+]
>solu         90: Bxc6    [  6+]
>solu         91: Rxf4    [  2+]
>solu         92: Bxf2    [  1+]
>solu         93: c4      [  1+]
>solu         94: Rb7     [  1+]
>solu         95: Bb3     [  1+]
>solu         96: Ba2     [  1+]
>solu         97: Be4     [  1+]
>solu         98: Nf7     [  1+]
>solu         99: Nh4     [  1+]
>solu        100: Bf7     [  1+]
>solu        101: Rf7     [  1+]
>solu        102: Kh4     [  1+]
>solu        103: Rb8     [  1+]
>solu        104: Rb5     [  1+]
>solu        105: Ne6     [  1+]
>solu        106: Ne4     [  1+]
>solu        107: Nh3     [  1+]
>solu        108: Nh2     [  2+]
>solu        109: Bc3     [  1+]
>solu        110: Be6     [  5+]
>solu        111: Bg8     [  1+]
>solu        112: Bc4     [  1+]
>solu        113: Re5     [  1+]
>solu        114: Rf6     [  4+]
>solu        115: Rf8     [  1+]
>solu        116: Qh6     [  1+]
>solu        117: Qg6     [  3+]
>solu        118: Qh8     [  1+]
>solu        119: Qg8     [  1+]
>refu 65: Qc4     Bd2+    [  6-]
>refu 66: Qd4     Bd2+    [  6-]
>refu 67: Qe4     Bd2+    [  6-]
>refu 68: Qa4     Bd2+    [  6-]
>refu 69: Qb5     Bd2+    [  6-]
>refu 70: Qxb6    Bd2+    [  6-]
>refu 71: Qb3     Bd2+    [  6-]
>refu 72: Qxc5    Bd2+    [  6-]
>refu 73: Qa3     Bd2+    [  6-]
>refu 74: Qc3     Nxg1    [  6-]
>refu 75: Qd2     Bxd2+   [  6-]
>refu 76: Qbxe1   Rxc6    [  6-]
>solu          1: Nd4     [  2+]
>solu          2: Nd2     [  2+]
>solu          3: Nxe1    [  2+]
>solu        120: Nxg1    [  6+]
>solu        121: Ne5     [  2+]
>solu        122: Qxg7    [  6+]
>solu        123: Ra6     [  6+]
>refu 77: Qa5     Bd2+    [  6-]
>refu 78: Kd1     Bb3     [  6-]
>solu          8: Ne4     [  5+]
>refu 79: Kb1     Nd2+    [  6-]
>
>Have a nice day!

The same for you, Heiner!

Leonid.

>Heiner

```