Homework 2

Game Playing/Logic

1) We looked at game playing using Chapter 6 of AIMA. Different games provide different issues for artificial intelligence researchers.

Use your book (pages 180-183) to familiarize yourself with issues in Chess and Go, and look at Sections 1.1, 2.4, and 6 of: M. Müller. Computer Go. Artificial Intelligence, 134(1-2):145-179, 2002, 668k. [ compressed ps file, 668k compressed pdf file, 592k ] (If you do not wish to, you do not have to read the entire article; read only the sections listed above.) If you cannot get the file directly from the page above, it is available through the CSI Library through Elsevier Science Direct. At our Library home page there is a link to search for periodicals and journals – search for Artificial Intelligence and you will get the correct link to download the article.

Write a discussion, or a list of points, (½ -1 page long) on the difficulties of computers solving the game Go, and the differences (from an AI researcher standpoint) between Go and other games.

2) Assume that you have the following game tree, with the max and min nodes specified as usual, and play starting with the max node.

a) Show the backed up values for each node when minimax searching (without alpha-beta pruning) is done. Which branch will max choose?

b) Show which nodes would be pruned (by circling on the graph) when minimax searching is done with alpha-beta pruning. You may use our method from class or the algorithm in your book.

c) Give a reordering for the children of the black node that would cause alpha-beta to prune more nodes. Show which nodes would be pruned in this case.

3) Think about a board game that incorporates chance and 3 or more players such as monopoly (or any similar one of your choice).

a) How can ‘states’ be described in this game?

b) What is the initial state in the game?

c) Try to describe a bit of the search tree.

d) How would possible collaboration between players cause problems in the creation of the search tree?

e) Describe what the evaluation function would depend upon.

4) Problems from AIMA: 5.5 b, 6.1 b,c,d,e, 6.2, 7.5, 7.9, 7.11 a, b