4
$\begingroup$

My only experience with Machine Learning is Andrew Ng's Coursera course, but I did work through that just fine and passed with 100%.

I decided to practice by making up some problems and solving them. My idea was to create a simple tic tac toe game, and have it just play millions of random games, and use the data to learn to predict the next move based on sequences that won in the past.

Is it reasonable to expect to learn to predict a good move from 1 million samples of games that player X won?

I have a function getWinSequences('X', 1000000) that returns of list of sequences that win for X. A sequence represents series of choices, 1 to 9, on the game board.

The board would look like this:

1|2|3
-----
4|5|6
-----
7|8|9

So WinsX looks like this:

[
    [4,2,5,3,6],
    [1,4,2,8,3],
    [1,2,4,3,5,8,9]
]

So in the first sequence, that means that player X chose 4, O chose 2, X chose 5, O chose 3, X chose 6

So X won with 3 in a row, 4,5,6 ([4,2,5,3,6])

Now, I'm not doing machine learning on the winning sequences, because I want the program to get a "current board position" not a sequence. In other words, given a board with none or some X's and O's, assuming it's player X's turn, predict a good move (1-9) based on past observations a boards, and knowledge of the next move that was chosen

So I have a function that converts a winning sequence into a series of board positions, and a label saying which move is next.

So the actual data that I train on is like this

X[0] = [0,2,2,
        1,1,0,
        0,0,0]
y[0] = 6

0 means empty, 1 means an X is there, 2 means a Y is there. So based on my winning sequences, I am able to automatically label that position as "6", because the board is a recreation of what the board looked like just before we "randomly" won by choosing 6.

Because I want to be able to predict a good move even if there is no winning move, then whenever I have a winning sequence, I don't just create a board as it was just before the win, I create a board for every step along the way of a winning sequence, and label it with the next move from the winning sequence.

So a winning sequence will usually result in 3 to 5 examples of a board position, and a label (1-9) saying what the move for that board should be.

I figured that with a million examples of winning sequences, and the board positions that led to the win, I would be able to predict the next move. Is that reasonable? If so, what is a good way to train on the data? When I trained on 1 million examples, I got a score of .29 from GradientBoostingClassifier.

the relevant code looks like this:

winsX = getWinSequences('X', 1000000)
samplesX = samplesFromWins(winsX)

X = [row[:9] for row in samplesX]
y = [row[9] for row in samplesX]

X_train, X_test = X[:700000], X[700000:]
y_train, y_test = y[:700000], y[700000:]

print("got data, ready to train")

clf = GradientBoostingClassifier(n_estimators=100, learning_rate=1.0,
    max_depth=1, random_state=0).fit(X_train, y_train)

print(clf.score(X_test, y_test))

I just want to know if I'm on the right track, or if there is a fundamental flaw in what I'm doing.

$\endgroup$
3
$\begingroup$

The main flaw in this method is the following one. You want to predict a move that leads to winning, but instead the model you use tries to guess one certain move from the database that may lead to winning. To fix that, at least you should estimate your model performance not by predicting the “correct” move for the test example, but by the rate of wins it actually achieves. In most cases, there is no single correct move, since multiple moves can lead to winning. For example, for your object

X[0] = [0,2,2,
        1,1,0,
        0,0,0]

the most reasonable prediction is 6, although the training set probably also contains 9, since it may eventually lead to winning as well. However, the move 9 is worse than 6: the rational opponent would win in that case. However, the model treats that moves equally since the training set lacks any losing strategies.

If you still want to treat it as a supervised learning problem, you can instead model the distribution $P(\textit{result} \mid \textit{move}, \textit{board})$ where $\textit{result} \in \{\textit{win} , \textit{draw}, \textit{lose} \}$. To choose the move, just maximize the probability of winning, or minimize the probability of losing. More generally,

$m = \arg\!\min_{move} ~f\Big(P(\textit{result} = \textit{win} \mid \textit{move}, \textit{board}), P(\textit{result} = \textit{lose} \mid \textit{move}, \textit{board}) \Big)$,

where $f$ is some loss function. You can estimate those conditional probabilities from simulations, similarly to what you done for generation of winning strategies.

However, this model has the problem: it treats your opponent’s moves (and your further moves) as being drawn randomly. Game theory advices to choose your strategy assuming that your opponent is rational, i.e. you chose your move to maximize your expected payoff, assuming your opponent then chooses hers by minimizing it. For tic-tac-toe, the best strategy in this sense can be found deterministically by traversing the tree of board configurations, not even exploiting learning from data.

If you want to account for long-term strategies in games like that, you should use techniques from reinforcement learning, which is, roughly speaking, learning not from class labels, but from simulations. Q-learning is one such technique. Here is the lab assignment asking to implement q-learning exactly for tic-tac-toe. It quotes this chapter on theory of reinforcement learning.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. This is exactly why I decided to practice, because when courses give you an assignment and tell you which method to use, of course it's going to work, but it's not realistic. $\endgroup$ – AwokeKnowing Aug 13 '14 at 15:59
  • $\begingroup$ with regards to treating the correct moves "6" and "9", my intuition was that with a large dataset, there would end up being more 6's than 9's for that board configuration, because some of the 9's would end up loosing. So I thought that would take care of the probabilities being better for 6. The training however consistently chose 7, though I'm not sure why. $\endgroup$ – AwokeKnowing Aug 13 '14 at 16:05
  • $\begingroup$ I do understand that the problem is better suited for reinforcement learning, but my goal was to try to tackle the problem without "modeling" it too closely. I figured in "real life" I wouldn't always understand the data exactly, but if there was a pattern, I should be able to predict it. I chose tic tac toe so I could fully understand the model and evaluate where I went wrong, but I didn't want to build the a priori knowledge (eg, 3 in a row wins) into the model. The "pattern" is just that there will be more samples where a certain (good) move wins than the bad moves. $\endgroup$ – AwokeKnowing Aug 13 '14 at 16:14
  • $\begingroup$ You mention the problem with modeling the moves as random. What if the trained brain iteratively plays against itself to generate new data? If the training makes it any better at all, by having more instances of the same board where 6 was chosen than 9 (because some 9's lost, so were not included), then it seems it would get smarter by playing against itself, since it would start to cull away the randomness. I think I'll try that next, but if you could provide a Yes/No and brief why, that would be helpful. $\endgroup$ – AwokeKnowing Aug 13 '14 at 16:17
  • $\begingroup$ You are right, the classifier should prefer more popular label. It probably does not due to underfitting: it “merges” similar boards and tries to infer a common good answer. Try to increase the number of trees. Also try to call the predict_proba(X) method to look at the distribution. As for your new suggestion, it seems close to ideas of reinforcement learning. You have not specified what loss function you’ve been going to minimize, but I am sure you can choose a good one. I think it should still be task-specific (i.e. connected to game result), this is what you typically do have in practice $\endgroup$ – Roman Shapovalov Aug 13 '14 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.