Neural networks, anyone?

[Scryer]

[bluegaspode]

I wonder if the count of input nodes can be reduced.

what about (from the view of an ant) to just take the 5 nearest enemy + 5 nearest own ants + the own and enemy hill position (if one wants to use the net for defending + razing as well).

Each other ant/hill is only represented by (euclidean) distance and direction (as angle), which would make just 12*2 inputnodes. All ants are sorted by euclidean distance before assigned to the input nodes.

Don't know if using the angle+distance is a good idea though. delta x/y might work good as well.

Maybe also one should consider the 5 nearest water tile, to give the net a very rough impression about direction, but as ants can fight over water, maybe this would only be important when razing hills (and the ants shouldn't try to cross the water)
Or just consider ants with line of sight to the hill for a razing szenario ...

[dimkadimon]

[Darhuuk]

[DrClaes]

Dimkadimon: The wikipedia article about minimax, describes quite well a probabilistic way of thinking about optimum solutions for games with simultaneous moves. I don't have any experience myself with how to use data structures and algorithms efficiently for that, though.

I've looked more closely at the output of my neural net as well as at the training data, especially in light of the probabilistic nature of optimum solutions for this game; indeed, just choosing the output with the highest value will cause behavior very different to that of the bot I'm trying to imitate. It turns out that many examples of game situations recur frequently; for example, the 1 vs 1 scenario with the enemy ant 3 tiles to the north and 3 tiles to the east of your friendly ant popped up 4,000 times (out of 950k situations) in 45 of Xathis's games, and the distribution of responses by X was approximately 45% north, 45% east, 5% south, 5% west (most of the south/west responses are when he's blocked by something)... and my neural net outputs values that match that distribution quite well.

I'm more optimistic about the neural net approah after this insight; I will add a couple of parameters for whether we are in visual range of either the home hill or enemy hill and see if that has any particular impact on the results, but other than that I'm on to implemntation. Unfortunately I started this NN endeavour in the middle of a refactoring of my working bot code, so I need to finish that before I can look at matrix and floating point libraries for java...

Computationally, the good thing about taking a neural net approach to the problem is that the time grows O(n) with the number of ants within fighting range of the enemy; the bad thing is that the constant factor is probably pretty high since there's a few thousand floating point operations that need to be done for each ant.

As before, I'll happily report my results back here!

Claes

[DrClaes]

Hey,

Thought I'd share the kind of output I'm getting from the NN: Below are some randomly chosen local situations and the output, converted to percentages, of the net. X is the ant in question, * is enemies, and & is friendlies. Not shown but available to the net as input, is the water status of the 4 adjacent tiles. The five numbers correspond to n, e, s, w, and staying in place...

Whether something interesting will emerge from plugging this into a probabilistic tactical move engine (all ants independent except for not allowing collisions) very much remains to be seen... the objections to NN:s as game AI that I've read, of being too black box and hard or impossible to debug, are surely valid..... but we'll see!

/C


.....
.......
.........
.........
....X....
.....&...
..*......
.......
.....
27 25 5 38 6

.....
...*...
.........
.........
....X....
.........
.........
......*
.....
2 9 85 3 1

..*..
....*..
........*
...&.....
....X....
.........
.........
..&.&..
.....
4 16 39 18 23

*...*
..****.
.........
&&.......
..&.X.&..
..&.&&...
....&.&..
.......
.....
0 6 32 22 41

[DrClaes]

OK, I'm back! We're down to the last couple of days of the challenge, and I've spent a couple of nights this past week implementing the neural network tactics module in java and incorporating it into my bot. It's playing on the main server as well as on tc-pants even as I'm posting this.

I ended up going with one of the first and simplest network architectures I tried: 74 input nodes (the 68 tiles around the ant in question, valued 1 for enemies, -1 for friendlies and 0 for everything else, then 4 nodes representing whether the adjacent tiles contained water or not (probably redundant), then two input bits for whether we were in range of one of my own hills or in range of an enemy hill (probably redundant). 70 hidden nodes in one layer, then 5 output nodes. I've gone with a deterministic model which ranks the possible options according to the neural net output, then picks the highest ranked move that's still possible based on where previous ants have moved.

The behavior I'm seeing is, well..... certainly not like xathis, maybe like xathis after a couple of bottles of wine and some pain killers.... the jury is still out on whether this tactics module performs better than my simplistic previous model...plus I'm getting a lot of timeouts, which I don't think are related to the moderate sized matrix multiplications I'm performing...

I'll see where this ends up and then write a more detailed post about this learning experience.

Did anyone else go down this road over the course of the contest?

/C

[Darhuuk]

[DrClaes]

Darhuuk: I ended up training my network on between 100k and 300k of example situations taken from xathis' games (version 1). When I tried using much smaller example sets (like 10k) I had the problem of overfitting, meaning much larger validation set error than training set error. When I tried using all the data I'd extracted from xathis' games (900k examples), I couldn't do the backpropagation in a reasonable amount of time. I converged to a solution within 200-500 iterations, and consistently was able to predict about 60% of xathis' moves for the validation set. Sometimes 58%, sometimes 62%, depending on my parameters. I went with one of the neural nets that saw the most data eventually, and which hit 58% on both the validation and training data sets.

This number was disappointing to me initially, but my most important discovery was that when I trained on only one-vs-one situations, which I assumed would be simpler, the percentage dropped to around 50%.... because in the 1-vs-1 scenario, there's often two moves which are equally favorable...

I'm delighted to report that my neural network produces at least some apparently coordinated behavior, like walling off the mazes as in
http://tcpants.com/replay.2984
and occasionally surrounding groups of enemy ants before engulfing them. It does tend to err on the cautious side (which was a characteristic of xathis v1, I believe)... but all in all, it's not terrible. To clarify: as soon as my ants get within roughly 4 tiles distance from the enemy, the neural net assumes all control, I'm not doing anything else except checking for and avoiding collisions.

Right now, I'm tweaking all the non-neural-net parameters and trying out different combinations of weights for roaming, enemy hill attack, backing up my friends in trouble, and so on...

/Claes

[agent_smith]

So your bot actually uses neural network for fighting? I'm impressed!