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