WPI Worcester Polytechnic Institute

Computer Science Department

CS4341 Introduction to Artificial Intelligence 
Project 2 - A Term 2017

By Carolina Ruiz, Samuel Ogden and Ahmedul Kabir

Due Dates:
Canvas Initial Submission: by Wednesday, Sept. 27th, 2017 at 11:00 pm
Canvas Tournament Submission: by Wednesday, Oct. 11th, 2017 at 12:00 NOON (no late submissions will be accepted)



This project consists of developing and implementing a computer program that plays Gomoku. Gomoku, also known as "five in a row", is a board game similar to tic-tac-toe but on a larger board. The project will exemplify the minimax algorithm and alpha-beta pruning.


(For simplicity, the following game description will use "it" to refer to a player, as the player will be a computer program you'll write.)

A possible state of the game is shown in the following figure

[ Example 15 X 15 Board ]
A possible board configuration for a Gomoku game in a 15 X 15 board


A game will consist of a sequence of the following actions:
  1. A random selection method is used to determine which player will use the white stones and which player will use the black stones. In what follows, the player who gets to use the white stones is called player1 and the player who gets to use the black stones is called player2.

  2. Player1 gets to play first.

  3. After player1 has made its first move, player2 is given the chance to change the color of the stone on the board to black. This is done to limit the advantages of playing first.

    For example, if player1 places its first white stone at E7 and player2 decides that it wants that position, then player2 can place its first black stone at E7.

    This is the only time during the game that a player is allowed to put a stone in an already occupied cell.

  4. After that, players 1 and 2 take turns making moves. A move should satisfy the following constraints:
    1. Time Limit There is a 10 second time limit for a player to make its move.
    2. Move preconditions
      1. The color is white if it is player1's turn and black if it is player2's turn.
      2. The cell at the intersection of column and row on the board is empty. (The only potential exception to this precondition is during player2's first move as described above.)
    3. Move postconditions
      1. After the move, the cell at the intersection of column and row on the board will be occupied by a stone of the color representing the player who made the last move.
      2. It will be the other player's turn.

  5. The game ends when either of the following two cases happen:
    1. one of the players gets five of its stones contiguously in a row (vertically, horizontally, or diagonally). This player wins the game, and the other loses the game.
    2. all the cells on the board are occupied and no player got 5 stones in a row. In this case, the game ends in a tie .


The project assignment consists of the following:
  1. Your group must implement a program that plays Gomoku.
  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: For sample evaluation functions and heuristic game strategies, study Sections 5.3.1, 5.4.1 and 5.4.2 of Russell and Norvig's textbook and investigate approaches described in other online sources. The better your evaluation function and your heuristic game strategy, 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 be able to read each of the opponent's moves, and should execute them. (The process is described in the following section.)
  7. Your program must follow the specification given in this project so that it can interface with other groups' programs.
  8. 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. (As described below, a referee program will be provided which will display the board during a game.)


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 programming languages. All the moves are communicated through a file accesible to both players.

  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. The referee will decide at random which player goes first, check the validity of the moves, check for game ending conditions, and maintain the communication between the two groups' programs. The referee program will be provided and posted to this webpage soon. You do NOT have to write the referee program.
    In most parts of this document, we will refer to the referee program as "the referee" or simply "Referee".
  4. The referee will maintain four text files: a file called move_file , two groupname.go files (one for each group) and an end_game file that will be created upon the completion of the game and which will contain the final outcome of the game (e.g., the winning player, if any). Note: not all four of these files will exist at all times as they are used to control the flow of turns. Please see below for more details.
  5. The presence of a groupname.go file indicates that it is that player's turn. When groupname.go file appears in the directory, the groupname's program should first check to see if an end_game file exists. If this file exists, it means that the game is over and this file contains the result of the game as described below. If the end_game file doesn't exist then the groupname's program should read the opponent's move from move_file, pick its own move, and overwrite move_file with its own move. When groupname.go is absent in the directory, the groupname's program should simply wait for it to appear.
  6. A move will have the following format: <groupname> <column> <row> (e.g., "myGroup B 4" but without the " " around the move)
  7. At the beginning of the game, each program should wait until the file groupname.go with its groupname appears in the directory. The program then reads move_file . If this file is empty, then the program plays with white stones and hence makes the first move. Otherwise, if a move already exists in move_file , then the program plays with black stones.
  8. Each program is allowed a maximum of 10 seconds to make its move. The timer starts as soon as the groupname.go file appears, and a move is considered done 100 ms after a write to move_file is made. (This is because the referee polls move_file every 50 ms to see if its timestamp has changed. After it detects a change it then waits 100 ms to allow the team to finish writing out their move and then reads the move from the file. This allows the player program time to write out in case the polling happened right as they opened the file. The player programs' file write should NOT take any longer than 100 ms. The program needs to open the file for writing, write the move and close the file all in one concise operation to ensure the referee reads in what they mean.
  9. The two groups' programs now take turns making moves until the end_game fle is created. The possible messages the referee can write on the end_game file are:
  10. To summarize, each group's program does the following

For illustration purposes, here is an example sequence of events that happens in a game between two groups GroupX and GroupY.
  1. GroupX and GroupY programs start and wait for their respective "go" files.
  2. Referee starts and creates the file move_file. Referee then randomly selects a group as the first player. Let's assume that player is GroupX.
  3. Referee creates the file GroupX.go and starts timing.
  4. GroupX detects the presence of the GroupX.go file, reads move_file, finds out it is empty, and knows it is the first player.
  5. GroupX calculates its move (let's say D 3) and writes in move_file the line "GroupX D 3" (without the " ") within 10 seconds.
  6. The current content of move_file is
         GroupX D 3  
  7. Referee detects a change in move_file, waits 100 ms, reads the move, checks timing and validity of move, checks if the game has ended.
  8. Since the game hasn't ended yet, Referee deletes the GroupX.go file and creates GroupY.go.
  9. GroupY detects the presence of the GroupY.go file, reads move_file, finds out it is NOT empty, and knows it is the second player.
  10. GroupY reads GroupX's move, calculates its own move (let's say E 4) and writes in move_file the line "GroupY E 4" (without the " ") within 10 seconds. (As per the game's rules, GroupY could have chosen as its move D 3 if it wanted.)
  11. The current content of move_file is
         GroupY E 4 
  12. The process above is repeated until there is an invalid / late / out-of-order move, or if someone wins, or if the board is full. In each of these cases, the referee program creates the end_game file and writes a corresponding message to it as described above. The referee also creates both groupname.go files so that both players are prompted to look for the end_game file. Let's suppose GroupY wins. Then the end_game file will contain:
         END: GroupY WINS! GroupX LOSES! Five in a row! 
  13. All programs stop running.


A referee program to conduct the game will be provided. The functions of the referee have been detailed in the previous section.

Specifically, the referee program will be in charge of:

  1. Assigning which program goes first, as described above.
  2. Displaying a graphical depiction of the board configuration after each move.
  3. Giving turns to each of the playing programs. By creating the file groupname.go, 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.go.  If a program exceeds its time limit, the referee program will stop the game, announcing that the offending program has lost. (Note that your 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 tie.
  7. Ending the game when one of the programs makes 5 stones in a row, announcing the winner and loser.

This referee program can be found in the github repository at https://github.com/samogden/WPI.CS4341.git. If you find any issues or bugs with this referee program, or any deviations from the specifications provided on this webpage, PLEASE report them on the Canvas discussion board immediately. In such event, we will try to fix any bugs, update the version of the referee program in GitHub and notify the class.


By Wednesday, Sep 27 at 11 pm, one (and only one) member of your group must submit the following files using Canvas:

  1. The names of the members of your group
  2. Instructions on compiling and running your program
  3. The utility function that your program uses
  4. The evaluation function that your program uses
  5. The heuristics and/or strategies that you employed to decide how to expand (pieces of) the minimax tree without exceeding your time limit
  6. Results:
    • describe which tests you ran to try out your program. Did your program play against human players? Did your program play against itself? Did your 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(s) you picked are good choices.

Finding a good static evaluation function and a good heuristic depends heavily on the experience you have with the game. We recommend you start playing the game and getting the flavor of what a good Gomoku 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.

Please note: 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.


MORE details about the tournament have now come...