Language: C++
League: Legend
Rank: around 150 before rerun
Strategy
My strategy is based arround cracking the seed of the game as soon as possible to predict the angle of each spawn, and predict when and where a mob is entering in the visible game area. This allow me to plan far in advance timing attacks that would otherwise be hard to setup.
Some examples (when it worked):
Scouting (collecting information)
I scout the 3 first waves, there is 2 new mobs and their symmetric per wave, so I collect information about 6 mobs. I am solely interested in their direction vector. If I spot an odd-id monster, I flip the direction to end up with 6 directions of even-id mobs. For instance:
6: (-361, 170)
8: (-386, 103)
10: (16, 399)
12: (-229, 327)
14: (-5, 399)
16: (-329, 226)
That’s all I need! For the technique to work, I don’t need them to be consecutive nor the first 6, but it simplifies a lot the implementation and avoid having to handle winds (that also draw numbers from the random generator and thus change it’s state). Since the last mob spawn at turn 11, it is impossible that a player collected enough mana and that a mob reached inside a base before this time, so wind cannot affect the first 3 waves. To make sure that I didn’t miss a mob, I generate 32 probes for each spawn pair at each wave, covering the angle range, and I assign my heroes to cover them all (once a probe is spotted, it is removed).
Cracking the seed (in 1 turn)
Note: I’m not going into the details of how the method works, but there is already an excellent 2 part video on the subject by Matthew Bolan (in the context of minecraft seedfinding) Minecraft Seedfinding Ep. 2 Pt.1 - A General Seedfinding Problem - YouTube Minecraft Seedfinding Ep. 2 Pt. 2 - Lattices and Linear Programming - YouTube)
Once I collected the 6 directions I can reverse the vector to find the approximate random angle:
double rvalue = (-std::atan2(dir.x, dir.y) + maxDirectionDelta) / (2.0 * maxDirectionDelta);
Based on my observations, I conservatively chose a confidence interval of ±0.001, and reversed Java’s Random nextDouble function to find min and max values for the internal seed every 2 state of the random (nextDouble calls next twice for the 26 higher and 27 lower bits, unfortunately, the lower bits and some of the higher bits are lost in the approximation):
long minLong = (long) std::ceil((rvalue - 0.001) * (1L<<53));
long maxLong = (long) std::ceil((rvalue + 0.001) * (1L<<53)) - 1;
mins[i] = (minLong >> 27) << 22;
maxs[i] = ((maxLong >> 27) << 22) | 0x3fffff;
Which for the example above gave me the values:
rvalues: [0.9318906091090353, 1.0003956303151396, 0.4846910347877601, 0.733358520016807, 0.5047863642993761, 0.8700910401509881]
seeds_min: [262022411321344, 281304859934720, 136146919096320, 206140596027392, 141803252613120, 244627378536448]
seeds_max: [262585366609919, 281867815223295, 136709874384895, 206703551315967, 142366207901695, 245190333825023]
Now, finding the seed is about finding a vector of 6 values inside this interval that when used in Java’s Random generator gives us the result we expect. A solution would be to try every possibility, but due to our missing bits, that would be 562955288575^6 combinations to test. Fortunately, we can reduce this by exploiting lattices, linear programming and a branch-and-bound search (see Mattew’s video). In the case of the challenge, 6 values constrains the search enough so that only 1 possible sequence of seed is searched. So one matrix multiplication later, we get the sequence of internal seeds:
seeds: [262309646766292, 281466933482926, 136375006762776, 206475916988306, 142282001333660, 244993047446454]
We can verify that it is indeed what we are looking for by comparing to the seed of the game in the ide (9135968950900845600). When setting a seed in Java’s random, only the lowest 48 bits are used and the value is xored with Java’s LCG multiplier:
(9135968950900845600 & ((1L << 48)-1)) ^ 0x5DEECE66D = 135647475894861
We could advance this seed one step to get the first value of our sequence of seeds, but a cooler way is to go one step backward from seeds[0]. The inverse of a LCG is also an LCG, in case of Java, you can rewind a random using:
prev_seed = ((seed * 246154705703781L + 107048004364969L) & ((1L << 48) - 1));
Which gives us what we expect:
((262309646766292 * 246154705703781L + 107048004364969L) & ((1L << 48) - 1)) = 135647475894861
That’s it, now I can predict all spawns in the game.
A few additional notes:
- since the structure of the generation is fixed (6 consecutive
nextDouble) I can precompute all the matrices I need offline, for that I used the LattiCG library: GitHub - mjtb49/LattiCG: Reverses the internal seed(s) of JavaRandom given information on its output in the form of a system of inequalities on various Random calls. Works by reducing the problem to finding certain vectors in a lattice, which is then solved through a branch and bound algorithm using a reduced version of the lattice. - I wrote a simple runtime in c++ for the search, I didn’t bother to implement a BigFraction type like in LattiCG and simply used long and double, which in this case worked just fine.
Keeping the seed in sync
One caveat, is that the seed can be modified by the players, if they use wind from inside their base to push a monster outside. Since the order of mob processing is hard to predict (since it relies on the implementation of HashMap in the referee, see this PR Maintain order when processing push by wind by pikazlou · Pull Request #27 · CodinGame/SpringChallenge2022 · GitHub) I didnt bother to account for winds, and just resynchronize the seed by trying each n-skip possibilities when encountering a monster that has spawned in a weird direction. In practice, this kind of desynchronization happen very rarely (especially in higher leagues) and are quick to fix. I also later adapted my strategy to never wind defensively from inside to outside the base (I either wind before the mob enter, or make sure it stays inside).
If the wind processing order was deterministic, a simpler way to resynchronize would be to use the result (mob direciton) of my own winds. It could even be used to manipulate the outcome of the next spawns, by using wind at specific time. I didn’t bother going this way.
Farming
My farming strategy is very simple: going to the threatening mobs in priority and otherwise the closest, computing barycenters of closest mobs to maximize damage.
Attacking
I use 2 heroes and 2 main forms of attacks:
- one wind then double wind with stacked heroes (30 mana, 2 turns, 6900units)
- four winds with spaced heroes (40 mana, 4 turns, 9100units)
I didn’t used shields, and barely used redirects.
Feedback
This challenge was a lot of fun. As my ranking probably tell, reversing the seed isn’t that much of an advantage, especially against the higher leagues meta. I hope seed reversal will not get nerfed too much in the next challenges, nor become the new meta, but maybe make it like a puzzle inside the challenge that can give a small bonus to people who solves it.