CIS200: Assignment 5
12 points. Due Saturday, March 29, 2007, 10:00pm

Pente (pronounced ``pon-tay'') is a variant of tic-tac-toe where a player must place 5 marks in a line, horizontally, vertically, or diagonally, to win. In addition, a player can ``capture'' and remove from the board their opponents' marks: when one player has exactly two marks in a row, and at one end there is an opponent's mark, say like this: 
O X X _
then the opponent can place their mark at the other end, in the empty space (_), like this, O X X O. This captures the marks in the middle, and they are removed from the board: 
O _ _ O

Play continues until someone gets 5 in a line, either horizontally, vertically, or diagonally, or when a player captures 5 pairs of their opponent's pieces.

Behavior

You can read the history and rules of Pente at http://en.wikipedia.org/wiki/Pente. The game is usually played on a 19-by-19 board, but we will use 9-by-9. Here is the start of a sample game: 

$ python Pente.py
X's captures:  0
O's captures:  0
   00 01 02 03 04 05 06 07 08
00  _  _  _  _  _  _  _  _  _
01  _  _  _  _  _  _  _  _  _
02  _  _  _  _  _  _  _  _  _
03  _  _  _  _  _  _  _  _  _
04  _  _  _  _  _  _  _  _  _
05  _  _  _  _  _  _  _  _  _
06  _  _  _  _  _  _  _  _  _
07  _  _  _  _  _  _  _  _  _
08  _  _  _  _  _  _  _  _  _
Type your move:  row,col: 2,2
The computer moved to (2, 3)

X's captures:  0
O's captures:  0
   00 01 02 03 04 05 06 07 08     (the human placed their X at 2,2
00  _  _  _  _  _  _  _  _  _      and the computerized opponent chose 2,3)
01  _  _  _  _  _  _  _  _  _
02  _  _  X  O  _  _  _  _  _
03  _  _  _  _  _  _  _  _  _
04  _  _  _  _  _  _  _  _  _
05  _  _  _  _  _  _  _  _  _
06  _  _  _  _  _  _  _  _  _
07  _  _  _  _  _  _  _  _  _
08  _  _  _  _  _  _  _  _  _
Type your move:  row,col: 3,3
The computer moved to (1, 1)

X's captures:  0
O's captures:  0
   00 01 02 03 04 05 06 07 08
00  _  _  _  _  _  _  _  _  _   (the human is trying to make some pieces in
01  _  O  _  _  _  _  _  _  _    a line, but the computer is trying to block)
02  _  _  X  O  _  _  _  _  _
03  _  _  _  X  _  _  _  _  _
04  _  _  _  _  _  _  _  _  _
05  _  _  _  _  _  _  _  _  _
06  _  _  _  _  _  _  _  _  _
07  _  _  _  _  _  _  _  _  _
08  _  _  _  _  _  _  _  _  _
Type your move:  row,col: 2,1
The computer moved to (4, 4)
Capture between 4 4 and 1 1

X's captures:  0
O's captures:  1
   00 01 02 03 04 05 06 07 08
00  _  _  _  _  _  _  _  _  _  (when the human placed an X at 2,1 -- a bad move --
01  _  O  _  _  _  _  _  _  _   the computer placed an O at 4,4 and captured
02  _  X  _  O  _  _  _  _  _   the two pieces that were between the two Os)
03  _  _  _  _  _  _  _  _  _
04  _  _  _  _  O  _  _  _  _
05  _  _  _  _  _  _  _  _  _
06  _  _  _  _  _  _  _  _  _
07  _  _  _  _  _  _  _  _  _
08  _  _  _  _  _  _  _  _  _
Type your move:  row,col:
The program you will write will use a computerized player that I have already built for you.

The program's software architecture

Board games are almost always organized so that one module (file) holds the representation (``model'') of the game board and another module holds the commands that ``control'' the play of the game. Finally, there is a display or ``view'' of the game. This is called a Model-View-Controller architecture:
You will build your game in this architecture. I have already written module ComputerPlayer, and I have written ``skeletons'' of PenteBoard and Pente. You must finish writing PenteBoard.py and you must improve Pente.py so that it controls the Pente game like the example shown above so that the human and computer can make moves until someone wins.

The Model module

PenteBoard.py holds a nested list (two-dimensional array) that models the game board and functions that manipulate and maintain the board. It looks like this: 
# Build the board:
size = 9      # this size can be adjusted to make differently sized boards
EMPTY = "_"   # the value used for an empty square on the board
board = []
for i in range(size) :   # a clever way to build the nested list of correct size
    board = board + [ size * [EMPTY] ]

def printBoard() :
    """printBoard  displays the board as a grid, with coordinate
       numbers along the top and left side
    """
    # IMPROVE THIS FUNCTION so that it prints the board as a grid
    print board

def makeMove(row, col, mark):
    """makeMove attempts to insert a  mark  into the board at position, row,col.
       If the move is made, then any captures that result are performed.
       parameters: row - the row index;  col - the column index;  mark - "X" or "O"
       returns True if the move is successful; returns False otherwise.
    """
    # IMPROVE THIS FUNCTION so that it checks that the row and col are legal
    #  coordinates, that the selected square is empty, and once the
    #  mark  is placed in the square, all captures are correctly computed
    result = False
    board[row][col] = mark   # TOO simple!
    doCaptures(row,col,mark) # call this function to compute the captures
    result = True
    return result
 . . .

You must finish this module, completing the functions. Do not change the names of the functions. (The reason is that the ComputerPlayer module depends on the functions exactly as named. This is standard procedure when teams of people build a multi-module program: the teams will agree on the names of the functions, and each team fills in the details in their module's functions.) PenteBoard.py is found at http://www.cis.ksu.edu/~schmidt/200s08/Assign/Assign5/PenteBoard.py

The Controller module

The Controller module enforces the order of play. It is written as a separate file, Pente.py. The skeleton version I have supplied is standard (it uses an indefinite-iteration loop that prints the board; asks for the next move; and processes the move), but it's not quite finished; you can find it at http://www.cis.ksu.edu/~schmidt/200s08/Assign/Assign5/Pente.py

When you read this module, you will see that it imports PenteBoard.py and calls its functions. But the Controller module does not alter the game board directly! This is standard procedure that programming teams take: each team builds its own module to fit with the others, and each team minds its own business and promises not to alter the insides of the other modules. (That is, one module can call another module's functions and can look at another module's variables, but a module never changes, by assignment, the values of another module's variables --- in practice, this is far too dangerous!)

Finally, you need not look at it --- and you are certainly not allowed to change it --- but you should copy the ComputerPlayer module into the same folder where you copy the model and controller. When you are ready to use it, uncomment the lines in the controller that import and call the ComputerPlayer. The computer player is at http://www.cis.ksu.edu/~schmidt/200s08/Assign/Assign5/ComputerPlayer.py

Follow these stages of development

  1. Study the rules of Pente and look again at the example game shown above so that you understand what the computer program must do.
  2. Make a folder on your computer, name it Assign5, and copy into it PenteBoard.py, Pente.py, and ComputerPlayer.py. Start up Pente.py and see what happens. Then, read the codings for Pente.py and PenteBoard.py.
  3. Without altering Pente.py, go to work on PenteBoard.py: Improve printBoard and get it working correctly. Then, improve makeMove and get it working correctly. (But don't worry about doCaptures just yet.)
  4. Next, return to Pente.py and activate the ComputerPlayer module. (Remove the comment symbols from the key lines.) Test your program --- you and the computer should be able to take turns inserting X's and O's. You will find that the computer player will try to block any attempts you make at placing your marks in a line.
  5. Now, return to PenteBoard.py and write the doCaptures function. Play the game and confirm that the function works, that is, it removes marks from the board when a capture arises. (The computer player loves to do captures, so you can test doCaptures by making the human player do dumb moves that leave pairs of X's unprotected.)
  6. Finally, write the checkWinner function and call it from the correct place(s) within the loop inside Pente.py.
IMPORTANT: whenever you find yourself copying commands from one part of your program to another, this is a sign that you should define a helper function that holds the copied commands. Also, ensure that all functions you write contain useful documentation strings.

Do as much of this assignment as you can, following the stages listed above. (The last two stages are the hardest.) You will get partial credit for a partially completed project.

Remembering the captures

Notice in the behaviors shown above, the game remembers the captures made by X and O. To do this, the PenteBoard.py module must keep two variables that remember the counts of captures. The functions within PenteBoard.py will maintain these variables. Integer variables like this are called global variables in Python. Please read Section 6A.7 in the Lecture notes to see how to use global variables.

Submitting your program

Before you submit your program, you must ``zip'' (compress) your folder, Assign5:

  1. Locate the file-folder icon for folder Assign5 and right-click on it.
  2. From the menu that you see, select Send to, and from the new menu you see, select Compressed (zipped) folder. This will build a file named Assign5.zip.
  3. Submit the zipped file, Assign5.zip, at http://www.cis.ksu.edu/~schmidt/200s08/Assign
Please remember that this assignment, like all the previous ones, is a single-person exercise.