Welcome! Log In Create A New Profile

Advanced

Mock Exam Q4

Posted by ian.coetzer 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Mock Exam Q4
November 10, 2008 09:44PM
Hello, please take a look at my proposed answer to the alpha-beta pruning, would you give me the full 12 marks? if not please comment people!
Thanks smiling smiley



http://ian-coetzer.blogspot.com/2008/11/cos351-d-mock-exam-question-4-proposed.html
avatar Re: Mock Exam Q4
November 10, 2008 10:27PM
You would not get the full 12 marks, because you didn't show the order in which the nodes where visited. But you should get close to 12. smile

besides the obvious smile I have some comments / questions.
1. At node E, after the visit to node J, should the alpha / beta values not be [2;1] ?
2. Is K, and L not Beta pruned?
3. At node C, after the visit to node F, should the alpha / beta values not be [-inf; -3]?
4. Is G not Alpha pruned?

BTW: Max should choose action a1 and, the order in which the nodes are visited are: A, B, D, H, I, E, J, K, L, C, F, M, N (or do we show nodes visted "up" as well?)
Re: Mock Exam Q4
November 10, 2008 10:36PM
How does one determine whether it is an alhpa or beta cutoff?
Re: Mock Exam Q4
November 10, 2008 10:47PM
I thought that as soon as a value is visited and it causes a cut-off
that one should not replaced the alpha or beta values of the parent node since it ends there? is this assumption incorrect?

thanks
Re: Mock Exam Q4
November 10, 2008 10:49PM
If my last assumption is incorrect,
then should node F's alpha/beta values not rather be [1, -3]
since looking closely alpha is already one, and the child node of -3 is an max node so it would set the beta value of the parent node.
avatar Re: Mock Exam Q4
November 11, 2008 09:44AM
Ian,
Sorry, I did the trace again and your alpha / beta values are correct.
E is [-inf; 1]
C is [1; +inf]
You should not replace the alpha / beta values at the parent after cut off.

I'll check again when it's a alpha / beta cut off.
avatar Re: Mock Exam Q4
November 11, 2008 10:01AM
A good rule of thumb for alpha / beta cut off is; if it's below a MAX node it's a alpha cut off, and below MIN its beta cut off.
Re: Mock Exam Q4
November 11, 2008 10:38AM
I dont think that is correct, take a look here, according to this I think it is the other way around:

opponent = min = alpha cutoff
your move= max = beta cutoff

avatar Re: Mock Exam Q4
November 11, 2008 03:10PM
hehe, and I have two other power point slides that show the other way around....
damn thats what I hate about distance learning. (BTW: I looked at this one too)

Anybody got some explanation when it's a alpha / beta cut off?
Re: Mock Exam Q4
November 11, 2008 09:46PM
K, here is what I think about the alpha beta cutoff.

After visiting H + I. you know the answer will definitly be 1. Therefor the alpha and beta values there should be (1,1)

After visiting J, E's alpha value is set to 2. Then there is no need to visit K or L so the beta value never gets determined. so that stays at infinity.

I am not sure if B should be (1,1) or (-infinity, 1). Maby someone could correct me there. Or if I made a mistake earlier, im sorry, but thats how I see it.

As for the how the nodes are visited. Shouldnt it be, H, I, D, J, E, B ect?
Re: Mock Exam Q4
November 11, 2008 09:52PM
K just to correct myself, I think the alpha, beta for B should be (1,1) and for A should end up on (1,1). Based on the exaple on page 168. And not on the example from our tutorial letter (they seem to have alot of mistakes)
Re: Mock Exam Q4
November 11, 2008 10:20PM
Hi Christiaan

I'm looking now at the example on page 168.
I don't understand how they can at state (d)

the max child node at level 3 should set the parent's beta value to 2, thus node C should have for [alpha, beta] -> [3, 2] and this results in a cutoff
because beta is now smaller than alpha, thus we prune the remaining two child nodes.

i don't see why the did not have [3, 2] on node c but instead they have it as [-inf, 2] why? how can this possibly even help to prune the child nodes when you have infinity on the alpha side??

thanks


have [3, inf] for [alpha, beta]
surely a min node set the alpha value of the parent?
avatar Re: Mock Exam Q4
November 11, 2008 10:38PM
The only why they could have [-inf; 2] at C is if they started with a new set of alpha / beta values, because the alpha / beta coming down from the parent is [3; +inf], so the value should be [3; 2] like you stated and this results in a cut off.

That’s the way I have it. (It’s not according to the prescribed, but through many other online sources)
avatar Re: Mock Exam Q4
November 11, 2008 11:14PM
Re: Mock Exam Q4
November 11, 2008 11:37PM
My appologies. Guess the textbook example was wrong. That clears it up completely for me. Thanks for the good example.
Re: Mock Exam Q4
November 11, 2008 11:41PM
Ag sry just another silly question. In that example. slide 18. Will the 7 not update the top nodes Alpha value to 7? Will it in the end then be (7, infinity)?
Re: Mock Exam Q4
November 12, 2008 12:07AM
Yip, according to me if the value from the child node is accepted it must update the correct parent node value alpha/beta
in this case since the child node is a min node it must update thee alpha value of the parent node and in doing so set it to 7!
Anonymous User
Re: Mock Exam Q4
November 12, 2008 01:57AM
So....when is something alpha or beta pruning...
when it is after a MAX or after a MIN?
avatar Re: Mock Exam Q4
November 12, 2008 07:30AM
no idea? some say after MIN alpha and others say after MIN beta...etc.
Re: Mock Exam Q4
November 12, 2008 09:42AM
I think I have the answer...looking at the slide show that ian posted and finding it on the web I believe that a beta cut occurs below the MAX node and the alpha cut below the MIN node.

Reason why i say this is coz looking at all the examples of a alpha-beta search I noticed that the root node is always the MAX node and thus in the slide show I assume that the meaning of "your move" means the MAX node and "your opponents move" means the MIN node.

Looking at it that way makes understanding the types of cuts simple. Hope that clears it. Cheers

[url=http://www.cis.upenn.edu/~matuszek/cit594-2003/Lectures/38-alpha-beta.ppt#271,17,Best game playing strategies]Alpha-beta cutt offs[/url]
avatar Re: Mock Exam Q4
November 12, 2008 09:58AM
hehe, but the slide show shows that a alpha cut occurs below the MAX node, and beta cut below the MIN node?

If at a MIN node and value <= alpha, stop looking because MAX node will ignore. (Alpha cut)
If at a MAX node and value >= beta, stop looking because MIN node will ignore.
(Beta cut)
avatar Re: Mock Exam Q4
November 12, 2008 10:04AM
I think it shows an alpha cut under the MIN node (MAX moves first)
Re: Mock Exam Q4
November 12, 2008 12:44PM
I think it's this way:

beta-cut: Max nodes; value is compared to beta to determine whether to prune
beta-cut: Min nodes; value is compared to alpha to determine whether to prune
Re: Mock Exam Q4
November 12, 2008 12:59PM
nobbie u repeated beta cut twiceconfused smiley
avatar Re: Mock Exam Q4
November 12, 2008 01:01PM
That way, we can be sure that at least one of them is right winking smiley
Re: Mock Exam Q4
November 12, 2008 01:22PM
lol lieze...anyway it seem like I am writing this thing alone. I havnt seen any1 with a thick green book around here...

Am tired now. what i dont will just have to be like that ma head is full. Chat to ya'll after the paper.
Sorry, only registered users may post in this forum.

Click here to login