Reversi game state in Android

Question

I redid a Reversi game state class that is online. It follows the conventional rules of the board game. The game state connects to a command line interface now. I am unfamiliar with Android so comments related to that would be especially appreciated. Java related comments would be useful too.

/**
 * Date: 11/3/13
 * Time: 11:07 AM
 * based on https://github.com/dweekly/android-reversi
 */
public class GameState {
 public static final byte DIM = 8;
 public static final byte MAXRAYS = 8;
 public static final char LIGHT = 'W';
 public static final char DARK = 'B';
 private final static char[][] DEFAULTBOARD = {
 {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
 {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
 {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
 {' ', ' ', ' ', 'W', 'B', ' ', ' ', ' '},
 {' ', ' ', ' ', 'B', 'W', ' ', ' ', ' '},
 {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
 {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
 {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}
 };
 private char _board[][];
 private char _currentSide;
 private boolean _frozen;
 public GameState() {
 this(DEFAULTBOARD, DARK);
 }
 public GameState(char board[][], char currentSide) {
 _board = new char[DIM][DIM];
 transferBoard(_board, board);
 _currentSide = currentSide;
 _frozen = false;
 }
 public void freeze(boolean state) {
 _frozen = state;
 }
 public void transfer(GameState copy) {
 assert(!_frozen);
 _currentSide = copy._currentSide;
 transferBoard(_board, copy._board);
 }
 public void swapSides() {
 assert(!_frozen);
 assert (Location.isaSide(_currentSide));
 _currentSide = (_currentSide == LIGHT) ? DARK : LIGHT;
 }
 private static void transferBoard(char[][] board1, char[][] board2) {
 for (byte x = 0; x < DIM; x++)
 for (byte y = 0; y < DIM; y++)
 board1[x][y] = board2[x][y];
 }
 public byte moveTo(byte x, byte y, byte[] turners) {
 assert(!_frozen);
 return moveTo(x, y, turners, false);
 }
 public byte previewMove(byte x, byte y) {
 return moveTo(x, y, null, true);
 }
 private byte moveTo(byte x, byte y, byte[] turners, boolean preview) {
 assert (Location.isaSide(_currentSide));
 assert (Location.isEmpty(_board[x][y]));
 assert (Location.isInBounds(x, y));
 byte turnerCount = makeTurners(_currentSide, _board, x, y, turners);
 if (preview) {
 return turnerCount;
 }
 assert(!_frozen);
 _board[x][y] = _currentSide;
 for (byte i = 0; i < turnerCount; i++) {
 Location.setLocation(_currentSide, _board, turners[i]);
 }
 return turnerCount;
 }
 public char at(byte x, byte y) {
 return _board[x][y];
 }
 public boolean isCurrentSide(char c) {
 return _currentSide == c;
 }
 public boolean isFirstSide() {
 return _currentSide == GameState.DARK;
 }
 private static boolean checkForTurner(char currentSide, char[][] board, byte x, byte y) {
 return makeTurners(currentSide, board, x, y, null) != 0;
 }
 private static byte makeTurners(char currentSide, char[][] board, byte x, byte y, byte[] turners) {
 byte maxIndex = 0;
 for (byte dx = -1; dx <= 1; dx++) {
 for (byte dy = -1; dy <= 1; dy++) {
 if (dx == 0 && dy == 0)
 continue;
 for (byte steps = 1; steps < DIM; steps++) {
 int ray_x = x + dx * steps;
 int ray_y = y + dy * steps;
 if (Location.isOutOfBounds(ray_x, ray_y) || Location.isEmpty(board[ray_x][ray_y]))
 break;
 if (board[ray_x][ray_y] == currentSide) {
 if (steps > 1) {
 for (int backStep = steps - 1; backStep > 0; backStep--) {
 if (turners != null) {
 turners[maxIndex] = Location.toLocation(x + dx * backStep, y + dy * backStep);
 }
 maxIndex++;
 }
 }
 break;
 }
 assert(Location.getOtherSide(currentSide) == board[ray_x][ray_y]);
 }
 }
 }
 return maxIndex;
 }
 public byte makePossibleMoves(byte[] locations) {
 byte locationIndex = 0;
 for (byte x = 0; x < DIM; x++) {
 for (byte y = 0; y < DIM; y++) {
 if (Location.isEmpty(_board[x][y]) && checkForTurner(_currentSide, _board, x, y)) {
 if (locations != null) {
 locations[locationIndex] = Location.toLocation(x, y);
 }
 locationIndex++;
 }
 }
 }
 return locationIndex;
 }
 public byte getScore(char side) {
 assert (Location.isValid(side));
 byte result = 0;
 for (byte x = 0; x < DIM; x++) {
 for (byte y = 0; y < DIM; y++) {
 if (_board[x][y] == side)
 result++;
 }
 }
 return result;
 }
 public String toString() {
 StringBuffer sb = new StringBuffer();
 for (byte y = 0; y < DIM; y++) {
 for (byte x = 0; x < DIM; x++) {
 if (Location.isEmpty(_board[x][y]))
 sb.append(".");
 else
 sb.append(_board[x][y]);
 }
 sb.append("\n");
 }
 sb.append("\n");
 return sb.toString();
 }
} 
/**
 * Date: 11/3/13
 * Time: 11:33 AM
 */
public class Location {
 public static boolean isValid(char c) {
 return c == ' ' || c == 'B' || c == 'W';
 }
 public static boolean isaSide(char c) {
 return c == 'B' || c == 'W';
 }
 public static char getOtherSide(char c) {
 return c == 'B' ? 'W' : 'B';
 }
 public static boolean isEmpty(char c) {
 return c == ' ';
 }
 public static boolean isInBounds(byte b) {
 return isInBounds(toX(b), toY(b));
 }
 public static boolean isInBounds(int x, int y) {
 return x >= 0 && x < GameState.DIM && y >= 0 && y < GameState.DIM;
 }
 public static boolean isOutOfBounds(int x, int y) {
 return !isInBounds(x, y);
 }
 public static byte toLocation(int x, int y) {
 assert (isInBounds(x, y));
 return (byte) (x + y * GameState.DIM);
 }
 public static void setLocation(char side, char[][] board, byte loc) {
 board[Location.toX(loc)][Location.toY(loc)] = side;
 }
 public static byte toX(byte b) {
 return (byte) (b % GameState.DIM);
 }
 public static byte toY(byte b) {
 return (byte) (b / GameState.DIM);
 }
}

• Dave Jarvis: This code mixes the idea of a board with the idea of a game's rules. Without a lot of effort, you could refactor this code to apply to visually similar games (e.g., Go, Pente, Nine-Men's-Morris).

Answer 1

Your code looks very much like something one would write in C. On the one hand this is good, because you choose fairly efficient solutions. On the other hand, you throw away many powerful features of Java that would make your code simpler and safer. I'll just present a couple of spotlights that should get you going.

Java is Garbage Collected

This means you don't have to keep track of object ownership. For example, you can create a new array inside a method and return it without any problems. This is better than passing empty arrays as function arguments which you then populate. E.g. in makeTurners, the turners argument is unnecessary.

Arrays != Pointers

While arrays are a language primitive of Java, they are more sophisticated than their C counterpart. For example, they carry their length around with them: someArray.length.

The Java Collection Framework

Arrays suck, and are not useful in most use cases (this is true in C++ as well, where the Standard Library provides superior alternatives to C arrays). The main problem with arrays is that they are fixed-sized, which forces you to carry the highest index around in variable-length situations. In Java, you can find lots of useful Collection classes in the java.util namespace. In most cases where you'd think "array", use an ArrayList instead. They support parametric polymorphism aka. generics. You can instantiate a new instance like:

List<Integer> myList = new ArrayList<Integer>();

where Integer is the type of object inside that collection. Note that primitive types like char or int cannot be used here, because they aren't objects. However, there are wrapper classes like Character and Integer. In many cases, primitives are promoted to the wrapper type, so you don't have to care.

You can add a new element to a collection using the add method:

myList.add(42); // 42 gets promoted to an Integer

The List interface describes certain functionality that all Lists implement, e.g. ArrayLists and LinkedLists. For example, this mandates a get method, so that we can access out elements:

Foo fooFromTheList = myList.get(0);

You can get the size of a collection like myList.size().

There are many more collections like various Sets and Maps.

Iteration

The built-in collections and the dumb arrays can be iterated over using a for-each type loop. This is useful whenever you don't really care about the indices. For example:

 // with plain arrays
 int[] someInts = { 1, 42, 12 };
 for (int i : someInts) {
 System.out.println(i);
 }
 // with an array list
 List<Integer> moreInts = new ArrayList<Integer>();
 moreInts.add(1);
 moreInts.add(42);
 moreInts.add(12);
 for (int i : moreInts) {
 System.out.println(i);
 }

Java is Object Oriented

Currently, you are only using classes to namespace your functions. This is a good start. However, they are also useful as supercharged C structs, that is: to group data together.

For example, you could group the x and y to a single Location:

class Location {
 public in x, y; // here we declare member fields
 // this is a *constructor*
 public Location(int x, int y) {
 this.x = x;
 this.y = y;
 }
}

We can now create a new Location like Location overThere = new Location(x, y). We can access the fields like overThere.x. Other functions that are only about locations all belong in that class.

Another class you should create is a Board, e.g.:

class Board {
 public char[][] board;
 public int size;
 public Board(char[][] board) {
 this.size = board.length;
 // ... copy the primitive board over here
 }
 // ... utility methods
}

This class would then contain methods that are only about the Board, not about a Location or a GameState. Examples are field access and bounds checking, which belongs here. The Board should also have a toString() method which gets called when you try to print out a Board. The default board also belongs here, not into the game state.

The GameState would then have a member field containing a Board instance.

Single Responsibility Principle (SRP) and other design guidelines

The SRP is an object-oriented design principle that tells us that each class should have one single task. Any further functionality does not belong there. When I look at your code, I see various things that should be classes of their own:

• Already mentioned: Board, Location.
• Use a class for your Sides instead of chars.
• Use a class for your Fields instead of chars.

• Maybe use a class to represent each Move, rather than implicitly encoding this in the GameState. A Move would then have a source GameState, and lead to another one. It has a Location where a player places a disk, and a List<Location> of all discs that will be flipped by this move. What is the advantage of this abstraction?

  1. Because it records the prior state, you can easily implement an undo operation.
  2. This representation has the effect that each GameState can be viewed as a vertex and each Move as an edge in a game tree. This makes it much easier to implement an AI that can take enemy moves into account.

  Compare also the Command Pattern.

• Possibly a Rules class that encapsulates the exact rules of the game: Remember that Reversi and Othello are quite similar games that only differ in few details. But much of your code (especially for the board etc) could also be reused for a game of Draughts.

Don't be afraid of writing small classes that seem to do little. If chosen wisely, they actually provide an invaluable service: Structuring your code and data.

Enumerations

In Java, an enum is a special kind of class. In the simplest case, it just provides a couple of names:

enum Field { EMPTY, BLACK, WHITE }

This is better than using some special chars, because this is actually type safe and can guarantee that no illegal values show up where a Field is expected.

Because an enum is a class, we can also provide a constructor and member fields, e.g:

enum Field {
 EMPTY("."),
 BLACK("B"),
 WHITE("W");
 public final String symbol;
 public Field(String symbol) {
 this.symbol = symbol;
 }
}

Why are Enums awesome?

• They are fully comparable.
• We can now have a Field[][] instead of an char[][] for our board – but with full type safety!
• When coerced to a string, it produces its name: System.out.println(Field.EMPTY) is EMPTY.

• When printing out the Board, we can directly access the symbol in each instance:

  for (Field[] row : board) {
   for (Field f : row) {
   sb.append(f.symbol).append(" ");
   }
   sb.append("\n");
  }
  

  This is nicer than your Location.isEmpty(board[y][x]) test – which by the way is now boardInstance.at(someLocation) == Field.EMPTY.

You will probably also want

enum Side {
 BLACK(Field.BLACK), WHITE(Field.WHITE);
 public final Field field;
 public Side(Field f) {
 field = f;
 }
 public Side otherSide() {
 switch (this) {
 case BLACK: return WHITE;
 default: return BLACK;
 }
 }
}

Now we can fetch the other side from any side itself: side.otherSide(). I also added the corresponding field type to each instance, which makes setting new fields on the board easier. The "disadvantage" of type safety is that you can't easily misuse the same char to represent both a Side and a Field.

A closing note on Memory Efficiency

You went through great lengths to use bytes and chars instead of ints and classes. The usual method is to create a good design first, and then optimize only if necessary, and when you have profiled your code to tell you where you can actually optimize. Java allows you to twiddle low-level bits, but it's more effective to use good abstractions.

---

Topics not covered include:

• Algorithm correctness. You can't short circuit when looking for "Turners", because disks across multiple axes may be turned.
• General coding style.
• Encapsulation in OOP, especially use of public and private modifiers; Uniform Access Principle.
• StringBuffer vs. StringBuilder

• Dave Jarvis: Don't use public attributes. See: whitemagicsoftware.com/encapsulation.pdf
• amon: @DaveJarvis Thank you for spotting that. I decided to leave a discussion on public vs. private and accessor methods out of this answer, because quite frankly, there are more important OOP concepts for OP to understand first (classes, instances, static stuff, inheritance, interfaces). I did however mention this issue under "topics not covered".
• VoiceOfUnreason: Yup, that's worth discarding my answer for. The only things I think are missing are (a) using interfaces to isolate the implementation details from other classes and (b) that taking turns between black and white should be expressed via the State pattern.