Comp210
Due: 01.Dec.19, 17:00, under ian's door DH3103
To do before re-releasing:
Rather than them printing answer,
they call a ref func "set-move";
rather than their code worrying about timing out,
the ref just uses the last value given?
(Few enough people wrote tree-searches, that i
wouldn't worry about most people taking the max time on every move.)
Your program will read in a representation of
a game board, and then 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 referee 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:
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.
(list (list '- '- '- '- '-)
(list 'X 'X 'X 'X '-)
(list '- 'O 'O 'O 'O)
(list '- '- '- '- '-)
(list '- '- '- '- '-))
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.
(In particular, in previous years a non-negligible portion
of entries don't pass the minimum requirements.)
After grading,
we may post one large file with
everybody's output,
so be warned that others
might see how many test cases your code passes!
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.
For instance, if you have a function that returns
(list 4 1),
then (printf "~a" (list 4 1)) would
print this list as (4 1).
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
return
(list 4 1) (and a newline)
for the above input,
to win the game.
Note that Scheme does not have two-dimensional
vectors ("matrices") built-in.
Writing this yourself (as a vector of vectors) is not difficult:
analagous to vectors, write functions
make-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.
Make sure these general-purpose functions
don't crash on 0x5 or 5x0 arrays!)
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 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.
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.)
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-gui from the owlnet prompt. This program will prompt you for information, including the pathnames of what programs should act as the players. Run conn5-gui with the -h option for details. There is also a text version of the referee, 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 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. 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. First place will have their final grade boosted by 2/3 of a grade. 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 1 full grade improvement.)
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 function3. 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 20 seconds, 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:
read the board.
(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.)