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?

Surcharge

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)

Surcharge

Answer 2

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

Leptorrhine

#define TOTAL 4520 is the total of valid positions (combinations) of a tic-tac-toe game (with x always starting). – Leptorrhine