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

[Barefoot_Halibut]

I would have loved to have written my bot in Scala. My bot does a lot of list/collection manipulation which would have benefited greatly from Scala's collections library. So much boilerplate in my Java code. But unfortunately I found out about the starter package way too late in the competition.

[exaide]

Name: exaide
Profile: http://ai-contest.com/profile.php?user_id=6249
Current Rank: 112
Language: Java

~1200 LOC except junit tests. Simple hill climbing algorithm combined with turn (and profit) simulation and defense planning. Think code well-commented to understand.
Repository on github.

[RebelXT]

exaide, I think your bot is the first open sourced bot which has test cases. Nicely done! Most of us (including me) skipped automated testing and payed pretty high price for this mistake in terms of debugging time. Lesson learned..

[bocsimacko]

Name: Xrillo
Profile: http://ai-contest.com/profile.php?user_id=10212
Current Rank: 38
Language: C++

Bad and buggy implementation of a good algorithm - UCT.

Any chance to see the source and/or an explanation of how UCT was applied? I'm quite curious.

[davidjliu]

Name: davidjliu
Profile: http://ai-contest.com/profile.php?user_id=8047
Final Rank: 13
Language: python

So, what my bot essentially did was consider for an evaluation function for each planet, which was the change in the number of ships I have relative to the enemy if both of us do an all-out attack on that planet, with a horizon at the maximum distance between two planets. Then, it would carry out a hypothetical attack on that planet, and evaluate the results of that attack. If attacking the planet didn't negatively effect the evaluation function for other planets, then it would carry out the attack.

I've found that it's fairly good at opening expansions. The things that it pretty much fails at though are large-scale assaults against a lot of enemy planets, as when it takes an enemy planet, it doesn't consider the enemy taking it back so it will use the growth that the planet experiences in the future to take new planets even if the planet will be taken back next turn. It also won't take neutral planets that, after the horizon number of turns, hasn't paid itself back, which is a problem. The other issue is that I'm still using mostly the reinforcing code from a previous version of my bot, and it doesn't cooperate well with the structure in place.

[flagcapper]

If anyone's interested, my messy 91st placing heuristic bot can be found here: http://flagcapper.com/?c1

[barabanus]

cpp bot v3.6 for planetwars challenge by barabanus, 2010-11-28
==================================================================================================================

Name: barabanus
Final rank: 41
Profile: http://ai-contest.com/profile.php?user_id=9336

1. Each player has his own send order based on the topological index generated for each planet.
Its purpose is to send ships from backend planets first if possible. A planet gains +1 score
for each my planet it could defend and +1 score for each enemy planet it could reach before
my other planets. Lost planets (those which were conquered) are included in each side index
because of [2].

2. Each planet is assigned three values: my available ships to send, enemy ships, my reserved
ships to defend a planet. My available ships and enemy ships coexists on each lost planet,
so if my planet with 1000 ships had been conquered by enemy 2000 ships, I still have 1000 ships
on my planet, though they won't grow. In this way I could use these forces to conquer planets
(including the one I lost!) and defend.

3. Each turn consists of several phases:

a) initial plan: calculate TURNS_LIMIT (currently 35) turns ahead

b) initial plan: send ships to defend actual enemy fleets currently in the fly (<defend> order)

I assume that enemy doesn't defend his planets because:
(1) I usually send my ships number so that to cover possible enemy defence potential,
(2) If enemy could conquer (read: defend) his planet it would be taken into account
in evaluation function
(3) In this way enemy has bigger potential to conquer my another planet I could consider

c) for each plan: expand a plan by trying to conquer each enemy / neutral (<conquer> order)

The number of ships to send consider the max possible enemy defence force from nearest planets.
For neutral planets I assume that enemy is going to wait one turn to snipe it.

d) evaluate each plan

Evaluation function takes into account my ships number minus enemy ships number in TURNS_LIMIT + 100 turns.
If my planet could be conquered by enemy I assume it's lost, so the cost of a plan decreases.

e) take the best plan (initial plan might appear to be the best plan)

f) send excess ships from each planet to the planet with the greatest index (<excess> order)

In this way I get those support lines from backend planets. To check whether it's good to send
all the excess ships from the planet, I clone the plan, send those ships and evaluate the new plan.
If the new value is less than the original (e.g. enemy could conquer the planet because of
missing forces) I don't send any ship from that planet.

4. Technically the bot implementation is heavily optimized:

a) memory pool
b) power-of-two size of arrays
c) no constructors for the most used classes
d) preprocessor directives to disable debug code
e) a lot of assertions and comments

I could expand 15000 plans per second, though the most time a turn took < 0.1 sec

==================================================================================================================

[barabanus]

lua bot v1.5 for planetwars challenge by barabanus, 2010-10-19
==================================================================================

Rank: ~400

The bot is written in lua and submitted as C package with lua code.
Get time function replaced with gettimeofday() (original had been clock())
Unfortunately, contest organizers didn't support lua.

This was original bot I wrote when entered the contest. The cpp bot had been written in the last
three days before the deadline with 4 hours sleep a day =) I made a big progress in this days
from rank ~400 to 41. My problem was a perfectionism that didn't allow me to submit non-ideal bot.
Unfortunately, I hadn't too much time to improve the final version.

[Xrillo]

Name: Xrillo
Profile: http://ai-contest.com/profile.php?user_id=10212
Current Rank: 38
Language: C++

Bad and buggy implementation of a good algorithm - UCT.

Any chance to see the source and/or an explanation of how UCT was applied? I'm quite curious.

Sure, I'll try to describe the implementation. The source code is, like all my hobby projects, really awful to look at.. so I'll let you keep your lunch.

I read on your blog that you've done some UCT-coding so I'll skip the introductions. For those who don't know it, let google be your friend. I'm terrible at explaing stuff.. sorry.

I tried a few setups and finally settled with not doing any actual playouts. I merely built a tree, and each node was given a score - a linear combination of win/loss and the score-ratio. This makes sure you'll rely on the actual win rate in the end but also makes it greedy and trying to take all planets.

One issue was the immensely large state space, I trimmed this down by generating "actions" for each owned planet. I then gave those actions a weight based on distance, growth and cost. For each node I chose one action per planet by means of a weighted random selection ( the first couple of turns allows multiple actions per planet ). Whenever I tried to let it control the supply lines it failed, so I kept a hardcoded heuristic for this...

Another problem is the fact that both players move simultaneously, I "solved" this by keeping a two-layered tree. It's hard to explain.. but basically both players have their sets of actions.. each action gets a score based on UCT and the highest scoring gets selected. Both players select among their own actions and a state is generated from the combined actions of the two players... yeah, I told you I'm bad at explaining stuff.

Anyway, I probably gained about 300 elo from the tree part compared to just using the weighted selection. Oh, and I used progressive widening too... so yeah, there you have it... I'm sure someone else would be able to do a much better job with UCT.

[bocsimacko]

I tried a few setups and finally settled with not doing any actual playouts. I merely built a tree, and each node was given a score - a linear combination of win/loss and the score-ratio. This makes sure you'll rely on the actual win rate in the end but also makes it greedy and trying to take all planets.

I don't understand. If there are no playouts then what is the win/loss in the linear combination?