Author: Christophe Theron
Date: 11:57:51 02/20/00
Go up one level in this thread
On February 19, 2000 at 05:21:01, Bruce Moreland wrote:
>On February 18, 2000 at 19:17:08, Bruce Moreland wrote:
>
>>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.
>
>I meant to say "nickel" instead of penny here.
>
>>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
I like a lot your explanation, Bruce. Everytime I have to explain alphabeta to
somebody, it's a real pain.
I think next time I'll try to explain it your way. Thanks.
Christophe
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.