CIS 730 (Introduction to Artificial Intelligence)

Fall, 2003

 

Homework Assignment 2 (Problem Set)

 

Sunday, 21 Sep 2003

Due: Wednesday, 08 October 2003 (by 5pm)

 

 

This programming assignment is designed to apply your theoretical understanding of search-based problem solving algorithms for graphs, constraint satisfaction systems, and games to the simulation of search algorithms and derivation of CSP solvers.

 

Refer to the course intro handout for guidelines on working with other students.

Note: Remember to submit your solutions in electronic form by uploading them to the Yahoo! Group ksu-cis-730_fall2003 and produce them only from your personal notes (not common work or sources other than the textbook or properly cited references).

 

 

1.       (6 points total) Minimax / Alpha-Beta Game Tree Search.  Consider this game tree:

 

 

a)       (2 points) Simulate the behavior of the minimax algorithm on the above game tree.

b)       (4 points) Simulate the behavior of minimax with alpha-beta (a-b) pruning on the above game tree.  Show your work (mark the pruned branches and number the static evaluations and all a and b inequality updates, in order).

 

 

2.       (8 points total) Monopoly.  Problems 6.10 and 6.11, p. 192 Russell and Norvig 2nd edition.

a)       (3 points) Describe a state description, move generator, terminal test, utility function, and evaluation function for Monopoly.

b)       (2 points) Is the standard expectiminimax model appropriate?  Why or why not?

c)       (3 points) Discuss how you might deal with the fact that in some aspects of Monopoly, the players do not have the same knowledge of the current state.

 

3.       (20 points total) Search.   Simulate the following heuristic search algorithms on the graph below, given in the format specified for Machine Problem 1.  Your solution must clearly show the contents of the OPEN and CLOSED lists at each step.  Refer to Section 2.2.2, p. 64-65, Principles of Artificial Intelligence [Nilsson, 1980] for this definition and to make sure you understand how the CLOSED list is maintained.

 

| This example is due to CIS730 students who came to office hours in

| Fall, 2001.

| 8 nodes in the graph, numbered 0-7

8

| Start

0

| Goal(s)

6 7

| Edge-cost adjacency matrix

* 1 2 * * * * *

2 * * 1 4 * * *

3 * * * 1 1 * *

* 1 * * * * * *

* 3 1 * * * 4 3

* * 1 * * * * *

* * * * 4 * * *

* * * * 3 * * *

| Heuristic (is this admissible?  Monotonic?)

5

4

3

3

3

2

0

0

 

a)       (4 points) depth-first search

b)       (4 points) breadth-first search

c)       (4 points) branch-and-bound

d)       (4 points) best-first (greedy)

e)       (4 points) A*

 

4.       (8 points total) Iterative Improvement Search.  Simulate the following heuristic search algorithms on the graph in the previous problem.

 

a)       (4 points) hill-climbing

b)       (4 points) beam search (w = 2)

 

5.       (8 points) Constraints and Propositional Logic.  (Answer in complete sentences.)  Describe a propositional logic representation for problems on the Analytical Reasoning section of the Law School Admission Test (LSAT) from the Law School Admission Council (LSAC):

 

 http://www.west.net/~stewart/lwfaq.htm

 

Using this representation, define a constraint satisfaction problem (CSP) specification for such problems.  How might you use a CSP solver to work LSAT problems?  Finally, what efficiencies and inefficiencies might this hypothetical system have with respect to human test-takers?  (Your answer to this last question should be in terms of whatever real-time criteria you specify and should be consistent with the actual test environment – i.e., the time limits and scoring system.)

 

 

Extra credit:

a)       (5 points) What problems arise in applying your solution to the GRE General Test Quantitative exam?  Undergraduates who have not taken a GRE General Test: you may suppose that the question is being posed with regards to the SAT Quantitative section (the Math GRE is actually easier J).

b)       (5 points) Use SML, MATLAB, or Mathematica (installed on the N227 Windows XP workstations and on the KDD Linux systems) to implement A* search.  This may be a port of your MP1-2b implementation or a new solution.

 

Class participation:

Post a single paragraph commentary on intelligent agents for the Trading Agent Competition (http://www.sics.se/tac/) in the web board.  Address specifically the supply-chain management TAC environment.  What do you think might be an effective naïve or baseline strategy.