Comp210
200pts; Due 02.Dec.18 (Wed.), 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 X (black).
To receive full credit, your program should at least:
(read) its input and
must printf the move, as described below.
The input to your program is a list of (list-of-symbols), each sublist representing a row. The symbol
'- represents an empty location,
'X represents one of your pieces (you are always X), and
'O represents one of your opponent's pieces.
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.
We saw that vectors are
a natural data representation when we want
to access elements of a 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.
Note that as a matter of good style,
the input values
'X, 'O, '-
(which encode black, white, and empty)
should be named constants, rather than occuring
repeatedly in your code.
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.
Also, to think about:
if you wanted to change your code to play Connect-17 instead,
can you do this with minimal changes?
Other hints,
as well as
a previous year's grade guideline.
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.
Once your program reads input and prints the output,
you can run your program against our test cases
by executing test5 from the unix shell.
(This runs your program against a few non-comprehensive
tests, residing in
/home/comp210/Homeworks/Connect5/Tests/.)
In previous years, a non-negligible portion of programs
haven't pass the minimum requirements.
So that the referee can find your file, it must be named precisely as described under Administrative Details, below. You must follow the Administrative Details to receive credit for your project. 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.
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.)
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.)
Those programs that run successfully on all our test cases (more than the few we provided) will automatically be entered in a class tournament. Every program will play a match (two games) with at least three other programs. 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 dead week at a time and location to be announced on the newsgroup (probably around dec. 11).
The top three tournament winners will receive significant extra credit: 100pts, 75pts, and 50pts , respectively. Note: Because the public tournament will be held before the end-of-finals deadline, extra credit will be awarded both to the players that win the public tournament, and any other players whose final entry would have won a similar tournament. (Max of 100pts extra-credit.)
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 evaluation.
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).
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 sec, 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.
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.)
To aid in grading your lab, we ask that you provide three pieces of information:
register in Lab01 -- is accessible by the
course labbies, but not by your friends.
(For further help in creating directories and moving files,
see the intro-to-UNIX handouts in Mudd, or ask
a labby or friend.)
If you prepare your
assignments outside of Owlnet, you are fully responsible for
getting a running version of their programs to your Owlnet account.
We run some automated scripts to test your program; if
your program is not inside your ~/comp210/connect5/
directory, you will lose points.
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.
One note: 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.