Home

# Midterm 1 guide

Answers on the bottom. Also, you can bring a notecard (5in x 7in max) with notes or whatnot.

## Turing test

True or false? Turing first described a test between a monkey and a human before describing a test between a human and a machine.

True or false? The goal of the machine is to convince the judge that the human is a machine.

True or false? To pass the Turing test, the machine should be expected to fool the judge (convince the judge that the machine is a human) nearly 100% of the time; or, maybe just 70% of the time.

True or false? Dennett thinks that winning a chess championship is just as strong a test for computer intelligence as the Turing test.

## General Problem Solver

Modify the following “program” so that GPS can find the solution.

problem = {
"start": ["door locked"],
"finish": ["door open"],
"ops": [
{
"action": "open door",
"preconds": ["door unlocked", "door closed"],
"delete": ["door closed"]
},
{
"action": "unlock door",
"preconds": ["door closed"],
"delete": ["door locked"]
}
]
}


## Search

### General search

Give an initial state, describe possible actions and the transition model (i.e., how states connect), and specify a goal criterion for the following search problem:

A robot wants a path to exit a maze. The maze is represented as a square grid; open areas are represented by white grid cells, and walls are represented by black grid cells.

Repeat this exercise for the following search problem:

Recall from calculus that the derivative is the inverse of the integral. Finding the derivative of a formula is easy (no search needed). But finding the integral of a formula is often challenging, and may require a search procedure. Describe this search procedure.

Complete the following table for weighted, finite search graphs:

Search algorithmAlways complete?Always optimal?Uses a heuristic?
Random search
Depth-first searchNo
Hill-climbing search
Best-first search
A* searchYes

Recall the Goodale route search problem from Practice with searching notes. Answer the following questions for each of breadth-first search, depth-first search, hill-climbing search, best-first search, and A* search (using some heuristic like distance “as the crow flies”). Assume we start at Woodruff & Tuttle and the goal is Goodale parking lot. For each question, there may be more than one correct answer.

1. What are the first two states (beyond Woodruff & Tuttle) that will be checked?
2. What does the tocheck list look like after checking those states from question 1? Be sure to order the list by an appropriate sort order (breadth-first, hill-climbing, best-first, and A* will take the next state from the front of the list; depth-first will take the next state from the end).

What is the singular requirement for a heuristic to be called “admissible?”

Describe a utility function for an adversarial search procedure (e.g., minimax) for playing chess.

True or false? Minimax is an appropriate search procedure for single-player games (like a solitaire card game or a Rubik’s cube)?

True or false? Alpha-beta pruning, as applied to the minimax procedure, produces more optimal solutions (e.g., produces game moves that allow the computer to win in fewer moves).

True or false? Alpha-beta pruning (applied to minimax) uses different utility functions than regular minimax.

True or false? Alpha-beta pruning (applied to minimax) is the same algorithm as minimax, just faster because irrelevant computations are omitted.

What is the best move, according to a minimax procedure, for ‘x’ to make in the following tic-tac-toe board?

 o o x x x o

## Knowledge representation

### Boolean logic

Simplify the following expression using Boole’s and De Morgan’s laws: $$\neg(\neg x \vee \neg y) \wedge (x \wedge (y \vee \neg y))$$

### Propositional logic

Build a truth-table for: $$\neg A \vee (B \leftrightarrow A)$$ Find a satisfying assignment (if any exists) for: $$\neg A \wedge (A \rightarrow (B \wedge C))$$ Given,

1. $$(S \vee T) \wedge (A \vee B)$$
2. $$S \rightarrow Q$$
3. $$\neg Q$$
4. $$\neg C \vee Q$$

Prove (and state the rules and premises you utilize):

1. $$\neg S$$
2. $$T$$
3. $$\neg C \vee W$$

### First-order logic

Rewrite the following statements in first-order logic:

1. Tony is a tiger.
2. All tigers have stripes.
3. Some tigers are white.
4. If any tiger is white, then we know it lives in the snow (but not necessarily vice versa).
5. A tiger is not both white and orange.

Rewrite the following without using $$\forall$$ (hint: use negation): $$(\forall x)(P(x) \leftrightarrow (A(x) \wedge B(x)))$$ Rewrite the following without using $$\exists$$: $$(\exists x)(W(x) \vee \neg Q(x))$$

### Prolog

Given,

member(X, [X|_]).
member(X, [_|Tail]) :- member(X, Tail).

foobar(X, List) :- member(Y, List), X \= Y.


What are the values of each of these queries? (Write “true” or “false”, or give one value of the variable X.)

member(5, [1, 2, 3]).
member(X, [1, 2, 3]).
foobar(1, [1, 2, 3]).
foobar(1, [1, 1, 1]).


Given,

family(10392,
person(tom, fox, born(7, may, 1960), works(cnn, 152000)),
person(ann, fox, born(19, april, 1961), works(nyu, 65000)),
% here are the children...
[person(pat, fox, born(5, october, 1983), unemployed),
person(jim, fox, born(1, june, 1986), unemployed),
person(amy, fox, born(17, december, 1990), unemployed)]).

exists(Person) :- family(_, Person, _, _).
exists(Person) :- family(_, _, Person, _).
exists(Person) :- family(_, _, _, Children), member(Person, Children).


What are the values of each of these queries (write “true” or “false”, or give one value for each of the variables)?

family(_, person(_, _, born(_, _, Year), _), _, _), Year > 1960.

% don't forget to give one value for each variable:
% FirstName, LastName, and X
exists(person(FirstName, LastName, _, X)), X \= unemployed.


Do the following unify, and if so, what are values for the variables (one set of values for each question), if any variables are involved, that make the unification work?

• foo and foo
• foo(X) and X
• foo(foo(foo)) and foo(X)
• foo(X, foo) and foo(foo, X)
• foo(X, foo) and foo(Y)
• foo(foo(X, Y)) and foo(Z)

Suppose we have the following knowledge base:

f(a).
f(b).

g(a, a).
g(b, c).

h(b).
h(c).

k(X, Y) :- f(X), g(X, Y), h(Y).


Draw the resolution tree for the first successful proof of k(X, c).

### Turing test

True or false? Turing first described a test between a monkey and a human before describing a test between a human and a machine.

False — the original test was between a man and a woman; the man was supposed to impersonate the woman.

True or false? The goal of the machine is to convince the judge that the human is a machine.

True — or, False — my fault, both answers are true: the machine is supposed to convince the judge that it is a human, which is equivalent to convincing the judge that the human is a machine.

True or false? To pass the Turing test, the machine should be expected to fool the judge (convince the judge that the machine is a human) nearly 100% of the time; or, maybe just 70% of the time.

False — the machine should not be expected to be “more human than human,” so convincing the judge just 25% of the time seems sufficient. Over 50% may well change our definition of humanity…

True or false? Dennett thinks that winning a chess championship is just as strong a test for computer intelligence as the Turing test.

False — beating humans in chess is not sufficient because chess requires only a narrow kind of intelligence, more calculation than anything

### General Problem Solver

Modify the following “program” so that GPS can find the solution.

problem = {
"start": ["door closed", "door locked"],
"finish": ["door open"],
"ops": [
{
"action": "open door",
"preconds": ["door unlocked", "door closed"],

"delete": ["door closed"]
},
{
"action": "unlock door",
"preconds": ["door closed"],
"delete": ["door locked"]
}
]
}


### Search

#### General search

Give an initial state, describe possible actions and the transition model (i.e., how states connect), and specify a goal criterion for the following search problem:

A robot wants a path to exit a maze. The maze is represented as a square grid; open areas are represented by white grid cells, and walls are represented by black grid cells.

• initial state: the robot’s starting location
• possible actions: move north, south, east, west (not all movements are always possible)
• transition model: look at the map, connect grid locations via north/south/east/west links
• goal criterion: finding the exit from the maze

Repeat this exercise for the following search problem:

Recall from calculus that the derivative is the inverse of the integral. Finding the derivative of a formula is easy (no search needed). But finding the integral of a formula is often challenging, and may require a search procedure. Describe this search procedure.

• initial state: the starting formula that needs a symbolic integral to be found
• possible actions / transition model: create a database like this:
• sin(x) --> -cos(x)
• cx --> cx^2/2
• x^n --> (x^(n+1)/(n+1))
• goal criterion: say you are looking at a new formula g, and the original formula is f, then you want dg/dx = f; every “state” (formula) is checked in this way

Complete the following table for weighted, finite search graphs:

Search algorithmAlways complete?Always optimal?Uses a heuristic?
Random searchYesNoNo
Depth-first searchYesNoNo
Hill-climbing searchNoNoYes
Best-first searchYesNoYes
A* searchYesYesYes

Recall the Goodale route search problem from Practice with searching notes. Answer the following questions for each of breadth-first search, depth-first search, hill-climbing search, best-first search, and A* search (using some heuristic like distance “as the crow flies”). Assume we start at Woodruff & Tuttle and the goal is Goodale parking lot. For each question, there may be more than one correct answer.

1. What are the first two states (beyond Woodruff & Tuttle) that will be checked?
• breadth-first (one possible answer): Lane & Tuttle, High & Woodruff
• depth-first (one possible answer): Lane & Tuttle, SR-315 & Lane
• best-first (only answer): High & Woodruff, High & 15th
• hill-climbing (only answer): same as best-first
• A* (only answer): Lane & Tuttle, High & Woodruff
2. What does the tocheck list look like after checking those states from question 1? Be sure to order the list by an appropriate sort order (breadth-first, hill-climbing, best-first, and A* will take the next state from the front of the list; depth-first will take the next state from the end). Assume already-checked states are not added.
• breadth-first (one possible answer): [SR-315 & Lane, High & 15th]
• depth-first (one possible answer): [High & Woodruff, SR-315 I-670 offramp, SR-315 & King]
• best-first: [High & 11th, US-23 & 15th, Lane & Tuttle]
• hill-climbing: [High & 11th, US-23 & 15th]
• A*: [High & 15th, SR-315 & Lane]

What is the singular requirement for a heuristic to be called “admissible?”

• The heuristic must always underestimate (or exactly match) the true cost from the current state to the goal state.

Describe a utility function for an adversarial search procedure (e.g., minimax) for playing chess.

• One possible answer: Number of captured pieces, maybe with a weight for each piece (so a queen will have a large weight, a pawn not so much)

True or false? Minimax is an appropriate search procedure for single-player games (like a solitaire card game or a Rubik’s cube)?

False — there is no adversary to simulate and minimize, thus no minimax

True or false? Alpha-beta pruning, as applied to the minimax procedure, produces more optimal solutions (e.g., produces game moves that allow the computer to win in fewer moves).

False — alpha-beta does not change the solutions.

True or false? Alpha-beta pruning (applied to minimax) uses different utility functions than regular minimax.

False — the utility functions are not changed, just which parts of the search space are actually searched.

True or false? Alpha-beta pruning (applied to minimax) is the same algorithm as minimax, just faster because irrelevant computations are omitted.

True — that’s all alpha-beta pruning is; it still does minimax.

What is the best move, according to a minimax procedure, for ‘x’ to make in the following tic-tac-toe board?

 o o x x x o

The answer is that ‘x’ should move in the exact middle, as proved by this minimax search tree: ### Knowledge representation

#### Boolean logic

Simplify the following expression using Boole’s and De Morgan’s laws: $$\neg(\neg x \vee \neg y) \wedge (x \wedge (y \vee \neg y))$$

• Change $$y \vee \neg y$$ to $$T$$, yielding: $$\neg(\neg x \vee \neg y) \wedge (x \wedge T)$$
• Change $$x \wedge T$$ to $$x$$, yielding: $$\neg(\neg x \vee \neg y) \wedge x$$
• Distribute the negative, yielding: $$(x \wedge y) \wedge x$$
• Get rid of parentheses, reduce redundancy, yielding $$x \wedge y$$

#### Propositional logic

Build a truth-table for: $$\neg A \vee (B \leftrightarrow A)$$

$$A$$$$B$$$$B \leftrightarrow A$$$$\neg A \vee (B \leftrightarrow A)$$
TTTT
TFFF
FTFT
FFTT

Find a satisfying assignment (if any exists) for: $$\neg A \wedge (A \rightarrow (B \wedge C))$$ Build a truth table to find this:

$$A$$$$B$$$$C$$$$B \wedge C$$$$A \rightarrow (B \wedge C)$$$$\neg A \wedge (A \rightarrow (B \wedge C))$$
TTTTTF
TTFFFF
TFTFFF
TFFFFF
FTTTTT
FTFFTT
FFTFTT
FFFFTT

The last four rows will provide satisfying assignments.

Given,

1. $$(S \vee T) \wedge (A \vee B)$$
2. $$S \rightarrow Q$$
3. $$\neg Q$$
4. $$\neg C \vee Q$$

Prove (and state the rules and premises you utilize):

1. $$\neg S$$
1. From 2, 3 and modus tollens.
2. $$T$$
1. From $$\neg S$$ (above) and 1, simplification, and disjunctive syllogism.
3. $$\neg C \vee W$$
1. From 3, 4 and disjunctive syllogism (which gives us $$\neg C$$); now apply addition plus introduce the arbitrary symbol $$W$$ (which is allowed with the addition rule)

#### First-order logic

Rewrite the following statements in first-order logic:

1. Tony is a tiger.
• $$Tiger(Tony)$$
2. All tigers have stripes.
• $$(\forall x)(Tiger(x) \rightarrow Striped(x))$$
3. Some tigers are white.
• $$(\exists x)(Tiger(x) \wedge White(x))$$
4. If any tiger is white, then we know it lives in the snow (but not necessarily vice versa).
• $$(\forall x)((Tiger(x) \wedge White(x)) \rightarrow LivesInSnow(x))$$
5. A tiger is not both white and orange.
• $$(\forall x)(Tiger(x) \rightarrow (\neg White(x) \vee \neg Orange(x)))$$

Rewrite the following without using $$\forall$$ (hint: use negation): $$(\forall x)(P(x) \leftrightarrow (A(x) \wedge B(x)))$$ $$\neg(\exists x)((P(x) \vee (A(x) \wedge B(x))) \wedge (\neg P(x) \vee \neg(A(x) \wedge B(x))))$$ Rewrite the following without using $$\exists$$: $$(\exists x)(W(x) \vee \neg Q(x))$$ $$\neg (\forall x)(\neg W(x) \wedge Q(x))$$

#### Prolog

Given,

member(X, [X|_]).
member(X, [_|Tail]) :- member(X, Tail).

foobar(X, List) :- member(Y, List), X \= Y.


What are the values of each of these queries? (Write “true” or “false”, or give one value of the variable X.)

member(5, [1, 2, 3]). % --> false
member(X, [1, 2, 3]). % --> X = 1 or 2 or 3
foobar(1, [1, 2, 3]). % --> true
foobar(1, [1, 1, 1]). % --> false


Given,

family(10392,
person(tom, fox, born(7, may, 1960), works(cnn, 152000)),
person(ann, fox, born(19, april, 1961), works(nyu, 65000)),
% here are the children...
[person(pat, fox, born(5, october, 1983), unemployed),
person(jim, fox, born(1, june, 1986), unemployed),
person(amy, fox, born(17, december, 1990), unemployed)]).

exists(Person) :- family(_, Person, _, _).
exists(Person) :- family(_, _, Person, _).
exists(Person) :- family(_, _, _, Children), member(Person, Children).


What are the values of each of these queries (write “true” or “false”, or give one value for each of the variables)?

family(_, person(_, _, born(_, _, Year), _), _, _), Year > 1960.

% don't forget to give one value for each variable:
% FirstName, LastName, and X
exists(person(FirstName, LastName, _, X)), X \= unemployed.
% one answer: FirstName = tom, LastName = fox, X = works(cnn, 152000)


Do the following unify, and if so, what are values for the variables (one set of values for each question), if any variables are involved, that make the unification work?

• foo and foo
• Yes, they unify (trivially).
• foo(X) and X
• No. There is no value of X such that X = foo(X).
• foo(foo(foo)) and foo(X)
• Yes, with X = foo(foo).
• foo(X, foo) and foo(foo, X)
• Yes, with X = foo.
• foo(X, foo) and foo(Y)
• No, arities differ.
• foo(foo(X, Y)) and foo(Z)
• Yes, with Z = foo(X, Y).

Suppose we have the following knowledge base:

f(a).
f(b).

g(a, a).
g(b, c).

h(b).
h(c).

k(X, Y) :- f(X), g(X, Y), h(Y).


Draw the resolution tree for the first successful proof of k(X, c). 