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:

  1. A hardcopy of your final program (pledged and signed), including Readme file.
  2. 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.)
  3. Some further test cases, in your ~/comp210/connect5/ directory. The provided tests don't test several important types of checks.
  4. 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