Author: Ratko V Tomic
Date: 05:41:44 10/15/99
Go up one level in this thread
>>I was talking in this thread about current state of the art alpha-beta >>searchers. The deeper they look the greater is the percentage of junk positions >>they weed through, and that is an exponential convergence toward 0 percent of >>useful positions examined. Yes of course, they see more useful positions too, >>just because they see so many more positions in absolute numbers, but the net >>efficiency in useful processing still drops exponentially toward zero with the >>depth. And this type of phenomenon, in any kind of evolving or competing system, >>can only mean one thing ahead: a dead end, an extinction. > >I'd appreciate seeing an instrumented program that demonstrates this behavior. >I think your assertion is false for today's state-of-art chess programs. >Caveat: I don't consider a position to be "junk" if looking at it helps to >establish that a predecessor position is not "junk". One approximate way to measure this would be to label each node (leaf or external) which scores, say, 0.5 pawns worse than the current PV score, a junk. Obviously that will undercount the junk nodes (since PV score may improve and lots of stuff which wasn't junk would be junk relative to the improved PV score). But if we are intertested only in showing the kind of increase in the percentage of junk nodes, as suggested earlier, this may be a good enough approximation. As to your caveat, within Alpha-Beta algorithm almost every calculation "helps" the algorithm in some way establish or narrow down the values of the parent nodes. That doesn't make them non-junk in absolute sense. Only relative to (or within the context of) a mindless crunching they may seem non-junk. But since in the experiment suggested above we would count the internal and the leaf nodes independently, the non-junk status of the parent sholdn't make its children non-junk (after all, the root is non-junk). But even without an empirical test, one can see why this would be so from considering how many reasonable (non-junk) continuations are typically in a position. Since, however good your alpha-beta cutoffs are, you will still look at practically all non-junk moves from a given parent, as well as a few junk ones, the effective branching factor will almost always be larger than the number of non-junk continuations, hence the percentage of non-junk drops as (NJ/B)^Depth, since NJ/B < 1, i.e. it goes to 0 as Depth increases. Roughly estimating, there are perhaps 3-4 non-junk moves in a typical middlegame position and the effective branching factor may be 6-8 in such position. So, with each extra ply of search depth the percentage of the non-junk would roughly drop to a half of its D-1 percentage.
This page took 0.01 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.