CS 171 - First Programming Project

CS 171 Introduction to Artificial Intelligence

First Programming Project

Your assignment is to write a computer program that plays Dots and Boxes, which we will call Dox. If you haven't played this game a hundred times on napkins at restaurants while waiting for your dinner, you might want to get in some practice. The program can be written in any language that can be run on the Windows computers in the ICS 364 lab. (If your language isn't Java, C, C++, C#, or Python, you should check first with Prof. Frost, just to be safe.) The program will run from the command line, and will not have a graphical user interface. The program will use minimax and will be able to use alpha-beta pruning.

Command line interface

We will run your program on the command line, e.g.

java Dox 3x3 A XXXX..X.XXX. AB.. 3 Y 1

for a Java program, or

Dox 3x3 A XXXX..X.XXX. AB.. 3 Y 1

for a C program.

Your program should read in seven parameters from the command line, separated by spaces:

3x3 — the number of rows (first) and columns (second) of dots, with an x inbetween.
A — the player whose turn it is, A or B
XXXX..X.XXX. — a string in which X indicates a line that has been drawn, and . indicates a space between two dots. The locations are indicated in the following order: horizontal locations, top to bottom, left to right, then vertical locations, left to right, top to bottom. For instance, with a 3 x 3 board, with asterisks indicating dots, the line locations are

* 0 * 1 *
6 8 10
* 2 * 3 *
7 9 11
* 4 * 5 *
AB.. — a string indicating which boxes belong to which player, A, B, or . meaning the box's walls are not complete. For instance, with a 3 x 3 board, with asterisks indicating dots, the box locations are

* * *
0 1
* * *
2 3
* * *
3 — a number indicating the maximum number of plies the algorithm should look ahead.
Y — Y indicates that alpha-beta pruning should be used, N means don't use alpha-beta
1 — indicates which board evaluation heuristic shold be used. 1 is a supplied simpleBoardEval method, and 2 is one that you write.

Using these parameters, your Dox program should select a move and print it on the console (standard output). (Your program doesn't have to play a full game, it need only select a move.)

Your program

The programming assignment is:

Implement a minimax-based routine that employs alpha-beta pruning when (and only when) instructed to do so on the command line. Note that your AI should always return the same move with and without alpha-beta pruning. The method should use either simpleBoardEval() or customBoardEval(), as indicated on the command line. The method should do minimax search to the specified depth (or perhaps less, when a final state is reached).
Write a customBoardEval() that is superior to simpleBoardEval().

Starter code, in Java, is provided in Dox.java and DoxBoard.java. If you are not programming in Java, you may still find this code worth utilizing.

Later in the quarter, we will have a tournament, in which all the Dox programs compete. (You can update your code for the tournament.)

Your report

You will also write a report, the quality of which will be a significant factor in your score for the project. It should contain the following information:

A discussion of the status of your implementation. If there are any known bugs, or parts of the assignment you didn't get working at all, list those. Does your implementation throw any Exceptions or produce other errors as it runs (it shouldn't)? Does using alpha-beta search change the choice of moves your AI makes (it shouldn't)?
Description of your customBoardEval() method. Reference any sources or ideas or inspiration you used. You are welcome to take advantage of others' ideas, but you must give them credit and not directly copy any source code.
The results of a set of experiments you have conducted. You should try to answer, or at least discuss, the following two questions about time and quality of play:
1. What are the trade-offs between more plies and the better board evaluation method?
2. How much, if any, does alpha-beta help?
Provide specific results, numbers, and cogent analysis.

How to turn in the project

The project is due at 11:55 pm on Sunday, Feb. 10. The project will be turned in by uploading it to the EEE DropBox "CS 171 - Proj 1".

Source code: turn in all your source code. Your source code should be at the top level, not, for instance, in a src/ subdirectory.
Executable: Dox.class, Dox.exe, or whatever. At the top level.
Project report: a .doc, .docx, .txt, or .pdf file.

Put all your files in a zip file called Dox.zip.

To evaluate your implementation, we will log onto an ICS lab Windows computer, open a command prompt window, cd to a folder containing your .unzipped files, and enter

java Dox parameters

or whatever is appropriate for your programming language. It is strongly recommended that you test your system using this same technique. Projects that work "on your machine" or "only in Eclipse" or "only if you enter something special on the command line" will not receive full credit. Projects that have missing files, or files in subfolders, will be penalized.