Representing game states in Tic Tac Toe

Question

The goal of the assignment that I'm currently working on for my Data Structures class is to create a of Quantum Tic Tac Toe with an AI that plays to win.

Currently, I'm having a bit of trouble finding the most efficient way to represent states.

Overview of current Structure:

AbstractGame

• Has and manages AbstractPlayers (game.nextPlayer() returns next player by int ID)
• Has and intializes AbstractBoard at the beginning of the game
• Has a GameTree (Complete if called in initialization, incomplete otherwise)

AbstractBoard

• Has a State, a Dimension, and a Parent Game
• Is a mediator between Player and State, (Translates States from collections of rows to a Point representation
• Is a StateConsumer

AbstractPlayer

• Is a State Producer
• Has a ConcreteEvaluationStrategy to evaluate the current board

StateTransveralPool

• Precomputes possible transversals of "3-states".
• Stores them in a HashMap, where the Set contains nextStates for a given "3-state"

State

• Contains 3 Sets -- a Set of X-Moves, O-Moves, and the Board
• Each Integer in the set is a Row. These Integer values can be used to get the next row-state from the StateTransversalPool

SO, the principle is Each row can be represented by the binary numbers 000-111, where 0 implies an open space and 1 implies a closed space.

So, for an incomplete TTT board:

From the Set<Integer> board perspective:
X_X  R1 might be: 101
OO_  R2 might be: 110
X_X  R3 might be: 101, where 1 is an open space, and 0 is a closed space

From the Set<Integer> xMoves perspective:
X_X  R1 might be: 101
OO_  R2 might be: 000
X_X  R3 might be: 101, where 1 is an X and 0 is not

From the Set<Integer> oMoves perspective:
X_X  R1 might be: 000
OO_  R2 might be: 110
X_X  R3 might be: 000, where 1 is an O and 0 is not

Then we see that x{R1,R2,R3} & o{R1,R2,R3} => board{R1,R2,R3}

The problem is quickly generating next states for the GameTree. If I have player Max (x) with board{R1,R2,R3}, then getting the next row-states for R1, R2, and R3 is simple..

Set<Integer> R1nextStates = StateTransversalPool.get(R1);

The problem is that I have to combine each one of those states with R1 and R2.

Is there a better data structure besides Set that I could use? Is there a more efficient approach in general? I've also found Point<->State mediation cumbersome. Is there another approach that I could try there?

Thanks!

Here is the code for my ConcretePlayer class. It might help explain how players produce new states via moves, using the StateProducer (which might need to become StateFactory or StateBuilder).

public class ConcretePlayerGeneric extends AbstractPlayer {

 @Override
 public BinaryState makeMove() {
  // Given a move and the current state, produce a new state
  Point playerMove = super.strategy.evaluate(this);
  BinaryState currentState = super.getInGame().getBoard().getState();


  return StateProducer.getState(this, playerMove, currentState);
 }
}

EDIT: I'm starting with normal TTT and moving to Quantum TTT. Given the framework, it should be as simple as creating several new Concrete classes and tweaking some things.

Answer 1

Shouldn't each square have only three possible states (, X, O)?

Either store a grid of 3-state squares, or store 2 lists of moves. You don't need to store the overall board because it is defined by the moves.

Also, what do you mean by:

generating next states for the GameTree

What is a GameTree? and what are some examples of "next states"?

Answer 2

My suggestion:

• Consider representing individual squares rather than rows, whereby +1 == O, -1 == X and 0 implies an empty square. This allows you to detect an end state by checking whether the sum of a horizontal, vertical or diagonal row equals +3 or -3.
• Secondly "flatten" this 2D 3x3 matrix into a single array whereby elements[0-2] represent the first row, elements[3-5] represent the second row and elements[6-8] represent the third row.
• Use either recursion or an iterative approach to generate subsequent game states given the current state of the board.

EDIT

I got bored and so decided to write some "toy code" to implement the game board, including methods to determine if it is in a terminal state and to generate the set of board states after the next move is made. It should generalise to any size board although I haven't tried. Enjoy ...

Sample Output

$ java Board
Creating board:

---
---
---

Initialising board:

-OX
O--
XO-
Terminal state: false


Generating next move states:

XOX
O--
XO-

-OX
OX-
XO-

-OX
O-X
XO-

-OX
O--
XOX

Code

import java.util.List;
import java.util.LinkedList;
import java.util.Random;

public class Board {
    private final int[] squares;

    public Board() {
    this.squares = new int[9];
    }

    protected Board(int[] squares) {
    this.squares = squares;
    }

    public void init() {
    Random rnd = new Random();
    int turn = 1; // 'O' always goes first.

        for (int i=0; i<squares.length; ++i) {
        double d = rnd.nextDouble();

        if (d < 0.75) {
     squares[i] = turn;
     turn = turn == 1 ? -1 : 1; // Flip to other player's turn.
        } else {
     squares[i] = 0; // Empty square.
        }

        if (isTerminalState()) {
     break;
        }
    }
    }

    public boolean isTerminalState() {
    boolean ret = false;

    boolean foundEmpty = false;
    int hSum = 0;
    int[] vSum = new int[3];

    for (int i=0; i<squares.length; ++i) {
        hSum += squares[i];

        if (isWinningRow(hSum)) {
     ret = true;
     break;
        } else if (i == 2 || i == 5) {
     hSum = 0;
        }

        int col = i % 3;
        vSum[col] += squares[i];

        if (isWinningRow(vSum[col])) {
     ret = true;
     break;
        }

        if (squares[i] == 0) {
     foundEmpty = true;
        }
    }

    if (!ret) {
        if (!foundEmpty) {
     ret = true;
        } else {
     int diag1 = 0;
     int diag2 = 0;
     int rowSz = (int)Math.sqrt(squares.length);

     for (int i=0; i<squares.length; ++i) {
         if (i % (rowSz + 1) == 0) {
      diag1 += squares[i];

      if (isWinningRow(diag1)) {
          ret = true;
          break;
      }
         }

         if (i > 0 && i % (rowSz - 1) == 0) {
      diag2 += squares[i];

      if (isWinningRow(diag2)) {
          ret = true;
          break;
      }
         }
     }
        }
    }

    return ret;
    }

    private boolean isWinningRow(int rowSum) {
    return rowSum == 3 || rowSum == -3;
    }

    public List<Board> getNextStates() {
    List<Board> ret = new LinkedList<Board>();

    int tmp = 0;
    for (int i=0; i<squares.length; ++i) {
        tmp += squares[i];
    }

    // Next turn is 'O' (i.e. +1) if the board sums to 0.
    // Otherwise it's 'X's turn.
    int turn = tmp == 0 ? 1 : -1;

    if (!isTerminalState()) {
        for (int i=0; i<squares.length; ++i) {
     if (squares[i] == 0) { // Empty square      
         int[] squaresA = new int[squares.length];
         System.arraycopy(squares, 0, squaresA, 0, squares.length);
         squaresA[i] = turn;
         ret.add(new Board(squaresA));
     }
        }
    }

    return ret;
    }

    public String toString() {
    StringBuilder sb = new StringBuilder();

    for (int i=0; i<squares.length; ++i) {
        if (squares[i] == 1) {
     sb.append('O');
        } else if (squares[i] == -1) {
     sb.append('X');
        } else {
     assert squares[i] == 0;
     sb.append('-');
        }

        if (i == 2 || i == 5) {
     sb.append('\n');
        }
    }

    return sb.toString();
    }

    public static void main(String[] args) {
    System.err.println("Creating board:\n");
    Board bd = new Board();
    System.err.println(bd);

    System.err.println("\nInitialising board:\n");
    bd.init();
    System.err.println(bd);
    System.err.println("Terminal state: " + bd.isTerminalState() + '\n');

    System.err.println("\nGenerating next move states:\n");
    List<Board> nextStates = bd.getNextStates();

    for (Board bd1 : nextStates) {
        System.err.println(bd1.toString() + '\n');
    }
    }
}