Midterm 2001

CSC242: Artificial Intelligence 2001

1.SEARCH There is a technical meaning to the concepts of heuristic vs. constrained vs. hill-climbing search. I wanted to make sure you had the idea for CSP that each element was initially assigned all its possible values and that as elements were assigned particular values during the search that cut down the possible values on OTHER variables. When someone asks for heuristic search they are asking for the g and h functions in the heuristic function f = g+h. Prose descriptions are OK but you need those functions, that's the point. Also you need the operator you use, which depends on your g and h functions -- swapping 2 elements is a pretty good op. For this problem it maybe took a little thought to see that the goal was not to find the sum on the rows and columns that was the same, it was to find the elements given that you knew the sum. (The sum clearly has to be (sum of 1 through N*N)/4, no? Last, for hill-climbing it is important that you know you start out with a full solution (array full of elements) and you have a function expressing ``goodness'' (maybe same as h above, maybe different), and you have an op (here, swapping elements certainly occurs naturally) that changes the situation a little and whose effect is measured with the good ness function. You pick the best swap (how many are there???) that will improve things.

Anyway, the point is that these searches are conceptually quite different and not too many people convinced me they knew the basic concepts behind them.

2. MIMIMAX You may want to be a leetle careful here to say the right thing, but it is important at least to notice that MAX is definitely going to consider all of MIN's next moves. He will evaluate each of them in this recursive minimax fashion until he think he knows what MIN will do if min plays the best game he can (according to Max's theory -- using his evaluation function). If MIN plays worse than that, MAX will never be worse off (using MAX's eval function).

Then there's more to say (see provided answer).

3. Alpha Beta Pruning: This stuff is fiddly and tough to do, under pressure. I gave a lot of credit for reasonable-looking answers, most people seemed to have a handle on what I was talking about.

4. INFERENCE and GMP. Charity points for you, I picked something out of the book by accident. I have no idea who would have got this right if it wasn't explicitly in the book. There were some unexpected answers that showed you knew what GMP was, which got partial credit.

5. Resolution. When someone asks this sort of question, and they always do, they want 1. formalization of the premises 2. put them in clause form -- note there'll ALWAYS be a Skolem fn or constant! 3. add the negated conclusion 4. RESOLUTION (don't use other rules if resolution is requested) It's best to draw a picture of the clauses cancelling out; visual and easier to grade.

Most people sort of thrashed at the problem, and had one or more of the problems of: missed the skolem, formalized the premises slightly wrong, forgot to add the conclusion, and didn't do a clear resolution proof.

6. Unification. People either knew it or didn't, except almost everyone missed the idea in c) that with these 2 clauses, the universally quantified variables are different. That is, they can be relabelled to be different (as in a) without changing the semantics. That's vital.

7. Planning: probably a little unclear. Idea was that if you stuck A on C first, you wouldn't be able to stick B into its place. Not making that explicit kind of muddied the question. Still, it's important to get the right buzzwords with these two systems. Strips is state-space, regressive, backward chaining, uses a goal stack; POP's search in plan space, are uncommittal about order of steps until they are forced to by threats, use promotion and demotion, have temporal order links, etc. etc.

*Last update: 29.3.01.*