Backpropagation for 'Classification' Neural Network

Question

Question: How does one formulate a back propagation algorithm (either batch, gradient, anything that works) for a neural net, playing a game of Tic Tac Toe?

(Java is being utilized)

Scenario: There are 9 input neurons, one for each square. A value of -1 represents X, 1 represents O, and 0 represents an empty space. These values are stored in 1x10 array (the tenth input being bias). These lead to a single hidden layer, with n nodes (n selected on boot). The weights between the input and hidden layer are stored in a 10 x n array. A typical sigmoid activation function is used on the hidden layer. The hidden layer then leads to 9 output neurons, with weights stored in a n x 9 array. A separate function is used to normalize the output, dividing every point by the largest output, and whichever neuron is storing "1", the next move is made there. I've gotten this portion to work.

The cost function is as follows- Every board has an "advantage", which is equal to 10(turns till lose) - 8(turns till win) - 100(boolean invalid[i.e. placing a piece over another piece]). A negative advantage is bad for the AI, positive is good. Cost therefore, is cost = 1/2(best possible delta(advantage), - the delta(advantage) that the AI comes up with)^2. Squared in order to make the function convex, multiplied by .5 for the power rule to make it cleaner.

Here lies the problem: I need to calculate the derivative, so I know what way is down hill. How do I calculate the derivative for the advantage function, if it uses if statements, loops, etc.? It really is more of an operator, than a function- is there a way to re-write a cost function for tic-tac-toe which would be more conducive to machine learning? Or is there a way to derive around this?

I hope I explained that correctly- P.S. This is not for a class, rather my own blatant curiosity.

Answer 1

As D.W. points out, please consult a textbook on neural networks, or Wikipedia. The answer to your question lies in the insight that neural networks do not inspect the cost function or algorithm used to compute it, but it is an empirical method. That is, you will have to play many games of Tic Tac Toe (or generate configurations at random, whichever), compute the cost function yourself, and then feed the configuration with its cost function to your neural network, which then does backpropagation, and repeat. Alternatively, you may collect a large batch of data and feed the batch to the neural network. Either way, the gradient of the network at a particular configuration is a value computed only from available data.

That said, and while most numerical algorithms have no well-defined derivatives, there are edge cases, for example the identity function $f(x) = x$, but most have no practical use. Then there are algorithms that estimate the derivative of a function such as the one you supplied form a large batch of data that a neural net can use to aid its search by improving its gradient estimate, but that will get you into some very deep waters. Deep waters, but fun waters, so consult a textbook if you want to know about that.

Answer 2

The way you do back propagation for neural network has nothing to do with what you are using the neural network for. It depends only on the structure of the neural network.

Consequently, all that information about tic tac toe doesn't seem relevant.

Lots of textbooks explain how to do backpropagation for a neural network. I suggest you try applying the description of how to do backpropagation from a textbook; or seek out an existing implementation of a neural network that does backpropagation for you.