Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Very easy mate to solve.

Author: Heiner Marxen

Date: 08:51:53 12/23/01

Go up one level in this thread


On December 23, 2001 at 08:18:16, leonid wrote:

[snip]

>Probably our chess solving part is very close in response, even if your initial
>speed is much better. How we ever come to this closeness is a mystery for me.
>Few times I tryed to find some visible explanation for this but each time I
>could see later that my explanation was wrong. Fact is that our two solvers
>stays completely aside from main part of mate solvers in "heavy positions".

That is not so much of a mystery to me:  our two programs are the only
non-trivial, brute-force, full-width mate solvers I know of.  I.e. these two
programs share a certain approach/algorithm which others don't do.
[Alybadix may be an exception (I just don't know)]

Some dedicated mate solvers either are relatively trivial (not much special
handling in the last plies), or do not really do full-width (heuristic
forward pruning).  Both kinds are not quite comparable.

Playing programs are also different: they do not really do a fixed depth
search: they use e.g. extensions to find the mate faster.  Their search
tree has a much different shape than our tree.

> I
>remember one the most striking coincidence in one positions that I will write
>here.
>
>[D]8/qkqqb2p/4n2P/1NRRqNQK/1B2b3/1QQQnQQP/4p2Q/qnqrr2B w - -
>
>This position I wrote around two months ago and when I tried it I was almost
>sure that I have some bug in my code. I went later to your program and could see
>that our programs responded in almost identical way on it. Strange thing in it
>is terrible jump in branching factor between 7 and 8 move. My time was:
>
>Move         Time            Branching factor          NPS
>
>4            0.32 sec                                  41k
>                             6.1
>5            2.03 sec                                  73k
>                             7.1
>6            13.9 sec                                  73k
>                             16.5
>7            3 min 49 sec                              215k
>                             73.5
>8            4 hours 41 min 55 sec      mate found.
>
>Your program had identical gramatic jump in branching factor just on the same
>place.
>
>Cheers,
>Leonid.

I did the above for depth 7 and 8, and the statistics quite clearly show
an explanation for this effect.  My timing (K7/600, thus quite comparable):

#  1      0.00s                 0kN           0.87          1-         0
#  2      0.00s                 0kN           1.00          1-         0
#  3      0.01s                 0kN [  9.90]  0.93         79-         0
#  4      0.07s [  7.00]        2kN [  5.03]  1.03        458-         0
#  5      0.33s [  4.71]       14kN [  6.57]  1.21       2152-         0
#  6      2.15s [  6.52]      105kN [  7.61]  1.38      11906-         0
#  7     29.83s [ 13.87]     1757kN [ 16.78]  1.46     137095-         0
#  8   2492.29s [ 83.55]   160191kN [ 91.16]  1.62    9690993-   1511157

When computing depth=8 a significant amount of defender moves, which were
sufficient to defend for depth=7, now turn out to be not sufficient.
As a consequence more defender moves have to be searched.
That can make the search tree to "explode".

Below is a statistic about white and black move counts and branching factors
indexed by the depth still to go.  For total depth=7 and then for depth=8:

mvx  7:         72         72  [ 72.000  1.000]          6
mvx  6:        448        471  [  6.222  1.051]          6
mvx  5:       2357       2634  [  5.004  1.118]         34          1
mvx  4:      16459      17767  [  6.249  1.079]        255          2
mvx  3:     143965     143123  [  8.103  0.994]
mvx  2:    1068359     271386  [  7.465  0.254]
mvx  1:      90207          0  [  0.332       ]

mvx  8:         72        143  [ 72.000  1.986]          6
mvx  7:        486        882  [  3.399  1.815]          6
mvx  6:       4355       6885  [  4.938  1.581]         34
mvx  5:      55023      69456  [  7.992  1.262]       1540          5
mvx  4:     764360     859969  [ 11.005  1.125]      24250         47
mvx  3:   10269283   10390199  [ 11.941  1.012]
mvx  2:   98598864   27783303  [  9.490  0.282]
mvx  1:   11388173          0  [  0.410       ]

Note the much increased EBF for black on the high levels.  When larger than 1
it indicates defender failures, and here we have comparatively many.
Most often the defender EBF does not exceed 1.1, but here it does multiply.

The method used to achieve the really small EBF up to depth=6 or 7 turns
out to be not so good for the larger depth and fires back.
E.g. it may happen, that black looses all its critical defender pieces
due to aggressive checking moves, and bad capture trades.  That will work
if the depth does not exhaust the defender's material, but then, quite
suddenly, with just one move more depth, will fire back: the defenders
are gone, and white mates easily.

BTW, such an explosion on search tree size does happen with the playing
programs, too, for quite similar reasons.  And there is not much you can
do about it.  As long as the mate is not completely forced, a "better"
move ordering can help, but only so much: if the move ordering were much
better, we would not need the search any more :-))
And when there really is a forced mate... the proving tree for a mate in N+1
can be _much_ larger that the proving tree for not-a-mate in N.
What can we do about it?

At least that is how I do explain such effects to myself.

Cheers,
Heiner



This page took 0.09 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.