Going through some past Java exercises so I can improve my programming in general and I've been stuck on this for quite a while. I'm going to post all of the source that's required, since this project is quite large and there's a lot of interfaces and subclasses that just offer to confuse.
public class Board {
public final static char NOUGHT = 'O';
public final static char CROSS = 'X';
public final static char EMPTY = ' ';
// Each cell is indexed as follows:
// 1 2 3
// 4 5 6
// 7 8 9
private char[][] grid; // a matrix to store the positions of the board
private int numOfMarks; // number of moves made on the board
private int lastMarkPosition; //position of last move maode in the board
public Board() {
grid = new char[3][3];
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 3; col++) {
grid[row][col] = EMPTY;
}
}
numOfMarks = 0;
lastMarkPosition = 0;
}
//post: Returns true if the board is finished.
// A board is finished because either there is a winner or the board is full.
public boolean isFinished() {
return numOfMarks == 9 || getWinnerMark() != EMPTY;
}
//post: Records the position of the last mark made on the board.
public void setLastMarkPosition(int lastPosition){
lastMarkPosition = lastPosition;
}
//post: Returns the position of the last mark
public int getLastMarkPosition(){
return lastMarkPosition;
}
//post: Returns the mark ('X' or 'O') of the winner player if a winning condition exists in the board,
// returns EMPTY otherwise.
public char getWinnerMark() {
for (int i = 0; i < 3; i++) {
// check if there are three in a horizontal row
if (grid[i][0] != EMPTY && grid[i][0] == grid[i][1]
&& grid[i][1] == grid[i][2]) {
return grid[i][0];
}
// check if there are three in a vertical row
if (grid[0][i] != EMPTY && grid[0][i] == grid[1][i]
&& grid[1][i] == grid[2][i]) {
return grid[0][i];
}
}
// check if there are three in a diagonal row
if (grid[1][1] != EMPTY
&& (grid[1][1] == grid[0][0] && grid[1][1] == grid[2][2] || grid[1][1] == grid[0][2]
&& grid[1][1] == grid[2][0])) {
return grid[1][1];
}
// otherwise, return EMPTY as there is no winner
return EMPTY;
}
//post: Sets the given mark at the given position in the board
public void setMark(int pos, char mark) throws GameException {
if (numOfMarks == 9) {
throw new GameException("attempted to set mark on a full board.");
}
if (pos < 1 || pos > 9) {
throw new GameException(
"attempted to set mark in a wrong position: " + pos);
}
if (mark != NOUGHT && mark != CROSS) {
throw new GameException("attempted to set an invalid mark: "
+ String.valueOf(mark));
}
// perform board update
int row = (pos - 1) / 3;
int col = (pos - 1) % 3;
if (grid[row][col] != EMPTY) {
throw new GameException(
"attempted to set mark on a non-empty position: "
+ pos);
} else {
grid[row][col] = mark;
numOfMarks++;
}
}
//post: Returns the mark that is at a given position in the board
public char getMark(int pos) {
return grid[(pos-1)/3][(pos-1)%3];
}
//post: If the grid is not full, calculates whose turn is, based on the marks in the grid.
// Returns EMPTY if the board is already full.
public char getTurn() {
if (numOfMarks == 9) {
return EMPTY;
} else if (numOfMarks % 2 == 0) {
// by default, CROSS should go first
return CROSS;
} else {
return NOUGHT;
}
}
//post: Copy the board and returns it
public Board makeCopy() {
Board copy = new Board();
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 3; col++) {
copy.grid[row][col] = this.grid[row][col];
}
}
copy.numOfMarks = this.numOfMarks;
return copy;
}
//post: Prints the given board
public static void display(Board board) {
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 3; col++) {
System.out.print(" ");
char mark = board.grid[row][col];
if (mark != EMPTY) {
System.out.print(mark);
} else {
System.out.print((row)*3+(col+1));
}
System.out.print(" ");
if (col < 2) {
System.out.print("|");
}
}
System.out.println();
if (row < 2) {
System.out.println("-----------");
}
}
}
GameTreeInterface
public interface GameTreeInterface {
//post: Returns the board at the root of the game tree.
public Board getRootItem();
//post: Expands the game tree fully by adding all possible boards in the game.
// It uses a recursive auxiliary method.
public void expand();
//pre: The game tree is fully expanded.
//post: Assigns a score to each board in the game tree.
// It uses a recursive auxiliary method.
public void assignScores();
//pre: Each board in the game tree has a score.
//post: Computes an array of positions (1..9) optimal available moves.
// These are the last mark positions in the children boards that have the highest score.
public int[] BestMoves();
//post: Returns the number of boards stored in a game tree.
// It uses a recursive auxiliary method.
public int size();
}
GameTree
public class GameTree implements GameTreeInterface {
private GameTreeNode root; // reference to the root board of a game tree
public GameTree(Board board) {
this.root = new GameTreeNode(board);
}
// post: Returns the board at the root of a game tree.
public Board getRootItem() {
return root.getBoard();
}
// post: Returns the number of boards stored in a game tree.
// It uses a recursive auxiliary method.
public int size() {
return sizeTree(root) + 1;
}
// post: Returns the number of boards stored in a game tree, excluded
// the root.
private int sizeTree(GameTreeNode node) {
int total = 0;
for (int i = 1; i < node.numberOfChildren(); i++) {
if (node.getChild(i).getBoard() != null)
total++;
}
return total;
}
// post: Expands the game tree fully by adding all possible boards in
// the game.
// It uses a recursive auxiliary method.
public void expand() {
expandTree(root);
}
// post: Expands the game tree from the given node by adding
// all the possible moves that the computer and the user player
// can make, until the game is finished, from the given node onwards.
private void expandTree(GameTreeNode node) {
if (!node.getBoard().isFinished()) {
char c = node.getBoard().getTurn();
for (int i = 1; i < 9; i++) {
if (node.getBoard().getMark(i) == Board.EMPTY) {
GameTreeNode n = new GameTreeNode(node.getBoard());
n.getBoard().setMark(i, c);
n.getBoard().setLastMarkPosition(i);
node.getChildren().add(2, n);
expandTree(n);
}
}
}
}
// pre: The game tree is fully expanded.
// post: Assigns a score to each board in the game tree.
// It uses a recursive auxiliary method.
public void assignScores() {
char player = (root.getBoard()).getTurn();
assignScoresTree(root, player);
}
// post: Assigns scores to each board in a game tree for the computer
// player.
private void assignScoresTree(GameTreeNode node, char player) {
Board board = node.getBoard();
if (board.isFinished()) {
// base case of recursion
// score 3 for a winning board for the given player,
// score 2 for a draw baord,
// score 1 for a losing board for the given player
char winner = board.getWinnerMark();
if (winner == Board.EMPTY) {
// this is a draw!
node.setScore(2);
} else {
node.setScore(winner == player ? 3 : 1);
}
}
else {
// tries to assign the scores to all the children boards
// first, recursively
int minScore = Integer.MAX_VALUE;
int maxScore = Integer.MIN_VALUE;
GenericList<GameTreeNode> children = node.getChildren();
for (Iterator<GameTreeNode> it = children.iterator(); it
.hasNext();) {
GameTreeNode child = it.next();
assignScoresTree(child, player);
// keeps track of the maximum and minimum scores
// of the children boards so far
int childScore = child.getScore();
if (childScore > maxScore)
maxScore = childScore;
if (childScore < minScore)
minScore = childScore;
}
// Assigns score to the current board in the recursion
// according to the player's turn
if (board.getTurn() == player) {
// get the maximum score as the player wants to
// win
node.setScore(maxScore);
} else {
// get the minimum score (as the player wants
// the opponent to lose;)
node.setScore(minScore);
}
}
}
// pre: Each board in the game tree has a score.
// post: Computes an array of positions (1..9) optimal available moves.
// These are the last mark positions in the children boards that have
// the highest score.
public int[] BestMoves() {
int maxScore = Integer.MIN_VALUE;
GenericList<GameTreeNode> highestScoreBoards = new GenericList<GameTreeNode>();
GenericList<GameTreeNode> children = root.getChildren();
for (Iterator<GameTreeNode> it = children.iterator(); it
.hasNext();) {
GameTreeNode nextBoard = it.next();
int curScore = nextBoard.getScore();
if (maxScore < curScore) {
maxScore = curScore;
highestScoreBoards.clear();
highestScoreBoards.add(1, nextBoard);
} else if (maxScore == curScore) {
highestScoreBoards.add(1, nextBoard);
}
}
int[] moves = new int[highestScoreBoards.size()];
for (int i = 0; i < moves.length; i++) {
Board board = (highestScoreBoards.get(i + 1))
.getBoard();
moves[i] = board.getLastMarkPosition();
}
return moves;
}
}
GameTreeNode
public class GameTreeNode{
private GameTreeItem item; // includes the board object and the score
private GenericList<GameTreeNode> children; //list of gameTreeNodes of possible next moves.
public GameTreeNode(Board newBoard) {
this.item = new GameTreeItem(newBoard);
this.children = new GenericList<GameTreeNode>();
}
//post: Returns the board stored in a GameTreeNode
public Board getBoard() {
return item.board;
}
//post: Returns the children stored in a GameTreeNode, as a list of GameTreeNodes
public GenericList<GameTreeNode> getChildren(){
return children;
}
//post: Returns the score of the board
public int getScore() {
return item.score;
}
//post: Sets the score of the board to be equal to the given score
public void setScore(int score) {
item.score = score;
}
//post: Removes all the children
public void removeChildren(){
children = null;
}
//post: Returns the number of children
public int numberOfChildren(){
return children.size();
}
//post: Returns the child at a given position in the list of children, as a
GameTreeNode
public GameTreeNode getChild(int i){
return children.get(i);
}
//Inner class for storing a board and the score
private class GameTreeItem{
private Board board;
private int score;
public GameTreeItem(Board newBoard) {
this.board = newBoard;
score = 0;
}
}
Apologies for the rather large amount of code but I don't think I could explain the problem without having everything here. There's still a lot of extra code for the GenericList but it's a pretty straightforward implementation for a generic linked list.
If anyone does go through this code, my problem is in the GameTree class with the sizeTree() method. I offered a solution but I think it's far too simple to be correct. As I understand it, a GameTreeNode includes a GameTreeItem containing the current state of play and a reference to a linked list of GameTreeNode. However, my specification says that I have to use recursion to implement this method but I'm not sure how. Would my method work since it goes through every single child of the root and checks for the boards?
I know it's a long shot but if anyone can offer any help I'd really appreciate it!