Representing game states in Tic Tac Toe
- by dacman
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.
