WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

CS4341 Introduction to Artificial Intelligence 
Project 2 - D 2001

By Chris Shoemaker and Carolina Ruiz
Special thanks to Mike Sao Pedro for suggesting connect4 as the game for this project 

DUE DATE: Friday, Mar. 30 at 5 pm. 
------------------------------------------


PROJECT DESCRIPTION AND GOAL

This project consists of designing and implementing a program that plays Connect 4.  It will exemplify the minimax algorithm and alpha-beta pruning.


GAME DESCRIPTION

Connect 4 is a two player game (one of them being your computer program). The classical game board is a 7 (horizontal) by 6 (vertical) grid.  The two players take turns dropping pieces onto the board. The player who first gets 4 of his pieces in a row wins.

One of the players uses white pieces and the other one uses black pieces.

We will use an 7x6 board. Pieces are placed in one of the 7 columns.  A column may never have more than 6 pieces in it.  We label the columns A through G, and the rows 1 through 6.

A game will consist of a sequence of the following actions:
  1. It is selected at random which player will use the white pieces and which player will use the black pieces. In what follows, the player that gets to use the white pieces is called player 1 and the player that gets to use the black pieces is called player 2.
  2. Player 1 gets to play first.

  3. After that, the players take turns moving.  A move (color column row) must satisfy the following constraints:
    • Time Limit There is a 60 second time limit for a player to make his move. (user time, not CPU time.)
    • Move preconditions
      1. color is W if it is player 1's turn and B if it is player 2's turn.
      2. There is no piece at column, row.
      3. Every place in column, lower than row is already occupied.
      4. column, row is a valid board location (A <= column <= G, 1 <= row <= 6)
    • Move postconditions
      1. After the move, the place at column and row on the board will be occupied by a color piece.
      2. It will be the other player's turn.
  4. The game ends in any of the following cases:
    1. one of the players gets four of his pieces in a row (vertically, horizontally, or diagonally). This player wins the game, and the other loses the game.
    2. the board is full, but neither player can place four pieces in a row - the game is a draw.
    3. a player makes an illegal move - the other player wins.
    4. a player fails to move within the time limit - the other player wins.

PROJECT ASSIGNMENT

The project assignment consists of the following:
  1. Your group must implement a program that plays Connect 4.
  2. Each group needs to pick a one-word name for its program.
  3. Your program must use the minimax algorithm with alpha-beta pruning.
  4. If your minimax with alpha-beta pruning cannot expand the whole search tree in the time allowed, your program should use a game strategy: The better your evaluation function and your heuristic, the better your program will play, and the better your grade in the project.
  5. Your program must produce only valid moves.
  6. Your program must verify that each of the opponent's moves is valid, and should execute them.  If the opponent's move is invalid, your program must display the offending move, and state the error.  (e.g. space occupied, column full, lower spaces unoccupied... etc.) 
  7. Your program must detect if the game has come to an end, and if so, it must print a message stating who won.
  8. Your program must follow the specification given above so that it can interface with other groups's programs.
  9. If you want, you may implement a graphical interface for your program, that displays the configuration of the board during the game. Such an interface is NOT required.

PROGRAM COMMUNICATION

There are many communication methods that are far more elegant and efficient than this one, but the intent is that this method will result in the least elaborated code, and that it allows you to implement your program in your choice of languages.

  1. Each group needs to pick a one-word name for its program. We'll refer to that name as groupname in what follows.
  2. Each group must submit the code of its program and an executable (or script) named groupname.
  3. A referee program, described below, will be told what two groups are going to play and the referee will execute the programs.
  4. Each program will have two interface files:
       groupname.in
       groupname.out
  5. The program will read input from groupname.in and output its moves to groupname.out

  6. At the beginning of the game, the file groupname.in will contain the letter W, if the corresponding program must play with the white pieces, and the letter B otherwise. The referee program will take care of creating this files and making this assignment.
  7. Each program must read the groupname.in file to determine which color it will be.
  8. After reading its color, each program must DELETE its own groupname.in file, so the referee program knows that each player knows its color. In what follows, the program that gets to use the white pieces is called group1 and the program that gets to use the black pieces is called group2.
  9. Group1 writes the first move, say (W C 1), to the file group1.out.
  10. Then, the referee will copy this move into group2.in so the second program can read the move.
  11. After reading this move, group2 must DELETE the group2.in file, and before exceeding its time limit, write its move to group2.out, say (B A 1).
  12. The referee program will read this file and copy it into group1.in, and the whole process is repeated until the game is over.
  13. Note that a program will know that it is its turn by the presence of a groupname.in file. After reading that file, the program must delete it. Also, the program must CLOSE (not delete) groupname.out at the end of its turn and re-create it on its following turn.


REFEREE

A referee program will be provided. This referee program will be in charge of deciding which program goes first, giving each program's turn to the other program, displaying the board configuration, detecting illegal moves, and enforcing time limits.

Specifically, the referee program will be in charge of:

  1. Assigning which program goes first, as described above.
  2. Displaying the board configuration after each move.
  3. Giving turns to each of the playing programs. By creating the file groupname.in, the referee program is giving the turn to groupname.
  4. Timing each of the players. It starts measuring the time for groupname's move just after creating groupname.in.  If a program exceeds its time limit, the referee program will stop the game, announcing that the offending program has lost. (Note that a program should not time its opponent.)
  5. Detecting invalid moves. If the referee program finds an invalid move, it will stop the game, announcing that the offending program has lost.
  6. Ending the game when all positions on the board are occupied, announcing a draw.
  7. Ending the game when one of the programs makes 4 pieces in a row, announcing the winner.

TOURNAMENT

  1. N.B. The time limit for the tournament will be lowered to 30 seconds.
  2. Your program must not consume computing resources during your opponent's turn.  In this spirit, when it is your opponent's turn, your program should simply wait for your opponent's move.  Your program may check for the existence of the input file, at most, every 100 ms.  To do this, your process must block.  In C, this will probably mean some use of ualarm() and pause().  In Java, Thread.sleep() will do the trick.  In C++, maybe there are some convenient functions in <pthread_alloc>.  Whatever you do, you MAY NOT simply "burn time" by counting in some tight loop in between file checks.  Your process must block.
  3. The tournament will take place on either cpu.wpi.edu or wpi.wpi.edu.
  4. Both players will be executed on the same machine, and may not spawn processes on any other machine.

MORE details have come...


REPORT SUBMISSION AND DUE DATE

Along with your code, you must also submit code documentation.  It must follow the Departmental Documentation Standard (see http://www.cs.wpi.edu/Help/documentation-standard.html).  Project 2 is due at 5pm on March 30, 2001.  One (and only one) member of your group must submit the following files using the turnin program:

  1. the names of the members of your group
  2. instructions on compiling and running your program
  3. the static evaluation your program uses,
  4. the heuristics employed,
  5. strategy used for minimax and alpha beta pruning,
  6. results:
    • describe which tests you ran to try out your program. Did you program play against human players? Did you program play against other programs? How did your program do during those games?
    • describe the strengths and the weaknesses of your program.
  7. a discussion of why the evaluation function and the heuristic are good choices.

Finding a good static evaluation function and a good heuristic depends heavily on the experience you have with the game. I recommend you start playing the game and getting the flavor of what a good Connect 4 strategy is. Also, research the strategies that other people have used for this and other games. Lots of information can be found in the references listed in your syllabus, the web, and magazine articles.


OTHER RESOURCES

Although you are welcome to look at code and systems available online to guide the design of your program, you MUST submit your own original code.

GRADUATE CREDIT PROBLEM: