Geek Answers Handbook

Quantum tic-tac-toe with alpha beta pruning - a better view of states?

For my AI class, I have to make a quantum tick-game using alpha-beta cropping.

I think of the best way to represent the state of the board - my first intuition is to use some neighborhood matrix, i.e. 9x9 matrices, and on M[i,j] - an integer that represents the movement in which the tic-tac-toe i and j squares are marked (if there is no such connection, M[i,j] is zero). M[i,i] not equal to 0 if square i collapsed. Then I create a game tree of such matrices and use the classic minimax with alpha-beta cropping.

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

I have a feeling that there should be a more reasonable solution - maybe something similar to a line, considering a quantum game as a set of classic tic-tac-toe games and use a kind of generalized minimax search, so this is all regression on ( a small) set of classic tick problems? I do not see how this will work.

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

+4
source share
2 answers

If anyone is still interested in this

I ended up using two separate data structures:

  • classic tic-tac-toe board (3x3 matrix) for folded nodes
  • list of graphs for tangled nodes. The nodes of each graph are the coordinates of the board (in a 3x3 matrix), and the graph is fully connected.

When we confuse nodes A and B:

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

If your problem is just Tic-Tac-Toe, then you can present your board like my program http://pastie.org/1715115

This is a ternary matrix of numbers. The board is a 9-digit number, where each digit has one of three possible values: 0 for empty, 1 for x and 2 for o.

This approach is great for minimax, as the board can be installed in one piece! The matrix has the form:

 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 current position and (b) the next best position, previously calculated minimax. So, if the board is empty (suc [0] [0] == 0), the next best position is to put "x" at position 5, that is, the center (suc [0] [1] == 000010000)

In fact, with this program you don’t even need to create minimax, since this program has already calculated all possible answers in the ad-hoc matrix. The most important function, in order to choose the next step, was done by a simple search for the success matrix (successor):

 /* 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; }

This is a good approach for quantum algorithms (and embedded systems). Hope this helps you.

Take care

0
source

More articles:


All Articles