Author: Dave Gomboc
Date: 19:59:10 10/26/99
Go up one level in this thread
On October 26, 1999 at 15:01:45, Ratko V Tomic wrote: >> Some people do multiple searches on the same nodes with different >> evaluation weights in specific circumstances. It's impractical to >> do this everywhere, because it is quite costly. (A wag might >> refer to it as searching junk 5 times instead of once! ;-) > >With Botvinik's multilevel system, only the low level alpha-beta search is >initiated multiple times from the same high level node (belonging to the sparse, >human-like search tree of unrestricted depth). Unlike the search with different >evaluation functions, here the search is highly constrained, looking for >specific narrow objective (e.g. can sufficient [for capture] pressure be brought >on this weak pawn within the next N moves), thus the evaluation is exact and the >cutoffs due to failure to meet the given narrow objective are very efficient. >One can see this type of efficiency in mate finders, which can find mate in N >moves tipically many times faster than a general search algorithm of a playing >program (which looks for many other things, not just a mate). The actual >objective (or sub-goal) and its parameters (parts of a plan) are set-up by the >higher level reasoning module which contains chess knowledge and also uses >search results to come-up with new/suboordinate objectives. > >When you merely add all positional evaluation components into a single number, >you're not moving (in the search space) along a directed line (plan) toward a >goal but rather performing a much less efficient random-walk-like motion in a >multidimensional space, where each evaluation parameter drives the search in its >own direction, often cancelling out with other effects in an almost random >fashion, fluctuating from iteration to iteration, and from actual move to the >next actual move. Of course if the evaluation function were exact (such as with >table-base), that wouldn't happen. But the actual evaluation functions (on a >truncated tree) gives only some type of average over an unknown distribution, >which has an error margin (at least 0.1-0.2 pawns). So the conventional >alpha-beta searcher has a random fluctuation band and the final pick is >essentially a coin tossing between several candidate moves within that band. >(That's why an N-ply program can beat the N+1-ply otherwise identical program at >least 20% of the time, even though in each move the N+1-ply program always sees >"more" accurately; in fact it doesn't.) > >Thus the amorphous adding of unrelated and inexact positional contribution as >one lump figure (the "positional value") destroys the longer term coherence of >the play, i.e. a human player (or a Botvinik's type program) will consider >various plans separately. The positional aspects (evaluations) relevant for a >plan (under the current consideration) are not mingled (added) with those of >other possible plans (which will be looked at later). > >Even if the individual evaluation components are equally inexact in the two >approaches, the second approach doesn't add up errors of all the positional >compontents in the programs repertoire, but only of those few components which >are relevant for the plan being considered. If you have N random variables with >errors (dispersion) E1, E2,... EN, then the expected error (dispersion) of the >sum is sqrt(E1^2+E2^2+... + EN^2). In the simple case when all errors are equal >to each other (equal E) the first approach will yield error E*sqrt(N) while the >second approach which uses for each plan a very small subset of evaluation >parameters, say M parameters (where M<<N), the error will be E*sqrt(M), which is >always a much smaller error than for the first approach. (Of course, when the >planning program compares the final value of any two plans, its error grows to >sqrt(2)*EP, where EP is the "plan error" i.e. EP=E*sqrt(M), hence to gain in >this regard over the regular alpha-beta searcher the M must be smaller than N/2; >Botvinik's type planner would have typically M=1 or 2 i.e. it tries out via the >alpha-beta search only the very narrowly directed plans.) > >In a general way, one can characterize the nature of this gain as utilizing the >noise band of the conventional program's evaluation. Such small gains obtained >consistently over a longer sequence of moves can add up to enough value to >squeeze a point out of conventional program (or a player playing without a >longer term plans). > >One can reach the same conclusion by realizing that various positional >evaluation contribution are not a value by themselves, but rather they are >values if utilized in a specific way. For example creating double or weak pawn >in the opponent's pawn structure doesn't gain anything on its own, unless one >follows up with specific pressure on such pawns. Any evaluation factor has its >own purposes and types of followups to convert them into a material (or >generally, a permanent type) gain. By lumping all such factors into an amorphous >sum, the conventional program is ignoring the fact that the followups which are >needed to convert such potential for gains into the real gains cannot generally >be pursued simultaneously. From a human player's perspective, the program is on >every move changing plans based on spurious "gains" it sees in the noise band of >its evaluation function, and unless a lucky tactical strike comes its way (and >it is overlooked by its oponent), the program will lose to a player who >coherently adds small gains into a convertable value. A strong human player >judges not only the positional "gain" of a move, but does that in the context of >a concrete plan aimed at converting that potential "gain" into the permanent (or >real) gain. He doesn't maximize the sum of all potential gains but maximizes the >single most realizable gain. > > >> Alpha-beta is a full-fledged theorem prover. I think people don't give >> it enough credit. With a good evaluation function, it is extremely >> powerful. > >I think the catch here is "good evaluation function." If the evaluation function >is _perfect_, you wouldn't need search at all. If it is not perfect (as it is >whenever the search is needed), a program guiding the alpha-beta search toward >specific goals will see a smaller evaluation error than a full width alpha-beta >searcher using the lump sum type of evaluation function. Your post is an excellent example of what I mean when I say that alpha-beta is underrated. When I spoke of a "good evaluation function", I did not mean a highly accurate one. I meant one that isn't random, isn't constant, has a reasonable, if minimal, understanding of what is going on, i.e. it doesn't think that getting oneself checkmated is a good thing. I'm not asking for a "highly-tuned specimen" here. All of that multi-level stuff can be done in one function. One. You may find it easier to express with some layered approach, but it boils down to exactly the same thing. The program decides where it wants to go, based upon a strict weak ordering of likely outcomes. If you can write a Botwinnikesque evaluator, I can generate an equivalent that interacts only with an alpha-beta search. _Nothing_ need be lost in the translation. You can denigrate a "lump sum" evaluation function all you want, but in the end you have to make a choice between various positions. When you do this, you are "lump summing", whether your evaluation architecture has five levels of indirection or none. Whatever evaluator you have is selecting a preference between a countably infinite number (or less) of possibilities, which means the evaluation function is representable as a mapping from a position to an integer. Dave
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.