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)
AI's have been updated to work with pente. Sorry it took so long. New distributions available here:
Changed some small submission details and submission system is now online. Added section on the tournament (more details to come).
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 19×19 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.
For this problem set you will have two main tasks:
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:
Here is a rough breakdown of how points will be assigned on this problem set:
10% : Design reviewWarning: 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.
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.
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. |
You will hand in 2 files containing your code and documentation respectively:
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.
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.
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:
For example, if I wanted to submit RandomAI to the tournament, I would submit the file aisources.cm with the following contents:
Group is smlnj-lib.cm types.sml (* needed for compilation, but you can't change the contents *) player.sig (* needed for compilation, but you can't change the contents *) randomai.sml
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.
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.
Start. Black must respond with the coordinates of
the center, which are next passed to the White player as the previous move
coordinates.
A few notes about the problem set download:
use "test-gui.sml"; use "guigame-fn.sml";This will compile the files and allow you to use the code.
If you're interested in why these restrictions are necessary, drop by Hubert's office hours.
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 end
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 end
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 end
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.
RandomAI : plays a random but valid move.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 endTo 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.
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
Ingredients:
board->move list
board->int
int
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:
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:
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.
There are a number of user interface components commonly used for GUI programming and supported by SmlTk:
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. |
let fun endInput _ = changeTitle mainID (mkTitle(readTextAll entID1)) in Entry{widId=entID1, packings=[], configs=[Width 20], bindings=[BindEv(KeyPress "Return",endInput)]} end |
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. |
SmlTk.init(); 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.
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 31×31 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:
|
|
|
|
|
|
|
|
|
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!