Building a Tic Tac Toe game which learns by itself

Question

Let's assume we have a huge database gathered which contains winning sequences, which each player played and won. (Both the players are programmed, to obtain random numbers and attempt playing the game).

What would be the best way to use these winning sequences each player has gathered for future plays? Are we going to program one occurrence to play without using historical data and few other occurrences using historical data?

What would be the best way to save the winning sequences, the entire path which both the player One and Player Two has taken or only the sequence used by the winning player?

This is my first attempt to machine learning paradigm and hope some support could be taken!

Answer 1

I took an introductory computer science course on Coursera a few years back where we had to use a Monte Carlo algorithm to build a tic-tac-toe AI. Instead of using historical data, we generated data using a function that would play through a series of games with random moves, but I think the principle is basically the same.

Each square on the board has a separate score associated with it. For each game completed, the scores change based on which player won. If the player designated as the machine player won, the machine player's score for each square on the board where it placed a mark would increase and the "other" player's score would decrease for every square where it placed a mark. Conversely, if the other player won, its score would increase for each square on the board where it placed a mark and the machine player's score would decrease. If the game is a tie, the number of points for each square would not change.

So, to answer your question, I think it is important to track both the winning and losing player's moves because we need to know not only what works but also what doesn't work.

Edit: I just remembered that my first implementation did not deduct points on the grid for games lost and because of this, my AI had an all-out "offensive" strategy. In other words, it focused on getting three-in-a-row without making any effort to block the human player. This is why it's important to track moves that result in a loss.