1. Computers and thought (7 pts)

1. Describe the Turing Test and its importance in artificial intelligence. (4 pts)

2 pts Describing the test

1 Def’n of intelligence needed for AI

1 Discussing relationship between cognition and computation

 

2. "Computers can never be intelligent because they can only do what their programmers tell them to do — they’re only reflecting the intelligence of their creators." Comment on this statement. (3 pts)

2pts Humans follow instructions too (and they’re our only model)

1 pt Ability to adapt

 

3. Everybody has problems (14 pts)

1. Give the definition of "problem" as we have used the term in studying search, and briefly describe each element. (5 pts)

1 pt for each and 1 pt for distinguishing goal tests

Initial state — The starting state the agent knows it is in

Operators — Actions available to an agent

Goal test — Can be either a set of states, or a property of a set of states

Path cost — Function that assigns a cost to a path

 

2. Using your definition of problem, describe the game of Super Tic-Tac-Toe, which is played on an NxN board with k players. (4 pts)

1 pt for each

Initial state — blank board, an array/matrix of size NxN

Operators — Place a marker for player i

Goal test — N markers in a row, column or diagonal for player i

Path cost — Don’t care (Number of moves isn’t right, because we don’t have to worry about cycles/infinite games)

 

3. What is a CSP? (3 pts) Why distinguish CSPs from other problems? (2 pts)

3 pts CSP is restricted form of problem in which the operators are assignments of values to variables, states are particular assignments to variables and the goal test is stated in terms of constraints the assignments must satisfy

2 pts More efficient algorithms for CSP’s than in the general case

 

5. Searching (14 pts)

1. Why study search in artificial intelligence? (3 pts)

2 pts Search is well understood, and flexible because we can often cast many different problems as search problems (e.g., crossword puzzles, route finding, VLSI layout)

1 pt Some evidence that people engage in search themselves to solve some problems

 

2. Write the pseudocode for Iterative-Deepening-Search. Your answer should consist of three procedures: one that includes code applicable to searches in general, one that is slightly broader and a third that is specific to Iterative-Deepening-Search. (6 pts)

function General-Search(problem, QUEUING-FN) returns solution or failure

nodes ß MakeQueue(Make-node(Initial-state(problem)))

loop do

if nodes is empty return failure

node ß Remove-Front(nodes)

if Goal-Test(node) then return node

nodes ß Queueing-Fn(nodes, Expand-Node(node))

end

function Depth-Limited-Search(problem, depthLimit, Optional: node)

if Goal-Test(node) then return node

if NodeDepth(node) = depthLimit then return failure

for each node in ExpandNode(node, problem)

solution ß Depth-Limited-Search(problem, limit, n)

If solution then return solution

end

function Iterative-Deepening-Search(problem) returns solution or failure

for depth = 0 to infinity

if Depth-Limited-Search(problem, depth) succeeds then return result

end

return failure

 

3. When is Iterative-Deepening-Search appropriate? (2 pts)

1 pt for each

When the search space is large (1) and the solution depth is not known (1)

4. Is DFID efficient? Explain why or why not. (3 pts)

Yes, it is efficient because even though it revisits many nodes, it revisits them in proportion to their depth, which is only log (n) where n is the total tree size. In other words, most of the nodes are at the bottom of the tree, and those nodes are visited the least frequently.

7. Heuristic searching (14 pts)

1. Distinguish uninformed searching from informed searching by describing all the elements used in uninformed searching, and those that must be added to inform search. (3 pts)

2 pts Uninformed

Initial state

Operators and their costs

Goal function

Search strategy

1 pt Informed

Problem-specific knowledge (Usu. heuristic evaluation function)

2. Why might it be difficult to use heuristic search techniques for a given problem? (3 pts)

There are many reasons, but the simplest is that a good heuristic function might not be available. If the problem space is especially complex, and a heuristic function can only be very approximately estimated, then there won’t be much gain from heuristic search.

 

3. Define the admissibility property for heuristics, and explain why it is important. (5 pts)

3 pts Admissible heuristics never overestimate the cost of achieving the solution (they’re optimistic)

2 pts Overestimation would skip paths that might yield the solution

 

4. When might you choose to sacrifice admissibility? (3 pts)

Admissibility is needed for completeness, because complete algorithms must promise to find a solution. On the other hand, the more accurate your heuristic function is, the faster A* (or another best-first search) will work. Admissibility rules out functions which are always very, very close to the true cost, but sometimes exceed it. Thus, by sacrificing admissibility, you might see very large gains in efficiency.

8. Lisp

1. Draw the result of the following expression in box and pointer notation: (3 pts)

(cons ‘a (cons (cons ‘b ‘c) ‘d))

 

 

2. Define functional programming, and give a rationale for it. Why might the functional style be well-suited to artificial intelligence programming? (4 pts)

Functional programming is modeled on the mathematical notion of function evaluation — the variable x is unchanged by the calculation of f(x). Programs are built by layering functions on top of one another (an "onion" structure), rather than a sequence of statements to execute (procedural programming). Because we have only function evaluation, and no side effects, this eliminates a common source of bugs, but also means that code can be executed in any order.

Functional programming works well with AI because it makes it easy to explore concepts by layering more complex behaviors on top of simpler ones, and the support that functional languages usually offer for symbols makes the transition from idea to code simpler.

 

3. Define the term special variable, and give two techniques for avoiding the use of such variables. (4 pts)

2 pts A variable that is dynamically bound, as opposed to lexically bound. In other words, the value is resolved in the calling environment, not in the environment of definition. Global variables are always special variables.

1 pt for each way to avoid

Pass values as function arguments

Use closures

4. Why is there no definition for Make-Cannibal-Problem in the AIMA code for the missionaries and cannibals problem? (3 pts)

The Make-Cannibal-Problem procedure is automatically defined by the defstruct that creates cannibal problems, as are the slot accessors and other functions.

9. AIMA Code

1. Explain what the following code does in English. (4 pts)

(defmethod initialize ((env grid-environment))

(unless (environment-initialized env)

(setf (grid-environment-grid env)

(make-array (grid-environment-size env)

:initial-element '()))

(parse-specs env (grid-environment-aspec env))

(parse-specs env (grid-environment-bspec env))

(parse-specs env (grid-environment-cspec env))

(call-next-method)))

The code initializes a grid environment (but only once) by creating an array to represent the grid squares. The code then creates the requested agents (aspec), basic objects (bspec) and changing objects (cspec) within the environment.

2. When is this function invoked? (3 pts)

As its first step, the function RunEnvironment initializes the environment.

3. Rewrite the code to use the if special form and a mapping function. Justify your choice of mapping function. (4 pts)

3 pts

(defmethod initialize ((env grid-environment))

(if (not (environment-initialized env))

(progn ; unless has an implicit progn

(setf (grid-environment-grid env)

(make-array (grid-environment-size env)

:initial-element '()))

(mapc #'(lambda (x)

(parse-specs env (funcall x env)))

'(grid-environment-aspec

grid-environment-bspec

grid-environment-cspec))

(call-next-method))))

1 pt I used mapc() because it doesn’t bother to cons up a list (as mapcar() does). Since the value of initialize will be the value of call-next-method(), there’s no point in returning a list — in other words, we’re only calling the aspec, bspec and cspec functions for their side effects.

4. What does call-next-method() do? (3 pts)

2 pts Call-next-method() invokes the next most specific method of the applicable methods. When call-next-method is called with no arguments, it passes the current method's original arguments to the next method.