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.