Author: David Mitchell
Date: 00:26:40 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? > >Are we saying that alpha/beta is the same old thing we have all been using for >centuries, but just adapted for computers? > >Still confused. > >Bob D. > >Bob D. Bob, I don't think A/B rates up there any higher in sophistication than Archimedes' law of buoyancy, but it is wonderful to watch it do the same work as mini-max, but somehow do it with a lot less work, and time required. I couldn't say how long A/B has been around, but like other notable computer algorithims, they do the job of other algorithims, but a lot faster. Quicksort for sorting, or Binary searches, for example. The latter is just common sense, kids play games and use it to guess what another has chosen as a "secret" number, even. But to see the improvement it can mean to a search that used to be done sequentially through thousands or millions of records, is to have a new appreciation for it, altogether. Especially since most programs that do that kind of job, will be searching those records over and over again, for different data, and requestors. Just like a chess program will be searching the tree of possible positions, looking for the best move, over and over. There certainly isn't any "magic" about A/B, but it's results seem stunning if you've ever programmed up a simple game, even, using mini-max to find the best move. Yikes! It's worth it just take a simple (very simple), position on the board, and work thru A/B by hand, with paper and pencil, perhaps using one of the many on-line examples you can find on the net. It's not rocket science, but it does apply good common sense to a search space that can be very large and difficult to work with. dave
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.