cpp bot v3.6 for planetwars challenge by barabanus, 2010-11-28
Final rank: 41
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. 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