CISC 6525 Artificial Intelligence
Fall 2018
Assignment #3 Out: 10/22 Due: 11/5
Q1.
- Invent a heuristic function for the 8-puzzle that sometimes overestimates (i.e., it is notadmissible).
- Demonstrate (by example or mathematically) how this can sometimes lead to a suboptimal
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).
- 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 costminimum).
- Generate a large number of 8 queen problems (using random numbers), and solve themusing 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
Q3.
- explain briefly in your own words how minimax works for regular, two player, zero sum
- explain how to modify minimax to work for two player non-zero sum
- explain how to modify minimax for multi-player, non-zero sum
