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.02 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.