Bot name: _iouri_Unoficial rank: Somewhere in top 20-30
Language: C++
Source: https://github.com/ikhramts/planet_wars/tree/simplifiedI'll probably make a more detailed post lated, with a cleaned up code. For now though, I think I actually do a lot of what smloh1 writes about above. What I do is:
(1) Calculate the state for every planet given existing fleets and planet states. The calculations are done from current turn to about 30-38 turns ahead (up to
horizon), depending on the planet size.
(2) Given data from (1), for every planet, for every turn
t = 1, ...,
horizon, and for every radius
d = 1, ...,
t, I calculate:
- defense potential, which roughly answers the question "if the enemy were to send an all out attack on this planet at turn t - d, would I be able to respond on the following turn and still keep the planet?" More precisely, it's the sum of my ships that can be sent from distance d - 1 from the planet to arrive at turn t (including those on the planet), minus the sum of enemy ships, including those on the planet, that can be sent from at most d distance from the planet to arrive at turn t. If the defense potential is negative, then there's a risk of losing the planet, and I'd need to pre-emptively send some supporting fleets. The specific pattern of ships to send will be dictated by the distribution of the defense potentials for the turn t; e.g. if defense potential at t = 5 and d = 3 is negative, there's little point in sending support ships from a planet 2 turns away. Sending the fleets will happen later though; for now we're just calculating. From the defense potentials we also derive:
- minimum defense potential at t, which is the smallest defense potential on the planet at turn t for any distance d. This is used to quickly determine whether a planet of mine is in danger.
- support potential, which is the same as defense potential, except it's sum of all my ships minus all enemy ships within distance d from the planet that can arrive at turn t. The support potentials themselves aren't as interesting; however, these are used to calculate
- full support potential at t, which is the balance total of ships that both of us can send to the planet t, from any distance. This will indicate whether the planet can theoretically be held/conquered.
- maximum support potential at t, which is the maximum of support potentials at t for all d = 1, ..., t. If this number is positive for an enemy planet at turn t, then the planet will be likely vulnerable and we should start planning for the attack.
(3) Given data from (1) and (2), for each planet, I calculate:
- total ships gained from the planet, which is the number of ships I would likely earn from the planet minus the number of ships the opponent would likely earn. If the planet is mine, and the minimum defense potential at a given turn is negative, then I assume that the planet will be lost.
- potential total ship gain from the planet, which makes a rough guess as to how much each one of us can hold the planet based on the full potentials.
Phew, that's out of the way, now we can start actually thinking about which moves to make. Move picking works as follows, roughly:
(4) For every planet, and for every arrival turn
t, check:
- Is it my planet with a negative min defense potential?
- Is it an enemy or neutral planet with a positive max support potential?
If the answer to any of the above is yes, then compose an invasion plan, basing the number of ships to send mostly from the defense potentials (yes, for attacking enemy too; "defense" is a misnomer here). The ships are coordinated to arrive at turn
t; they are first picked from the unreserved ships on closest planets, and if that's not enough, more are recruited from the planets farther out. If there are not enough ships available to take over the planet (or prevent it from being taken over), then the whole plan is dropped. The strategy for picking which planets will send which fleets is not the best, but it worked decently enough so it wasn't at the top of my list of things to fix.
(5) Calculate the potential return on the move. This is done more or less by adding the invasion fleet to the game timeline, and recalculating (1) - (3) above, though being smart about updating only the effects of values that have changed. Once that's done, I see how the potential values have changed on all of planets
that are mine at any point in time (not enemy planets though, or neutrals; I didn't manage to make that part work properly). Then I take the total potential ships gained from my planets, minus potential ships gained before applying the invasion plan to the timeline, and that gives me potential ships gained.
Once done that, I calculate the potential return on the move by dividing the increase in potential ships gained by the total ships to send (with some adjustments).
(6) I select the plan that gives me the highest return per ships sent. The plan is added to the timeline, the ships are reserved.
------------
The steps (1) to (6) are repeated until we're either out of time, there are no more ships to send, or there are no more available invasion plans with positive returns.
A few more things:
-
Send simple support without excessive calculations: after step (3) and before step (4), to speed things up, I figure out which planets need support (based on defense potentials). If sending the support will not disadvantage any other planets, then the supporting fleet will be sent without calculating the potential returns. Otherwise the bot will be cripplingly slow, as step (2) takes forever to calculate, esp if it's done over many move picking rounds..
-
Limit small supporting actions many turns ahead: for the same reason as just mentioned, I do not evaluate (and skip altogether) supporting fleets that would depart more than a few turns from now.
- I add constraints on which planets may be supported. If any of the calculations between steps (1) and (6) make it so that a planet will become vulnerable to the opponent, then it's judged that it's for the best of the nation and I prohibit other planets from sending support fleets to that planet. Otherwise, there are too many ships flying back and forth.
-
Sending ships to front: after all invasion plans have been established, I feed the remaining unused fleets from the rear planets to the front planets. I check for every planet whether there is another planet closer to the enemy, and if the defense potentials allow it, send the remaining unreserved ships to that front planet. This is actually not the smartest algorithm, as sometimes the fleets end up where they're not that useful, but I didn't get around to finding a better one.
I prohibit rear planets from attacking enemy's planets (as we don't want the enemy seeing the attack coming from 22 turns away). This is reflected in all potential calculations as well.
-
Keeping enough ships on planet to fight off enemy arrivals: I do not do this. I used to do this, and it used to give me advantage, but after implementing the potentials my tests have suggested that not forcing the planet to keep enough ships to hold the planet was a better approach. This way the lower growth planet would have to problem sending all of its ships away to capture a higher growth planet.
.