Neural network

[alkatran]

I'm working on a game of tic-tac-toe that uses an NN evolved using a genetic algorithm. The problem is that the GA doesn't seem to be finding the answer. Even after a hundred generations the best NN doesn't even go for the obvious 'complete your friggin row' moves!

I don't suppose anyone has any obvious hints for this? I'm currently using a "how good is this board?" approach, where I pass each possible move to the NN, it returns a fitness value, and then the highest fitness move is taken. I'm passing the value of all the cells to the NN (1 for yours, -1 for his, 0 for empty) as well as the absolute value of cells (filled or empty). Right now it has 18 inputs, 2 9-neuron hidden layers and a single output (the fitness) ... The fitness of each NN is determined solely based on wins (+1), loses (-2) and ties (0). They are randomly matched against 5 opponents each in a tournament to determine fitness.

Is there some problem that makes Tic-Tac-Toe unsuitable for this?

[cyborg]

I can't help you with this, but I'm really interested in how NN apps work and would like to learn some basic stuff...
Do you have any good sites with tutorials or something?

[alkatran]

ai-junkie.com is an excellent site for this type of thing, even though it's essentially never updated.

[cyborg]

Thanks, I'll have a look!

[Asgorath]

2 tic-tac-toe expert players always tie the game...
maybe the standard minimax algorithm is better then GH for this particular kind of game.

Regards
Jorge

[alkatran]

2 tic-tac-toe expert players always tie the game...
maybe the standard minimax algorithm is better then GH for this particular kind of game.

Regards
Jorge

Well of course, the game is so simple you can search the entire space each move, the idea is to learn about neural networks. I've already programmed simple unbeatable tic-tac-toe AIs composed of the simple rules: win, block, check for preprogrammed blocks, random move.

[Shaggy Hiker]

I'm not so familiar with NN as I am with GA. My experience with GA is that it WILL find an answer to the question you asked. If the results are not what you expected, and the program is working, you should check whether or not the question being asked is REALLY the question you intended to ask.

For instance, I had a GA that evolved equations using some variables. I posed a problem to it where I KNEW that one variable HAD to be in the equation, but I wasn't sure about the rest. To my surprise, the GA never included the one variable that HAD to be there. I had tested the program on some sample data, so I felt confident that it worked. When I went back to my data, I realized that all the values I was using for that one variable were roughly the same. Therefore, including the variable in the equation had the effect of mulitplying by 1. Little wonder the GA thought that wasn't worth doing.

In your case, I wonder if the impossibility of a good outcome (you can't win against a competent opponent) might be causing the prog to learn the wrong lesson.

[alkatran]

That's generally what I thought: I figured that the evolution was going a loop, where strategy X beats Y which is beat by Z which is beat by X. Maybe it's just not the type of problem evolution is good at.

[Shaggy Hiker]

It may not be. In a way, it may be too simplistic. One thing I have found with GA's (and I have since read this in a paper on the subject) is that they do really well for a while, then they seem to lose steam. They get to a certain quality of answer, but can't seem to progress past that point.

I have gotten around that with two and three tier GA's where there are multiple runs, and the winner of each run is added to a new population. When that winners bracket population fills up, that is evolved against each other. Some people have described this as hybrid vigor, and it sure does seem to act that way. The winner of the winners is better than any one winner. I have now got a program with three tiers, where the winner of the winners is put on a super bracket, then the whole thing repeats. This takes FOREVER!!! The program has run times measured in days for reasonable problems. However, the members of the super bracket all have roughly the same value, and the winner of the winners of the winners still seems to be slightly better than any of the winners of the winners (if that fool sentence parses).

Your tic-tac-toe may be simple enough that the level at which the system ceases to improve may be pretty nearly right at the beginning. I have no idea how you could implement a multi-tiered NN, but if you can, you probably would end up with better results at the cost of longer runtimes.