Introduction to Artificial Inteligence
Quiz 1 - answers
0. An intelligent agent has to answer 3 questions in a quiz on AI, what is
the optimal time allocation and pruning on the search space for solutions?
(most people have flunked this part of the quiz), solution to this
question embedded in the rest of the answers.
1. In the anti tic-tac-toe game, the current position is:
| | X
---+---+---
O | O |
---+---+---
X | | X
1.1: The game tree up to the terminal nodes: we will use the notation
(who's move: position)
to denote the new move in each case. Board position to be read by the
path from the state up to the current move. Position is denoted by (x,y),
where x is from the right and y from the top.
Thus, we have the following tree (omitting the initial position). Tree
also includes values for terminal nodes.
MAX MIN MAX
O:(1,1) X:(2,1) O:(2,3) X:(3,2) Value: 1 (win for O)
O:(3,2) Value: -1 (win for X)
X:(3,2) Value: 1 (win for O)
X:(2,3) Value: 1 (win for O)
O:(2,1) X:(1,1) O:(2,3)) Value: -1 (win for X)
O:(3,2)) Value: -1 (win for X)
X:(3,2) Value: 1 (win for O) *
X:(2,3) Value: 1 (win for O) *
O:(2,3) X:(1,1) O:(2,1) Value: -1 (win for X)
O:(3,2) Value: -1 (win for X)
X:(2,1) O:(1,1) X:(3,2) Value: 1 (win for O) *
O:(3,2) Value: -1 (win for X) *
X:(3,2) Value: 1 (win for O) *
O:(3,2) Value: -1 (win for X)
1.2 Optimal ordering for alpha-beta is exactly as above. Now, if the program
does NOT know the maximal value of the game, it will compute the whole
subtree rooted at O:(1,1) to get an alpha value of 1. Then, all branches
marked * can be pruned, as in each case X is guaranteed a win and
thus it is sure that O will not make that move.
If, in addition, the program knows the bounds of 1 on game score,
it need only evaluate the subtree rooted at O:(1,1), but without
the sub-branch O(3,2), because it can never get a score higher than
1 elsewhere!
1.3 Clearly, optimal move is O:(1,1).
1.4 If we have a RANDOM player, we need to look at the tree as an EXPECTI-MAX
tree rather than MINIMAX. But we can save a lot of work by computing
BOUNDS. Since move O:(1,1) forces a win against ANY moves by the
oppenent, this move also has an EXPECTED VALUE of 1 (anything higher is
impossible). Thus, no need to check anything else, the best move against
a random opponent is STILL O:(1,1) !
1.5 If we cannot see the response by the opponent, we MIGHT wish to model
this as a random move - and thus use an "expecti-mini-max" tree. However,
that will unfortunately be incorrect. The problem here is that the state
is not currently observable, NOT that it is stochastic. And since there
is an intelligent agent as an opponent, not a random process, we cannot
use the expecti-mini-max to obtain optimum. This is a HARD problem, but
then you were NOT required to find the solution here!
2 Resolution theorem proving in CNF propositional logic.
2.1 The given KB as a CNF (listed as separate clauses, with
conjunction between clauses written as commas, for convenience):
A , ~A v B , ~B v C , ~C v D , ~E , ~A v D v E
2.2 First, resolve the last two clauses to get ~A v D
Then, resolve the clause A with the above to get D
2.3 This is optimal because there is no 0-step proof (obvious).
We can prove that there is no one-step proof by trying all possible
resolution steps from the initial KB:
1st and 2nd clauses: result B
2nd and 3rd clasues: result ~A v C
3rd and 4th clauses: result ~B v D
1st and last clauses: result D v E
The above list (including the one in 2.2) are all possible applications
of resolution in the original KB, and none of the produce a one-step
proof. Thus, the proof in 2.2 is the shortest (though there may be,
and in fact there IS, another 2-step proof).
The "direct" proof: A -> B -> C -> D requires THREE steps.
2.4 First, we show that h(n) is an admissible heuristic. It is exact
for a goal state - since if the KB contains the result, h(n)=0.
The resolution operator on CNF can only at most decrease the size of a
conjunct by 1, (and even that only if one of the conjuncts is of UNIT
size). Since the heuristic measures the size of the SMALLEST disjunction,
containing the goal literal minus 1, this heuristic is clearly OPTIMISTIC.
Thus, the heuristic is ADMISSIBLE. Therefore, A* is guaranteed to find
the optimal solution, i.e. a shortest proof IF it exists using only
resolution steps.
Admissability of h(n) allows for a shorter proof in 2.3 - for the original
KB we have h(n) = 1. The only clause with distance 1 is ~C v D, but
no single resolution step on this clause can produce D, and thus the
children of the original KB under A* must all have h(n) = 1. Since
h is optimistic, the solution length is at least 2!
3. Situation calculus question. This is a VERY simple domain. The axioms
required are:
If the robot grabs an object, it will be holding it as a result:
(forall x, s) holding(x, result(grab(x), s)
If the robot is holding an object, it will still hold it after it
grabs an object (whether the same object or not is immaterial):
(forall x, y, s) holding(x, s) => holding(x, result(grab(y), s))
If the robot executes exit in a situation where it is holding exactly
2 object, it will be in a situation wher wins is true:
(forall s) ((exists x, y) holding(x, s) ^ holding(y, s) ^ ~(x=y) ^
(forall z) ~holding(z, s) v z=x v z=y) =>
wins(result(exit, s))
Since the above contains complicated nesting of quantifiers, there
are several equivalent variants...