Author: Robert Hyatt
Date: 20:09:23 10/16/99
Go up one level in this thread
On October 16, 1999 at 13:41:17, Ratko V Tomic wrote: >>the issue is 'null-move' that selectively reduces the depth on non-critical >>branches, which reduces the effective branching factor. > >The Sqrt(Width) lower boundary for optimal minimaxing still remains. Anything >with smaller B is an approximate minimaxing, i.e. not guaranteed to return the >same value as the plain alpha-beta would (which always returns the rigorous >minimax value). Hopefully the approximate minimaxing has the error of roughly >the same magnitude as the error due to the uncertainty of the evaluation >function, otherwise the algorithm is performing sub-optimally given the >computing resources and time limits. I suppose one could tune the two sources of >errors by using deeper search as a substitute for exact node value (e.g. to >estimate the error distributions on the samples of regular searches). > I wasn't disagreeing at all. There are two ways to speed things up. (1) change the _real_ branching factor. All of us did this in the 60's/70's. It was called 'forward pruning'. And it is very dangerous. (2) change the effective branching factor by reducing the overall depth on uninteresting branches. Null move, razoring, etc do this. So no, any program with a branching factor < 6 is _not_ a pure minimax/alpha-beta searcher. it would be impossible... >> if you try several different positions, you ought to see numbers way >> below 4.5 on average... Note that tactical tests are the wrong kind >> of positions... because they, by definition, are not searched optimally... > >It may be that what Fritz UI displays as "Nodes=" for Crafty 16.6 engine means >different than what full Crafty program displays. In the message to Jeremiah I >left the position I used, which had Width=38 (and fairly stable), so we can see >whether he gets B=4.5..4.7 at fixed depths 10-12 or B closer to 3. > > >>there are still massive problems. IE lazy evaluation. And when searching >>moves from position "X", the first might produce a score of -.1 which is enough >>to cause a cutoff. But if you searched further, the second might produce a >>score of -2, which is even more than enough to cause a cutoff. But alpha/beta >>doesn't search the second... >> > >I think your objection is from the viewpoint of trying to find out the >objective/actual amount of "junk" in a tree. In that case, yes, even the plain >aplha-beta won't work. But I was talking about the _evaluated_ amount of "junk" >(vs the evaluated amount of non-junk), as occuring in the state of the art >alpha-beta searchers. The point of that was to establish whether the current >state of the art programs have the _evaluated_ proportion of non-junk going >exponentially to zero with increasing depth. I think they do, meaning that the >their efficiency goes to zero, with depth, as well. > In that case, the percentage of junk is very high for normal positions where the program doesn't change it's mind frequently while searching... > >>I wouldn't disagree. minimax has a huge number of 'junk' positions by any >>definition. However, the search can't be executed without them. > >Well, if you look at human player using computer for in depth analysis of a >position, such as for postal game, you will see that the best result is not >obtained by letting the program think on its own for 24 hours. Instead human >player will guide moves over plausible alternatives and have it do much shorter, >mini searches, along the way, going much deeper than program would do by itself. >(I think there were some results by Althoffer [sp??] showing that "hybrid" >player (human guiding/advising computer) is significantly stronger than either >that human or the program.) That merely shows that there is, at least in >principle, a more effective way to search. > I'll bet this is changing. Because a program (crafty) can easily hit 15-16 plies overnight... and find some really deep tactics. When you 'guide' you can also 'overlook'. A fine line to walk... I think comps will get better and better at long time controls over the years. >A multilayered control, with alpha-beta search employed as the lower layer and >guided by a more intelligent and flexible type of algorithms into the mini >searches (a la "hybrid player") satisfying certain higher level imposed >constraints (i.e. looking for some objective, thus gaining an extra cutoff >source, in addition to the mini-tree vs full tree gains), will eventually be >created and drive extinct the current alpha-beta searchers (with their ad hoc >shortcuts). > >The main underlying reason why these kinds of programs will be superior is that >they will be able to harness coherently the tiny evaluation fluctuations, which >in the current programs appear as evaluation noise (be it from ply to ply among >iterations or among the top alternatives within the same iteration), and pick >them in such a way (by comparing their suitability for some longer term >objectives, i.e. comparing their fit to plans) that over a longer span of moves >they can coherently add up to some longer term advantage. With the current >alpha-beta searchers, these fluctuations add up randomly/incoherently from move >to move, i.e. one move may make it look as if the program has one longer term >objective (well beyond search horizon), the next move may undo that small step >and appear to go for a different long term objective. Like a Brownian particle, >these steps, by undoing incoherently each other, will advance it forward by >sqrt(NumSteps) in the fluctuation space, while a coherent strategy will advance >it lineraly with NumSteps. > >Even though you ridicule Botvinnik's work, his scheme is actually one highly >refined form (as only a person of his level of chess understanding could create) >of the next higher layer which should guide the brute force search in much more >coherent and efficient (instead of efficiency exponentially going to 0) way. >Whether he/his cooworker(s), with their severe (Soviet era) resource >limitations, actually had a program do all the simulations or they did some by >hand (without telling always straight which is which), that's ultimately >irrelevant, whatever Hans Berliner says (he has been known as given to grand >exaggerations himself, so it's a case of pot calling cettle black). Even Newton >(and other great scientists, e.g. Dalton) have tweaked or invented the >experimental data to make them appear fitting better their grand theory which >they believed (rightly) to be a major advance. I didn't really ridicule his work. Berliner pointed out that most of it was outright fabrication. Most of us agreed with his conclusions, although we didn't like the way he publicized them. But it was all totally bogus. And while it looked reasonable in theory, in practice, zilcho...
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.