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

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 generalize开发者_运维技巧d 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?

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)

If your problem is just Tic-Tac-Toe, than you can represent your board the way this program of mine does http://pastie.org/1715115

It is a ternary based number matrix. A board is a 9-digit number where each digit has one of 3 possible values: 0 for empty, 1 for x and 2 for o.

This approach is excellent for minimax as a board can be set in a single integer! The matrix has a form of:

int suc[TOTAL][2]={ { 0, 10000}, { 1, 20001}, { 10, 20010}, { 12, 1012}, { 21, 1021},
    { 100, 20100}, { 102, 100102}, ...

where each pair of numbers corresponds to (a) the present position, and (b), the next better position calculated beforehand by a minimax. So, if the board is empty (suc[0][0]==0) the next better position is to put an 'x' into the position 5, i.e. the center (suc[0][1]==000010000)

Actually, with this program you even don't need to create a minimax as this program already calculated all possible answers in the ad-hoc matrix. The most important function, to chose the next move, is done simple looking into the suc (successor) matrix:

/* find and return the next board after the given board terno */
int move(int terno)
{
    int i;

    for (i=0; i<TOTAL; i++)
        if (suc[i][0]==terno)
            return suc[i][1];
    return 0;
}

It is a good approach for quantum algorithms (and embedded systems). I hope this helps you.

Take care