Author: Ed Schröder
Date: 15:39:27 06/18/00
Go up one level in this thread
On June 18, 2000 at 12:35:31, Gian-Carlo Pascutto wrote: >On June 18, 2000 at 12:00:08, Ed Schröder wrote: > >>On June 18, 2000 at 10:36:40, Gian-Carlo Pascutto wrote: >>> >>>I find it interesting to notice that even Rebel has some trouble with this, >>>taking more than 10 times as much time to resolve the 10th ply. >> >>That's pretty normal whith such big score differences (2.47 -> 11.74) as >>search is confrontated with big score fluctuations which causes move >>ordering to collapse. I wouldn't bother too much about it, it's quite >>normal. > >It may be 'normal' for most chessprograms, that doesn't make it good. >I'm specifically trying to get the search/time relation more stable >in positions with lots of threats/extensions. I'd prefer the score to >gradually increase over several plys than to have it search for 30 minutes >and come up with the mate score. Some programs are very good at this, some >totally botch it. > >I suspect Memory Enhanced testers (e.g. MTD(n,f)) are very good at this, >but I heard they can give weird results due to extensions sometimes, and >that's exactly the problem I'm fighting here ;) >A little test with AnMon showed that indeed the fail-high is very gradual >and constant over time, but it still has the blow-up effect when moving >over to the next ply, and pretty badly even. (I suppose that is because >of the moveordering failing) > >I'm trying to get an idea how to control this effect in an aspiration/PVS >searcher. That's why I'm asking for as much data as possible, and the details >of the search that are used. > >This is one of the best I've got so far: > >Analysis by Little Goliath 2000 v2.8: (edited) > >19.Rg1 Nf6 20.Kb1 b6 21.Rgh1 h5 22.f4 > µ (-1.00) depth: 8 00:00:02 414kN >19.Rxh5 > µ (-0.89) depth: 8 00:00:03 414kN >19.Rxh5 gxh5 20.Rxh5 Kf8 21.Rxh7 Ke8 22.Qf5 Kd8 23.Qxf7 Kc7 24.Qxe7+ Kc8 > ± (1.33) depth: 9 00:00:04 2184kN >19.Rxh5 gxh5 20.Rxh5 Kf8 21.Rxh7 Ke8 22.Qf5 Kd8 23.Qxf7 Kc7 24.Qxe7+ Kc8 25.Rh8# > +- (2.43) depth: 9 00:00:07 2184kN > >Times 5, quite acceptable. > >19.Rxh5 Qxa2 20.Rxh7 Qa1+ 21.Kc2 Qxh1 22.Rxh1 f5 23.e4 Re8 24.exf5 g5 25.Rg1 > +- (9.80) depth: 10 00:00:36 3654kN >19.Rxh5 Qxa2 20.Rxh7 Qa1+ 21.Kc2 Qxh1 22.Rxh1 f5 23.e4 Re8 24.exf5 g5 25.Rg1 > +- (9.80) depth: 11 00:00:37 19616kN > >For some reason it now fails low again ?!? > >19.Rxh5 Kf8 20.Rxh7 Ke8 21.Qe4 Kd7 22.Rxf7 Re8 23.Rg1 Qxa2 24.Rxg6 > +- (5.40) depth: 11 00:00:50 19616kN >19.Rxh5 Kf8 20.Rxh7 Ke8 21.Qe4 Kd7 22.Rxf7 Re8 23.Rg1 Qxa2 24.Rxg6 > +- (5.40) depth: 12 00:00:55 30184kN > >Times 6, again not bad. > >19.Rxh5 Kf8 20.Rxh7 Ke8 21.Qe4 Kd7 22.Rxf7 > +- (#9) depth: 12 00:06:02 30184kN > >But now we get a fail-low again... > >19.Rxh5 > +- (#109) depth: 12 00:06:10 30184kN >19.Rxh5 Kf8 20.Rxh7 Ke8 21.Qe4 Kd7 22.Rxf7 > +- (#9) depth: 12 00:06:10 30184kN > >This is the worst: > >Analysis by Amy 0.7: > >19.Rxh5 > = (0.00) depth: 8 00:00:01 83kN >19.Rxh5 gxh5 20.Rxh5 Kf8 21.Rxh7 e6 22.dxe6 fxe6 > µ (-0.91) depth: 8 00:00:01 83kN >19.Rxh5 gxh5 20.Rxh5 Kf8 21.Rxh7 e6 22.dxe6 fxe6 23.Kb1 > µ (-0.78) depth: 9 00:00:02 143kN >19.Rxh5 > = (0.00) depth: 10 00:00:03 246kN >19.Rxh5 gxh5 20.Rxh5 Kf8 21.Rxh7 Ke8 22.Qf5 Kd8 23.Qxf7 Qxc4 24.Qxe7+ Kc8 > ³ (-0.27) depth: 10 00:00:03 246kN >19.Rxh5 > = (0.00) depth: 11 00:00:05 473kN >19.Rxh5 gxh5 20.Rxh5 Kf8 21.Rxh7 Ke8 22.Qf5 Kd8 23.Qxf7 Kc8 24.Qf8+ Kc7 > ² (0.44) depth: 11 00:00:06 473kN >19.Rxh5 > = (0.00) depth: 12 00:00:13 1089kN > >Times 25 ! This is nearly minimax. > >19.Rxh5 gxh5 20.Rg1+ Kf8 21.Bg7+ Ke8 22.Bh6 > +- (2.20) depth: 12 00:05:08 1089kN >19.Rxh5 > = (0.00) depth: 13 00:06:01 >19.Rxh5 gxh5 20.Rxh5 Kf8 21.Rxh7 e6 22.dxe6 Qxa2 23.Qxd6+ Kg8 24.Rxf7 Qa1+ >25.Kd2 Rd8 > +- (1.95) depth: 13 00:06:12 >19.Rxh5 > = (0.00) depth: 14 00:08:48 > >After 14 plys there still is no sign of a decent score. > >Actually I think there may be a bug in Amy: notice it is >failing low to exactly zero each time. The search results >look very strange. > >-- >GCP Most of nowadays so called top programs have a branch factor of 2-2.5 which is very good and almost close to perfect. But the exceptions of a search that collapse will always remain so now and then. These cases usually happen with a fail-high and in a lesser extend to a fail-low. And the deeper you are in iteration depth the more worse a search can collapse because of a constantly failing move ordering. Infamous examples are these blocked pawn-endings where programs may hit 30 plies or deeper within a few seconds. If you then get a fail-high on iteration 40 (or so) it in extreme cases can take hours to resolve the fail-high. But if your program takes one hour to resolve a (low) 7 ply research than something is wrong with your search. Something wrong can mean anything from insufficient move ordering, something is wrong with the HT, maybe even a bug, perhaps you are doing to much extensions and so on. Ed
This page took 0 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.