CSC 122: Computer Science II, Fall 2006

Project 1

Ramping up with Java - Reversi

Deadline: Friday, September 1, 5:00 p.m.

Overview:

This project deals with the game of Reversi, also known as Othello. It is played on an 8-by-8 checker board, with 64 pieces which are black on one side and white on the other. Initially, the four center squares are covered with pieces, turned to white on one diagonal and black on the other. The two players, black and white, then take turns placing one piece of their color at a time on an empty square of the board. Any pieces of the opposite color which form a contiguous line (horizontal, vertical, or diagonal) bounded at one end by the new piece and at the other by another piece of the same color are then flipped over to the player's color. Each turn must result in at least one of the opponent's pieces being flipped; if there is nowhere that a player can put a piece, their turn is skipped. The game ends when neither player can play; the winner is the one with the most pieces turned to their color.

Your task will be to implement two strategies for this game: a greedy approach which chooses the move that flips the most pieces, and a priority approach which searches the squares in a fixed priority order and chooses the first legal move.

Specification:

• You will need a Board class which maintains the state of the board. It will contain an 8-by-8 array of type char, where each cell can be '.', 'B', or 'W'. It should provide the following methods:
  • void reset(): clear the board and place the initial four pieces.
  • int checkMove(char player, java.awt.Point position): return the number of opposing pieces which would be flipped by the given player ('B' or 'W') playing at the given position (where (0,0) is at the upper-left and (7,7) is at the lower-right). If the move is not legal, return 0.
  • boolean makeMove(char player, java.awt.Point position): change the board to reflect the given move (note that checkMove does not change the board), and return true. If the move is not legal (that is, if checkMove would have returned 0), leave the board unchanged and return false.
  • int count(char player): return how many of the given player's pieces are currently face up on the board.
  • void display(): print the board on System.out. For example, here is the result of calling display() right after reset():

    ........
    ........
    ........
    ...BW...
    ...WB...
    ........
    ........
    ........
    				    

• You will need a GreedyStrategy class which implements the greedy strategy. It should provide the following methods:
  • GreedyStrategy(char player, Board board): the constructor simply saves in fields the color of its player ('B' or 'W') and a reference to the Board on which the game will be played.
  • java.awt.Point move(): returns the best position at which this player should place a piece on the current board, determined by which position will result in the greatest number of opposing pieces flipped. If there are no legal moves, then return the point (0,0).
• You will need a PriorityStrategy class which implements the priority strategy. It should provide the following methods:
  • PriorityStrategy(char player, Board board): the constructor saves in fields the color of its player ('B' or 'W') and a reference to the Board on which the game will be played. It should also initialize a list of points in order of priority. This order will be up to you -- for example, you might want to put the four corners at the top of the list, since they are very good cells to control (note that once you take a corner, it can never be flipped).
  • java.awt.Point move(): returns the first position which has a legal move, searched in priority order. If there are no legal moves, then return the point (0,0).
• Finally, you will need a Driver class which has a play() method. This should construct a Board object, a GreedyStrategy for black, and a PriorityStrategy for white, and then play a game of reversi. That is, it should reset the board, then alternate asking each strategy for a move and making that move. It should print out the move and the state of the board after each turn. When neither player can move (makeMove has returned false two times in a row), the game ends; the player with the higher piece count is the winner.

The Project and Getting Started:

Standards:

Your project should be well-written, neatly-formatted, modular, and well-documented. I suggest you use a test-driven approach to implementation: first create the classes and method stubs, next write appropriate tests for each method, and then fill in the bodies of the methods to make the tests succeed.

You may work in pairs or individually. Please review the policies on collaboration in the syllabus -- in particular, if you submit work developed as a pair, you need to make sure that you and your partner both understand all of the code submitted.

To submit your project, put all of the source files in an appropriately-named folder within I:\10607_CSC122\ and send me an email telling me where to find the files and, in the case of a pair, who your partner was.

Grading:

• Board constructor and reset method (10 points)
• checkMove and makeMove methods (20 points)
• count and display methods (10 points)
• GreedyStrategy class (10 points)
• PriorityStrategy class (15 points)
• Appropriate priority list of cells -- document your reasoning (5 points)
• Driver class (15 points)
• Documentation and style (15 points)

For extra credit, add functionality so that a human player can compete against one of the computer strategies. Also, I am planning to hold a tournament among all of the submissions, with 5 points of extra credit going to the winning strategy.

DePauw University, Computer Science Department, Fall 2006
Maintained by Brian Howard (bhoward@depauw.edu). Last updated