Controlling the Map
One thing you’ll frequently hear in pro match commentary is the concept of “map control”. It’s a topic that everyone understands, but which has never really been quantified in a decent and holistic way. Some phrases are tied to it and matter, like ' “the outer towers are all taken”, or “deep vision placed” and there are existing metrics to support these ideas, but I’d like to try create a framework for a more general system.
My goal for this is an approach which describes the map control at a point in time, is easy enough to understand graphically what is going on (even if the maths is a bit wild), and should be at least slightly predictive of how the game will proceed from that gamestate. It would also be nice if the output model is stateless - it can take in a single state and simply return the “map control” for that state.
The Math Section - Feel Free To Skip This
At first I thought that Voronoi diagrams (the dual of Delaunay triangulations) would be a good idea - after all these are about cutting planes (in our case, the Dota 2 map) into partitions based on the points inside it (each point ‘owns’ the space closest to it).
I experimented a bit them, and also with non-Euclidian variations like power distance. I also tried a two-pass approach - merging commonly owned regions together (after all towers and creeps and heroes are not all equal in terms of control). After a bunch of trial and error I realized that this approach was just not going to work - there’s a lot of space which is not really controlled by anyone and this leads to exaggerated and unrealistic views of control.
So despite that being a dead-end, some bits were salvageable for the next approach - which is a spatial ‘influence’ model. I took 5-second snapshots of the map for key entities. Each entity within the model radiates out influence proportional to its ‘importance’, and with some entity-specific drop-off. There’s a few different layers being calculated in parallel - this makes it easier to extend the model with more types of control in the future:
hero influence: each hero is on the map, weighted by a log of their networth
buildings: each alive building radiates control for its owner based on the type of building (T1, T2, T3, T4, melee rax, ranged rax, ancient, outpost, watcher)
wards: radiate control (only observers)
These layers will then be combined into a single influence per team (by summing them up for each team), and then normalized into a single per-cell per-time value:
control(x,y,t) = (influence_radiant - influence_dire) / (influence_radiant + influence_dire)
There’s also a minimum influence threshold so that areas with tiny influence are just uncontrolled rather than being strongly controlled by one side (because of a small denominator).
But what about weighting? In the model described above there’s no mention of each object’s weight, nor on how diffuse of a Gaussian blur should be applied. Initially I set these with just some reasonable initial guesses (thanks to Astini and TeaGuvnor who gave their input for the initial values) and then later optimized them via Optuna.
With this approach I was trying to optimize a correlation coefficient between control_score at time t to networth shifts at t + 60, t + 90, and t + 120. The idea here is that map control at a point in time should (on average) turn into economic gains over the next short period of time. Why networth and not XP or kills you ask? Because networth is the single “simple” (visible in the game) value which is most highly correlated with the outcome of the game - you can build a very fine win predictor model just using networth difference and time (there’s a niftier version of this view here).
All the object weights and Gaussian blur sigma values were optimized over ~8 hours on my desktop (960 replays, i7-12700k, NVME drive, 6 parsers in parallel; then 200 Optuna trials for the 12 parameters) including the time for parsing. I ran a small trial on different grid sizes beforehand and went with 64x64. I also ran some validation tests, including a comparison between a networth-only logistic regression model and a {gold + control} model. In the second model, the log-likelihood of the networth difference coefficient went to 0, and the model accuracy increased!
I took those optimized parameters and wanted to visualize the model with them for real data at any point in time, so I made a small streamlit interface to load a parsed replay and manually QA’d the output.
Not All Control is Equal
Something that I thought about in the Voronoi version was that some parts of the map are essentially meaningless. What would be great would be a separate grid-weighting that could be incorporated with the existing control grid. The easiest one to consider for this was Neutral Camps - it makes sense that controlling neutral camps is important. This metric was initially very simple to do - you just need to calculate expected gold value for each camp.
So What Have We Got?
On each match page (of 7.40) there’s now a graph on datdota showing a few values:
networth advantage at that time (updated per minute, from frame data)
the map control value at that time (updated per 5 seconds)
a neutral control value (updated per 5 seconds)
a cumulative neutral control value (updated per 5 seconds, derived from neutral control value)
There’s also a Teams → Map Control section which shows aggregate team map control within a filter query, and the 100 highest & 100 lowest control value games (you can also filter by wins/losses if you want to compare).
What’s next?
As I mentioned above, I could add more control layers representing more data: creep positions, summons, and other edge cases (Lone Druid is a mess right now!).
Another thing would be great is coming up with another grid-weighting (like we did for neutral creeps), but for something else like Roshan, or areas of the map which teams prioritize. What is difficult is coming up with weights that make sense (like EV for neutral camps)
There’s also potential to improve the Gaussian blurring to consider the map terrain - exerting control over cliffs is more difficult than down a ramp, or just through open jungle area.
The hero networth calculation could be improved a bit - instead of log(networth) it could be optimized as networth^f for a new model parameter f. Right now the influence between two heroes is fixed based on the ratio of their networths (although the weighting between heroes and non-heroes is optimized).
I also need to run the collector + optimizer over prior patches; right now I’ve just got 7.40 working.
Cheers, Noxville