IC210 Fall 2007

Programming Project 3

Reversi

 


 

 

Pre-Coding Analysis: Due in class on Thursday, 15 November 2007. Turn in a flowchart (either neatly hand-drawn or using the RAPTOR tool) for a function that will check for multiple pieces to flip (i.e. the  key part of Step 4). Make sure you give sufficient detail -- e.g. if there is a loop, what controls it and when will it stop?  Make sure that your flowchart clearly shows how you intend to solve the conceptually difficult parts of the project.  Note that you DO NOT have to actually code up the solution as part of the Pre-Coding Analysis.

1.      Note that this Pre-Coding Analysis is NOT a routine out-of-class assignment, but rather is part of the project and therefore subject to the Department's policy concerning programming projects.

2.       Recall that the Department’s policy states that “midshipmen may give no assistance whatsoever to any person and may receive no assistance whatsoever from any person other than the assigning instructor” on a project.  Please view http://www.usna.edu/CS/academics/ProgrammingPolicy.pdf for additional details on this issue.

 

 

Executive Summary

A minute to learn...a lifetime to master. 

For this project, you will write a program that lets two people play Reversi (or Othello if you prefer)

 

 

Due Dates and Honor

 

            The Pre-Coding Analysis will be due in class on 15 November 2007.

 

This project will be due by the close of business on Thursday, 29 November 2007.  See the course policy for details about due dates and late penalties. Again, this is a Programming Project, and it is very important that you understand and abide by the Department's policy concerning programming projects. Please view: http://www.usna.edu/CS/academics/ProgrammingPolicy.pdf 

 

Acceptable reference sources: Note that the policy states that "midshipman may not use information in any format, electronic or printed, other than their own class notes, the course textbook, or materials distributed by the instructor. If midshipmen wish to use additional sources, they must receive explicit permission from the instructor."

 

Extra Information

 

1.      Game rules

The board is 8 x 8 with two white and two black pieces to begin.  Black always goes first.

Black must place a piece with the dark side up on the board, in such a position that there exists at least one straight (horizontal, vertical, or diagonal) line between the new piece and another dark piece, with one or more contiguous light pieces between them. The picture below shows (in gray) the 4 such legal moves for black in the initial state.

 

 

After placing the piece, dark captures (flips) all white pieces lying on a straight line between the new piece and any anchoring dark pieces. All reversed pieces now show the dark side, and dark can use them in later moves -- unless light has reversed them back in the meantime.

 

 

Players take alternate turns. If one player cannot make a valid move, play passes back to the other player. When neither player can move, the game ends. This occurs when the grid has filled up, or when one player has no more pieces on the board, or when neither player can legally place a piece in any of the remaining squares. The player with more pieces on the board at the end wins.

 

Details

 

The project is divided up into seven steps. You are strongly encouraged to solve each step completely - including thorough testing - before you move on to the next step. Also, remember that your program’s source code must comply with the Required Style Guide in order to maximize the grade you receive on this project.  Compile your program often so you don’t end up with a snake’s nest of errors at your first compile.

 

Save frequent backups! Someone really lost all of their Project 2 code last time, 1 day before the deadline -- don't let it happen to you!!!

 

 

Step 1: Initialize and display the board

Write a program that sets up the game and displays it in the specified format. 

 

The game state will be represented as a struct.  It will include, at a minimum:

1. The game board as a 2D array of chars.  The possible chars are ' ' (space),☻(ASCII 1) or ☺ (ASCII 2)

2. The dimension of the game board - in case we want to change the size.

3. The char of whose turn it is.  Possibilities are ☻(ASCII 1) or ☺ (ASCII 2)

4. The number of pieces each player currently has on the board.

 

It should call a function to initialize every variable in your struct and then call a function to display the board - in the format shown below.

 

HINT: Starting from the original TicTacToe lab code is not a bad idea. Make sure you understand all of it before you proceed!

 

 

Step 2: Add interaction

Improve your program so that it updates and prints the number of pieces that each player currently has.  It will then get a move from the player whose turn it is.  It shall place a piece at that location and change whose turn it is.  This process will repeat indefinitely. For now, don't worry about checking for legal moves -- that will come later.

 

Think about the functions that would be useful to accomplish these steps.

 

 

 

Step 3: A game that can flip one piece in one direction

Improve your program such that if "you" place a piece directly above (in the same column) exactly one of your opponent's pieces followed by one of your own, it will flip the opponent's piece between your two pieces. For now, you only have to check this one direction (e.g. moving down from the just-played piece).  Like all steps, however, this should work if the "you" in question is Black or White. You must also properly update the piece counts for each player.

 

This shall be implemented using a function that updates the board and returns 1 if it flipped a piece and 0 if it did not. The arguments to the function should include the row and column of the just-played piece.

 

 

Step 4: A game that can flip any number of pieces in one direction

Improve your program such that if "you" place a piece above any number of your opponent's pieces followed by one of your own, it will flip the opponent's pieces between your two pieces. Again, you have to check just one direction (down from the just-played piece).  You must also properly update the piece counts for each player.

 

This shall be implemented using a function that updates the board and returns the number of pieces that were flipped (possibly zero).

 

Step 5: A game that will flip any number of pieces in any direction (Almost there!)

Improve your program such that it will now flip all opponent's tiles between your new piece and any others. You must also properly update the piece counts for each player.

 

Do not write pages of code for this step!  Instead, think about how to generalize the function you wrote in the previous step so that it can handle any possible direction that need to be considered.

 

HINT: There are 8 directions to consider. You probably want to make 8 different calls to the same function, one for each direction. That's not a hard requirement, but you won't earn full credit for a solution that instead repeats bunches of very similar code in 8 different ways.

 

 

 

Step 6: Check for legal moves

 

Up until this point, your program has probably allowed for illegal moves.  There are two types: trying to place a piece where one already exists and trying to place a piece where it will not cause any flips.  Ignore illegal moves from the user and prompt that player again for a move.

 

 

 

 

Step 7: Finish the game

 

The final step in creating this game is figuring out who the winner is!  Check if the board is full or if a player loses all his pieces and then print out the winner. Note that you do not have to explicitly check for the situation where a player has no legal moves.

 

 

 

 

What to submit and how it will be graded

You will only submit a solution to one of the seven steps above. You will submit your solution for the highest numbered step that actually works! For example, if you had a working solution to Step 3, but only a partially completed solution to Step 4, you would submit your Step 3 solution.

 

How points are assigned for a particular solution is at your instructor's discretion, however, program structure, documentation, variable names, etc. will be considered along with program correctness. Important points:

 

·       If your program does not compile as submitted, you will receive a zero.

·       If your program does not give correct results, penalties will be substantial. If you can't get a working Step k+1 solution, submit your Step k solution instead.

·       Your program must read input and write output in the exact format specified in this project description.

·       Your program’s source code must comply with the Required Style Guide in order to maximize the grade you receive on this project. A portion of your overall grade depends upon providing comments that help explain the functionality of the code. Do provide a comment before each function explaining what it does, in terms of its arguments ("returns the GCD of 'a' and 'b' "). Don't comment things that are obvious to someone who knows C++ ("this increment i").

 

There will be both a paper and an electronic part to your submissions. The paper submission can be handed to your instructor in class, slid under their office door, or put in their mailbox. For the purposes of any late penalties, your project is not considered submitted until your instructor receives BOTH the electronic and paper portions of your submission.

 

Electronic submission: Unless otherwise specified by your instructor, electronic submission should be a single email message with title “IC210 Project Submission”. Include just your main.cpp file. If you have any questions, send a separate message with a different subject. Be certain to include the file!

Here's what to submit  (follow instructions for one of the following):

 

Step 0 Pre-coding Analysis: (5 pts). See description at start of project.

 

Step 1 submission: (max 25 pts)

Paper: Submit a printout of your source code and a screen capture showing your program being run. You will also submit a signed copy of the project cover page (see IC210 home page) and your graded Pre-Coding Analysis from Step 0.
Electronic: See above. 

 

Step 2 submission: (max 45 pts)

Paper: Submit a printout of your source code and a screen capture showing your program being run on input b2. You will also submit a signed copy of the project cover page (see IC210 home page) and your graded Pre-Coding Analysis from Step 0.
Electronic: See above.

 

Step 3 submission: (max 60 pts)

Paper: Submit a printout of your source code and a screen capture showing your program being run on input c4.  You will also submit a signed copy of the project cover page (see IC210 home page) and your graded Pre-Coding Analysis from Step 0.

Electronic: See above.

 

Step 4 submission: (max 80 pts)

Paper: Submit a printout of your source code, a screen capture showing your program being run on input c5 b5. You will also submit a signed copy of the project cover page (see IC210 home page) and your graded Pre-Coding Analysis from Step 0.
Electronic: See above.

 

Step 5 submission: (max 90 pts)

Paper: Submit a printout of your source code, a screen capture showing your program being run on input c4 c5 e6. You will also submit a signed copy of the project cover page (see IC210 home page) and your graded Pre-Coding Analysis from Step 0.
Electronic: See above.

 

Step 6 submission: (max 95 pts)

Paper: Submit a printout of your source code, a screen capture showing your program being run on input c4 b4. You will also submit a signed copy of the project cover page (see IC210 home page) and your graded Pre-Coding Analysis from Step 0.
Electronic: See above.

 

Step 7 submission: (max 100 pts)

Paper: Submit a printout of your source code, a screen capture showing your program being run on input (paste it into the window):

f5 d6 c3 d3 c4
f4 f6 g5 e6 d7
e3 c5 f3 e7 b6
b5 a6 g4 c6 g3
h3 f2 h6 d2 c2
e2 c7 b3 b4 a3
d1 e1 c1 a5 g6
h5 c8 h4 f8 g7
f7 g8 h8 h7 a4
a7 b2 a1 b7 a8
b8 b1 a2 d8 e8
h2 g2 h1 g1 f1

 

You will also submit a signed copy of the project cover page (see IC210 home page) and your graded Pre-Coding Analysis from Step 0.
Electronic: See above.

 

 

Extra Credit: (Maximum of 10 points -- do any combination of these)

A. Make a version of the game that you can play against the computer.  A good opponent is very tough. An opponent that randomly picks valid moves is definitely worth some credit. Only get smarter than that if you got some serious time and energy.

 

B. We skipped some true othello rules.  Implement any of the following and get some more credit:

 

1.  If there are no legal moves for a player, his turn is skipped.

2.  If there are no legal moves left for either player, the game is over.

 

Submit a screen capture showing your program being run on input:

f5 d6 c3 d3 c4
f4 f6 g5 e6 d7
e3 c5 f3 e7 b6
b5 a6 g4 c6 g3
h3 f2 h6 d2 c2
e2 c7 b3 b4 a3
d1 e1 c1 a5 g6
h5 c8 h4 f8 g7
f7 g8 h8 h7 a4
a7 b2 a1 b7 a8
b8 b1 a2 d8 e8
h2 h1 f1 g1 g2

 

It will look like this: