Comp210: Principles of Computing and Programming
Fall 2004 -- Final Project: Connect-N   

(11/13/04) If you have already downloaded the supplied files, download them again, as they have changed significantly.

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-N.   This is a modernized version of the "final project formerly known as Connect-5".  

CONNECT-N REQUIRES THE "PLT: PRETTY-BIG" LANGUAGE LEVEL TO RUN!!

Connect-N Overview

Connect-N is a two player game played on a board consisting of an M by M array of squares (N and M are not related and could be any number, though we will typically play N & M around 5). Each player takes turns placing a white or black (in our game, yellow and red, actually) stone in an unoccupied square for the first and second players respectively.¹. The first person to place N 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 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-N. 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 be told what player for whom it is supposed to calculate a move.

To receive full credit, your program should at least:

1. find a winning move², if any exist.
2. block an opponent's winning move, if one exists for them.
3. Otherwise, make a legal move.

The input to your program is a Board structure (see the page on Supplied Functions), which, among other things, contains a list-of-list-of-any representing the players' tokens on the board where each sub-list represents a row.

For example, your program may be given the a Board containing the following layout of tokens:

(list (list '- '- '- '- '-)

      (list 'X 'X 'X 'X '-)

      (list '- 'O 'O 'O 'O)

      (list '- '- '- '- '-)

      (list '- '- '- '- '-))

where the above values represent

'-  = an empty location.

'X = one player's token.

'O = the other player's token.

NOTE:  THESE SYMBOLS ARE USED FOR THE PURPOSES OF THIS WEB PAGE ONLY.   YOUR PROGRAM WILL USE OTHER DEFINED VALUES TO REPRESENT PLAYERS AND EMPTY SQUARES.   DO NOT HARD CODE THE SYMBOLS!!

In a Connect-5 game, if you are playing X, the required move here is row 1, column 4.  On the other hand, if you are playing O, the required move here is row 2, column 0.

Program interface

• Your DrScheme file must be named "connectN.scm"  (the upload system will automatically prepend your username(s)).  If you upload multiple versions, be sure to inform the staff, as the automated testing systems will only look at version #0.
• Your connectN.scm file must define the following function:

;;playFnFac: any any natnum natnum natnum--> playFn  (defined below)
;; A factory for a playFn.
;; (playFnFac yourId otherId size minLength maxTime) returns a playFn where
;; yourId is an any representing the player whose turn it is.
;; otherId is an any representing the other player.   
;; These id corresponds to the values stored in the board.
;; size is the size of the board.
;; minLength is the minumum length of a chain to win
;; maxTime is the maximum number of seconds given to calculate each move.

where

;; playFn: Board (-->num) --> Loc
;; A function specification that calculates the next move 
;; for a player, which is returned as a Loc structure
;; A call to a playFn would look like:
;; (playFn aBoard timeLeftFn)
;; where aBoard is a Board structure and
;; timeLeftFn is a no-parameter function that returns the number
;; of seconds left in this player's turn.
;;A Loc structure would be returned, representing the desired move
;; to be made.
 

The some of the structures and values used in the input parameters are pre-defined in the supplied game-control.zo file (see the page on Supplied Functions).

If you are wondering why you are required to provide the factory for the playFn and not the playFn itself, ask yourself  why is this necessary in order for a playFn to both retain information between moves and to be able to play itself in a game.

Playing games

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 ("opponents") and provides one program with an empty board. It then takes the move returned by the first opponent, updates the board, and calls the second opponent with the new board. When the second opponent returns a move, the referee again updates the board and passes it back to the first opponent, and so on until one opponent wins or it's a draw. (A opponent is never given a full board as input, so your code need not do anything in particular in that case.) Note that technically, the referee hands a copy of the board to the opponent. The referee checks that the opponent make legal moves and whether or not the game is won or is a draw.

The referee program will impose a maximum time limit on the move, which your program should consider to be an arbitrary amount.    Generally, it will around size/4 seconds, but that time may be lengthened or shortened depending on the playing conditions.   For instance, it may be shortened to create a "lightning round" elimination.   Failure to make a move in the allotted time will result in an immediate forfeiture of the game.

If a player returns an invalid or illegal move, that player will immediately lose the game.

So that the referee can find your file, it must be named precisely as described under Turning it in, below.

Here is are some sample programs for you to examine and to test against:

• humanPlayFn.scm:  This is allows the user to input a desired row and column.  Note that inputting an illegal move will cause you to instantly lose the game (this is a function of the referee program).
• randomPlayFn.scm:  This player simply takes the first open space it finds; if you can't beat this one, you're in trouble. (Note that this function would not meet the minimum project requirements.)

In order to play a game, you will need the game control software (be sure to download the appropriate version!):     (11/24/04) Updated versions available!  

• For DrScheme v. 208 ONLY (latest version): v208/game-control.zo 
• For Dr.Scheme v.207 ONLY (Owlnet installed version): v207/game-control.zo

If you get an error that looks something like:

read (compiled): code compiled for version XXX, not YYY

please contact the comp210 staff right away.   Be sure to include the complete text of the above error message so we know what version you need.

This is a compiled Scheme file that in order to use, you must put the line

(load "game-control.zo")

at the top of your DrScheme file.  

See the page on Supplied Functions to find out information on the various functions and values defined in game-control.zo.

Also, a sample program showing how to load playFnFac's and run a game is provided: game-test.scm -- see the code itself for instructions.

Monitor the WebCT discussions to see if new versions of the sample code are posted!

Your connectN.scm file should NOT contain the (load "game-control.zo")line as this is already included in the game or testing files that will load your connectN.scm code.  (This will eliminate problems with multiple definitions of structures.  Your code in connectN.scm will be able to access all the functions in game-control.zo because they will already be loaded by the game or testing code.)

NEW!!  If you would like to have a reasonable competent opponent to test your code against, download Dan Jackson's winning code from a few years ago:

• For DrScheme v. 208 ONLY (latest version): v208/drj4ever.connect5.zo 
• For Dr.Scheme v.207 ONLY (Owlnet installed version): v207/drj4ever.connect5.zo

To use the code, simply load it as you would any other playFnFac.   Don't forget the .zo extension. There are a few caveats to using Dan's code however:

1. It will only run as Connect-5 since that was all that was required when he took Comp210 (they had it so easy, didn't they?).   It will run on any size board however.
2. It doesn't utilize the timeLeftFn, but it generally completes its move in size/4 seconds.

If your code can consistently beat Dan's code, you'll be in pretty good shape.

It would be an Honor Code Violation to attempt to decompile this or any other supplied compiled code.

Testing your program

We have provided a few non-comprehensive tests as examples: student-tests.scm  See the code itself for descriptions on how to set up your tests. 

NEW:  11/29/04: The above link is to a new version of student-tests.scm that fixes a typo in the last two tests.  ("board1" should be "board2")   11/30/04:  fixed another typo on line 43 ("playFn1" should be "playFn1b") 

Monitor the WebCT discussions to see if new versions of the test examples are posted!

Your tests should be

1. Complete -- should cover as many different situations as possible, e.g.
   1. win or block vertically, horizontally and diagonally
   2. win or block by moving to the middle of a chain, not just the ends
   3. different size boards
   4. different minimum lengths
   5. different maximum times
   6. Include any tests needed for any functions not hidden behind locals.
2. Documented -- what are you testing at each point?
3. All in a separate file called tests.scm.  Do NOT put test code in connectN.scm!

For grading purposes, we have a more comprehensive test suite that we will not publish. Half of your grade will come from this automatic testing.

To test to see if your code can complete under a given amount of time, check the timeLeftFn after the playFn returns to see if it is still a positive value.

Program Style

The minimum-requirements Connect-N 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.

Your code should not be tied to playing one player or the other.   Nor should it be tied to using particular values for the player ID's.    Your code should however, always use the pre-defined EMPTY-CELL placeholder to get the value to represent an empty square.

Certainly, the magic number "5" should not occur in any place in your program. Your program should be able play no matter what size the board is or how many in-a-row is required to win.

A Board structure contains lambdas that can be used to directly access any row and column in the board, but you may need to write some of your own board processing functions and data structures.  You may find that these functions are too slow for your needs.  In that case, we saw that vectors are a natural data representation when we want to access elements of a fixed-length sequence by index.  Direct access of a location through a vector is much faster than the same operation through a list.  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: analogous 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?) 

Suggestion: get your code working properly with lists first, encapsulate well and then switch to using vectors if you need speed.   If you have encapsulated well, the changes should be minimal.  Do not optimize you code before you know that your code works!

The getSquare and setSquare! lambdas in the Board structure are useful for looking at a single row-col location, but are too slow for processing the entire board.   Use foldl (why is foldl better than foldr?) or map to process the rows, which are lists of lists.

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 unless you make the for-loop tail recursive, it may not be faster than foldl or map.

You'll almost certainly have function(s) which look for streaks of length N. While that's all that's needed for the program, you might easily pass these functions a number k, and have them just look for streaks of length k. No extra work, and you might be able to re-use this in your board valuation.

Similarly, while you might have different functions for looking at the board horizontally, vertically, and diagonally. These are all pretty similar. How can you abstract the differences? You might think "This function adds 1 to row, while this other doesn't change row at all, so they can't be combined." But, consider: "This function adds 1 to row, while this other adds 0 to row. It will be fun to clean up my code by factoring out the row-offset!"

There's no need to use set! to satisfy the minimum requirements for this assignment. If you use it, ask yourself whether it is truly appropriate, or if just having functions return values suffices. Exception: If searching the game tree, you might use set! to communicate the idea of the best-solution-so-far between branches of the recursion (rather than passing an accumulator around).   Also, to retain information between calls to the playFn, you may need to use set! 

For help on coming up with a good game-playing algorithms, please see the Connect-N Algorithms page.

Grading Guidelines

The project is worth 100 points total.

50 points: Correctness, i.e., passing all our test cases (not just yours).

1. Common mistakes include not blocking a winning move when there are multiple moves to block.
2. More partial credit is given if you document that you are aware of particular bugs. More partial credit is given if you outline what is needed to fix it.

30 points: Code style, especially abstraction.

1. Use local helper functions for small, well-defined tasks. Even if you only call the function once, you still add clarity over one huge function.   Using local functions also will minimize any problems with name clashes and masking/redefinitions of any functions in the referee or testing programs.
2. For looking at the four possible directions, just have functions that take in a dx,dy rather than four separate, otherwise-identical functions.
3. Your program should be able to play Connect 7 or Connect 19 without modification. Of course, any heuristics for the extra credit should still work, although not necessarily be as "smart".   Likewise, your code should work independent of the board size (you may assume a square board however).
4. set! should only be used when necessary and only when protected by closures.
5. Note that the entire connect5 basic program can be written in 2.5 well commented, nicely spaced pages. That's counting one page for the matrix utilities, but not counting each function's test cases. Previously, some people turned in dense, 20-page epics -- ugh!

10 points: Code documentation.

1. In a comment box at the top of your file, write a clear and complete discussion of the overall strategy used by your program and any bugs that exist.
2. Includes contract and purpose for each function, as usual. .
3. If you use heuristics in making moves, we will be a bit lenient on the explanation of why you choose particular heuristics. But, you still need to explain what the heuristics are and what the specific heuristic functions do.

10 points: Code testing.

1. Includes tests for individual functions, as usual.
2. Includes test data of your overall program. Beyond the few simple tests we provide, you need to create your own.
3. Include all test data in your test file.
4. Clicking "Run" in DrScheme with your code open should execute all your test cases.

Additionally, there is extra credit for playing the game well. Those that pass all our test cases (more than the few we provided to you) will automatically be entered in a class tournament. The top three teams will receive significant extra credit: 100 points, 75 points, and 50 points, respectively.

Every program will play a match with at least three other programs. Each match consists of two programs playing each other twice, so that each program gets to play as each color. 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 finals at a time and location to be announced on the newsgroup.

Administrative details

Work with your homework partner to get the basic requirements done, i.e., checking for an immediate win/loss, and otherwise placing a piece with no heuristic method. This can be turned in for full credit.

All teams that pass the graders' tests will automatically be entered into the tournament.   Bonus points will be given equally to the members of the winning teams (e.g. 100 pts each for winning the tournament).

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.

PUT YOUR NAME(S) INSIDE EVERY FILE YOU UPLOAD!!!

1. Turn in a two DrScheme files: "connectN.scm" and "tests.scm".  Do NOT zip up the files!
2. Upload both your files as normal under "Final Project".  
3. If you upload more than one version, please contact the staff right away, as the automatic referee programs will want to see version #0.