Author: Ratko V Tomic
Date: 12:01:45 10/26/99
Go up one level in this thread
> 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.
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.