Quantum tic-tac-toe with alpha-beta pruning - best representation of states?

Question

For my AI class, I have to make a quantum tic-tac-toe game using alpha-beta pruning.

I'm thinking about the best way to represent a state of the board - my first intuition is to use a sort of neighborhood matrix, that is, a 9x9 matrix, and on M[i,j] is the integer which represents the move in which (tic-tac-toe) squares i and j are marked (if there is no such connection - M[i,j] is zero). M[i,i] is not 0 if square i is collapsed. Then, I would create a game tree of such matrices and use classical minimax with alpha-beta pruning.

However, it seems that this approach would be quite expensive - there would be a relatively big branching factor plus the basic operations for every node - checking for cycles and finding all equivalent states for 9x9 matrix.

I have a feeling that there's got to be a smarter solution - maybe something along the line as seeing a quantum game as a set of classical tic-tac-toe games and use a kind of generalized minimax search, so it would all regress to a (small) set of classical tic-tac-toe problems? I can't see how that would work exactly.

Does anyone have experience with this (or similar) problem, and could you point me in the right direction?

Answer 1

If anyone is still interested in this

I ended up using two seperate data structures:

• classical tic-tac-toe board (3x3 matrix) for collapsed nodes
• list of graphs for entangled nodes. Nodes of each graph are board coordinates (in a 3x3 matrix), and the graph is fully connected.

When we entangle nodes A and B:

• if neither are in an existing graph, create a new graph [A,B] (NEW_GRAPH)
• of one (A for example) is in an existing graph [..., A, ...] (EXISTING_GRAPH)
  • if B is not in an existing graph, add B to the EXISTING_GRAPH
  • if B is in an existing graph we know we closed a cycle, and we do a collapse (graphs are removed from the list, and new nodes are added to the classic board)