I wrote a little tic-tac-toe game to experiment with AI. It can support anysized board in two or three diminsions and any number of players. I can plug in little AI people to play! Fun fun, anyways I was wondering if there are any good Neural Net software kits for free, which could be used for such a problem? I'm really interested in neural nets, because what i've heard is that they are good at learning? Also does anyone have some good reference material on the actual math involved? Most of the articles I've found on google are just intros which just tell me what they do but not how? Thanks, Nick

A Neural net seems to me, to not be the best candidate for this. A simple minimax algorithm will always give the best move easily.
[google] for minimax.
And if you don't want it to play perfectly every time then you could throw a little randomness into the minimax calculations and vary the aparent level of intelligence. (Allowing you to sometimes win)

I encourage the use of overkill on problems, to give the programmer an idea of what techniques are best for themselves.. and what better project to implement such a challenging programming technique than a simple program?

As for neural nets, there are great tutorials at aijunkie.com at least I think that is what the sites name is.

Quote: Original post by iMalc
A Neural net seems to me, to not be the best candidate for this. A simple minimax algorithm will always give the best move easily.
[google] for minimax.
And if you don't want it to play perfectly every time then you could throw a little randomness into the minimax calculations and vary the aparent level of intelligence. (Allowing you to sometimes win)

While you are correct that a neural net would certainly not be the best method to use for tic-tac-toe, I would still encourage nickmerritt to continue his experimentation. Sometimes it's not about the best way, but about learning an interesting technique. I'm a sucker for machine learning techniques because i get a thrill out of the fact that I didn't have to tell my algorithm anything about the task it performs. It just learns on its own.

Quote: Original post by nickmerritt
Also does anyone have some good reference material on the actual math involved? Most of the articles I've found on google are just intros which just tell me what they do but not how?

When I learned to implement back-propogation with gradient descent, I learned it from a textbook, so I don't have any references on where to pick it up on the net. However, any textbook on AI worth its weight should have a section on this. I suggest a trip to a library.

I also recommend you write your own neural network. It's a pretty small application, and if you understand the math, you can probably hammer it out in a few hours. If you give yourself the ability to generate arbitrary topologies in your implementation, you'll be pretty much set.

One thing I can do for you is propose a framework for getting a neural network to learn to play tic-tac-toe. It will follow the general layout of Gerald Tesauro's TD-Gammon algorithm, so go ahead and google for that paper for background. For simplicity, I will limit it to a 3x3 board.

First, we will have to have a set of terminal states. These are states where either player has won.

In addition to a neural network, you should look into the SARSA algorithm. It is a temporal difference reinforcement learning algorithm that will be able to establish the error function for your neural network's output.

My suggested topology for the network (which might be wrong), would be to have two neurons for each cell on the board. One neuron represents x and the other represents o. The input to that neuron will be 1 if the player occupies that cell and zero otherwise. Then comes a hidden layer and then a single output neuron. This output neuron should represent the probability of winning the game from that state. Once you understand SARSA, you will know how to figure this probability out and train the network. Then, you choose your action based on checking all possible successor states to your current state and choosing the state that maximizes your probability of winning.

It's working nice with ANNs:
http://www.colinfahey.com/2003apr20_neuron/2003apr20_neuron.htm

You should really implement alphabeta, once you've done minimax.
It works well, as it will expand sqrt(n) nodes, where minimax expands n nodes. This is with random move sorting. if you sort it the right way, it inspects fewer nodes.

Worst case is 3^27 (Number of permutaions in a 3x3x3 board. (3d)).
Thats 7,625,597,484,987 nodes. Thats every possible board position.
Now with alphabeta, you only have to acess 2,761,449 nodes. that is tiny.
2M nodes, you could do that in a few seconds.
Say you have a minute, to work through the entire tree.
Thats 60 / 2,761,449 Seconds per node.
Thats 0.000021727723380008103 seconds per node.
Now, you probably have a 3Ghz processor.
Thats 3 billion cycles per second.
Thats 3 * 10^12 cycles * 0.000021727723380008103.
So, you have 21,727,724 Cycles per node. Thats a lot of time.
And, thats assuming you don't use hash tables, or anything else, to speed up your search. and that you search the entire thing.

Just something to think about.

From,
Nice coder