200 pts; Due 03.Apr.25 (Fri.), 17:00, but with free grace period until 03.May.1 (Thu.), 17:00; under Dr. Wong's door DH3102
The final assignment for COMP 210 is a medium-sized programming project that involves building a program that plays a simple game known as Connect Five.
Connect Five is a two player game played on a board consisting of an n by n array of squares (n is at least 5, and typically less than 20). Each player takes turns placing a white (player 1) or black (player 2) stone in an unoccupied square.1. The first person to place five of their stones in a row either vertically, horizontally or diagonally is the winner. If the board is filled without either player achieving this goal, the game is a draw.
Your program will play a single move of the game: it will take in a board, and return a next-move. Your program does not have to keep track of an entire game of Connect Five. We will provide referee software that will allow you to run your single-move program against an opposing single move program and play an entire game. Your program will always play as black ('X).
To receive full credit, your program should at least:
(read) and
output your move using (printf …), as described below.
The input to your program is a list of (list-of-symbols), where each sublist represents a row. The symbols are one of the following:
'-, representing an empty location.
'X, representing a piece of yours.
'O, representing an opponent's piece.
For example, your program may be given the board
(list (list '- '- '- '- '-)
(list 'X 'X 'X 'X '-)
(list '- 'O 'O 'O 'O)
(list '- '- '- '- '-)
(list '- '- '- '- '-))
The required move here is column 4, row 1.
(Remember, we use 0-based indexing.)
As mentioned, your main function will receive a list-of-list-of-symbols representing the board. You will presumably define several boards as test cases.
To run your program against somebody else's though,
your program needs to be a bit more interactive.
After getting your program working on your test cases,
make it so that clicking Execute will have your program
(read) a board from the keyboard,
and then printf its answer.
For example, if your main function is named make-move,
the last line of your file may well be
(printf "~v" (make-move (read))).
The printed output of your program should be
a list of two numbers: the column and row index (in that order)
of your next move.
(Columns and rows are indexed starting from 0,
in a left-to-right, top-to-bottom order.)
If make-move returned (list 4 1),
then this will print out (4 1),
to win the game.
The minimum-requirements program can be written in 3-4 readable, commented pages. If your program is substantially larger, you might want to think whether you can factor common code into single functions.
Note that as a matter of good style, the input values
'X, 'O, '-
(encoding black, white, and empty)
should be named constants, rather than occuring
repeatedly in your code.
Certainly, the magic number 5 should not occur in many places in your program. If we changed the program at the last moment to be Connect Nine, your program should still play, with only changing the definition of that constant.
We saw that
vectors
are a natural data representation when we want
to access elements of a fixed-length sequence by index.
Similarly, a natural representation for the board might be a
matrix (two-dimensional vector).
While Scheme does not have matrices built-in.
implementing them yourself (as a vector of vectors) is not difficult:
analagous to vectors, write functions
build-matrix,
matrix-ref,
and
matrix-set!
all of which include a row- and column-number as arguments.
(Also, analagous to vector-length, you'll want functions
like matrix-rows and matrix-cols.
Do these general-purpose functions crash on 0x5 or 5x0 arrays?)
Similarly, writing some form of a for-loop (as in Lab12) will probably be a very useful way to abstract out repeated code.
You'll almost certainly have function(s) which look for streaks of length 4. While that's all that's needed for the program, you might easily pass these functions a number k, and have them just look for streaks of length k. No extra work, and you might be able to re-use this in your board valuation, described below.
Similarly, while you might have different functions for looking at the board horizontally, vertically, and diagonally. These are all pretty similar. How can you abstract the differences? You might think "This function adds 1 to row, while this other doesn't change row at all, so they can't be combined." But, consider: "This function adds 1 to row, while this other adds 0 to row. It will be fun to clean up my code by factoring out the row-offset!"
There's no need to use set! for this assignment.
If you use it, ask yourself whether it is truly appropriate,
or if just having functions return values suffices.
Exception: If searching the game tree, you might use set! to
communicate the idea of the best-solution-so-far between branches
of the recursion (rather than passing an accumulator around).
We have provided a few non-comprehensive tests in
/home/comp210/Homeworks/Connect5/Tests/.
Once your program reads input and prints the output,
you can run your program against these tests
by executing test5 from the UNIX shell.
(In previous years, a non-negligible portion of programs
haven't passed the minimum requirements.)
For grading purposes, we have a more comprehensive test suite that we will not publish. Half of your grade will come from this automatic testing.
You might find it convenient to test your program from the UNIX command line with the following ideas, rather than from within DrScheme.
If you want to run a Scheme program from the UNIX command line, you can start up mred and tell it to run your file. (mred is mzscheme (the underlying Scheme engine -- i.e., interactions window of DrScheme) plus the GUI libraries (so that it can read files with comment-boxes).) Create a file (say) go with the following two lines in it:
#! /bin/sh
mred -L plt-pretty-big.ss lang --script myfile.ss
You can use any editor, including DrScheme, to make this two-line file.
Then, make this file executable:
From the UNIX prompt, type
chmod a+x go
Now, go is an executable file;
typing go will run your Scheme program.
(If you get an error "Unable to open display", it means you need to
run this on a machine with a X windows screen. Any
machine in an Owlnet lab will suffice.)
The above can be nice when combined with UNIX's idea of redirecting input. From the UNIX prompt,
go < some-input-file
Will run go, and rather than reading from the keyboard,
that program will get input from some-input-file.
For more details, see e.g.,
here.
We have written a referee program in Scheme
that pits two single-move programs against each other.
This referee program takes as input the filenames of two single-move
programs ("players") and provides one program with an empty board.
It then takes the move returned by the first player, updates the board,
and calls the second player with the new board.
When the second player returns a move, the referee
again updates the board and passes it back to the first player,
and so on until one player wins or it's a draw.
(A player is never given a full board as input, so your code need not
do anything in particular in that case.)
The referee takes care of presenting each board to a player
as if that player were playing black ('X).
(It also checks that the players make legal moves, of course.)
So that the referee can find your file, it must be named precisely as described under Turning it in, below. A sample program is in the directory /home/comp210/Homeworks/Connect5/Players/first.ss. This player simply takes the first open space it finds; if you can't beat first.ss, you're in trouble.
To run a program against an opponent, you invoke the referee with conn5-gui from the owlnet prompt (or a text version, conn5-text). This program will prompt you for information, including what programs to play against each other; use the --help option for details. Entering comp210 as an opponent's id will use first.ss; the aforementioned Players/ directory has another dumb opponent or two. Entering another student's id as a player should result in a file-not-readable error.
The project is worth 100 points total.
50 points: Correctness, i.e., passing all our test cases.
Common mistakes include not blocking a winning move when there are multiple moves to block.
More partial credit is given if you document that you are aware of particular bugs. More partial credit is given if you outline what is needed to fix it.
30 points: Code style, especially abstraction.
Use local helper functions for small, well-defined tasks. Even if you only call the function once, you still add clarity over one huge function.
For looking at the four possible directions, just have functions that take in a dx,dy rather than four separate, otherwise-identical functions.
Your program should be able to play Connect 7 or Connect 19 with the change of only one placeholder definition. Of course, any heuristics for the extra credit should still work, although not necessarily be as "smart".
set! should only be used when necessary.
Using vector-set! will be more useful,
but also shouldn't be overused.
Note that the entire connect5 basic program can be written in 2.5 well commented, nicely spaced pages. That's counting one page for the matrix utilities, but not counting each function's test cases. Previously, some people turned in dense, 20-page epics -- ugh!
10 points: Code documentation.
Includes contract and purpose for each function, as usual.
Includes a Readme file to discuss the board representation, overall strategy, and any bugs.
If you use heuristics in making moves, we will be a bit lenient on the explanation of why you choose particular heuristics. But, you still need to explain what the heuristics are an what the specific heuristic functions do.
10 points: Code testing.
Includes tests for individual functions, as usual.
Includes test data of your overall program, possibly as separate text files. Beyond the few simple tests we provide, you need to create your own.
Additionally, there is extra credit for playing the game well. Those that pass all our test cases (more than the few we provided to you) will automatically be entered in a class tournament. The top three will receive significant extra credit: 100 points, 75 points, and 50 points, respectively.
Every program will play a match with at least three other programs. Each match consists of two programs playing each other twice, so that each program gets to play as each color. The programs with the best few scores (the top four or so) from this stage will go to a playoff round; any tied scores will be decided in favor of the program which has defeated those with which it's tied, or (in case of a draw) the program which took fewest moves in its winning matches in the final. The finals of the tournament will be held during finals at a time and location to be announced on the newsgroup.
Programs that just satisfy the minimal requirements for full credit are not necessarily spectacularly skilled Connect Five players. Here are two basic approaches to improve play.
Write a board valuation function which takes a board as input, and returns a value between (say) -100 and +100, representing how good the current position seems to be for White. For example, -20 denotes an (apparently) slight advantage for Black, while +100 might indicate a won game (or a guaranteed win) for White. An infinitely smart valuation function might always return +100 or -100, depending on which player has a forced win.3. Your function, though, will probably have to generate a value based on heuristics: for instance, having several sequences of three which aren't totally blocked might lead to a high valuation. Designing a good valuation function is an art.
Once you have a valuation function, you can use it to play the game: For each possible move, see what your valuation function rates each one, and choose one with the highest value. (How much does this process mimic how you play the game?)
Human players also make further improvements: You can consider not just at your possible moves, but also the opponent's possible responses, evaluating each resulting board. It's reasonable to assume that opponent will probably choose the move which gives you the worst resulting position. Thus you want to choose the first-move which gives the maximum valuation, assuming the second-move is chosen so that it gives you the minimum valuation.
You can generalize this strategy to look more than two moves into the future, using generative recursion to enumerate sequences of moves. This method is known as "minimax", since you alternate your moves (choosing maximum values) with your opponent's (choosing minimum values). A good reference for the minimax method, appears here.
Note that this minimax approach still rests upon a static board valuation function4. While searching many moves ahead is a powerful method, you first want a smart valuation function. You are encouraged to implement minimax, but first write a function which only considers the one next move.
Since a minimax search can be very expensive in terms of computer time, the referee program will enforce the restriction that each move be made within a time limit (at least N/5 seconds, where N is the number of locations on the board), on the workstations in Ryon. Those programs that fail to satisfy this requirement during the tournament will default their game. There are numerous ways to refine the basic minimax search, in order to speed it up. The most common is alpha-beta pruning.
Work with your homework partner to get the basic requirements done, i.e., checking for an immediate win/loss, and otherwise placing a piece with no heuristic method. This can be turned in for full credit. Any further strategy will be done individually. Those who do so will be entered in the tournament individually.
When the referee runs your Scheme programs, they will not be case sensitive, unlike within DrScheme. So don't have two identifiers which are identical except for capitalization.
To aid in grading your lab, we ask that you provide three pieces of information:
For each homework team, a hardcopy of your final program including the Readme file.
For each person, a readable version of your Scheme program in your Owlnet home directory, named ~/comp210/connect5/connect5.ss. (If you each have a copy, then your partner can modify their copy for the tournament w/o intefering with your copy.) You can create that directory with mkdir ~/comp210/connect5, and then save your Scheme file inside it.
Note that this is inside your personal comp210 directory --
created when you ran register in Lab01.
It is accessible by the course labbies, but not by your friends.
We run some automated scripts to test your program; if
your program is not inside your ~/comp210/connect5/
directory, you will lose points.
If you prepare your assignments outside of Owlnet, you are fully responsible for getting a running version of their programs to your Owlnet account.
Pressing DrScheme's Execute button should be
exactly what we need to do to start your program running,
including a call to read the board.
(Again, you can see the player first.ss
as an example of a working program.)
Again, running test5 will run our test script
against a paltry two test cases, but will verify
that your program can be run by our automated scripts.
For each person, some further test cases, in your ~/comp210/connect5/ directory. Remember, the provided tests don't test several important types of checks. Homework partners may share tests cases.
For each person, a Readme file in this same directory. The Readme file should contain user information (what does the program do -- you can just refer to the assignment sheet -- and exactly what a user needs to type to run your program -- very straightforward in this case).
More importantly in this case, your Readme is what the labbies read before grading your homework. You should mention your overall strategy (How do you represent the board? How do you find a move?), how your program is organized at a high level, and any problems/bugs/interesting features of your program. For example, if the final version of your project only partially works, please note this in your Readme file.
This project is to be done under the Rice Honor Code. Specifically, you may discuss the ideas and concepts necessary to do this lab with the instructors, labbies, and fellow students. However, you must write your own code. In particular, you may NOT share or even examine source code of other students in the class. For example, you may not solicit the help of a fellow student in debugging your code. (Labbies and instructors may be consulted.) The exception is that you are allowed to ask others about syntax questions ("What does this error message mean?"); such questions involve only one or at most two lines of code.
You are welcome to browse sources outside the class for ideas about your project. However, you may not copy existing code. Any code used in this project must be written entirely by you and your homework partner. Furthermore, any work for the tournament (beyond the minimal requirements) must be done individually. (You can still discuss game strategies with others, but code should be worked on by you alone.) (Help from labbies always allowed, of course.)