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?

Thanks!

Edit: 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

To provide a learning feature to your implementation, you may look into an emulator for Donald Mitchie's MENACE (Matchbox Educable Noughts And Crosses Engine)...

Edit:
In looking into it, this has been done quite a bit, see for example this on CodeProjet
Furthermore, and while acquiring a statistical model of the world (or here of the Tic-Tac-Toe reduced world) and basing future actions upon such a model is intelligent behavior, it may be considered out of scope by your professor, because not touching key concepts you probably covered in class (knowledge representation, decision trees...)

Answer 2

Impress your professor by implementing patterns and real-OO code instead of boring lengthy if/else blocks in one large method block. As it's a strategy game, start with the strategy pattern. Also try to care every element as an fullworthy Object with properties and methods. That's your strategy for now.

Answer 3

There are 2 parts to evaluating a turn based game.

1. The game tree.
2. A utility function.

The game tree allows you to play out moves ahead of time to see where they will lead. If the game is complex enough that you cannot compute all possibilities (http://en.wikipedia.org/wiki/Solved%5Fgame), then you need a way of determining how "good" a particular board scenario is. A poor utility function for chess might simply count piece values and ignore position.

You also need an efficient way of traversing the game tree. Read about Minimax, Alpha-beta pruning, Negascout, etc.

Answer 4

Your desire to learn new things (on your own even) is good. However a complicated solution is often not the best solution.

There is a very good reason your professor suggested using a game tree for the AI. It's suggested because its the right tool for the job. There is not a better approach that you can research because it is the best approach.

You mentioned that you're in a data structures class (which is usually a first or second year class). I'm guessing that the point of your assignment is to learn about tree data structures. If you want to make things more complicated, write the tree version first and then go and research other ways of solving the same problem.

Answer 5

I'm actually working on this specific problem right now: http://www.rickb.com/quantum-tic-tac-toe

I had considered doing something more advanced as well, but I'm just sticking to the good ol' alpha-beta search algorithm. My main problem is coming up with a good algorithm to "score" each particular board state. QTTT is much more complicated than standard tic tac toe, the number of states to search is exponentially larger. I have the full standard tic tac toe game tree in memory which I use to quickly look up the score for each "classical" board state, but then I have to somehow score the superposition state. The number of states is so large that you can't go too deep in the tree so an appropriate scoring function to prune the tree early is a must.