CSE 511A: Introduction to Artificial Intelligence

Lab 1

Due: October 14

1. In this lab you will write a computer program to play a game, dots and boxes. (http://en.wikipedia.org/wiki/Dots_and_boxes)

Starting with an empty grid of dots, players take turns, adding a single horizontal or vertical line between two unjoined adjacent dots. A player who completes the fourth side of a box earns one point and takes another turn. (The points are typically recorded by placing in the box an identifying mark of the player, such as an initial). The game ends when no more lines can be placed. The winner of the game is the player with the most points.

2. You should implement the minimax search algorithm with alpha-beta pruning, discussed in Chapter 6. You may learn and use the code at the AIMA website. (http://code.google.com/p/aima-java/). You may not use any other existing implementation of minimax or game engine.

3. Since the search tree can be very deep, you should implement the cutoff test strategy in Section 6.4. You need to design a heuristic evaluation function for a given configuration. (That’s the key for your computer player’s strength).

Try different cut-off depths and set a depth so that each move takes roughly less than five seconds on your computer.

4. Your program should have an interface for a human player to play against the computer. A graphical interface would be nice but not required. You should at least have a simple text interface that displays the current configuration and takes input from the user to specify the next line.

5. The size of the board should be a parameter in your program. For example, the user can specify the size as 2 X 2, 3 X 3, etc. To simplify your programming, you can assume the maximum size is 6 X 6.

6. Submissions:

a. Print out parts of your source code for minimax search, alpha-beta pruning, and heuristic evaluation function.

b. Print out a screenshot of a complete game playing session between a human player and computer on a 3X3 board. For each computer move, print out the Minimax-Value of the current configuration.

c. Run computer vs. computer for increasing board sizes 2X2, 3X3, 4X4, …, until the memory runs out or the running time is too longer (e.g. more than an hour) on your computer.

Give a table summarizing the results. For each board size, list: the score of player 1 (who moves first), the score of player 2, the depth of the search tree (with an empty board as the root), and the number of nodes pruned by alpha-beta pruning.

7. We will have a “dots and boxes” tournament during class on Oct 19. Your program vs. others. Bring your laptop or the executable of your program in a flash drive. Winners get extra points for this lab!