CSC 330 Artificial Intelligence

Programming Project #3 Alpha-BetaGame Playing

For this programming assignment, you should implement the Alpha-Betaalgorithm to play a game of your choice. Your program does not need to have any graphics or graphical user interface, but it should be obvious whose turn it is and how to enter a move. This assignment should be done individually.

This project is worth 10 extra-credit points. It is not required to complete this project.

Some notes about this assignment:

• The easiest game to use for this assignment is NIM, since you already have the code available for it from our first programming project. However, if you want to make a more interesting game, please do so. Tic-tac-toe or Othello (Reversi) are interesting choices that should be relatively straightforward.
• Depending on the game you choose, you may have to implement an evaluation function, as the alpha-beta algorithm may never have enough time to build the entire tree. More simple games (NIM or tic-tac-toe, for example) should be able to build the complete tree.
• If you choose to implement NIM, you should change your program to allow the user to select the initial number of sticks in the pile and the maximum number of sticks that can be taken in a move.
• When implementing the algorithm, there is a slight problem with the Min-Valueand Max-Valuefunctions, because they are mutually recursive. To implement them (at least in C++), you need to declare them before you define them. In other words, at the top of your program, you will need:

float minValue( state current, float alpha, float beta );

float maxValue( state current, float alpha, float beta );

Then later you have:

float minValue( state current, float alpha, float beta ) {

actual code

}

float maxValue( state current, float alpha, float beta ) {

actual code

}

The declarations at the top inform the compiler that the functions exist, so they can be used in the later function definitions. Note that the names and parameters must match up exactly. This should not be necessary in Java.

Also note that state current is just a placeholder for however you choose to represent the state of the game. In NIM that is as simple as an integer representing the number of sticks left, tic-tac-toe would probably be a 3x3 array of characters, etc.

Please let me know if you have any questions. Submit your source files on Moodle, or leave them on the I: drive before the due date and time.