Tell us your secrets, unleash your bot's code!

[Cthulhu]

hi guys,
the contest is almost over and im interested in what approaches you took with your bots. I can think of several methods and im courious if anyone used them and what problems they had. So maybe i can learn something from other users without having the trouble to implement a -lets say genetic algorighm- myself

- Game tree expansion
Advantages:
Things like the importance of the center on some maps come natural to this method..Also it avoids any blunder like attack neutrals just to have your front planets taken within the next turns
Disadvantages:
That tree is damn huge. you need to prune it heavily. Also within one second its very difficult to get any meaningful results. Pruning the tree has other disadvantes like
orchestrated attacks (launch some ships now, that are later joined by others launched from different planets) are not possible. Moves like "attack planet with 61 ships with 5 ships from this planet and nothing else" are the first branches of the tree that get cut....

- Bot made by genetic algorithms
Advantages: its cool...other than that: none
Disadvantages: you can be happy if you finally have a bot that issues a valid order. You must carefully choose what kind of mutations/crossovers you allow to happen.

- Neural net
Advantages:
You need like PLAYERS * MAXPLANETS input nodes for planets and how much ships are on them and whom they belong. another HUMAN_PLAYERS * MAXPLANETS * MAXDISTANCE input nodes for how many ships are arriving, when and to whom they belong, and the same for distances an planet growth.3 hidden layers of unknown (a lot) node count and then some output node. Its easy to implement , not likely to exceed time limit and guaranteed to find the optimal solution. At least I'm somewhat sure because you do a stochastic gradient descent...bla bla...
disadvantages:
neccecary node count for hidden layers not known
you need A LOT of time and EVEN MORE cpu power, not likely to be strong within acceptable time

All of these methods have the disadvantage that they have no domain knowledge. They should find the right moves but perform poorly in carrying them out (like using to many or too much ships, not attacking as soon as possible, etc) on the other hand whe have the

-Hashtable-Bot
Advantages:
Opens a TCP connection to a server where all situations and their optimal moves are precalculated. The client is easy to implement...
Disadvantes:
Might be considered cheating. You need a fast server with a huuuuge storage

-Handcrafted shiny hardcoded student-bot (most likely contestant *g*)
Advantages:
Step-by-step improvements, you actually KNOW why it does what it does. Pretty good tactics because the "obviuos" correct move are easy to describe (attack with one more ship than defender has on the turn you arrive etc...)
Disadvantages:
Most programmers will spend their time forcing some strategy into their bots after they continuously loose when failing to taking planets in the center, or taking them just to be sniped. This results in bots with lots of tweaking, weird "measures" of how good a move is, redundant code that performs the same task in different manner, lots of "commented out" and generally messy code. I know it. I've seen it
Some may hardcode a gametree of depth 1 for this...When i do this, what would the opponent do... but in the end, all these bots are doomed to reach a point, where additional "improvements" conflict with other parts of the bot and actually make him perform worse.

What i think is most promising, is a combination of a hand made bot that nows how to perform certain tasks, and a generic "learning" algorithm that provides a strategic value for every possible task or even better: every task combination. This algorithm can be based on any of the methods mentioned in the beginning. space.invaders seems to do something similar to this and I am curious how well they perform in the end.

Things like opponent modelling where you try to learn how your opponent works and exploit his weaknesses (we dont have to play optimal, just better than him...) are left out because that would be at least unusual. So finally...feel free to tell me what your experiences are or if im mistaken with any of my statements. After all I did not do any of the cool stuff, I just wrote the first things that came to my mind about them...
And also...if you did something completly different...le us know

amstan here: Please use this topic, do not make new ones.

[Janzert]

-Hashtable-Bot
Advantages:
Opens a TCP connection to a server where all situations and their optimal moves are precalculated. The client is easy to implement...
Disadvantes:
Might be considered cheating. You need a fast server with a huuuuge storage

This would definitely be cheating and should be prevented by the server setup.

Janzert

[cobracom]

I went with incremental improvements and I'm quite satisfied with the result (I'm hoping to get to the top 50, after getting to the top 100 in the Tron challenge).
And yes, my code is a bit of a mess with a lot of commented out methods, but since I'm not going to touch it starting tomorrow, code readability wasn't my goal.

I've started this competition with a genetic approach. Had a population of robots fighting against some test bots and those who had won the most games were able to reproduce. This approach went no where, it was very slow and I had a simple test bot that was always winning against the evolving population. Just on a whim I decided to submit that test bot and it went straight to the top 200. I never looked back.

[paddy]

I just discovered this contest so I won't be able to make anything useful(I'll still try to, even though I can't submit it), but both Neural Networks and Genetic Algorithm/Programming seems a bit.. odd to use independent of each other.

I had a few ideas, one was combining neural networks and GA to evolve a neural network which could play the game, but haven't had time to think too much about it. The other idea was using swarm intelligence, but I've never actually done anything in this kind of AI field before.

I guess the advantage of neural network + GA would be that it could be fairly quick(Once you've evolved a decent ann you only need to hardcode it and let it fire instead of spending time to evolve/train). However, I'm not entirely sure how an ann could be implemented for this kind of game.
The obvious disadvantage is that you'll have no idea why it works. Which is one of the downfalls of neural networks.

As for the swarm intelligence idea, I don't really know if it would even work at all. Haven't had time to read up on it.

[dabino]

I wonder if someone has randomness? It was a hard decision for me to go with mixed strategy (because you just can't gradually improve your bot - it shows different result vs the same algoithmon on the same map), but worked.
After that I was only busy with (a) move generator (b) estimate function, and these too are as you described - a lot of messy code with small corrections.Well, a couple of them made some leap and allowed to stay within top100.
So now I hope for server's randomizer, please shuffle the deck well 8)

[krokkrok]

My bot is a pure mindless greedy algorithm.

It sorts each attacking planet:target by quickest return on investment in turns, minimizing for each attacking planet (Distance+NumShips/Target Growth-Rate); calculates how large the attack fleet needs to be to hold for one turn [recruiting ships from nearer friendly planets if needed], and attacks new targets until it can't take a planet. If an attacking planet does not have enough ships to take a planet for at least one turn, it sends its ships to the nearest friendly planet to its chosen target instead.

This insanely simple-minded strategy has kept it near the top 100 for an astonishing amount of time. We'll see how it does in the final.

[jonoff]

The hardest part for me was whether or not to attack planets halfway between the enemy and myself (the ones in the middle that aren't mirrored), especially on the first turn. If I send only enough to capture, the enemy might have more than that on their turn, and if I sent all my ships, they are locked in travel for a period of time, and if I don't send any and the enemy does, that planet is the most likely one to turn the battle.

[lakeweb]

I must say, this has been a real learning task for me. I wish I could have spent more time on it. I like to code as I'm sure most here do. I had a new bot that was getting a much better elo on 72.44.46.68 tonight than my old bot. But I ran out of time not knowing that gcc would balk so much about some of the things I did that were perfectly fine in VS. I might have found myself in the few hundreds, so no big deal.

But yea, if there is going to be a reveling, I would very much like to see other's code and would zip my solution up for download.

Best, Dan.

[margoth]

My first bot was a monolithic collection of simple rules on evaluating and executing attacks for each MyPlanets x OtherPlanets combination. It made it to top-200 but was hopeless to improve.

I then did a complete rewrite that starts with analysing different metrics of the current situation and 30 turns to future based on fleet movements and planet growth. Using simple heuristic rules I create a set of candidate action targets for each of those look-ahead 30 turns. Another heuristic is then used to order the targets.

Next I seek out potential contributing planets of mine to offer fleets for the actions, committing sets that fulfill a goal, and manifesting these as Command proposals. Some targets like "attack planet 5 in turn 5" and "attack planet 5 in turn 6" are mutually exclusive.

Command proposals go through some simple filters that optimize away emergent glitches. Finally, write them out.

An addition this week introduces semi-random mutations to heuristic parameters and established choices. These mutations are made as long as there is time and all reached solutions are evaluated based on the projected game state they would result in (highest I have seen has been > 120 unique solutions). This evaluation works very poorly and is a major weak point in my bot.

Still, I hope it has a fighting chance to make it to the top-100 in the finals.

[antimatroid]

I managed to jump on board for this right at the start, so I've played around with a few different ideas, I'll try to give a bit of an outline below...

First to explain how I represented things a little bit, a "move" consisted of a vector of fleets, all with the same destination planet but fleets could be sent from anywhere and at any time (provided they arrived no later than the maximum distance of the map in the future). The main types of moves I made were for expanding, defending, attacking, redistributing and redirecting. The first four should be pretty self explanatory, redirecting consisted of sending fleets added at time zero to a friend planet with a closer enemy planet such that the ships could make it to their final destination in time.

As with any other ai contest, what one really wanted to do was get a game tree going with minimax, the problem with this game is the true game tree is impossibly large to do anything with, so one has to make huge guesses at what are actually reasonable moves, and even then one is extremely limited in the number of moves they can test.

I first wanted to use dynamic programming for move selection, but my test implementations were running unbearably slow (like over 15 seconds a turn at some points with a basic heuristic bot, so that wasn't going to work for move selection in a tree) so I quickly ditched any attempts at using that, then I considered trying to use linear programming to do it, but I never really worked out a decent way to do it (it would also need to be set up as an integer program, which I've never actually played around with).

My final move selection consists of running through the planets and just picking out moves up to the maxdistance on the map to that planet, and using that as a possible move. It's horribly inefficient and a huge bottleneck on generating much of a game tree, but alas it's the best thing I ended up with.

As for my macro strategy, I tried modelling it both using a game tree and a payoff matrix but I was never able to get much success with the payoff matrix, but I liked that idea most. I constructed my state evalation such that it was zero sum to make it easier in both instances.

The issues with the simultaneous game were that it didn't consider strings of moves and I couldn't generate a very big game matrix within the 1 second (it was also very hard to pick strategies for each player then create the needed payoff matrix and time it for near 1 second). The idea was to pick sets of moves that were jointly feasible and treat those as pure strategies for each player. Then to pick my pure strategy to play, I was going to pick out my favourite pure strategy Nash equilibrium that I could play (or even try some kind of minimax regret method going, although I never worked out specifics for that), if no such equilibrium existed, I would try to obtain (or approximate) a mixed strategy Nash equilibrium (msne) and play that.

There are a couple of ways I would have tried to get the msne, the first is to get an actual msne using simplex, the cool thing being that simplex iteratively approaches the optimal solution with feasible solutions, so if you ran out of time you could just use what had been calculated so far as an approximation. The second would have been to try and approximate it numerically somehow, I found a few ideas for that online, the best was one method of having players optimally respond in pure strategies (I think) to the opponents current mixed strategy and then accumulate results for updating said current mixed strategies. Given I was having trouble getting a simple version of this running with just pure strategies in the required time, I didn't see much point in actually trying to implement that full idea, so it never eventuated.

Finally I came back to the normal approach for these kind of problems, minimax search on a game tree. I tried a few different methods for this (my final submission I only actually implemented this morning, so I have no idea if it will flop or not, but it seemed to work better in the few test games I managed to play). The first is to have each player pick moves for a current game state, then generate two layers and repeat the process, the problem I had with this was that the last move I make completely ignored what moves they might respond with, and it would often make moves that would be great if there was no opponent responding, but alas this is a game and that is not the case.

The second was to have the opponent respond to my moves in each child of mine, which removes the above issue of them not getting to respond to all moves I consider, but it also means you have to generate their moves a whole bunch more and process a whole lot more states for the same number of nodes in the tree.

What I implemented this morning was like the second, but after generating each 2 layers, it'd pick the minimax solution for that and then keep extending from there, the benefit to this is I actually end up considering and making more "actual" moves each turn, but I don't think it's quite as smart with the moves that it does make.

(Edit: upon further looking at my code, I didn't do what I thought this morning, the bot is doing pretty much what is described as the second option, although I just had one crash recently, hopefully I don't get too many of them).

One last thing, I was never sure what to send in the way of redistribution ships, if I send all unused ships it sends too much at first, but if you send just the growth amount of the planet some get stuck at the back and planets with other planets redistrbuting to them build up as well, my simple hack as to send up to 4 times the growth of the planet in redistribution moves, that way it would slowly reduce the ships at the backline without sending too many ships into the air at once, and there isn't as much of an issue with builds ups on the path to the front line.

Edit: You can get a copy of my code here https://github.com/amstan/antimatroid and if you so cared, watch it play here http://ai-contest.com/profile.php?user_id=3945