Project
Connect Five
Comp210
Due: 98.Dec.09 (Wed.) in class,
or by 17:00 at 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
Connect Five is a two player game
played on a board consisting of an
n by n array of squares (n is typically a small
number between 5 and 20). Each player takes turns
placing a white (player 1) or black (player 2) stone in an unoccupied
square. 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.
Project description
Your program should read in a textual description of
a game position and print out an appropriate
single move for that position. Note that your program
does not have to keep track of an entire game of
Connect Five. We will provide software that will
allow you to run your single move program against
an opposing single move program and play an entire
game.
To receive full credit,
your program should at least detect
whether there is a move that immediately
wins the game. If such a move exists,
your program should always return that move.
If no such move exists, then your program should
attempt to block any immediate winning move available
to your opponent. If more than one winning move is
possible for your opponent, then your program
may choose to block any of the winning moves.
The input to your program is a sequence of
numbers. The first number is n, the
size of the board. For the sake of
simplicity, you may assume that n
is always between 5 and 20.
Following n are n2 numbers
denoting the status of each square
on the Connect Five board.
The numbers 1, 0,
or -1 encode that the square contains your
piece, nothing, or your opponent's piece,
respectively.
The squares are given in a left to right,
top to bottom order. For example, the following
is valid input:
5
0 0 0 0 0
1 1 1 1 0
0 -1 -1 -1 -1
0 0 0 0 0
0 0 0 0 0
A few test cases are present in
/home/comp210/Assignments/Connect5/Tests/.
These test cases are not meant to be comprehensive;
part of your project involves thinking about and writing
more test cases.
The output of your program should be the
column and row index (in that order) of your next move.
These number should be separated by a blank
and be followed by a NEWLINE (very important).
The columns and rows are indexed from 0
to n-1 in a left to right, top to
bottom order.
For example, your program should
print out 4 1 (and a newline)
for the above input,
to win the game.
Your program may be written in either
Scheme or extended C.
In Scheme, the command (read) gets the next number
from standard input.
The command (diplay obj)
displays the value of obj to output.
The command (newline)
prints a newline.
In Extended C, you should use cin and
cout to read and write the appropriate
information.
Note that Scheme does not have two-dimensional
arrays built-in.
Writing this yourself (as a vector of vectors) is not difficult:
as suggested in class, write functions make-matrix,
matrix-ref,
and
matrix-set!
all of which take a row- and column-number as arguments.
If you use C, declare a 20x20 array,
and (if the actual board is smaller)
only use a portion of your array.
Note that as a matter of good style, the
max board size 20 and
the input values -1, 0, +1
should be named constants, rather than occuring
repeatedly in your code.
Extra credit: a Connect Five tournament
We have written a referee program in Scheme
that allows two single-move programs to be pitted
against each other.
This referee program takes as input the location of two single-move
programs and provides one program with an empty board.
It then takes the move suggest by the first program,
updates the board, and calls the second program
on the new board. The referee program takes the
move returned by the second program, updates
the board and calls the first program with the
new board. This process is repeated until one
program wins or the board is filled and a draw
is reached.
In order to help us semi-automate the tournament,
you will need to exactly follow some naming conventions
mentioned under Administrative Details.
To run a program against an opponent,
you invoke the referee with conn5.
This program will prompt you for information, including
the pathnames of what programs should act as the players
(either a Scheme file or compiled C executable).
Run conn5 with the -h option for details.
There is also a text version of the referree, conn5-text.
A sample opponent is in the directory
/home/comp210/Assignments/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.
Those programs that run successfully on the
all standard test data 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 taken the fewest moves.
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. 12).
The top three tournament
winners will receive
significant extra credit.
Third place will have their final grade boosted
by 1/3 of a letter grade (e.g. B+ --> A-).
Second place will have their letter grade boosted
by 1/3 of a letter grade (e.g. B+ --$gt; A-).
First place will have
their final grade boosted by
2/3 of a grade.
Good algorithms for game playing
static board evaluation
Programs that satisfy the minimal
requirements for full credit
may not play a particularly
good game of Connect Five.
Here is one basic approach to playing
which can later be augmented to improve play.
Write a board valuation function which takes a board as input,
and returns a value bewteen (say) -1.0 and +1.0,
representing how good the current position seems to be for White.
For example, -0.2 denotes an (apparently) slight advantage for Black,
while +1.0 might indicate a won game (or a guaranteed win) for White.
An infinitely smart valuation function might always return +1 or -1,
depending on which player has a forced
win.¹.
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?)
minimax
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 pieces 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, as applied to Othello,
appears
on
the Web.
Note that this minimax approach still rests upon a
static-board valuation function².
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 program which works
by only looking only at the 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 20 seconds, on the workstations in Ryon.
Those programs that fail to
satisfy this requirement during the
tournament will default their game.
Administrative details
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.
To aid in grading your lab, we ask that you provide three pieces of
information:
- A hardcopy of your final program
(pledged and signed), including Readme file.
- Either an executable version of your
final C program, named ~/comp210/connect5/connect5,
or a readable version of your Scheme program,
named ~/comp210/connect5/connect5.ss.
If written in Scheme,
pressing DrScheme's Execute button should be
exactly what we need to do to start your program running.
(Again, you can see the player first.ss as an example
of a working program.)
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.
(For help in creating directories and moving files,
see the intro-to-UNIX handouts in Mudd, or ask
a labby or friend.)
-
Some further test cases,
in your ~/comp210/connect5/ directory.
The provided tests don't
test several important types of checks.
- A Readme file in this same directory.
The Readme file should contain
user information
(what does the program do -- you can just point to
the assignment sheet -- and exactly what a user needs to
type to run your program -- very straightforward in this case).
More importantly for us,
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.
¹
Or 0, if one of the players can't force a win, but can force a draw.
Is it really true that
one of those three values must hold?
(back)
²
By static board valuation function,
we mean a function which valuates the board as-is,
without searching through possible moves.
This distinction is made because
in general,
a valuation function might search ahead,
but
it needs a base case to stop:
the static-board valuation function.
(back)
Back to Comp 210 Home