CISC6525 Artificial Intelligence
Fall 2018
Assignment #3 Out: 10/22 Due: 11/5
Q1.
(a) Invent a heuristic function for the 8-puzzle that sometimes overestimates (i.e., it is not admissible).
(b) Demonstrate (by example or mathematically) how this can sometimes lead to a suboptimal solution.
Q2. (a) If V is list of queen positions on an 8×8 chess board, write the code to determine how many pairs of attacking queens there are. A list of queen positions is a list or string of integers between 0 and 7, e.g., 31046715, which means column 0 has a queen on row 3 and column 1 has a queen on row 1. (Any solution must have exactly 1 queen in each column, so this is an acceptable simplification).
(b) Write a program for a local beam search, that takes the beam size k as input, and that uses the heuristic developed in (a) to solve 8-queen problems. Make sure you have a termination condition, either successful (cost=0) or not (local cost minimum).
(c) Generate a large number of 8 queen problems (using random numbers), and solve them using your beam search for k=1, k=10 and k=50. Generate results that show the performance of each value of k for many examples and explain those results.
Q3.
(a) explain briefly in your own words how minimax works for regular, two player, zero sum games.
(b) explain how to modify minimax to work for two player non-zero sum games.
(c) explain how to modify minimax for multi-player, non-zero sum games.
合作：幽灵代写
