CSE 473 Introduction to Artificial Intelligence

Autumn 2001

 

Problem Set 2

 

Due: Oct 17, 1:30pm

 

Reading: chapter 12.

 

  1. (10 points) Write a game-playing program that does a depth-first mini-max search of a tic-tac-toe game tree.   Turn in well-documented code and a trace of your program playing against a human player.

 

  1. (5 points) Add alpha-beta pruning and report on the average impact in terms of number of game-tree nodes evaluated and CPU time on three sample games (choose different initial moves for each game).

 

  1. (2 points) Show a 2-ply game tree where alpha-beta pruning results in no savings in node evaluation for a depth-first minimax procedure.

 

  1. (3 points) How would you modify the game-tree search algorithm so that iterative deepening can result in improved alpha-beta pruning?  Explain the modification and draw an example game tree where it helps.

 

Printable copy (ps) (pdf)

 

Earlier Assignments