CS 102 (Spring '04)
[Schedule] [Examples] [Programs] [Notes & Reference] [Syllabus] [Lab & TA] [Tests] [Grades]

Program #2: Nine Men's Morris

Prof. Reed, CS 102, Spring '03
Due Tuesday 2/18/02 at 2:00 in the afternoon

Not only does Shakespeare reference this game in a Midsummer Night's Dream, but there are records of this game in ancient Egypt, from over 3000 years ago. See more information at http://www.tradgames.org.uk/games/Nine-Mens-Morris.htm.

Running your program will look like the following, except you should have your own name and TA information. The boldfaced text is something that you type in.

[ernie] ~/programs/morris> morris

Author: Dale Reed
Assignment: #2, Nine Men's Morris
TA: A. Stoun Ding, Mon 1:00-1:05

Each player has nine pieces. The players take turns putting their 
pieces (one at a time) on the board at places where lines meet. 
Each player tries to get three pieces in a row (a "mill") while 
preventing her opponent from doing the same. 

When a player gets three pieces in a row then she may take one of her 
opponent's pieces off the board. After both players have put all of 
their pieces on the board, a piece is moved by sliding it from its 
space to a neighboring empty space. 

Players keep trying to get three pieces in a row so they can take 
away an opponent's piece. The game is over when one player 
is left with two pieces.

Moves are made by referencing a row and column, e.g. A1 is the upper
left corner.

    1   2   3  4  5   6   7

 A  .......................  A
    .          .          .
 B  .   ...............   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  .........     .........  D
    .   .   .     .   .   .
 E  .   .   .......   .   .  E
    .   .      .      .   .
 F  .   ...............   .  F   
    .          .          .
 G  .......................  G

    1   2   3  4  5   6   7
Player X has 9 pieces to place.  Enter a move position: A1


    1   2   3  4  5   6   7

 A  X......................  A
    .          .          .
 B  .   ...............   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  .........     .........  D
    .   .   .     .   .   .
 E  .   .   .......   .   .  E
    .   .      .      .   .
 F  .   ...............   .  F   
    .          .          .
 G  .......................  G

    1   2   3  4  5   6   7
Player O has 9 pieces to place.  Enter a move position: B4


    1   2   3  4  5   6   7

 A  X......................  A
    .          .          .
 B  .   .......O.......   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  .........     .........  D
    .   .   .     .   .   .
 E  .   .   .......   .   .  E
    .   .      .      .   .
 F  .   ...............   .  F   
    .          .          .
 G  .......................  G

    1   2   3  4  5   6   7
Player X has 8 pieces to place.  Enter a move position: a2
Sorry, that is invalid.  Enter a move position: b4
Sorry, that is invalid.  Enter a move position: a4


    1   2   3  4  5   6   7

 A  X..........X...........  A
    .          .          .
 B  .   .......O.......   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  .........     .........  D
    .   .   .     .   .   .
 E  .   .   .......   .   .  E
    .   .      .      .   .
 F  .   ...............   .  F   
    .          .          .
 G  .......................  G

    1   2   3  4  5   6   7
Player O has 8 pieces to place.  Enter a move position: b6


    1   2   3  4  5   6   7

 A  X..........X...........  A
    .          .          .
 B  .   .......O......O   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  .........     .........  D
    .   .   .     .   .   .
 E  .   .   .......   .   .  E
    .   .      .      .   .
 F  .   ...............   .  F   
    .          .          .
 G  .......................  G

    1   2   3  4  5   6   7
Player X has 7 pieces to place.  Enter a move position: a7


    1   2   3  4  5   6   7

 A  X..........X..........X  A
    .          .          .
 B  .   .......O......O   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  .........     .........  D
    .   .   .     .   .   .
 E  .   .   .......   .   .  E
    .   .      .      .   .
 F  .   ...............   .  F   
    .          .          .
 G  .......................  G

    1   2   3  4  5   6   7
*** Player X formed 3 in a row!  Enter opponent's piece to remove: b4

    1   2   3  4  5   6   7

 A  X..........X..........X  A
    .          .          .
 B  .   ..............O   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  .........     .........  D
    .   .   .     .   .   .
 E  .   .   .......   .   .  E
    .   .      .      .   .
 F  .   ...............   .  F   
    .          .          .
 G  .......................  G

    1   2   3  4  5   6   7
Player O has 7 pieces to place.  Enter a move position: d6


    1   2   3  4  5   6   7

 A  X..........X..........X  A
    .          .          .
 B  .   ..............O   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  .........     ....O....  D
    .   .   .     .   .   .
 E  .   .   .......   .   .  E
    .   .      .      .   .
 F  .   ...............   .  F   
    .          .          .
 G  .......................  G

    1   2   3  4  5   6   7
Player X has 6 pieces to place.  Enter a move position: d6

   .
   .
   .
   (and so on, until both players have placed all their pieces)
   .
   .
   .


    1   2   3  4  5   6   7

 A  X..........X..........X  A
    .          .          .
 B  .   X......O......O   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  O...X...O     X...O....  D
    .   .   .     .   .   .
 E  .   .   .......   .   .  E
    .   .      .      .   .
 F  .   O......O......X   .  F   
    .          .          .
 G  O..........X..........X  G

    1   2   3  4  5   6   7
Player X to move.  Enter positions moving from and to: A7 D7


    1   2   3  4  5   6   7

 A  X..........X...........  A
    .          .          .
 B  .   X......O......O   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  O...X...O     X...O...X  D
    .   .   .     .   .   .
 E  .   .   .......   .   .  E
    .   .      .      .   .
 F  .   O......O......X   .  F   
    .          .          .
 G  O..........X..........X  G

    1   2   3  4  5   6   7
Player O to move.  Enter positions moving from and to: f4 e4


    1   2   3  4  5   6   7

 A  X..........X...........  A
    .          .          .
 B  .   X......O......O   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  O...X...O     X...O...X  D
    .   .   .     .   .   .
 E  .   .   ...O...   .   .  E
    .   .      .      .   .
 F  .   O.............X   .  F   
    .          .          .
 G  O..........X..........X  G

    1   2   3  4  5   6   7
Player X to move.  Enter positions moving from and to: a4 a7


    1   2   3  4  5   6   7

 A  X.....................X  A
    .          .          .
 B  .   X......O......O   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  O...X...O     X...O...X  D
    .   .   .     .   .   .
 E  .   .   ...O...   .   .  E
    .   .      .      .   .
 F  .   O.............X   .  F   
    .          .          .
 G  O..........X..........X  G

    1   2   3  4  5   6   7
*** Player X formed 3 in a row!  Enter opponent's piece to remove: f2


    1   2   3  4  5   6   7

 A  X.....................X  A
    .          .          .
 B  .   X......O......O   .  B   
    .   .      .      .   .
 C  .   .   .......   .   .  C
    .   .   .     .   .   .
 D  O...X...O     X...O...X  D
    .   .   .     .   .   .
 E  .   .   ...O...   .   .  E
    .   .      .      .   .
 F  .   ..............X   .  F   
    .          .          .
 G  O..........X..........X  G

    1   2   3  4  5   6   7
Player O to move.  Enter positions moving from and to: b4 a4

   .
   .
   .
   (and so on, until one player has only two pieces left)
   .
   .
   .


    1   2   3  4  5   6   7

 A  X..........X..........X  A
    .          .          .
 B  .   ...............   .  B   
    .   .      .      .   .
 C  .   .   O......   .   .  C
    .   .   .     .   .   .
 D  O...O....     ....X....  D
    .   .   .     .   .   .
 E  .   .   .......   .   .  E
    .   .      .      .   .
 F  .   ...............   .  F   
    .          .          .
 G  ......................X  G

    1   2   3  4  5   6   7
*** Player X formed 3 in a row!  Enter opponent's piece to remove: d1


    1   2   3  4  5   6   7

 A  X..........X..........X  A
    .          .          .
 B  .   ...............   .  B   
    .   .      .      .   .
 C  .   .   O......   .   .  C
    .   .   .     .   .   .
 D  ....O....     ....X....  D
    .   .   .     .   .   .
 E  .   .   .......   .   .  E
    .   .      .      .   .
 F  .   ...............   .  F   
    .          .          .
 G  ......................X  G

    1   2   3  4  5   6   7

Player X wins!

Thanks for playing.  Exiting program...


[ernie] ~/programs/morris>

The description of moves for this program was based on http://www.plimoth.org/Education/ninemens.htm.

You need to know the following concepts in order to write this program:

Everything from the first program; How to use functions, including parameters. Using static variables could also simplify your life.

Hints:

For 85 out of the total 100 points, write the program to allow two players to play against each other. For the extra 15 points, allow playing against either another person, or against the computer, where the computer does a reasonable job of making the right move.
You are not allowed to use arrays for this program, but you must use functions.
You will need to declare 24 character variables to represent the 24 positions on the board. You may declare these 24 variables as global variables, though doing this is generally frowned upon. You may not make any other variables global variables.
Note that upper or lower case input is allowed. Your program should give error messages as shown above. You may assume that the format of user's input is correct, even if the attempted move is invalid.
Note that when a "mill" (group of 3) is formed, you get to remove an opponent's piece. On a subsequent move, if that mill remains, you don't get to remove a piece.

Here is an outline of what the main part of your program could look like:

 	// variable declarations
	
	// display identifying information and instructions
	displayIdInformation();
	displayInstructions();

	// display the starting board configuration
	displayBoard();

	// Main game loop.  
	while ( notDone) {
		// See whose turn it is, 'X' or 'O', and determine who the opponent is
		determinePlayerToMoveAndOpponent( ...);

		// Display appropriate prompt and find what move is to be made
		displayPromptAndGetMove( ...);

		// Make the move
		makeTheMove( ...);

		// display the board
		displayBoard();

		// See if we are done yet.  
	}

	// Determine who the winner was and display message

Note that your structure could vary from what I've shown above. For instance, you could have two loops. The first could handle the "placement" phase of the game, and the second loop would be the "moving pieces" phase of the game. I elected to combine the two above.

Error checking: Note that the "Sorry, that is invalid. Enter a move position:" message should appear under the following conditions:
       - if the destination location was invalid,
       - or the destination is not blank,
       - or a player is not moving his or her own piece.
Make your output look exactly like mine (except you know, change the name and TA info.). That way it makes it easier for me to give you a good grade.
You can execute my version of this program at

~i102/programs/morris/morris
Use the g++ compiler on the CS machines. Assuming your program is stored in file prog2.cpp, you can compile this using:
g++ -o prog2 prog2.cpp
which creates an executable called prog2 rather than the default of a.out
Remember to include your TA's NAME and your LAB DAY in the documentation header of your programs AS WELL AS in the output that appears on the screen.
Turnin your program electronically using the "turnin" command as follows:
turnin -c cs102 -p program2 prog2.cpp
where your file name in your account is prog2.cpp Note that using prog2.cpp is just an example. It is simply the name of the file being turned in. To practice using the turnin command you can use the project named "test" (rather than program2 in the example above.)

If you want to verify that your project was turned in, look in the turnin directory for a file with your userid. For instance for this project, from your CS account you would type:

turnin -c cs102 -p program2 -v

where 'v' stands for verify. This will list all files turned in, the timestamp for each, and the exact name of each file turned in.

Test input:
Do you get tired of having to play a whole game just to test your "endgame" code? Me too. Here's a hint: type out all your moves at once. They get buffered, and your program runs through all of them. You can also store them in a file and either redirect your program's input ( morris < inputfile) or simply copy and paste them into your program once it starts running. Here is some sample input that takes you to the end of the game, with X winning.
```
a1 a4 a7 b2 b4 b6 c3 c4 c5 d1 d2 d3 d5 d6 d7 g1 g4 g7
g4 f4 
g1 g4 f4 e4 d1 g1 a1
e4 e5 g1
g4 g1 d2 d1 d6 f6 d5 d6 g1 g4
d6 d5 g7
a4 a1 d5 d6 g4 g1 d6 d5 a1
g1 g4 d5 d6 g4 g1 d6 d5 b2
g1 g4 d5 d6 g4 g1 d6 d5 b6
g1 g4 d5 d6 g4 g1 d6 d5 d3
g1 g4 d5 d6 g4 g1 d6 d5 f6
```

[CS Dept] [UIC] [Prof. Reed]