Project

Connect Five

Connect Five

Project description

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 n² numbers denoting the status of each square on the Connect Five board. The numbers 1, 0, or -1 denote 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

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.

In 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

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-text. 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-text with the -h option for details. When the graphical referee interface becomes available, it will be named conn5-gr.

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 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.

The top two tournament winners will receive significant extra credit. 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. More tangibly, the first place winner will get their choice of a Java book or an Algorithms text, and second place will get the other.

Good algorithms for game playing

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 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 15 seconds. Those programs that fail to satisfy this requirement during the tournament will default their game.

Administrative details

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.
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.