CS 025 Computer Science Fundamentals I
Assignment 2

This assignment is out of 60 points.

Paper copies of your work must be handed in to the CS 025 locker (using the assignment submission form) and electronic copies should be submited via the usual Computer Science Department electronic assignment submission system.

Paper copies of your work must be handed in to the CS 1025 locker and electronic copies should be submited via the usual Computer Science Department electronic assignment submission system. Detailed instructions on how to submit an assignment are located on the How to Submit Assignments page.

Please see the course outline for information on late penalties and the rules of ethical conduct.

Introduction

Reversi, also known as Othello, is a two-player board game in which the players place markers on an 8x8 board with the goal of owning the most squares at the end of the game.

We will call the two players White and Black. Each marker has a White side and a Black side. A player's turn consists of placing a marker on an empty square with their own colour face up. Suppose it is Black's turn to move. Black may place a marker black-side up on any open square so long as it causes one or more "flips". A flip occurs when a line of pieces of one colour have end pieces of the opposite color. So Black can place a piece if it causes at least on straight line of pieces (along a row, column or diagonal) to be: Black, some number of White, and finally Black.

The details of how the game is played are nicely described on the Wikipedia Reversi page.

For this question you will do the following:

Question 1. Board representation (10 points)

Create a class to represent a Reversi position. The class should represent the board as some sort of array or array of arrays. The number of rows and columns should be given by final private static int variables. You should have three final public static int values White, Black and Empty to describe the contents of a square.

• int getSquare(int i, int j) -- returns the contents of the given square (White, Black or Empty) with the squares numbered (0,0) up to (nrows-1, ncols-1).
• void setSquare(int i, int j, int contents) -- sets the contents of the given square.
• int squareScore() -- return the number of black pieces in the position minus the number of white pieces. For example, if there are 8 black pieces and 13 white pieces, -5 is returned.
• int edgeScore() -- same as squareScore but only the 28 squares on the edge of the board are examined.
• int cornerScore() -- same as squareScore but only 4 squares at the corners of the board are examined.

Question 2. Position output (10 points)

Add a method to output a Reversi position on a PrintStream given as an argument. The output should look like:

[. . . . . . . ./
 . . . . . . . ./
 . . . . . . . ./
 . . . X X . . ./
 . . . O O O . ./
 . . . . . . . ./
 . . . . . . . ./
 . . . . . . . .]

That is, the board is given inside a pair of square brackets. Rows are separted by slashes, newlines and spaces to line up as shown. Empty squares are given as periods, Black squares given as X and White squares as O. There should be a space between squares horizontally.

Question 3. Position Input (20 points)

Write a method that creates a Reversi position by reading from an InputStream. Input is the same format as the output, except that the spaces and newlines are optional. The above position could be given as it is shown above or (for example) as:

[......../......../......../...XX.../...OOO../......../......../........]

You should do error checking to make sure that the board has the right number of rows and right number of columns in each row.

Question 4. Move Generation (15 points)

Write another class called ReversiMoveGenerator that has a method to calculate the possible moves from a given position. It should be declared as:

• public int[] generateMoves(ReversiPosition pos, int toMove) -- The result is an array of squares which give legal moves, with a move to square (row, col) being represented as row × ncols + col. The argument toMove is White or Black specifying which player is to move.

You should write a couple of helper methods that solve the following sub-problems:

• Would the square (r, c) be a legal move?
• Would the square (r, c) give a flip in the direction (x,y), where x gives the change in column index moving in the direction and y gives the change in row index. That is, the 8 directions are North = (0,-1), North east = (1,-1), East = (1,0), South east = (1,1), South = (0,1), South west = (-1, 1), West = (-1, 0), North west = (-1,-1).

Question 5. Move Selection (5 points)

Add the following methods to the ReversiPosition:

• ReversiPosition copy() -- make a copy of a position
• void applyMove(int toMove, int row, int col) -- add a piece of color given by toMove to the given square and then make the necessary flips on the board
• int findBestMove(int toMove) -- use the move generator to generate all possible moves and find the best one using the formula:

  squareScore() + 8 * edgeScore() + 20 * cornerScore()
  

Question 6: General Board Size (10 bonus points)

Do the above where the number of rows and columns is not fixed at 8, but can be different for each board. Notice that for input, the size of the board will depend on the number of rows and columns given in the input text.

Question 7: Playing a Game (20 bonus points)

Add a driver program to allow your program to play a human. Ten points of this bonus question are for the top-level driver program. The 10 points are for making the program look three moves ahead.

As always, the conceptual clarity of the solutions, the programming style, documentation, and demonstrated testing are important factors in evaluating assignments.