1 Million+ Step-by-step solutions

Define in your own words:

(a) Intelligence,

(b) Artificial intelligence,

(c) Agent.

(a) Intelligence,

(b) Artificial intelligence,

(c) Agent.

Read Turing’s original paper on Al (Turing, 1950). In the paper, he discusses several potential objections to his proposed enterprise and his test for intelligence. Which objections still carry some weight? Arc his refutations valid? Can you think of new objections arising from developments since he wrote the paper? In the paper, he predicts that, by the year 2000, a computer will have a 30% chance of passing a five-minute Turing Test with an unskilled interrogator. What chance do you think a computer would have today? In another 50 years?

Every year the Loebner prize is awarded to the program that comes closest to passing a version of the Turing test. Research and report on the latest winner of the Loehner prize. What techniques does it use? How does it advance the state of the art in AI?

There are well-known classes of problems that are intractably difficult for computers, and other classes that are provably un-decidable. Does this mean that Al is impossible?

Suppose we extend Evans’s ANALOGY program so that it can score 200 on a standard IQ test. Would we then have a program more intelligent than a human? Explain.

How could introspection—reporting on one’s inner thoughts—be inaccurate? Could I be wrong about what I’m thinking? Discuss.

Examine the Al literature to discover whether the following tasks can currently be solved by computers:

a. Playing a decent game of table tennis (ping-pong).

b. Driving in the center of Cairo.

c. Buying a week’s worth of groceries at the market.

d. Buying a week’s worth of groceries on the web

e. Playing a decent game of bridge at a competitive level.

f. Discovering and proving new mathematical theorems.

g. Writing an intentionally funny story.

h. Giving competent legal advice in a specialized area of law.

i. Translating spoken English into spoken Swedish in real time.

j. Performing a complex surgical operation.

For the currently infeasible tasks, try to find out what the difficulties are and predict when, if ever, they will be overcome.

a. Playing a decent game of table tennis (ping-pong).

b. Driving in the center of Cairo.

c. Buying a week’s worth of groceries at the market.

d. Buying a week’s worth of groceries on the web

e. Playing a decent game of bridge at a competitive level.

f. Discovering and proving new mathematical theorems.

g. Writing an intentionally funny story.

h. Giving competent legal advice in a specialized area of law.

i. Translating spoken English into spoken Swedish in real time.

j. Performing a complex surgical operation.

For the currently infeasible tasks, try to find out what the difficulties are and predict when, if ever, they will be overcome.

Sonic authors have claimed that perception and motor skills are the most important part of intelligence, and that “higher level” capacities are necessarily parasitic—simple add-ons to these underlying facilities. Certainly, most of evolution and a large part of the brain have been devoted to perception and motor skills, whereas Al has found tasks such as game playing and logical inference to be easier, in many ways, than perceiving and acting in the real world. Do you think that AI’s u-traditional focus on higher-level cognitive abilities is misplaced?

Why would evolution tend to result in systems that act rationally? What goals are such systems designed to achieve?

Are reflex actions (such as moving your hand away from a hot stove) rational? Are they intelligent?

“Surely computers cannot be intelligent—they can do only what their programmers tell them.” Is the latter statement true, and does it imply the former?

“Surely animals cannot he intelligent—they call do only what their programmers tell them.” Is the latter statement true, and does it imply the former?

“Surely animals, humans, and computers cannot be intelligent—they can do only what their constituent atoms are told to do by the laws of physics.” Is the latter statement true, and does it imply the former?

Define in your own words the following terms: agent, agent function, agent program, rationality, autonomy, reflex agent, model-based agent, goal-based agent, utility-based agent, learning agent.

Both the performance measure and the utility function measure how well an agent is doing. Explain the difference between the two.

This exercise explores the differences between agent functions and agent programs.

a. Can there be more than one agent program that implements a given agent function? Give an example, or show why one is not possible.

b. Are there agent functions that cannot be implemented by any agent program?

c. Given a fixed machine architecture does each agent program implement exactly one agent function?

d. Given an architecture with n bits of storage, how many different possible agent programs are there?

a. Can there be more than one agent program that implements a given agent function? Give an example, or show why one is not possible.

b. Are there agent functions that cannot be implemented by any agent program?

c. Given a fixed machine architecture does each agent program implement exactly one agent function?

d. Given an architecture with n bits of storage, how many different possible agent programs are there?

Let us examine the rationality of various vacuum-cleaner agent functions.

a. Show that the simple vacuum-cleaner agent function described in Figure is indeed rational tinder the assumptions listed.

b. Describe a rational agent function for the modified performance measure that deducts one point for each movement. Does the corresponding agent program require internal state?

c. Discuss possible agent designs for the cases in which clean squares can become dirty and the geography of the environment is unknown. Does it make sense for the agent to learn from its experience in these cases? If so, what should it learn?

a. Show that the simple vacuum-cleaner agent function described in Figure is indeed rational tinder the assumptions listed.

b. Describe a rational agent function for the modified performance measure that deducts one point for each movement. Does the corresponding agent program require internal state?

c. Discuss possible agent designs for the cases in which clean squares can become dirty and the geography of the environment is unknown. Does it make sense for the agent to learn from its experience in these cases? If so, what should it learn?

For each of the following agents, develop a PEAS description of the task environment:

a. Robot soccer player,

b. Internet book-shopping agent;

c. Autonomous Mars rover;

d. Mathematician’s theorem-proving assistant.

a. Robot soccer player,

b. Internet book-shopping agent;

c. Autonomous Mars rover;

d. Mathematician’s theorem-proving assistant.

For each of the agent types listed in Exercise 2.5, characterize the environment according to the properties given in Section 2.3, and select a suitable agent design. The following exercises all concern the implementation of environments and agents for the vacuum-cleaner world.

Implement a simple reflex agent for the vacuum environment in Exercise 2.7. Run the environment simulator with this agent for all possible initial dirt configurations and agent locations. Record the agent’s performance score for each configuration and its overall average score.

Consider a modified version of the vacuum environment in Exercise 2.7, in which the geography of the environment—its extent, boundaries, and obstacles—is unknown, as is the initial dirt configuration. (The agent can go Up and Doum as well as Left and Right.)

a Can a simple reflex agent be perfectly rational for this environment? Explain

b. Can a simple reflex agent with a randomized agent function outperform a simple reflex agent? Design such an agent and measure its performance on several environments.

c. Can you design an environment in which your randomized agent will perform very poorly? Show your results.

d. Can a reflex agent with state outperform a simple reflex agent? Design such an agent and measure its performance on several environments. Can you design a rational agent of this type?

a Can a simple reflex agent be perfectly rational for this environment? Explain

b. Can a simple reflex agent with a randomized agent function outperform a simple reflex agent? Design such an agent and measure its performance on several environments.

c. Can you design an environment in which your randomized agent will perform very poorly? Show your results.

d. Can a reflex agent with state outperform a simple reflex agent? Design such an agent and measure its performance on several environments. Can you design a rational agent of this type?

Repeat Exercise 2.10 for the case in which the location sensor is replaced with a “bump” sensor that detects the agent’s attempts to move into an obstacle or to cross the boundaries of the environment. Suppose the bump sensor stops working; how should the agent behave?

The vacuum environments in the preceding exercises have all been deterministic. Discuss possible agent programs for each of the following stochastic versions:

a. Murphy’s Law twenty-five percent of the time, the Suck action fails to clean the floor if it is dirty and deposits dirt onto the floor if the floor is clean. How is your agent program affected if the dirt sensor gives the wrong answer 10% of the time?

b. Small children: At each time step, each clean square has a 10% chance of becoming dirty. Can you come up with a rational agent design for this case?

a. Murphy’s Law twenty-five percent of the time, the Suck action fails to clean the floor if it is dirty and deposits dirt onto the floor if the floor is clean. How is your agent program affected if the dirt sensor gives the wrong answer 10% of the time?

b. Small children: At each time step, each clean square has a 10% chance of becoming dirty. Can you come up with a rational agent design for this case?

Define in your own words the following terms: state, state space, search tree, search node, goal, action, successor function, and branching factor.

Explain why problem formulation must follow goal formulation.

Suppose that legal-actions(s) denotes the set of actions that are legal in state s, and result(a, s) denotes the state that results from performing a legal action a in state s. define successor-en in terms of legal-actions and result, and vice versa.

Show that the 8-puizle states are divided into two disjoint sets, such that no state in one set can be transformed into a state in the other set by any number of moves. Devise a procedure that will tell you which class a given state is in, and explain why this is a good thing to have for generating random states.

Consider the n-queens problem using the “efficient” incremental formulation given. Explain why the state space size is at least and estimate the largest ii for which exhaustive exploration is feasible.

Does a finite state space always lead to a finite search tree? How about a finite state space that is a tree? Can you be more precise about what types of state spaces always lead to finite search trees? (Adapted from Bender, 1996)

Give the initial state, goal test, successor function, and cost function for each of the following. Choose a formulation that is precise enough to be implemented.

a. You have to color a planar map using only four colors, in such a way that no two adjacent regions have the same color.

b. A 3-foot-tall monkey is in a room where some bananas are suspended from the 8-foot ceiling. He would like to get the bananas. The room contains two stackable, movable, climbable 3-foot-high crates.

c. You have a program that outputs the message “illegal input record” when fed a certain file of input records. You know that processing of each record is independent of the other records. You want to discover what record is illegal.

d. You have three jugs measuring 12 gallons, 8 gallons, and 3 gallons and a water faucet. You can fill the jugs up or empty them out from one to another or onto the ground. You need to measure out exactly one gallon.

a. You have to color a planar map using only four colors, in such a way that no two adjacent regions have the same color.

b. A 3-foot-tall monkey is in a room where some bananas are suspended from the 8-foot ceiling. He would like to get the bananas. The room contains two stackable, movable, climbable 3-foot-high crates.

c. You have a program that outputs the message “illegal input record” when fed a certain file of input records. You know that processing of each record is independent of the other records. You want to discover what record is illegal.

d. You have three jugs measuring 12 gallons, 8 gallons, and 3 gallons and a water faucet. You can fill the jugs up or empty them out from one to another or onto the ground. You need to measure out exactly one gallon.

Consider a state space where the start state is number 1 and the successor function for state n returns two states, numbers 2n and 2n + 1.

a. Draw the portion of the state space for states 1 to 15.

b. Suppose the goal state is 11. List the order in which nodes will be visited for breadth- first search, depth-limited search with limit 3, and iterative deepening search.

c. Would bidirectional search be appropriate for this problem? If so, describe in detail how it would work.

d. What is the branching factor in each direction of the bidirectional search?

e. Does the answer to (c) suggest a reformulation of the problem that would allow you to solve the problem of getting from state I to a given goal state with almost no search?

a. Draw the portion of the state space for states 1 to 15.

b. Suppose the goal state is 11. List the order in which nodes will be visited for breadth- first search, depth-limited search with limit 3, and iterative deepening search.

c. Would bidirectional search be appropriate for this problem? If so, describe in detail how it would work.

d. What is the branching factor in each direction of the bidirectional search?

e. Does the answer to (c) suggest a reformulation of the problem that would allow you to solve the problem of getting from state I to a given goal state with almost no search?

We mentioned iterative lengthening search, an iterative analog of uniform cost search. The idea is in use increasing limits on path cost. If a node is generated whose path cost exceeds the current limit, it is immediately discarded, for each new iteration the limit is set to the lowest path cost of any node discarded in the previous iteration.

a. Show that this algorithm is optimal for general path costs.

b. Consider a uniform tree with branching factor b, solution depth d. and unit step costs. How much iteration will iterative lengthening require?

c. Now consider step costs drawn from the continuous range [0. 1] with a minimum positive cost. How much iteration is required in the worst case?

d. Implement the algorithm and apply it to instances of the 8-puzzle and traveling salesperson problems. Compare the algorithm’s performance to that of uniform-cost search, and comment on your results.

a. Show that this algorithm is optimal for general path costs.

b. Consider a uniform tree with branching factor b, solution depth d. and unit step costs. How much iteration will iterative lengthening require?

c. Now consider step costs drawn from the continuous range [0. 1] with a minimum positive cost. How much iteration is required in the worst case?

d. Implement the algorithm and apply it to instances of the 8-puzzle and traveling salesperson problems. Compare the algorithm’s performance to that of uniform-cost search, and comment on your results.

Prove that uniform-cost search and breadth-first search with constant step costs are optimal when used with the GRAPH-SEARCH algorithm. Show a state space with constant step costs in which GRAPH-SEARCH using iterative deepening finds a suboptimal solution.

Describe a state space iii which iterative deepening search performs much worse than depth-first search (for example. O(n2) vs. O(n)).

Write a program that will take as input two Web page URLs and find a path of links from one to the other. What is an appropriate search strategy is bidirectional search a good idea? Could a search engine be used to implement a predecessor function?

We said that we would not consider problems with negative path costs. In this exercise, we explore this in more depth.

a. Suppose that actions can have arbitrarily large negative costs; explain why this possibility would force any optimal algorithm to explore the entire state space.

b. Does it help if we insist that step costs must be greater than or equal to some negative constant c? Consider both trees and graphs.

c. Suppose that there is a set of operators that form a loop, so that executing the set in some order results in no net change to the state. If all of these operators have negative cost what does this imply about the optimal behavior for an agent in such an environment?

d. One can easily imagine operators with high negative cost, even in domains such as route finding. For example, some stretches of road might have such beautiful scenery as to far outweigh the normal costs in terms of time and fuel. Explain, in precise terms, within the context of state-space search, why humans do not drive round scenic loops indefinitely, and explain how to define the state space and operators for route finding so that artificial agents can also avoid looping.

e. Can you think of a real domain in which step costs are such as to cause looping?

a. Suppose that actions can have arbitrarily large negative costs; explain why this possibility would force any optimal algorithm to explore the entire state space.

b. Does it help if we insist that step costs must be greater than or equal to some negative constant c? Consider both trees and graphs.

c. Suppose that there is a set of operators that form a loop, so that executing the set in some order results in no net change to the state. If all of these operators have negative cost what does this imply about the optimal behavior for an agent in such an environment?

d. One can easily imagine operators with high negative cost, even in domains such as route finding. For example, some stretches of road might have such beautiful scenery as to far outweigh the normal costs in terms of time and fuel. Explain, in precise terms, within the context of state-space search, why humans do not drive round scenic loops indefinitely, and explain how to define the state space and operators for route finding so that artificial agents can also avoid looping.

e. Can you think of a real domain in which step costs are such as to cause looping?

Consider the sensor less, two-location vacuum world under Murphy’s Law. Draw the belief state space reachable from the initial belief state {1, 2, 3, 4, 5, 6, 7, 8), and explain why the problem is unsolvable. Show also that if the world is fully observable then there is a solution sequence for each possible initial state.

Trace the operation of A* search applied to the problem of getting to Bucharest from Lugoj using the straight line distance heuristic. That is, show the sequence of nodes that the algorithm will consider and the f, y, and h score for each node.

The heuristic path algorithm is a best-first search in which the objective function is f(n) = (2 – w) g(n) + wh(n). For what values of w is this algorithm guaranteed o be optimal? (You may assume that h is admissible.) What kind of search does this perform when w = 0? When w = 1? When w = 2?

Prove each of the following statements:

a. Breadth-first search is a special case of uniform-cost search.

b. Breadth-first search, depth-first search, and uniform-cost search are special cases of best-first search.

c. Uniform-cost search is a special case of A* search.

a. Breadth-first search is a special case of uniform-cost search.

b. Breadth-first search, depth-first search, and uniform-cost search are special cases of best-first search.

c. Uniform-cost search is a special case of A* search.

Devise a state space in which A* using GRAPH-SEARCH returns a suboptimal solution with an h(n) function that is admissible but inconsistent.

We saw that the straight-line distance heuristic leads greedy best-first search astray on the problem of going from lasi to Fagaras. However, the heuristic is perfect on the opposite problem: going from Fagaras to lasi. Are there problems for which the heuristic is misleading in both directions?

Invent a heuristic function for the 8-puzzle that sometimes overestimates, and show how it can lead to a suboptimal solution on a particular problem. (You can use a computer to help if you want.) Prove that, if h never overestimates by more than c, a using h returns a solution whose cost exceeds that of the optimal solution by no more than c.

Prove that if a heuristic is consistent, it must be admissible. Construct an admissible heuristic that is not consistent.

The traveling salesperson problem (TSP) can be solved via the minimum spanning tree (MST) heuristic, which is used to estimate the cost of completing a tour, given that a partial tour has already been constructed. The MST cost of a set of cities is the smallest sum of the link costs of any tree that connects all the cities.

a. Show how this heuristic can be derived from a relaxed version of the TSR

b. Show that the MST heuristic dominates straight-line distance.

c. Write a problem generator for instances of the TSP where cities are represented by random points in the unit square.

d. Find an efficient algorithm in the literature for constructing the MST, and use it with an admissible search algorithm to solve instances of the TSP.

a. Show how this heuristic can be derived from a relaxed version of the TSR

b. Show that the MST heuristic dominates straight-line distance.

c. Write a problem generator for instances of the TSP where cities are represented by random points in the unit square.

d. Find an efficient algorithm in the literature for constructing the MST, and use it with an admissible search algorithm to solve instances of the TSP.

We defined the relaxation of the 8-puzzle in which a tile can move from square A to square B if B is blank. The exact solution of this problem defines Gaschnig’s heuristic (Gaschnig, 1979). Explain why Gaschnig’s heuristic is at least as accurate as (misplaced tiles), and show cases where it is more accurate than both h1 and h2 (Manhattan distance). Can you suggest a way to calculate Gaschnig’s heuristic efficiently?

Give the name of the algorithm those results from each of the following special cases:

a. Local beam search with k = 1.

b. Local beam search with one initial state and no limit on the number of states retained.

c. Simulated annealing with T = 0 at all times (and omitting the termination test).

d. Genetic algorithm with population size N = 1.

a. Local beam search with k = 1.

b. Local beam search with one initial state and no limit on the number of states retained.

c. Simulated annealing with T = 0 at all times (and omitting the termination test).

d. Genetic algorithm with population size N = 1.

Sometimes there is no good evaluation function for a problem, but there is a good comparison method: a way to tell whether one node is better than another, without assigning numerical values to either. Show that this is enough to do a best-first search. Is there an analog of A*?

Relate the time complexity of LRTA* to its space complexity.

Suppose that an agent is in a 3 x 3 maze environment like the one shown in Figure. The agent knows that its initial location is (1, 1), that the goal is at (3, 3), and that the four actions Up, Down, Left, Right have their usual effects unless blocked by a wall. The agent does not know where the internal walls are. In any given state, the agent perceives the set of legal actions; it can also tell whether the state is one it has visited before or a new state.

a. Explain how this online search problem can be viewed as an offline search in belief state space, where the initial belief state includes all possible environment configurations. How large is the initial belief state? How large is the space of belief states?

b. How many distinct percepts are possible in the initial state?

c. Describe the first few branches of a contingency plan for this problem. How large (roughly) is the complete plan?

Notice that this contingency plan is a solution for every possible environment fitting the given description. Therefore, interleaving of search and execution is not strictly necessary even in unknownenvironments.

a. Explain how this online search problem can be viewed as an offline search in belief state space, where the initial belief state includes all possible environment configurations. How large is the initial belief state? How large is the space of belief states?

b. How many distinct percepts are possible in the initial state?

c. Describe the first few branches of a contingency plan for this problem. How large (roughly) is the complete plan?

Notice that this contingency plan is a solution for every possible environment fitting the given description. Therefore, interleaving of search and execution is not strictly necessary even in unknownenvironments.

In this exercise, we will explore the use of local search methods to solve TSPs of the type defined in Exercise 4.8.

a. Devise a hill-climbing approach to solve TSPs. Compare the results with optimal solutions obtained via the A* algorithm with the MST heuristic (Exercise 4.8).

a. Devise a hill-climbing approach to solve TSPs. Compare the results with optimal solutions obtained via the A* algorithm with the MST heuristic (Exercise 4.8).

In this exercise, we will examine hill climbing in the context of robot navigation, using the environment in Figure as an example.

a. Repeat Exercise 3.16 using hill climbing. Does your agent ever get stuck in a local minimum? Is it possible for it to get stuck with convex obstacles?

b. Construct a non-convex polygonal environment in which the agent gets stuck.

c. Modify the hill-climbing algorithm so that, instead of doing a depth-i search to decide where to go next, it does a depth-k search. It should find the best k-step path and do one step along it, and then repeat the process.

d. Is there some k for which the new algorithm is guaranteed to escape from localminima?

a. Repeat Exercise 3.16 using hill climbing. Does your agent ever get stuck in a local minimum? Is it possible for it to get stuck with convex obstacles?

b. Construct a non-convex polygonal environment in which the agent gets stuck.

c. Modify the hill-climbing algorithm so that, instead of doing a depth-i search to decide where to go next, it does a depth-k search. It should find the best k-step path and do one step along it, and then repeat the process.

d. Is there some k for which the new algorithm is guaranteed to escape from localminima?

Compare the performance of A and RBFS on a set of randomly generated problems in the 8-puzzle (with Manhattan distance) and TSP (with MST—see Exercise 4.8) domains. Discuss your results. What happens to the performance of RBFS when a small random number is added to the heuristic values in the 8-puzzle domain?

Define in your own words the terms constraint satisfaction problem, constraint, backtracking search, arc consistency, back jumping and mm-conflicts.

How many solutions are there for the map-coloring problem inFigure?

Explain why it is a good heuristic to choose the variable that is most constrained, but the value that is 1act constraining in a CSP search

Consider the problem of constructing (not solving) crossword puzzles:5 fitting words into a rectangular grid. The grid, which is given as part of the problem, specifics which square are blank and which are shaded. Assume that a list of words (i.e., a dictionary) is provided and that the task is to fill in the blank squares using any subset of the list. Formulate this problem precisely in two ways:

a. As a general search problem. Choose an appropriate search algorithm, and specify a heuristic function, if you think one is needed. Is it better to fill in blanks one letter at a time or one word at a time?

b. As a constraint satisfaction problem. Should the variables be words or letters? Which formulation do you think will be better? Why?

a. As a general search problem. Choose an appropriate search algorithm, and specify a heuristic function, if you think one is needed. Is it better to fill in blanks one letter at a time or one word at a time?

b. As a constraint satisfaction problem. Should the variables be words or letters? Which formulation do you think will be better? Why?

Give precise formulations for each of the following as constraint satisfaction problems:

a. Rectilinear floor-planning: find non-overlapping places in a large rectangle for a number of smaller rectangles.

b. Class scheduling: There is a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots for classes. Each professor has a set of classes that he or she can teach.

a. Rectilinear floor-planning: find non-overlapping places in a large rectangle for a number of smaller rectangles.

b. Class scheduling: There is a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots for classes. Each professor has a set of classes that he or she can teach.

Solve the crypt arithmetic problem in Figure by hand, using backtracking, forward checking, and the MRV and least-constraining-valueheuristics.

Use the AC-3 algorithm to show that arc consistency is able to detect the inconsistency of the partial assignment {WA = red, V = blue} for the problem shown inFigure.

What is the worst-case complexity of running AC-3 on a tree-structured CSP?

AC-3 puts back on the queue every arc (Xk, Xi) whenever any value is deleted from the domain of Xi, even if each value of Xk is consistent with several remaining values of X. Suppose that, for every arc (Xk, Xi), we keep track of the number of remaining values of Xk that are consistent with each value of Xk. Explain how to update these numbers efficiently and hence show that arc consistency can he enforced in total time O (n2d2).

Show how a single ternary constraint such as “A + B = C” can be turned into three binary constraints by using an auxiliary variable. You may assume finite domains. Next, show how constraints with more than three variables can be treated similarly. Finally, show how unary constraints can be eliminated by altering the domains of variables. This completes the demonstration that any CSP can be transformed into a CSP with only binary constraints.

Suppose that a graph is known to have a cycle cut set of no more than k nodes. Describe a simple algorithm for finding a minimal cycle cut set whose runtime is not much more than Q(nk) for a CSP with n variables. Search the literature for methods for finding approximately minimal cycle cut sets in time that is polynomial in the size of the cut set. Does the existence of such algorithms make the cycle cut set method practical?

Consider the following logic puzzle: In five houses, each with a different color, live 5 persons of different nationalities, each of whom prefer a different brand of cigarette, a different drink, and a different pet. Given the following facts, the question to answer is “Where does the zebra live, and in which house do they drink water?” The Englishman lives in the red house. The Spaniard owns the dog. The Norwegian lives in the first house on the left. Kools are smoked in the yellow house. The man who smokes Chesterfields lives in the house next to the man with the fox. The Norwegian lives next to the blue house. The Winston smoker owns snails. The Lucky Strike smoker drinks orange juice. The Ukrainian drinks tea. The Japanese smokes Parliaments. Kools are smoked in the house next to the house where the horse is kept. Coffee is drunk in the green house. The Green house is immediately to the right (your right) of the ivory house. Milk is drunk in the middle house. Discuss different representations of this problem as a CSP. Why would one prefer one representation over another?

This problem exercises the basic concepts of game playing, using tic-tac-toe (noughts and crosses) as an example. We define Xn as the number of rows, columns, or diagonals with exactly n X’s and no O’s Similarly, On is the number of rows, columns, or diagonals with just n O’s. The utility function assigns + 1 to any position with X3 = 1 and – 1 to any position with O3 = 1. All other terminal positions have utility 0. For non-terminal positions, we use a linear evolution function defined as Eval(s) = 3X2(s) + X1 (s) – (3O2(s) + O1(s)).

a. Approximately how many possible games of tic-tac-toe arc there?

b. Show the whole game tree starting from an empty board down to depth 2 (i.e., one X and one O on the board), taking symmetry into account.

c. Mark on your tree the evaluations of all the positions at depth 2.

d. Using the mini max algorithm, mark on your tree the backed-up values for the positions at depths 1 and 0, and use those values to choose the best starting move.

e. Circle the nodes at depth 2 that would not be evaluated if alpha—beta pruning were applied, assuming the nodes are generated in the optimal order for alpha—beta pruning.

a. Approximately how many possible games of tic-tac-toe arc there?

b. Show the whole game tree starting from an empty board down to depth 2 (i.e., one X and one O on the board), taking symmetry into account.

c. Mark on your tree the evaluations of all the positions at depth 2.

d. Using the mini max algorithm, mark on your tree the backed-up values for the positions at depths 1 and 0, and use those values to choose the best starting move.

e. Circle the nodes at depth 2 that would not be evaluated if alpha—beta pruning were applied, assuming the nodes are generated in the optimal order for alpha—beta pruning.

Prove the following assertion: for every game tree, the utility obtained by MAX using mini max decisions against a suboptimal MIN will be never be lower than the utility obtained playing against an optimal MIN. Can you come up with a game tree in which MAX can do still better using a suboptimal strategy against a suboptimal MIN?

Consider the two-player game described in Figure.

a. Draw the complete game tree, using the following conventions:

• Write each state as (SA, SB) where SA and 5B denote the token locations.

• Put each terminal state in square boxes and write its game value in a circle.

• Put loop states (states that already appear on the path to the root) in double square boxes. Since it is not clear how to assign values to loop states, annotate each with a “?” in a circle.

b. Now mark each node with its backed-up mini max value (also in a circle). Explain how you handled the “?” values and why.

c. Explain why the standard mini max algorithm would fail on this game tree and briefly sketch how you might fix it, drawing on your answer to (b). Does your modified algorithm give optimal decisions for all games with loops?

d. This 4-square game can be generalized to n squares for any n > 2. Prove that A wins if n is even and loses if n isodd.

a. Draw the complete game tree, using the following conventions:

• Write each state as (SA, SB) where SA and 5B denote the token locations.

• Put each terminal state in square boxes and write its game value in a circle.

• Put loop states (states that already appear on the path to the root) in double square boxes. Since it is not clear how to assign values to loop states, annotate each with a “?” in a circle.

b. Now mark each node with its backed-up mini max value (also in a circle). Explain how you handled the “?” values and why.

c. Explain why the standard mini max algorithm would fail on this game tree and briefly sketch how you might fix it, drawing on your answer to (b). Does your modified algorithm give optimal decisions for all games with loops?

d. This 4-square game can be generalized to n squares for any n > 2. Prove that A wins if n is even and loses if n isodd.

Develop a formal proof of correctness for alpha-beta pruning. To do this, consider the situation shown in Figure. The question is whether to prune node nj, which is a max- node and a descendant of node n1. The basic idea is to prune it if and only if the mini max value of n can be shown to be independent of the value of nj.

a. The value of n1 is given by n1 = (n2, n21, . . . n21r2) find a similar expression for n2 and hence an expression for n1 in terms of nj.

b. Let li be the minimum (or maximum) value of the nodes to the left of node ni at depth i, whose mini max value is already known. Similarly, let ri be the minimum (or maximum) value of the unexplored nodes to the right of ni at depth i. Rewrite your expression for ni in terms of the li and ri values.

c. Now reformulate the expression to show that in order to affect n1, nj must not exceed a certain bound derived from the li values.

d. Repeat the process for the case where nj is amm-node.

a. The value of n1 is given by n1 = (n2, n21, . . . n21r2) find a similar expression for n2 and hence an expression for n1 in terms of nj.

b. Let li be the minimum (or maximum) value of the nodes to the left of node ni at depth i, whose mini max value is already known. Similarly, let ri be the minimum (or maximum) value of the unexplored nodes to the right of ni at depth i. Rewrite your expression for ni in terms of the li and ri values.

c. Now reformulate the expression to show that in order to affect n1, nj must not exceed a certain bound derived from the li values.

d. Repeat the process for the case where nj is amm-node.

Prove that with a positive linear transformation of leaf values (i.e., transforming a value x to ax + b where a > 0), the choice of move remains unchanged in a game tree, even when there are chance nodes.

Consider the following procedure for choosing moves in games with chance nodes;

• Generate some die-roll sequences (say, 50) down to a suitable depth (say, 8).

• With known die rolls, the game tree becomes deterministic. For each die-roll sequence, solve the resulting deterministic game tree using alpha—beta.

• Use the results to estimate the value of each move and to choose the best, will this procedure work well? Why (not)?

• Generate some die-roll sequences (say, 50) down to a suitable depth (say, 8).

• With known die rolls, the game tree becomes deterministic. For each die-roll sequence, solve the resulting deterministic game tree using alpha—beta.

• Use the results to estimate the value of each move and to choose the best, will this procedure work well? Why (not)?

Describe or implement state descriptions, move generators, terminal tests, utility functions, and evaluation functions for one or more of the following games: Monopoly, Scrabble, bridge (assuming a given contract), and poker (choose your favorite variety).

Consider carefully the interplay of chance events and partial information in each of the games in Exercise 6.10.

a. For which is the standard expectiminimax model appropriate? Implement the algorithm and run it in your game-playing agent, with appropriate modifications to the game- playing environment.

b. For which would the scheme describe in Exercise 6.8 be appropriate?

c. Discuss how you might deal with the fact that in some of the games the players do not have the same knowledge of the current state.

a. For which is the standard expectiminimax model appropriate? Implement the algorithm and run it in your game-playing agent, with appropriate modifications to the game- playing environment.

b. For which would the scheme describe in Exercise 6.8 be appropriate?

c. Discuss how you might deal with the fact that in some of the games the players do not have the same knowledge of the current state.

The mini max algorithm assumes that players take turns moving, but in card games such as whist and bridge, the winner of the previous trick plays first on the next trick.

a. Modify the algorithm to work properly for these games. You may assume that a function WINNER(s) is available that reports which player won the trick just completed (if any).

b. Draw the game tree for the first pair of hands shown.

a. Modify the algorithm to work properly for these games. You may assume that a function WINNER(s) is available that reports which player won the trick just completed (if any).

b. Draw the game tree for the first pair of hands shown.

The Chinook checkers program makes extensive use of endgame databases, which provide exact values for every position with eight or fewer pieces. How might such databases be generated efficiently?

Discuss how well the standard approach to game playing would apply to games such as tennis, pool, and croquet, which take place in a continuous physical state space.

Describe how the mini max and alpha—beta algorithms change for two-player, nonzero-sum games in which each player has his or her own utility function. You may assume that each player knows the other’s utility function. if there are no constraints on the two terminal utilities, is it possible for any node to be pruned by alpha—beta?

Suppose you have a chess program that can evaluate 1 million nodes per second. Decide on a compact representation of a game state for storage in a transposition table. About how many entries can you fit in a 500MB in-memory table’? Will that be enough for the three minutes of search allocated for one move? How many table lookups can you do in the time it would take to do one evaluation? Now suppose the transposition table is larger than can fit in memory. About how many evaluations could you do in the time it takes to do one disk seek with standard disk hardware?

Describe the wumpus world according to the properties of task environments listed.

Describe the wumpus world according to the properties of task environments listed.

Consider the problem of deciding whether a propositional logic sentence is true in a given model.

a. Write a recursive algorithm PL-TRUE? (s m) that returns true if and only if the sentence s is true in the model in (where in assigns a truth value for every symbol in s). The algorithm should run in time linear in the size of the sentence. (Alternatively, use a version of this function from the online code repository.)

b. Give three examples of sentences that can be determined to be true or false in a partial model that does not specify a truth value for some of the symbols.

c. Show that the truth value (if any) of a sentence in a partial model cannot be determined efficiently in general.

d. Modify your PL-TRUE algorithm so that it can sometimes judge truth from partial models, while retaining its recursive structure and linear runtime. Give three examples of sentences whose truth in a partial model is not detected by your algorithm.

e. Investigate whether the modified algorithm makes TT-ENTAILS more efficient.

a. Write a recursive algorithm PL-TRUE? (s m) that returns true if and only if the sentence s is true in the model in (where in assigns a truth value for every symbol in s). The algorithm should run in time linear in the size of the sentence. (Alternatively, use a version of this function from the online code repository.)

b. Give three examples of sentences that can be determined to be true or false in a partial model that does not specify a truth value for some of the symbols.

c. Show that the truth value (if any) of a sentence in a partial model cannot be determined efficiently in general.

d. Modify your PL-TRUE algorithm so that it can sometimes judge truth from partial models, while retaining its recursive structure and linear runtime. Give three examples of sentences whose truth in a partial model is not detected by your algorithm.

e. Investigate whether the modified algorithm makes TT-ENTAILS more efficient.

Prove each of the following assertions:

a. α is valid if and only if True | = α.

b. For any a, False | = α.

c. α | = β if and only if the sentence (α → β) is valid.

d. α ≡ β if and only if the sentence (α ↔ β) is valid.

e. α | = β if and only if the sentence (α ^ β) is un-satisfiable

a. α is valid if and only if True | = α.

b. For any a, False | = α.

c. α | = β if and only if the sentence (α → β) is valid.

d. α ≡ β if and only if the sentence (α ↔ β) is valid.

e. α | = β if and only if the sentence (α ^ β) is un-satisfiable

Consider a vocabulary with only four propositions, A, B, C, and D. How many models are there for the following sentences?

a. (A Λ AB) V (B Λ C)

b. A V B

c. A ↔ B ↔ C

a. (A Λ AB) V (B Λ C)

b. A V B

c. A ↔ B ↔ C

We have defined four different binary logical connectives.

a. Are there any others that might be useful?

b. How many binary connectives can there be?

c. Why are some of them not very useful?

a. Are there any others that might be useful?

b. How many binary connectives can there be?

c. Why are some of them not very useful?

Using a method of your choice, verify each of the equivalences inFigure.

Decide whether each of the following sentences is valid, un-satisfiable, or neither. Verify your decisions using truth tables or the equivalence rules of Figure.

a. Smoke ↔ Smoke

b. Smoke → Fire

c. (Smoke → Fire) → (—Smoke → –––Fire)

d. Smoke V Fire V —Fire

e. ((Smoke Λ Heat) → Fire) ↔ ((Smoke → Fire) V (Heat → Fire))

f. (Smoke → Fire) → ((Smoke Λ heat) → Fire)

g. Big V Dumb V (Big → Dumb)

h. (Big Λ Dumb) V ––Dumb

a. Smoke ↔ Smoke

b. Smoke → Fire

c. (Smoke → Fire) → (—Smoke → –––Fire)

d. Smoke V Fire V —Fire

e. ((Smoke Λ Heat) → Fire) ↔ ((Smoke → Fire) V (Heat → Fire))

f. (Smoke → Fire) → ((Smoke Λ heat) → Fire)

g. Big V Dumb V (Big → Dumb)

h. (Big Λ Dumb) V ––Dumb

(Adapted from Bar wise and Etchemendy (1993)) Given the following, can you prove that the unicorn is mythical? How about magical? Horned? If the unicorn is mythical, then it is immortal, hut if it is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical if it is horned.

Any propositional logic sentence is logically equivalent to the assertion that each possible world in which it would be false is not the case. From this observation, prove that any sentence can be written in CNF.

Minesweeper, the well-known computer game, is closely related to the wumpus world. A minesweeper world is a rectangular grid of N squares with M invisible mines scattered among them. Any square may be probed by the agent; instant death follows if a mine is probed. Minesweeper indicates the presence of mines by revealing, in each probed square, the number of mines that are directly or diagonally adjacent. The goal is to have probed every un-mined square.

a. Let Xi,j be true ill square [i, j] contains a mine. Write down the assertion that there are exactly two mines adjacent to [1, 1] as a sentence involving some logical combination of Xi,j propositions.

b. Generalize your assertion from (a) by explaining how to construct a CNF sentence asserting that k of ii neighbors contain mines.

c. Explain precisely how an agent can use DPLL to prove that a given square does (or does riot) contain a mine, ignoring the global constraint that there ate exactly M mines in all.

d. Suppose that the global constraint is constructed via your method from part (b). How does the number of clauses depend on M and N? Suggest a way to modify DPLL so that the global constraint does not need to be represented explicitly.

e. Are any conclusions derived by the method in part (c) invalidated when the global constraint is taken into account?

f. Give examples of configurations of probe values that induce long-range dependencies such that the contents of a given un-probed square would give information about the contents of a far-distant square

a. Let Xi,j be true ill square [i, j] contains a mine. Write down the assertion that there are exactly two mines adjacent to [1, 1] as a sentence involving some logical combination of Xi,j propositions.

b. Generalize your assertion from (a) by explaining how to construct a CNF sentence asserting that k of ii neighbors contain mines.

c. Explain precisely how an agent can use DPLL to prove that a given square does (or does riot) contain a mine, ignoring the global constraint that there ate exactly M mines in all.

d. Suppose that the global constraint is constructed via your method from part (b). How does the number of clauses depend on M and N? Suggest a way to modify DPLL so that the global constraint does not need to be represented explicitly.

e. Are any conclusions derived by the method in part (c) invalidated when the global constraint is taken into account?

f. Give examples of configurations of probe values that induce long-range dependencies such that the contents of a given un-probed square would give information about the contents of a far-distant square

This exercise looks into the relationship between clauses and implication sentences.

a. Show that the clause (—P1 V . . . V —Pm VQ) iS logically equivalent to the implication sentence (P1 Λ . . . Λ Pm) Q.

b. Show that every clause (regardless of the number of positive literals) can be written in the form (P1 Λ. . . Λ Pm) (Q1 V . V Qn), where the Ps and Qs are proposition symbols A knowledge base consisting of such sentences IS in implicative normal form or Kowalski form. c. Write down the full resolution rule for sentences in implicative normal form.

a. Show that the clause (—P1 V . . . V —Pm VQ) iS logically equivalent to the implication sentence (P1 Λ . . . Λ Pm) Q.

b. Show that every clause (regardless of the number of positive literals) can be written in the form (P1 Λ. . . Λ Pm) (Q1 V . V Qn), where the Ps and Qs are proposition symbols A knowledge base consisting of such sentences IS in implicative normal form or Kowalski form. c. Write down the full resolution rule for sentences in implicative normal form.

In this exercise, you will design more of the circuit-based wumpus agent.

a. Write an equation, similar to Equation (7.4), for the Arrow proposition, which should be true when the agent still has an arrow. Draw the corresponding circuit.

b. Repeat part (a) for Facing Right, using Equation (7.5) as a model.

c. Create versions of Equations 7.7 and 7.8 for finding the wumpus, and draw the circuit.

a. Write an equation, similar to Equation (7.4), for the Arrow proposition, which should be true when the agent still has an arrow. Draw the corresponding circuit.

b. Repeat part (a) for Facing Right, using Equation (7.5) as a model.

c. Create versions of Equations 7.7 and 7.8 for finding the wumpus, and draw the circuit.

Discuss what is meant by optimal behavior in the wumpus world. Show that our definition of the PL-WUMPUS-AGENT is not optimal, and suggest ways to improve it.

Extend PL-WUMPUS-AGENT so that it keeps track of all relevant facts within the knowledge base.

How long does it take to prove KB | = α using DPLL when α is a literal already contained in KB? Explain.

A logical knowledge base represents the world using a set of sentences with no explicit structure. An analogical representation, on the other hand, has physical structure that corresponds directly to the structure of the thing represented. Consider a road map of your country as an analogical representation of facts about the country. The two-dimensional structure of the map corresponds to the two-dimensional surface of the area.

a. Give five examples of symbols in the map language.

b. An explicit sentence is a sentence that the creator of the representation actually writes down. An implicit sentence is a sentence that results from explicit sentences because of properties of the analogical representation. Give three examples each of implicit and explicit sentences in the map language.

c. Give three examples of facts about the physical structure of your country that cannot be represented in the map language.

d. Give two examples of facts that are much easier to express in the map language than in first-order logic.

e. Give two other examples of useful analogical representations. What are the advantages and disadvantages of each of these languages?

a. Give five examples of symbols in the map language.

b. An explicit sentence is a sentence that the creator of the representation actually writes down. An implicit sentence is a sentence that results from explicit sentences because of properties of the analogical representation. Give three examples each of implicit and explicit sentences in the map language.

c. Give three examples of facts about the physical structure of your country that cannot be represented in the map language.

d. Give two examples of facts that are much easier to express in the map language than in first-order logic.

e. Give two other examples of useful analogical representations. What are the advantages and disadvantages of each of these languages?

Consider a knowledge base containing just two sentences: P(α) and P(h). Does this knowledge base entail V x P(x)? Explain your answer in terms of models.

Is the sentence Э x, y x = y valid? Explain.

Write down a logical sentence such that every world in which it is true contains exactly one object.

Consider a symbol vocabulary that contains c constant symbols, predicate symbols of each arity k, and fk function symbols of each arity k, where 1 < k < A. Let the domain size be fixed at D. For any given interpretation—model combination, each predicate or function symbol is mapped onto a relation or function, respectively, of the same arity. You may assume that the functions in the model allow some input tuples to have no value for the function (i.e., the value is the invisible object). Derive a formula for the number of possible interpretation— model combinations for a domain with D elements. Don’t worry about eliminating redundant combinations.

Represent the following sentences in first-order logic, using a consistent vocabulary (which you must define):

a. Some students took French in spring 2001.

b. Every student who takes French passes it.

c. Only one student took Greek in spring 2001.

d. The best score in Greek is always higher than the best score in French.

e. Every person who buys a policy is smart.

f. No person buys an expensive policy.

g. There is an agent who sells policies only to people who are not insured.

h. There is a barber who shaves all men in town who do not shave themselves.

i. A person born in the UK, each of whose parents is a UK citizen or a UK resident, is a UK citizen by birth.

j. A person born outside the UK, one of whose parents is a UK citizen by birth, is a UK citizen by descent.

k. Politicians can fool some of the people all of the time, and they can fool all of the people some of the time, but they can’t fool all of the people all of the time.

a. Some students took French in spring 2001.

b. Every student who takes French passes it.

c. Only one student took Greek in spring 2001.

d. The best score in Greek is always higher than the best score in French.

e. Every person who buys a policy is smart.

f. No person buys an expensive policy.

g. There is an agent who sells policies only to people who are not insured.

h. There is a barber who shaves all men in town who do not shave themselves.

i. A person born in the UK, each of whose parents is a UK citizen or a UK resident, is a UK citizen by birth.

j. A person born outside the UK, one of whose parents is a UK citizen by birth, is a UK citizen by descent.

k. Politicians can fool some of the people all of the time, and they can fool all of the people some of the time, but they can’t fool all of the people all of the time.

Join SolutionInn Study Help for

1 Million+ Textbook Solutions

Learn the step-by-step answers to your textbook problems, just enter our Solution Library containing more than 1 Million+ textbooks solutions and help guides from over 1300 courses.

24/7 Online Tutors

Tune up your concepts by asking our tutors any time around the clock and get prompt responses.