Author: Dan Newman
Date: 14:35:00 05/14/99
Go up one level in this thread
On May 14, 1999 at 15:09:35, KarinsDad wrote: >On May 14, 1999 at 14:25:05, J. Wesley Cleveland wrote: > >>On May 14, 1999 at 13:14:36, KarinsDad wrote: >> >>> >> >>You seem to misunderstand alpha-beta. Alpha-beta *always* finds the same "best" >>move as exhaustive search does at any depth. What it does not tell you is how >>much better the "best" move is. > >Alpha Beta finds the best move "under the same depth and constraints", but does >not find the best move. That is why chess programs are not perfect at this point >in development (since they are restricted from performing exhaustive searches). > Well, yes, chess programs aren't perfect because they can't perform exhaustive searches depthwise. But I think there must be a misunderstanding of some sort, perhaps in terminology? The alpha-beta algorithm effectively does the same search that pure minimax does. Pure minimax is exhausive (widthwise): every node above a certain depth is examined. Alpha-beta gets the same result but only examines approximately the square root of the number of nodes in the tree that's searched. This is an enormous win when the depths are large. In chess it reduces the branching factor from approx 36 to approx 5 or 6. When people speak of "full-width, exhustive, brute-force" search it's alpha-beta that they are generally speaking of since the result is (more or less) identical to that achieved by pure minimax. The pruning done by alpha-beta is of an entirely different nature than the lossy pruning done in the quiescence search or by the null move heuristic. >If after a quiescence alpha beta search, you determine that you have lost a >knight for a pawn, most programs do not search much beyond that to find the >forced checkmate 4 moves later and hence do not find the sacrifice. The GM, on >the other hand, may find this. > >What this effectively means is that the alpha beta routines "prune" out lines >which do not look promising, but in actuality are very promising. > That's true, but pure minimax won't see that these lines are promising either. And it won't see as deeply (in the same period of time) because it's uselessly examining huge numbers of nodes that can't affect the result. >For example, let's take the opening. 1. d4 d5 2. c4 c6 3. Nc3 > >Most alpha beta programs would prune out the move c4 at ply 3 since there >appears (via the evaluation routine) for there to be a lot of other moves at >that point which develop pieces and are stronger. This does not mean that a >program may not find this on a re-search or something, however, you have to get >to ply 11 or so to start to appreciate the advantages of c4 and you will never >get there with a standard alpha beta search. You'll never get there with simple minimax, but you will get there with alpha- beta at 120 Mnps in 8 seconds or so. > This is the MAIN reason that >programs without opening books are so weak. The GMs have spent years analyzing >to some depth various openings and have found moves such as 2. c4 which are >strong, but a program would not find these moves in any reasonable amount of >time since it prunes via alpha beta. > >So, in the example of exhaustive 6 ply search, there are many lines dropped via >alpha beta at ply 1, 2, 3, 4, and 5 so that the evaluation routine does not even >get to compare those nodes at ply 6. If a line is dropped at ply 4, how can you >evaluate it's grandchildren at ply 6 or ply 9 or ply 12 and find that it is in >fact actually stronger, not weaker? > In alpha-beta you search from that node down to ply 6 and then evaluate, you don't simply evaluate at that node and drop it if its score is too low. In fact the nodes you drop are those that are too high...so high that your opponent will choose some other path to avoid that node and thence the disaster that likely lies ahead. So, you may as well not even finish searching it because you've proven your opponent won't allow you to get there. This is done recusively throughout the tree, and in this way lots of useless work is avoided. -Dan. >Do you still think that I do not understand Alpha Beta? Min Max and Alpha Beta >are the reasons that other techniques such as null move and razoring, etc. have >been developed. If we were doing exhaustive search to ply 14 and alpha beta >search to ply 20 after that, no human in the world could beat the program and >these other techniques would not be needed. > >KarinsDad :)
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.