Author: Uri Blass
Date: 01:15:05 02/23/04
Go up one level in this thread
On February 22, 2004 at 17:23:06, Bob Durrett wrote: >On February 22, 2004 at 16:50:26, David Mitchell wrote: > >>On February 22, 2004 at 15:27:44, Bob Durrett wrote: >> >>>In http://www.talkchess.com/forums/1/message.html?350711, Christophe Theron >>>made the fascinating and thought-provoking observation that: >>> >>> >>>"Conceptually, an alpha-beta search is doing several thousands takebacks per >>>second." >>> >>> >>>I do not doubt that this is true. However, I've never heard the alpha/beta >>>described quite that way. >>> >>>Could somebody please relate this to the more conventional concept of >>>alpha/beta? >>> >>>Bob D. >> >>Very simple, really. Before any position is evaluated, the move that leads to >>that position is "made", on a data struct inside the program. The internal >>"board", if you will. >> >>But is that position the best? The program can't tell, without comparing it to >>thousands, perhaps many thousands, of other positions. Each position is >>preceeded by the "move" that leads to it. Which has to be "made" and then >>"unmade", and then the next one "made", and "unmade", etc.. >> >>The important thing to understand A/B, to me, is that _first_ you make the moves >>to a depth you choose, and only _then_ (in only from a quiet position), is the >>position evaluated thoroughly and scored. Then, A/B takes those scores and the >>moves that made them, and works back _up_ toward the root position. Best moves, >>and scores are _lifted_ up from the tips, back toward the root, (starting >>position), and scores for your opponent's moves are negated (so if they're good >>for your opponent, they're bad for you), and vice-versa. >> >>All involving many moves being "made" and "unmade", every second. >> >>It's quite an amazing algorithim, actually. It's no wonder virtually every chess >>program uses it so extensively. >> >>dave > >But alpha/beta was sold as a very sophisticated thing. Does it really just boil >down to a bunch of takebacks? Isn't there something more than that to >alpha/beta? alpha beta is a simple algorithm and I do not know who sold you it as a very sophisticated algorithm. The only difference between alphabeta and minimax is that minimax searches all the possibility when alpha beta does not search unnecessary moves suppose 20.Nd4 c5 wins a rook based on your evaluation. You start to analyze 20.Nd4 d5 21.Rh1 and find that this line is winning a queen. Minimax is going to search also 20.Nd4 d5 21.Rg1 but alphabeta is based on the observation that you already know that 20...d5 is illogical so you do not need to search it and it is better to search other moves. Suppose that later the score of Nd4 +5.00 for white and black has nothing better than 20...c5 Now you search 20.Na1 c5 and finds that you only wins a pawn. Normal minimax may continue to search 20.Na1 d5 but alphabeta decides based on searching 20.Na1 c5 that 20.Na1 is illogical. Uri
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.