CISC 6525讲解、辅导Java/Python程序设计、讲解heuristic function、辅导C/C++语言

CISC 6525 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 8x8 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.