Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Very easy mate to solve.

Author: Uri Blass

Date: 10:57:01 12/23/01

Go up one level in this thread


On December 23, 2001 at 11:51:53, Heiner Marxen wrote:

>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.

It means that checks first is not the best move order
at big depthes and special search rules for big depthes
or for cases when the branching factor is too high may help

Maybe in this case starting with moves that wins more material
is more productive.

Uri



This page took 0.05 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.