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.