Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Another Alpha-Beta algorithm question

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.