UF CAP 4621 Artificial Intelligence Project

Project Description

For your project you will write a computer program in LISP capable of playing a variation of the game Go-Moku, which we will call FIVE-IN-A-ROW. FIVE-IN-A-ROW is played on an 8 x 8 (checker) board. The board squares are numbered 1 through 8 from left to right and 1 through 8 from bottom to top with the square in the lower right corner being square 1,8. At the start of a game every square of the board is empty.

Players alternate making moves. On each move a player is allowed to place one of their pieces in any square that is not occupied. Two single digits between 1 and 8 specify each move. The first digit specifies the row and the second digit the column in which your piece is being placed. Play continues with players alternating moves until one of the players has five pieces in a "row". Note that this "row" can be vertical, horizontal, or diagonal in the playing area.

Your program must be capable of playing either first or second. Tournament play will consist of two games: one where you start and one where your opponent starts.

Your program must display the board with all pieces that have been played, whose turn it is, and the position of the piece just played. At the start of the game your program should give a choice as to who is going the move first and should display a short description of the rules of the game and how moves are specified. Your program must recognize when the game is over (no matter whose turn it is), must identify who won, and allow the user the option of playing another game.

Two single digits between 1 and 8 specify each move. The first represents the row and the second the column. If your program specifies a position that is occupied or a position off the board (digits less than 1 or greater than 8), you will forfeit the game if your opponent recognizes the move as an illegal move. If your opponent fails to recognize the move as illegal, the game will continue as if nothing bad has happened. If your opponent makes an illegal move (a move off the board or to a full column), you should identify it as illegal and end the game.

The following time limits must also be followed by all programs: No program should take more than 30 seconds to make a single move or should average more than 20 seconds per move through the entire game when played on our fastest workstation with an average usage load. You are encouraged to implement your program so it varies its depth of search to stay within these limits.

Implementation Details

To enable us to develop an automated tournament, all programs should follow the following implementation conventions. Failure to follow these conventions will require to you manually play tournament games against the other programs in the class.

1. Your program should consist of the following routines, as a minimum:
   1. (main-xyzzz) This is the main routine that will be executed to start your program. xy, in this routine's name and all other routine names, should be your first and middle (if you have one) initials and zzz should be the first three letters of your last name. If your last name consists of less that 3 letters use only those letters for zzz.
   2. (init-xyzzz) This is the initialization routine that will be called by main-xyzzz. It will initialize the board and any other global variables required by your program.
   3. (rules-xyzzz) This routine displays the rules of the game and is called by main-xyzzz.
   4. (display-board-xyzzz) This routine displays the current board.
   5. (move-xyzzz move) This routine is passed a single value representing your opponent's move. The value of move is nil if you are to make the first move of the game; otherwise, it will be a list of two integers - the first representing the row of your opponent's move and the second representing the column of your opponent's move. This routine should update the board with your opponent's move (if legal), display the new board, determine if the game is over, calculate the computer's move, and update the board with this move. This routine returns one of three values:
      1. A list of three values, two integers representing your program's move and either the atom nil or win. This list should follow the conventions of your opponent's move: the first integer is the row of your move and the second is the column of your move - for example, (2 4 nil) specifying a move to position 2,4 where the game is not over or (4 6 win) specifying a move to position 4,6 where the computer wins,
      2. The atomic symbol loss, which identifies that your opponent just placed a piece in a winning position resulting in your program losing the game, or
      3. The atomic symbol forfeit, which identifies that your opponent just made an illegal move resulting in his/her forfeiting of the game.
2. All of your global variables should be named var-name-xyzzz in case an opponent's program contains a variable named var-name.
3. All of your routine names should be prog-name-xyzzz in case an opponent's program contains a routine named prog-name.

Your main routine should:

1. Print a welcome message.
2. Ask the user if he/she wishes to see the rule's of the game. If so, it should execute rules-xyzzz.
3. Ask the user if he/she wishes to play a game. If not, it should exit.
4. Call init-xyzzz to initialize all program variables.
5. Ask the user who will start the game, the human or the computer.
6. If the human is starting, the main routine should call display-board-xyzzz to display the board then it should ask for the human's move. This move is passed to move-xyzzz which will determine if the human's move was illegal or if the game was over and will return forfeit, loss, or the computer's move. This step is then repeated until the end of the game.
7. If the computer is starting, the main routine should pass move-xyzzz the value nil. This routine will return the computer's move. The main program should then call display-board-xyzzz to display the board then it should ask for the human's move. This move is passed to move-xyzzz which will determine if the human's move was illegal or if the game was over and will return forfeit, loss, or the computer's move. The moves then alternate until the end of the game.
8. At the conclusion of a game, this routine should print who won then repeat this whole process by returning to step 2 above.

Project Time Table

The following are important dates when project reports or demonstrations will be required. Note that these dates apply to local students only. NTU student dates will vary depending upon video tape viewing schedule.

Oct. 20 Demonstrations of projects.

These demonstrations will be of the board display, rules of the game, and other interactions involved in play. Your program should play a "random" game (pick any available move), should recognize when a game is completed, should recognize when a legal or illegal move is made (and take appropriate actions), and should ask if another game is desired. Any other added features ("bells and whistles") which you feel should be part of the user interface should be demonstrated here. Each student will turn in a copy of their program on this date (e-mailed). Submit, in class, a page describing what must be done to execute your program.

Oct. 27 Written report.

A hard-copy of your written report should be turned in on this date (approximately 1 page in length). This report will detail what intelligence you intend to implement in your program. Note: you might not be able (due to time until the end of the semester, time limits for a move, and space within the machine) to fully implement all of this. Your report should therefore be structured to contain the following two sections:

1. This is what I will definitely implement, and
2. This is what I hope to implement provided I don't have any major difficulties.

Nov. 10 Mini-Max/Alpha-Beta Search Implemented

On this date you should have a search program implemented that, as a minimum, performs Mini-Max search. No submission of code is required on this date!! This is merely a road marker for you.

Dec. 3 All projects must be fully implemented and running for final demonstrations.

These demonstrations will be used to show what you have a final program. You will be graded on the program playing a legal game, any changes which have been made since the last demonstration, and how well the program plays. You are to submit a version of your program and, again, a page describing how to load your program and what function should be executed to start your program.

Dec. 3 - 10 Tournament.

We plan to develop a program that will allow your programs to play each other automatically for tournament play. If we are unable to get this program working, everyone in the class locally will be divided into groups of approximately four. Everyone in a groups will play all other members of the group. Play will consist of two games -- you start one, your opponent starts the other. If class members desire, a second tournament round will be played to allow you to compete against programs of more equal skill levels and to find the best program in the class. Points on the final project grade will be awarded for how well the programs fare in this competition.

NTU students will be given the option of playing other students from the class. Arrangements for this tournament will be made toward the end of the semester. If no tournament is played between NTU students, the points for this section of the project will be distributed appropriately to the other project components.

Dec. 10 Final written report.

This report will detail the entire project. As a minimum this report should include:

1. A description of the game which was implemented.
2. A description of the approach which was taken.
3. A description of all programs written and all major variables used.
4. A flowchart of the program.
5. A calling hierarchy showing how the various functions call each other.
6. A description of what intelligence was implemented and what was not. Discuss why the non-implemented intelligence was not implemented.
7. A discussion of what you would do differently if you were able to start over.
8. A users manual on how to use the system (from login till completion of a game).
9. A complete code listing.

Grading

The grading of the project will be according to the following scale:

• Initial Demonstration 10%
• Intelligence Report 15%
• Tournament Play 15%
• Final Demonstration 25%
• Final Report 35%

Internal Links

Parent Article: UF_CAP_4621_Artificial_Intelligence