Neural networks, anyone?

[DrClaes]

Hey,

I'm taking the machine learning course online at Stanford, and having just completed the neural network homework I thought I'd try my hand at implementing a neural network to "classify" the appropriate one-ant response to a given tactical situation, for example codified as the friendly and enemy ants within about 4 tiles distance (still 80 tiles)... the promise of machine learning being a valid approach when you can't or don't want to work out the actual algorithm for solving the problem at hand seemed pretty good.

I've written some code to parse the JSON replay data available on the main site... in 45 games played by one of the top bots, I found over 300k "snapshots" of ants which had at least one enemy within 4 tiles radius...

Unfortunately, so far I'm not having a lot of luck--probably a combination of too naive codification of the data and inappropriate choices of network architecture (one hidden layer with, so far, 50-250 nodes, and an output layer of 5 nodes, one for each direction and one for standing in place)... the back-propagation is painfully slow when working with moderately large datasets like 100.000 examples, and doesn't converge to anything which is meaningful, whereas when working with small datasets I quickly converge to an overfit solution which doesn't generalize...

Has anyone else tried using neural networks for this and wants to share their experience? Be as general or as specific as you like!

Claes W

[gvsmirnov]

It's probably not a very good idea to use neural networks exactly like that. First of all, it is very unlikely that any good flocking patterns will emerge on their own from the neural network, especially if you calculate moves for each ant separately. Moreover, you cannot set any explicit rule for the neural network that is guaranteed to always hold true. A good example is not having any two ants move onto the same cell.

A better approach would be to have a more or less explicit algorithm for the bot's behavior. A good algorithm has multiple parameters (like weights of different types of goals etc.), which can be either static or dynamic. If they are dynamic, you can actually take them from the output of your neural network, which has some codification of the current game state on the input.

[DrClaes]

I agree that the problem probably isn't extremely difficult to code explicitly, but I'm toying with the neural network as a learning exercise to see where it takes me.

It turns out my parsing of the JSON strings was a tiny bit off, which resulted in the data I've been training the network on being gibberish, which could have something to do with my profoundly bad results...

My hope was that by "imitating" a very strong bot in tactical situations--then sanity checking for collisions, of course--and taking into account patterns of other friendlies and enemies within a 9x9 square, I actually might see some interesting emergent behaviors.

I'll report my new results as they come in!

[isysBot]

I would be very interested in the results - seems like a interesting approach to the problem. Keep us up to date

[kuisma]

A MLP is nothing more than a function approximator and not a magical solution for any random problem. You need to spend some more thoughts about what function you want to approximate. Simply mapping the grid as input and a north/south/east/west/stay for output is not going to be very fruitful. The input is simply not relevant enough to produce a good move. You need to provide other state information as well.

Also, I don't believe it's such a good idea to use the top level bots for training data. They are simply not good enough. A better idea would be either to generate sample battles via brute force exhaustive search, or even more fun, running your bot against itself in an evolutionary manner. Both those methods will give you more training data than you can handle. Even if backprop is quite slow, it's still my favorite. Each time I try something else (rprop, pso ...) I always revert back to backprop in the end. It might be slow, but I believe it's quite stable compared to many other faster algorithms. It's no too complicated to implement a massively parallel backprop using CUDA if you really want to, and then you don't have to worry about the learning speed any more (x100-x1000 times the speed of running on a CPU).

Experiment with different size of nets and numbers of hidden layers. Even if in theory any function is possible to implement using a single hidden layer, the economics is different. I.e. you may be able to reduce the total number of weights by using several smaller hidden layers instead of one large. And you don't have to worry about over training here, if you find this a problem, you have a too small training set. I would say your problem is the opposite, too hard to get the MLP to converge, especially if you have a suboptimal function you want to approximate in the first hand.

[DrClaes]

Thanks Kuisma for some pointers which will be very helpful in my experimentation with neural networks!

I realize there's nothing magical about the neural networks or, for tha tmatter, machine learning in general.

I agree that it'd be fun, and even toyed with the idea before, to brute force work out what would be truly optimal play in "staged" battles and use that as input, but probably won't go down that road...

With my quite naive approach of combat radius + 2 grid --> directional output I've got the network making the same move as xathis 2/3 of the time, which I thought wasn't so bad for a first attempt, just my second day of trying... If I'm able to think of some other input parameters which abstract the game situation in some relevant way I'm hoping for an even better approximation... then on to implementation in my bot, of course!

Will report my results in this thread...

[Darhuuk]

I am wondering how you trained your network and what sort of input you gave it. Mind sharing some tips? (I'd understand if you don't want to though .)

I was trying something similar (trying to recreate xathis' ants behaviour) with a NN in Matlab, but it failed miserably. First of all, I think the 81 inputs (9*9 field) might have been a bit much, and Matlab was also very wasteful with memory (reading data from a 1.4 Gb text file consumed more than 8 Gb RAM), which forced me to use quite smal training sets.

Is there anything special you did to the inputs? How do you represent the squares? Something simple like 1 for friendly ant, -1 for enemy, 0 for empty/water/hill?

[mac]

[DrClaes]

Darhuuk: I used Octave to try out some network architectures and parameters. Will use some more efficient way of training with larger data sets eventually. I've encoded the training data almost exactly as you said, but added information about the four tiles adjacent to an ant, with regards to being water or not. My thinking with that last bit is to weed out some impossible moves into water since they will be strongly reinforced to never do that. I've also chosen to train only on the subset of frames from xathis' games where one of his ants is within 4 tiles of an enemy ant. I've used one hidden layer with around 50-100 neurons, then 5 output neurons, each containing one of the possible orders (including doing nothing). I'm in the process of learning about other software options that will let me experiment with network architectures more easily, hopefully also using my graphics card to do some of the training calculations...

Mac: I agree totally with you that my accuracy in predicting xathis' responses to a given situation doesn't equate with either intelligence or even fitness for the bot, but it's the only way I can see of testing the performance of my learning algorithm, ie of the training process.

I do think xathis' dominance on the main server is pretty good evidence in favor of the quality of his moves... sure, it might be possible to work out better moves in various situations, but if that were easy he wouldn't be winning (long-haul) against everyone else with a bot on the main ladder...

To my thinking, there's a lot of philosophical/game theoretical questions that are raised when we start talking about the fitness/smartness of bots; I'm very curious as to how "good"/fit a bot could be made by relying on emergent behavior--every ant making his own decisions based on the local environment, without explicitly planning ahead or even looking back at what's been done--even in combat situations. Surely we'd need some clever way of abstracting the local situation into something the ant could use to make his choices... I'm curious since (1) the decentralized, "stupid ant" model works pretty well for the other aspects of the game--exploration and food gathering, (2) real-life ants "work pretty well" without a central intelligence...

My naive approach to combat in my actual working bot, currently with skill rating around 70 (not so good) is to let enemy hills attract, enemy ants repel one friendly ant each, and even with those rules I occasionally glimpse really nice emergent combat behavior where my attacking line of ants fans out and attacks a fortified hill...

Regards /C

[bluegaspode]