You have a 8x8 board, players take turns placing a piece on any grid. First player to get 4 in a line (either a row, or a column; diagonals are NOT counted) wins. The maximum amount of time allowed for generating the next move is 30 seconds. At the very beginning, your program should ask the user for the maximum amount time (in seconds) allowed for the computer to generate the answer and make sure that your search will stop when there's no time left. Your program should also ask the user to decide who is going to move first.

In order to make the process smooth, you are REQUIRED to use the following standard in the movement that your program will generate:

 1 2 3 4 5 6 7 8 Player vs. Opponent A - - - - - - - - 1. e5 d5 B - - O - - - - - 2. e4 e3 C - - O - - - - - 3. f4 d4 D - X O O O X - - 4. e6 e7 E - - O X X X O - 5. g4 h4 F - - X X - - - - 6. d6 d3 G - - - X - - - - 7. d2 c3 H - - - O - - - - 8. f3 b3 wins

Here is a sample program written in C.

Strategies and Other Requirements

To get a full credit, your program must satisfy the requirements listed above, and MUST use alpha-beta pruning to determine the computer's move. Note that, you will need to make some changes to the alpha-beta pruning introduced in the book. These changes include: an evaluation function so that you can evaluate non-terminal states and a cut-off test to replace the terminal test so that your program will return the best solution found so far given a specific period of time.

In general, you are allowed 5 seconds to run your algorithm, which should search at least 5 plies deep. If you use languages other than C or C++, the number of plies may be smaller. You can implement iterative deepening search with alpha-beta pruning so that your program will search as deep as possible given the fixed amount of time.

Given the same amount of time, if your terminal evaluation function is simple, then your program should be able to search deeper than one with a complex (but maybe better) terminal evaluation function. You can decide whether you want a deeper search and a simple evaluation, or a shallower search with a complex evaluation.

Your program is one player, and will attempt to defeat the human operator. Here, "X" means "computer", "O" means "human".

The program should detect when an illegal move has been entered and requires the human to re-enter a valid move, for example, trying to place on a non-empty space, or out of bounds.

Please refer to the tic-tac-toe.cc which implements MINIMAX as the base skeleton to develop the alpha-beta pruning.

A group of 2 is allowed to work on this project. You can also work individually. Your final executable program should be able to run on the computers in the CS labs. The top 3 or 4 teams will receive extra credits. All participants will earn participation credits.

How do two programs interact?

To make the interaction interface easy, your program should output what's the current choice for each step. Each program will run on one computer and the final result will be the opposite of each other. Please see the following illustration. Assume the opponent (the computer) moves first:

Computer (Opponent) running on computer 1: my movement is "e5"

 1 2 3 4 5 6 7 8 A - - - - - - - - B - - - - - - - - C - - - - - - - - D - - - - - - - - E - - - - X - - - F - - - - - - - - G - - - - - - - - H - - - - - - - - 

 My current move is: e5

 Choose your next move:

Your program running on computer 2: you will need to first input "e5", and then your program should print out the current movement after searching, for example, "d5"

 Choose your next move: e5

 1 2 3 4 5 6 7 8 A - - - - - - - - B - - - - - - - - C - - - - - - - - D - - - - X - - - E - - - - O - - - F - - - - - - - - G - - - - - - - - H - - - - - - - -

 My current move is: d5

 Choose your next move:

This process will continue until the end of the game.

How to run the tournament?

It depends on the number of groups who are willing to participate. Please let me know your decision on participation by Jun. 3rd.

Here's the strategy we used last time for small number of groups.

Student teams will be arranged into group of 3. The 3 teams will play against each other in the same group. Each match contains two games, with each team moving first. A group will play a total of 6 games. A win counts as 1 point, a draw as .5, and a loss as 0 points. Within each group, whoever has the most points is the winner of the group.

The next round will consist of winner teams from the first round and some 2nd place teams. This process will continue.