Can Neural Network play tic tac toe? Is this have any common sense?

Question

I'm thinking about theoretical possibility of playing tic tac toe by neural net. Is this have any common sense? Let's consider tic tac toe which contains 3 rows and 3 cols (it's 9 cells). Ok, then the input vector is contains of all our cells: [0..8], where 0 - is: "O", 1 - is: "X" and 2 - is empty cell.

But what we have for the target vector? On every NN's step we need to know some target and make our distance to target shorter. But the target of this game is only win (or maybe draw), I don't understand how we can make shorter our distance to win. Is any suggestions?

My goal is to learn more about neural networks in games that's why I consider such easy game. Maybe it's not the best choice for the NN and I need to consider some other game? :)

Answer 1

You define what is an advantage. For instance in an actual game scenario, an advantage may be defeating or damaging an enemy unit or perhaps recruiting an optimal unit. In this scenario, an advantage would be perhaps blocking one of the enemies paths while positioning yourself in a spot that is as unconstrained as possible.

Example:

Each player can win in two moves in two possible ways: straight column and a diagonal sequence.

X|_|O
_|_|_
 | | 

Possibly worse move: player X can now win in two moves, in three ways (two columns and one diagonal). However she did not block player O at all.

X|X|O
_|_|_
 | | 

A slightly superior move: player X can win in two moves in three ways (one column, one row and one diagonal) and also blocked one victory path for player) (the column).

X|_|O
_|_|X
 | | 

A superior move: player X can win in one moves in one way (one diagonal) and two moves in two ways (one column, one row) and also blocked one victory path for player) (the column).

X|_|O
_|_|_
 | |X

Basically each move pays for a making a theoretical victory possible in less moves, blocking a winning path for the enemy and thus increasing her minimal move count to victory.

Answer 2

"Neural network" is largely a buzzword, real game AI is a lot of different things, but rarely something that fits the term thoroughly.

The closest thing that can broadly be applied to games is automatic optimization of magic constants, that is when you have written a reasonable AI for your game, you can take all the potentially different constants of that AI, put them on a list, and have the AI play against itself with different values of those constants to determine which set is better. You can then take the winning set, apply some further changes, let the changed set play against the original etc. Depending on how fast you can play a game you might end up running through millions or billions of games in the process.

The process itself has to be crafted carefully, if you adjust the numbers too little it will be too slow, if you adjust them too much you'll almost never get anything better. If you don't play enough games with a given set of AIs the result might be too random. But do in general make sure that there is some random behaviour or you risk making an AI that only plays well against the previous iteration. Having a broad set of different enemies to test against may also be a good idea, even if they are objectively not very good.

And of course this whole process won't save you if you haven't made an AI that is suitable for it in the first place.

If you want to test it out on Tic Tac Toe, write an algorithm that for each possible move generate a number based on some properties of that spot. Then choose a move randomly with greater chance for choosing a move with a high number. If don't include the chance you won't train for countering a lot of the possible moves.

Answer 3

If it's really just for fun, how about you take the optimal solution that user41806 posted and use it to define the error?

Seeing that you know the number of possible wins, defeats and draws that each state can result in, you could assign a positive value to a win-scenario and negative values to defeats and draws. To get the desirability of a state you sum those values up and divide them by the number of total outcomes:

E = (nWins*3 + nDraws*-1 + nDefeats*-2) / (nWins + nDraws + nDefeats)

(or something like that)

Using an ANN here is really not practical though, because it's difficult to factor the opponent in: You might want to scale each outcome-value by the number of steps it takes to get to it, but in what way? With a dumb opponent you want to get to the end quickly, but a smart opponent might recognise a scenario that's too obviously bad for them.

ANNs are more useful for fuzzy, unclear situations, while perfect information games like Tic-Tac-Toe (Chess, Checkers etc) are usually done with mini/max, which is arguably a bit boring, but you can still make the agent behave more organically and human-like (stupid) by randomly limiting how far they look ahead or by scaling each state's desirability by a random Gaussian number, to make the agent make "mistakes".

Answer 4

While training a neural network to play Tic Tac Toe should be possible, I don't see the purpose. The game was fully analyzed and the optimum approach is known. A very good visualization for that can be found here: http://xkcd.com/832/

Answer 5

When i started working on my Tic Tac Toe which uses neural net and get its training data from the opponents moves(Human Player), i was also thinking of this problem about the output vectors, then I tried something which may help. I used a multilayer perceptron network with 9 input neurons and 9 output neurons, for input neurons the inputs were 0->empty,1->X,-1->O and for each board state I generate an output array as 1->last move that opponent played and 0->all other moves. then with each move i find the neuron with the largest output vector and the index of that neuron was the Neural Player's move.