Author: Robert Hyatt
Date: 21:05:29 05/15/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). > >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. > >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. 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. this has already been mentioned in another sub-thread, but this is wrong. your statement implies forward pruning. Alpha/Beta would actually try the move c4, but _quickly_ refute it by only looking at the capture at the next ply. IE alpha/beta is a "backward-pruning" algorithm rather than "forward- pruning". In that you _always follow a sequence of moves to the max search depth and only _then_ make decisions about pruning as you back up the scores thru the tree. _not_ the other way around.. > >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? > Alpha/Beta doesn't work like that. It is a "depth-first" search. No move gets dropped at ply 4, unless that move is not needed to prove that the move at ply=3 was bad. >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 :) I don't follow your last paragraph. As I mentioned before, alpha/beta will _always_ produce the exact same score and move as a pure brute-force minimax search to the same depth. _exactly_... proven by Knuth/Moore 25 years ago.
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.