Rift contest is over. It was a great experience with plenty of emotions : excitement, frustration, satisfaction, deception and thankfulness . I hesitated to share my strategy because I was not ranked high enough to give the most convincing words. Nevertheless, I still made up my mind to write something down, on one hand to capitalize this rich experience and on the other hand to hear and learn from you.
In this article, I’ll explain the important decisions made in my solution without diving too deeply into implementation details. I started with the 1v1 matches and then based on it, I developed the 1v2 and 1v3 strategy.
Intuitively, pods should be purchased on the richest zone because that will make money more efficiently. However, a rich zone very far far away from all others is not necessarily the best choice because it would take too much time for pods spawned there to come back to the remaining game.
Therefore, a neutral zone should not be rated solely on its own richness. Other reachable zones should also be taken into account. This idea led me naturally to build a score system where the zone having the highest score should be purchased in priority.
Then it came the most essential question :
For a given zone, how much should other reachable zones be weighted in its score ?
It’s like how our nose works. The closer a great wine is to us, the stronger we’ll smell it. Therefore, the contribution of other zones should be in function of distance. For a given zone x, its score is calculated as follows :
score(x) = sourceOf(x) + constant * sumOfSmeltSourcesBy(x)
where the source of a reachable zone y smelt by x runs as :
smeltSource(x, y) = Math.pow(0.5, distance(x, y)) * sourceOf(y)
As shown, source of a reachable zone is reduced by half every time it’s one step farther.
To build this system, I need a matrix to memorize the distance between all pairs of zones in a connected graph. This matrix is obtained thanks to Floyd–Warshall algorithm. This score system allows me to make purchases with high profitability.
Given that a player can only purchase pods on a neutral or his already-owned zone, the very first idea I got is to separate my pods into two groups :
- Pods at the frontier which are exposed to enemies or neutral zones
- Pods in safe zones. A zone turns safe when both itself and all its neighbors are captured by the same player.
Pods at the frontier are involved in conquering new zones or in defending owned ones whereas safe pods should move to the frontier to engage again in fights. Pods stop moving when the entire continent is captured.
Pods become safe after closing a frontier. Once mission accomplished, they should move toward other exposed zones. Two problems should be resolved in order to make a perfect move :
- Identify a destination
- Find a path toward the destination
Pods at the frontier
In absence of enemies, a pod at the frontier should make moves allowing to gain as many sources as possible. Since it’s only allowed to make one step move. A pod at the frontier should only focus on its neighbors. However, given it can have multiple neighbors it must choose the right direction. It should head for zones following the guide of the smell system. In the same way, this avoids moving to an isolated rich zone.
Given that zones already captured should not be targeted again, my score system is re-evaluated on each round by excluding my already owned zones. In other words, zones belonging to me are no longer smell-able.
Resources are limited. Confronting with enemies is inevitable. When enemy pods are detected, I keep my pods moving as if no enemy were detected. I prefer to be agile rather than motionless because staying still is more likely to miss opportunities to take control of extra zones. For example, I captured the green zone and one enemy pod is detected at the red zone. If I stayed still, the red one would probably take the neutral zone and I would remain immobile.
However, being agile is not always the best choice neither. In the above scenario, when I leave my zone, enemy pod could make an invasion and then occupy my zone. It would be stupid If I trade a rich zone with a poor one.
Before conquering the whole continent, frontier always exists. In other words, the exposed zones can be in danger. Therefore I always have an eye on the frontier. When enemy pods are spawned beside my exposed zones, I try to put the same number of pods there to prepare the possible invasion. On the contrary, if no enemy is detected, I do nothing.
Since the number of pods that I can purchase is limited each round, I always defend the richest zone in priority.
Most of time, a pod spawned at the frontier vanished together with the enemy. In case enemy doesn’t attack, my spawned pods turns into pods at the frontier and thus they’ll follow the strategy explained above.
to be continued…