Author: Bruce Moreland
Date: 16:17:08 02/18/00
Go up one level in this thread
On February 18, 2000 at 12:09:35, Jeff Anderson wrote: >Hi, I am still trying to learn about the Alpha-Beta algorithm. I have one more >question. Thanks to all the people that helped me before: > >With the Alpha-Beta algorithm does the program generate the entire tree and then >score the remaining positions when there has been a cut-off, or when there is a >cut-off does it not generate unnecessary positions at all? It completely avoids some unnecessary crap. Here is a game for you. The rules are as follows. There are several bags, each of which contains some money. You can paw through all of the bags, and at the end you get to pick one bag. You'll get to keep the lowest-denomination coin or currency in the bag. Obviously you want the bag that has no low-denomination money. Even one penny will wreck the bag as far as you are concerned, since you'll end up getting that if you pick the bag, even if there is a fifty dollar gold piece in there. You look through the first bag. It contains a dollar, a fifty-cent piece, and a quarter. So you know that you'll score a quarter if you take this bag. You look at the first coin in the second bag. It's a nickel. Do you really need to look through the rest of the coins in that bag? You don't, because you know that the *most* you are going to get is a penny, wherease you know that you can get at least a quarter if you pick the first bag. So you discard this bag, and it's absolutely safe to do so. If there was a ten dollar bill in the bag you wouldn't get it, you'd get the nickel. If there was a penny in the bag, you would have gotten that, but you don't have to care, since getting a nickel is bad enough, if you can get a quarter some other way. So that bag sucks. You can look through the rest of the bags the same way. You look at coins until you find a quarter or something worth less, at which point you can discard the bag. You'll notice that if you have a quick way of selecting small coins first, you can save yourself a lot of time, whereas if you consistently pull the big stuff out first, you'll have to go through a lot of crap. Alpha beta works the same way, you can discard huge chunks of tree, but it works best if you have a good way of guessing the best move for your opponent. bruce
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.