# Backpropagation for 'Classification' Neural Network

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.

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.