Quantum Tic-Tac-Toe AI

Question

In my data structures class, we've been assigned a project in which we are required to make a fully functioning Quantum Tic-Tac-Toe game in which a player faces a bot that plays to win.

The professor suggested we use a game tree in our AI. However, as usual, I am looking for something more challenging.

Can anyone suggest a better, more advanced approach that I could research and implement?

---

I'm not looking for something completely ridiculous that makes the problem more complex. Rather, I'm looking for an advanced approach -- like using an A* algorithm rather than a BFS.

Answer 1

In the Quantum Tic Tac Toe game, similar to the classic Tic Tac Toe, There are several important features which enable us to present it as a game tree:

• It is a zero-sum game for two players - only one can win through a loss of the other (except for a draw), and both players want to win.

• The game's turns performed serially (one after the other)

• Deterministic game: Given the same players moves the result of every move stays the same - there are no external nor random factors that affect the outcome.

• The game has "full information" about the state of the game and its rules.

These features enable us to see the game as a game tree with all possible moves as its nodes and to analyze the game using the search on the tree using the "Minimax" approach.

Since the number of vertices in the tree higher than what we can calculate on a reasonable time can't do a complete search over all the game tree nodes. 

We used the method of Alpha - Beta pruning in which we reduce the number of vertices on which we perform the search by skipping vertices that previous calculations show them irrelevant. 

In Tic Tac Toe the rules are applied for all the final (non-quantum) positions, therefore Tic Tac Toe strategies and heuristics can be used to some extent. One important aspect is that there are perfect games: The X player can force a draw assuming X plays first. There are also special situations that arise from the games "quantum" nature. We tried several heuristics that take those into account.

Heuristics

• Collapse Avoidance - This heuristic values boards with a higher number of non-collapsed marks over boards with more collapsed states.

• Threat Avoidance - This heuristic values boards in which there are fewer possible threats (that is, possible victories for the opposing player) over boards in which the opposing player has more quantum marks that form a possible victory. TBD Example

• Victories Evaluation - This simple heuristics gives all boards a value of 0 unless this board is a winning board, in that case, it gives it the value of the victory.

• Random player - A random player was created for testing purposes. It chooses actions at random.

If you wish to know more about Artificial Intelligence then visit this Artificial Intelligence Course.