Author: Andrew Dados
Date: 11:08:44 05/15/99
Go up one level in this thread
On May 14, 1999 at 19:14:58, James Robertson wrote: >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. >> >>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? >> >>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. Doh.. what is the difference between 'alpha-beta' and 'exhaustive search' in the above? alpha-beta *itself* does not 'prune' anything before getting to q-search... Andrew- >> >>KarinsDad :) > >Alpha-beta produces EXACTLY the same move as mini-max (at least according to the >programmers of Ostrich; I read it in their book). > >James
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.