How to code an artificial neural network (Tic-tac-toe)?

Question

Hello!

I want to play Tic-tac-toe using an artificial neural network. My configuration for the network is as follows: For each of the 9 fields, I use 2 input neuron. So I have 18 input neurons, of course. For every field, I have 1 input neuron for a piece of Player 1 and 1 neuron for a piece of Player 2. In addition to that, I have 1 output neuron which gives an evaluation of the current board position. The higher the output value is, the better is the position for Player 1. The lower it is, the better is it for Player 2.

But my problem is: How could I code that neural network? My idea was to use an Array[1-18] for the input neurons. The values of this array are the input weights. The I would walk through the array using a loop. Whenever there is a neuron to be activated, I add the weight to the output value. So the output value is the sum of the weights of the activated input neurons:

Output = SUM(ActivatedInputNeurons)

Do you think this is a good way of programming the network? Do you have better ideas?

I hope you can help me. Thanks in advance!

Answer 1

This is an excellent starter project for AI coding, but coming up with a complete solution will be way to big of an answer for SO.

As with most software, I recommend using an object-oriented design. For example: Define a Neuron class which has inputs, weights, and an output function. Then, create several of these Neuron objects in order to build your network.

See the wikipedia article on artificial neural networks for a good starting point.

Good luck with the code! Sounds like a lot of fun.

Answer 2

After adding the weights, you need to normalize the sum using a function, people usually use TANH, if you want to allow negative numbers.

edit:

Here is a java multilayer perceptron implementation that i worked on a few years ago. this one was used for checkers, but with less inputs you can use it for checkers too.

Also, you need to probably figure out a way to teach it to win, but thats another problem

Answer 3

It is not a direct answer to your question, but you should have a look at the following framework/tool: SNNS or its Java counterpart JavaNNS. I'm pretty sure that there you'll find an answer to your question.

Answer 4

I think you should implement a 'traditional' feed-forward ANN using transfer functions, as that allows you to train it using back-propagation. The code for these usually ends up being a few lines of code, something like this:

SetupInputs();
for (l = 1 .. layers.count)
    for (i = 0 .. layers[l].count)
        sum = 0
        for (j = 0 .. layers[l-1].count)
            sum += layers[l-1][j] * weights[l-1][j]
        layers[l][i] = TransferFunction(sum)

Answer 5

I don't particularly understand how you expect to get a meaningful summary of the board situation out of one output neuron. I would more look at having:

    I I I             O O O
    I I I      x      O O O
    I I I             O O O
9 input neurons  9 output neurons

in a fully connected network, i.e. 81 weights. Then train the output neurons for the relative desirability of playing in that position.

Answer 6

Well, you have an input layer of 18 neurons, and an output layer of 1 neuron. That's OK. However, you need to give your neural net the opportunity to put the inputs into relation. For that, you need at least one intermediate layer. I would propose to use 9 neurons in the intermediate layer. Each of these should be connected to each input neuron, and the output neuron should be connected to each intermediate. Each such connection has a weight, and each neuron has an activation level.

Then, you go through all neurons, a layer at a time. The input layer is just activated with the board state. For all further neurons, you go through all its respective connections and sum over the product of the connected neuron's activation level and the weight of the connection. Finally, you calculate the activation level by applying a sigmoid function on this sum.

This is the working principle. Now, you need to train this net to get better results. There are several algorithms for this, you will have to do some googling and reading. Finally, you might want to adjust the number of neurons and layers when the results don't get convincing fast enough. For example, you could reduce the input layer to 9 neurons and activate them with +1 for an X and -1 for an O. Perhaps adding another intermediate layer yields better results, or increasing the number of neurons of a layer.

Answer 7

there is a example http://derindelimavi.blogspot.com/2007/07/ysa-ile-tic-tac-toe.html

Answer 8

Have a look at my Tic project. I've solved this problem with both neural network and genetic algorithm. The source code is freely available.

http://www.roncemer.com/tic-tac-toe-an-experiment-in-machine-learning