Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Very easy mate to solve.

Author: Heiner Marxen

Date: 13:09:18 12/23/01

Go up one level in this thread


On December 23, 2001 at 13:57:01, Uri Blass wrote:

>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

Yes, exactly.  That is the natural consequence.

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

Yes, maybe.  But then, maybe not.  This is not really easy.

First, in many cases the simple aggressive strategy is sufficient, and
-as far as I know- in fact the best: it produces the smaller trees.
The reason is, that in nearly all searched lines white (the attacker)
has done a bunch of absurdly bad moves, and cannot win anymore.
A search is needed to proove it, but no sophisticated method is needed.

Second, _when_ we suspect that a more sophisticated approach should be used,
we are not quite sure, how much computation effort it is worth.
To estimate this we would need a good prediction for the size and success
of the simple aggressive search, as well as for the intended more
sophisticated one.  That is by far non-trivial.

I would very much like to have a more sophisticated method for large depthes,
but so far I failed to formulate something convincing (besides some
vague ideas).

>Uri



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