Prog 3: Nine Man's Morris

[See course schedule for due date.]

Write a program in C to play the ancient game of Nine Man's Morris, where your program allows two human players to play against each other, verifying input.  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.

[reed@ernie]$  ~reed/141/morris/morris  Author: Dale Reed Assignment: #3, Nine Men's Morris TA: Popre Tires, 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... 

[reed@ernie]$

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 prior programs; How to use functions, including reference parameters. 

Notes:

• 1. 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, however you may have global constants declared with const.  If you make any other global variables, that is a 40 point deduction.

  2. You are not allowed to use arrays for this program, but you must use functions.  This is part of the challenge of this program.  Think about how this can be done, where every array reference instead becomes a function call.

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

  4. You may use C++ reference parameters.  This is more convenient than C reference parameters where we must 1. Pass with ampersand, 2. Catch with asterisk and 3. Use with asterisk.

1. Player represented by 'X' should always go first.

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

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

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

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

2. Error checking: Note that the "Sorry, that is invalid. Enter a move position:" message should appear under the following conditions: 

• 1.        -  if the destination location was invalid, 

  2.        - or the destination is not blank, 

  3.        - or a player is not moving his or her own piece.

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

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

  6. You can execute my version of this program on the CS machines at

     1. ~reed/141/morris/morris

  7. Turnin your program electronically into Blackboard.  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. 

3. The 55 points for correct execution are further broken down approximately as follows:

• • 1. 0 points: Displays the board.  

    2. 10 points: Allows placing pieces on board.  You must get to this point to receive any score at all for this program.

    3. 15 points: Allows moving pieces

    4. 10 points: Error checking:

       1. 5 points: ensure source has piece from user to play, and destination is a valid square and is blank

       2. 5 points: ensure source and destination are different

    5. 15 points: When a "mill" of 3-in-a-row is first formed, allows removing an opponent's piece

    6. 5 points:  Detects when one user has won, giving an appropriate message and stopping play.  A player wins when the opponent is reduced to 2 pieces.  Note that if an opponent is unable to move, then that is a win as well, however your program doesn't need to check for this.

• 1. For up to 15 points of extra credit allow playing against either another person or against the computer, where the computer does a reasonable job of making the right move.

4. Test input: 

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

     1. a1 a4 a7 b2 b4 b6 c3 c4 c5 d1 d2 d3 d5 d6 d7 g1 g4 g7

     2. g4 f4

     3. g1 g4 f4 e4 d1 g1 a1

     4. e4 e5 g1

     5. g4 g1 d2 d1 d6 f6 d5 d6 g1 g4

     6. d6 d5 g7

     7. a4 a1 d5 d6 g4 g1 d6 d5 a1

     8. g1 g4 d5 d6 g4 g1 d6 d5 b2

     9. g1 g4 d5 d6 g4 g1 d6 d5 b6

     10. g1 g4 d5 d6 g4 g1 d6 d5 d3

     11. g1 g4 d5 d6 g4 g1 d6 d5 f6