Problem Set 6
A Two-Player Game

Issued: April 8
Design Review: April 15-19
Specification change: April 20
Due: May 2, 11:59pm

Change Log

Updated: May 1, 11:15PM

This update is to clarify the submission instructions, please read this before you submit (or if you've already submitted read them and if you did something different please update your submission)

Updated: April 26, 06:00PM

AI's have been updated to work with pente. Sorry it took so long. New distributions available here:

Known Issues

Updated: April 22, 11:55PM

Changed some small submission details and submission system is now online. Added section on the tournament (more details to come).

Updated: April 21, 6:15PM

The game signature changes along with updated UI files can be obtained off of the specification change page.


In PS 6, we are giving you more freedom to design. You will implement a game called Gomoku. Gomoku is similar to Tic-tac-toe but more complex; it is traditionally played on a 1919 Go board, and the goal is to get five in a row. There are two players, one using black pieces and one using white pieces. The players take turns playing a single piece on the intersections of the board until one player has achieved a line of 5 or more of his own pieces in a horizontal, diagonal, or vertical row. Traditionally, the player who has the black pieces goes first. The rules of Gomoku are relatively simple; the strategies are not.

Your task

For this problem set you will have two main tasks:

  1. Design and implement the game back end.
    We are giving you a game ADT that you need to implement. You have a great deal of flexibility in redesigning and implementing this abstraction, but you will be required to justify your decisions in a design document. To make sure you are on the right track, you must present a design review to a TA the week of April 15. After the design review, we will issue a specification change you must incorporate into your design and implementation.
  2. Design and implement an AI for the game.
    You are given a signature for an AI module to implement. You have complete freedom for your implementation of the AI. Information about how AI usually works is given towards the end of this problem set.

The emphasis in this assignment is on correctness and on design. While you will implement an AI module, relatively few points are allocated to how well your AI plays. It's much more important that the various parts of the game work correctly.


This assignment has several important milestones:

  1. April 15-19: Design review meeting with a TA. (You will sign up for a 20-minute slot sometime this week.)
  2. April 20: Change to problem specification released.
  3. May 2: Submission of code and report.
  4. May 10: Tournament! (optional, for bragging rights only, details TBA)

Assignment Scoring

Here is a rough breakdown of how points will be assigned on this problem set:

10% : Design review
25% : Design document
15% : Interface design
45% : Implementation correctness
5%: Coding style

Warning: If the code that you submit does not compile, we will deduct 50%, plus a tenth of a point per minute it takes us to get your code to compile (a good design document will help here!). Make sure your code works as the last step before submitting it, and make sure that you provide any instructions needed to make your code compile and operate.


Design review (April 15-19)

About halfway through the project you will be required to meet with a TA for a design review. This will happen the week of 4/15-4/19. Sign-up sheets will be posted on the door of Prof. Myers' office (Upson 4119C). The design review will consist of a 20-minute session where you will talk through your design of program.

You should bring a draft design document to the meeting. This document should include copies of the important interfaces that you have designed. Much of the design review will center on these interfaces and your ability to justify the decisions you have made. You should also have thought through important implementation issues and identified key data structures and algorithms that you plan to use. If your design is good, after the design review your task will be merely to implement the interfaces you have defined. You are not expected to bring your implementation to the review, although it is probably a good idea to have started on the implementation before the review.

Remember, you only have 20 minutes for the design review, which includes setup time and any questions the TA has for you, so budget your time accordingly. You will be graded on how effectively you can communicate that you have a good design in the time allotted. Plan ahead of time what you are going to say, and who is going to say it. We recommend aiming for a 10-minute presentation (do a dry run beforehand to find out how long it is!) and leaving 10 minutes for questions from your TA. If your explanation can be aided by drawing pictures, plan out what you will draw on the board.

If you find that you can't make your appointment, e-mail the TA that you have signed up with ahead of time and see if they can accommodate you.

Specification change (April 20)

After the last design review, the specification of the problem set will be revised. This change will not require extensive changes to your code (less than 100 lines of code) if you have thought ahead and have a good design. The specification change will be posted on the web page and to the newsgroup, and it will also appear in this space.

Click here for the project specification change.

Final submission (May 2)

You will hand in 2 files containing your code and documentation respectively:

  1. All documentation and design document material in a single file. The format must be ASCII, PostScript, or PDF. These are the only formats we will accept. Furthermore, if you choose to change formats (if you submit a PDF and then decide you'd rather submit a text file), overwrite your old submission with something to the effect of "Please disregard this" and then submit your new design document. Otherwise we may read the wrong document.
  2. All SML and signature files that you have used (including the ones that were in the distribution) in a zip file. This should be a self-contained package that we can unzip and compile without doing anything else. It should not include the CM directory (we will take points off if the CM directory is present). If you add any files other than the ones in the CM files, you must add those files to In other words, we should be able to type a CM.make() in the root directory and have that compile everything we need to compile (except for the GUI of course).

Design Document: Your design document should include at least the following sections:

The design document should be at most 12 pages long. We won't read anything beyond the 12-page point. You should focus on the parts of the design where you made interesting design choices. Note that this is a maximum, not a minimum, and 12 pages is more than enough for your purposes. (Your grade will go down if you fill the paper with meaningless comments.)

* Don't underestimate the importance of the testing strategy! A testing strategy is as much a part of a complete design as is the design and implementation of the code. Therefore, you must fully explain what your testing strategy was for both unit and integration testing -- also, of course, you should actually test using the strategy you describe. (Hint: representation invariants help!)

Back End and AI Code: For the code part, we expect you to have a fully functional game ADT that is functionally correct, and a working AI. The AI need not be very good, but it should be able to beat the random and "stupid" AI's that we provide you.

Optional AI Tournament (May 10)

At the end of the semester, when we have received all of the projects, all groups that have implemented a correct AI  may participate in a tournament against each other. Some members of the course staff will also submit entries to the tournament too! The student winner of this tournament (ignoring staff submissions) will win a prize and bragging rights, especially if it beats all of the staff submissions. The AI need not be the same as that submitted on May 2; you may improve it.

Details for the tournament

  1. The tournament will be run with a time limit of 5 minutes per player for a game.
  2. The tournament will be run on multiple P4 1.7 GHz machines with 512 MB of RAM each.
  3. The tournament format has not been decided. We are currently considering a few different options, if you have a preference you can e-mail Hubert. Possible tournament formats:
  4. Seeding will be done randomly.
  5. By submitting to the tournament, you give us the right to publish games to the web site that we think are interesting.

Submission instructions for AI Tournament

Before submitting, you need to register with us so that we can give you an unique ID to append to all your structure names so that there will be no naming collisions between structures used by different groups. E-mail Hubert with the subject line "CS312 Pente Tournament Registration" to register for the tournament (one person per group please!).

Your AI should conform to the PLAYER signature. If it does not, you will not be able to participate. Also, any calls that are to functions in the GAME signature should be to the structure "Game" (which is what our implementation will be called). This Game structure will be the referee, if you have a seperate structure that is used by your AI to keep track of the game state you should submit that.

The tournament AI should be submitted seperately from your regular project. If you are putting the AI in your regular project, you need to add it to both submissions.

You will submit a zipfile with only the necessary files needed for your AI. This should not include the following files:

There should also be a file "" submitted that is a CM file that compiles all of the files necessary to compile the AI. This "" file should not contain the implementation of your game file.

For example, if I wanted to submit RandomAI to the tournament, I would submit the file with the following contents:

Group is 
   types.sml    (* needed for compilation, but you can't change the contents *)
   player.sig   (* needed for compilation, but you can't change the contents *)

Submisson for the tournament will be open until May 8th, 11:59PM. We will try to run the prelminaries on the 9th and will try to run the quarter-finals to the finals on the 10th.

Design Hints

Much of your grade for this problem set will be determined by the quality of your design. There are many good designs for this assignment. We are looking for a design that is modular, has well-designed and clear interfaces, and supports software maintenance, reuse, and extension. Because your game components implement a standard interface, we should be able to plug other groups' components into your program and have them work correctly.

We are looking for clear, concise, well-designed interface definitions as well. You should identify opportunities to define data abstractions. As usual, we expect you to provide abstraction functions and representation invariants where needed.

Software reuse and easy extensibility also tie in with both modular design and well-designed interfaces: if you have well-designed interfaces, they provide the right functionality so that you can reuse them at multiple points within the program, and are easily extensible. Part of the reason we are issuing the specification change is to encourage good, modular designs.

Note that these are not the only things you should take into account when you are designing the parts of this project (other examples of things to consider would be runtime, representation invariants, and memory usage). Whatever you consider, we expect this to be written up in the design document that is handed in along with the rest of the project. This design document should also include your analysis of the limitations of your design and where it could be improved.

Game Rules

Here are more details on the rules that must be implemented by your Game ADT:

Board Size

Traditionally, Gomoku is played on a 1919 board. Your implementation must allow arbitrarily large square boards with minimum size 55. The length of one side of the board will always be an odd number.

Game Clock

The Gomoku game you implement will have a game clock for each player that keeps track of elapsed 'thinking time'. The game clock is initially set the same for both players. The white clock counts down when it is White's turn and the black clock counts down when its Black's turn. If a player runs out of time before moving, he automatically loses.

Initial Board Setup

In Gomoku, black technically moves first. However, black's first move must be in the exact middle of the board. Thus, when the game begins, Black first receives a previous move of Start. Black must respond with the coordinates of the center, which are next passed to the White player as the previous move coordinates.


A turn consists of a player placing one piece on an open board location. Once a piece is placed, it becomes the other player's turn. Once a piece is played, it is not removed from the board until the end of the game. Players continue to alternate turns until the game is over.

End of Game

The game ends when one player has 5 or more pieces in a contiguous row, either horizontally, vertically, or diagonally. If a player's time has expired at the end of its move, the player loses. If the board is filled with pieces and no one has five in a row, the game is a draw.


Getting started

PS6 requires that you install some more software and modify your existing SML installation. Installation instructions and files to download can be found here. Once you have followed the installation instructions, download one of the files below:

A few notes about the problem set download:

If you're interested in why these restrictions are necessary, drop by Hubert's office hours.

Types and Interfaces

Common Types

These common types are used both by the game.sig and the player.sig files, which will be discussed later on.
structure Types = struct

    datatype color = BLACK | WHITE

    (* The contents of a board location. NONE indicates 
     * that no piece exists at that location. *)
    type boardLoc = color option

    (* A coordinate (x,y) represents a location on the board.
     * x is the horizontal axis and y is the vertical axis.
     * Coordinates start at 0, so (0,0) is the upper-left
     * corner of the board. *)
     type coordinate = int * int

    (* A move. Ordinarily just a Move(c) where a new piece
     * is to be placed at c. "Human" tells the UI that it  
     * must get the move. "Start" is given to a player if 
     * the game has just started and it is the first to move *) 
     datatype move = Start | Move of coordinate | Human

Game ADT

The following is a suggested signature for implementation of the Game abstraction. It describes the state of an ongoing game, and provides operations that update that state with moves. It effectively serves as a "referee" that keeps track of the game, checks moves to ensure that they are legal, and decides which player has won.

signature GAME = sig

    type color = Types.color
    type boardLoc = Types.boardLoc
    type coordinate = Types.coordinate

    (* Human datatype to tell the UI that it must get the move from I/O 
     * Start datatype is given to a player if it is starting the game *)
    type move = Types.move

    type game

    (* datatype indicating who has won, if its a draw or if it is 
     * still in progress *)
    datatype winner = NoWinner | Win of color | Draw

    (* Raised by step when a move is attempted after the game has ended *)
    exception GameOver of winner

    (* Raised by step when an invalid move is  attempted *)
    exception InvalidMove of coordinate

    (* Gets value of location (x,y) on the board 
     * 1st argument is x, 2nd is y. returns NONE if nothing there. 
     * Checks that (x,y) is a a valid location. *)
    val getLocation: coordinate * game -> boardLoc

    (* Checks to see move is a valid move given the current game state  *)
    val validMove: move * game -> bool

    (* newGame(n,t) returns a new game object with a n*n board. The board
     * is initially empty. Each player has up to time t to finish the game 
     * and it is black's move. *) 
    val newGame: int * Time.time -> game

    (* Takes in current game state, and the location of the next move 
     * and returns the new game state with the current move applied to it.
     * Raises GameOver(p) if the game is already over. p should never be
     * NoWinner.
     * Raises InvalidMove(x,y) if the move is invalid. x,y are the 
     * coordinates of the failed move *)
    val step: game * move -> game

    (* returns the last move of the current game 
     * returns Start if the game passed in came directly from a call
     * to newGame *) 
    val lastMove: game -> move

    (* gets the winner of the game. Returns None if no one has won 
     * and it is not a Draw *)
    val getWinner: game -> winner

    (* gets the color of the player who plays next *)
    val getNextPlayer: game -> color

    (* gets the size of the board. Board is always square *)
    val getBoardSize: game -> int
    (* gets how much time left a current player has *)
    val timeLeft: (game * color) -> Time.time

If you wish, you may modify this signature; however you should have a good reason that you can describe in the design review and design document. If you do change the signature in a way that is not an extension, our sample AI's are not guaranteed to work with your code. Also, you are likely to break the text and graphical interface that we gave you, requiring compensating changes there.

AI Interface

Your implementation of the AI must satisfy the following signature:

signature PLAYER = sig

    (* A player p is represented by a function. Given a previous
     * move m and total remaining thinking time t, p(m,t) returns
     * the next move of the player. *)
    type player = Types.move * Time.time -> Types.move

    (* getName() is the name of the player. It should be of the form
     * <netid1>-<netid2>_AI for tournament submissions *)
    val getName : unit -> string
    (* createPlayer(c,n,t) creates a new player at color c that
     * expects to play on an n x n board with total thinking
     * time t. Checks: n is odd, n>=5, t>0. *)
    val createPlayer: Types.color -> int -> Time.time -> player

You may not change this interface.

We have provided a sample AI that you can run your code against, as well as a Human interface to play with.

The sample AI's are 2 structures called RandomAI and StupidAI. They implement the PLAYER signature and you may use them in the same manner that you can use the Human structure. Neither AI provided is particularly good at playing Gomoku, but they at least provide a benchmark that you can compare against.

  1. RandomAI : plays a random but valid move.
  2. StupidAI : does a little searching to find a reasonable move.

Game User Interfaces
We have provided you with two user interfaces: a text-based user interface called TextUI, and a graphical user interface called GUI. These interfaces are both functorized with the following header:

functor TextGameFn (P_WHITE: PLAYER)
                   (P_BLACK: PLAYER) :>
                   sig val start : int * Time.time -> unit 
To start a Text Game between two humans, execute the following commands:
  - structure humans = TextGameFn (Human) (Human);
  - humans.start(19,Time.fromSeconds(3600))

This starts a Text-based game with two human players, and gives them each a time limit of an hour (total game time will not exceed two hours). The same thing can be done with the GUI that is provided by using.

  - use "guigame-fn.sml"; (* if you have not already done so *)
  - structure humans = GUIGameFn (Human) (Human);
  - humans.start(19,Time.fromSeconds(3600))

AI players can also be used; in fact, the functors take any structures that implement the PLAYER signature. The parentheses around the structure name are important. You may apply these functors to the two AI structures RandomAI and StupidAI in addition to your own.

While the UI we provide should be sufficient for testing purposes, the GUI lacks snazzy game graphics and skimps on user-friendly features. This is because TAs are busy people. As a karma exercise, you may wish to improve on the GUI we provide! If you are interested, read the details in the Graphical User Interface section of the assignment for help on how to get started with SML graphics.

The AI How-To

An AI ("artificial intelligence") is a module that takes a board configuration and returns a legal move. The AI can choose moves via a number of methods. We encourage you to use the alpha-beta search technique described in recitation, though this is not required.

CS312 Do-It-Yourself AI Construction Kit


If we look at the current game board, all of our possible moves, all of our opponent's counter-moves, and so on, we are constructing a tree of possible board states. A good AI explores this game tree and choose a move that optimizes the worst-case board evaluation score (the minimax value of the current game board).

The first step is to choose a representation for the state of the game (in Gomoku, the board). The AI will be searching a tree in which every node is one of these states. For an effective AI, it is important that the board representation allow the search algorithm to be implemented efficiently. You should think carefully about what board data structure is the right choice.

Game search involves exploring the possible legal moves from a given board position. We want to choose the best of these moves. To evaluate these moves, however, we must consider all possible opponent counter-moves. We assume that the opponent will pick its best move and so we choose the worst of the opponent's possible moves as our worst case. Next we choose our best counter-counter-move. And so on, the evaluation continues down the tree, defining move quality recursively (when it's the opponents turn, we pick the least good move of all the options, when it's our turn we pick the best move) until we reach the desired search depth. At this point, we simply apply our board evaluation mechanism to evaluate all the leaf nodes. After we finish this, the recursion should unwind up the tree to yield the current desired move.

Exhaustive search is too slow, however. Consider Gomoku. There are easily 100 possible moves in any given position. If we want to search 4 moves deep, that's 1004 = 100,000,000 moves we have to evaluate. 100 million isn't a small number, even on modern computers. And depth-4 search means looking ahead just two moves, which isn't really enough to be a great Gomoku player. Thus, a good AI cannot waste time exhaustively searching all possible moves. There are ways to avoid this problem:

  1. Don't consider all possible legal moves. Instead, write a move selector that identifies the N 'best' moves according to some criterion.  The danger, of course, is that the move selector will miss the actual best move. You will want to think about some game-specific criteria for ignoring moves that are very unlikely to be good.
  2. Use alpha-beta pruning to avoid searching. This doesn't require any special knowledge of the game. It will be discussed in recitation.

Both of these techniques can dramatically increase the depth to which the AI is able to search the game tree.

Next, an AI strategy is only as good as its board evaluation mechanism. First, your board evaluation needs to be smart. Think of how you evaluate the board when you look at it. Your AI will make moves to optimize board evaluation -- if your evaluation mechanism is wrong then the AI will make the wrong move. Secondly, the mechanism needs to be fast -- it has to be run on the leaves of the search tree. Its probably worth designing your board structure and evaluation mechanism together to optimize evaluation running time. Its probably better to have a simple mechanism that has the correct fundamental principles than a more complicated mechanism because you can search deeper with the simpler, faster evaluation system. You can play around with your AI by shifting strategy between the evaluation mechanism (you code the strategy) and the search depth (let the AI determine strategy by searching). We will talk about search algorithms in a week or so.

Finally, based on the move selection technique and board evaluation method, you want to choose the largest possible search depth that completes in a reasonable amount of time. If your AI tries to be too aggressive you'll run out of time and lose the game!

Strategy Tips

In developing your static evaluator, you'll probably want to play Gomoku a bit to get the feel of the game. Here are a number of simple things that you might want to consider when developing your AI:

The Graphical User Interface

Although you are not required to do anything with the GUI, we figured some of you would be interested in how we are doing graphics. Feel free to extend the GUI in any which way you want. (Karma points for people doing cool stuff, and if that's not incentive enough, Jeff H. promises to buy the authors of the best GUI some 'soda').

We have seen that SML is a simple and elegant language. In PS 4 we also saw that we could create useful programs in SML. In this assignment we will that SML can be used to write a graphical program. Like any other modern language, SML can be used to create Windows (or X-Windows) applications.

We are supporting graphics in SML through a library called SmlTk. This library allows SML to connect to a TCL process to display graphics. TCL (pronounced "tickle") is a library written to produce a graphical user interface (GUI) using simple scripts. SmlTk provides a strongly typed functional SML interface to TCL.

Basics of GUI Programming

There are a number of user interface components commonly used for GUI programming and supported by SmlTk: 

A GUI interacts with the rest of the application through event handlers (also called callbacks), which are functions that are called when there is a user-interface event: for example,  a mouse click on a button, typing into a textbox, or closing a window. Each user interface component can generate its own events, and different event handlers may be associated with different events. The style of programming that results is called event-driven programming. The user must define the layout of the various Widgets in relation to each other. For a complete list of events and layout options, see the SmlTk manual.

Using SmlTk

Take a look at the test-gui.sml code. It defines a very simple GUI consisting of

Here are the highlights of the code:

val mainID = newWinId()
val entID1 = newWidgetId()
Generate unique ID's to identify the main window and the text field. These are required later to access these elements.
   fun endInput _ =
     changeTitle mainID (mkTitle(readTextAll entID1))
   Entry{widId=entID1, packings=[], configs=[Width 20],
         bindings=[BindEv(KeyPress "Return",endInput)]}
Creates a text-entry field with Width=20. It then binds the function endInput to an Enter key press. The function endInput calls the SmlTk function changeTitle for the window (identified by the windows Unique ID). The string inside the text-entry field is used converted to a title using the SmlTk function mkTitle and passed to changeTitle.
startTcl [mkWindow enterwin];
Initializes SmlTk and then starts the GUI with a new window made from the parameters mentioned in enterwin.

Warm-up exercise for those interested in modifying the Gomoku GUI: modify the test GUI to make the label change its text when the mouse moves over it, and change back when the mouse moves out. Hint: Bind the events Enter and Leave. Use the setConf method for setting widget configurations.

GUI for Problem Set 6

We provided you with a GUI that works but isn't very useful. Try adding features to the GUI so that it is complete and user-friendly. Since this is an optional part of the problem set, you have complete freedom over the design and implementation of your GUI, but make sure it keeps the same interface with the rest of the game components (otherwise your GUI and game won't work with our testing system!) Make your changes by modifying the file guigame-fn.sml. If you're having trouble, talk to course staff. The following details should help you get started.

The board is rendered by drawing an array of small gif images of size 3131 pixels. There are 9 possible types of positions depending on whether the gifs go in the interior of the board, at the board edges or at the corners:

For each color, there are 9 such gifs representing a filled location:

The whole board is made by positioning an appropriate number of these simple images inside a Canvas item:

Suggestions: The GUI provided to you currently just displays the game board and accepts user input (see guigame-fn.sml for explanations about how this is accomplished). However, it does not show whose move it is. It doesn't display if the game has already been won or not, and if so, who won it. The GUI also provides no feedback if the user clicks at an invalid location. Nor does it show how much time a player has left. You can find many more deficiencies in the GUI, and useful new features that might be added. Here are a few ideas:

GUI coding can be fun, so knock yourself out. Just remember it's optional and don't forget to implement the back end and AI by the due date!