may/june 2011 paper

has anybody attempted the alpha beta question (Question 5)
well my answer is as follows:

the order in which the nodes are visited are: A, B, D, J, E, K, F, L, C, G, N, O, H, P

I got the values to be A = 3
B= 3
D = 3
E = 5
F = 6 ( A beta cutoff occurs at M because 6 > the beta value of B (3)
C = 2 (An alpha cutoff occurs at I because 2 < alpha value of A (3)
G = 8
H = 2

Question 1:
1.1
the slide representation can be a grid of numbers and the blank can be represented by a zero

1.2 i am not sure if the state in the diagram can be used as the initial state

1.3 I know its yes, but didnt know how to explain

1.4 up , down , left, right ... movement of the blank

Question 4:

4.1
i started with the expansion of node 1 to get
2[1 + 7 = 8] , 3[1+6=7], 4[1+6=7], 5[1+7=8]
which is basically g + h = f
g = 1 because depth 1
and h(n) i took to be the total number of spaces that are availble on the board.
i then went on to expand based on the largest value of f.

not sure if its correct...

for Question 7

My Entropy(s) = 0.954

Hair:
Entropy(Sblonde) = 1
Entropy(Sbrown) = 0
Entropy(Sred) = 0

Gain(S,Hair) = 0.454

My effort - only starting now

Question 1
1.1. A set where the position of a value corresponds with its position on the puzzle, numbering from top left being 1, 2 is top middle, all the way down to 9 being bottom right. The value is number assigned to that position with 0 being the empty space. Every number from 0 to 8 may only occur once in the set.
1.1.1.The example would thus be {1,5,8,6,2,0,3,4,7}
1.2. Represented:
1.2.a. In the example it is {1,5,8,6,2,0,3,4,7}, but for every position it can be any random number from 0 to 8, not using a number more than once.
1.2.b. {1,2,3,4,5,6,7,8,0}
1.3. No – Only half of the states are reachable from any given state???. (I don’t know why – that’s what the book says on p71. I'm thinking that the goal state may potentially be an unreachable state?).
1.4. Moving the blank space would be the easiest: Up, Down, Left, Right.

@Tazz - what do you think about Q1.3? I hope we do not have to know the details of the examples.

Q4:

Order = 1,2,6,7,12,3,8,13,16

OPEN QUEUE:
1[0+16=16]
2[1+6=7],3[1+6=7],4[1+6=7],5[1+6=7]
6[2+1=3],7[2+2=4],3[1+6=7],4[1+6=7],5[1+6=7]
7[2+2=4],3[1+6=7],4[1+6=7],5[1+6=7]
12[3+0=3],3[1+6=7],4[1+6=7],5[1+6=7]
3[1+6=7],4[1+6=7],5[1+6=7]
8[2+3=5],4[1+6=7],5[1+6=7]
13[3+1=4],4[1+6=7],5[1+6=7]
16[4+0=4],4[1+6=7],5[1+6=7]
4[1+6=7],5[1+6=7]

@Tazz
The question states "the order in which the nodes are expanded (not generated)". Maybe this should then exclude J,K,L,N,O and P?

@ Marius I'm really not sure about question 1.3 but considering its only 3 marks I don't think the details are important.
@Hexium, I didn't read the question properly and you are right. I must make a note of that, it could catch me out in the exams.
I'm not sure if I'm ready for this paper, how much study material can you go over to reach a state of readiness.

@Marius & Tazz, have a look at this page: http://kevingong.com/Math/SixteenPuzzle.html , regarding 1.3

@hexium - Thanks will have a look
@Tazz - Agreed. I was more concerned that they expect us to know the details of the examples in the book. I have not seen any other question that require the same type of knowledge, so feel a bit better now.

@hexium - The site explain it nicely. Thanks. Pity that they ask it in the exam, but don't explain it so nicely in the book.

Thanks Hexium. I also found some notes in the 2009 forum under the headinf textbook summary. There's a link there that has some textbook notes. You might wanna have a look. Sorry for not pasting the link, I'm accessing the forum with my cellphone and features are limited.

Sometimes people post the coolest links. In Sem 1 this year, somebody posted some links to software that you can use to do problem solving with.. Pitty I only saw it now!

@Hexium about your previous comment about excluding nodes J, K. Etc. I'm looking at the exam tut letter and in their model solution, they have included it. Unless ofcourse there's a difference between expanded and visited. I hate the fact that they using small little words to catch us. I mean the knowledge of the meaning of words doesn't test whether or not you are effiecient in AI. I don't know, but I think to be safe we better just include it.

The marks would suggest that we should not write down the visited nodes. If we only show the expanded nodes, there are exactly 8, which sounds more like 4 marks than the alternative 14. I do agree with you though - I'm not sure if you can actually expand a "tip node" since it has no child nodes (and if processing a tip node counts as "expanding".

Why I reckon we should include it is because in the solution for exam paper 2.1 it is stated "the order of expansion of the nodes is as follow:" so I figured visited and expanded in AI dictionary is the same

Well, the safest thing might be to mark those entries and state that they can not be expanded since they are tip nodes. This then covers you in either case.