Influence of region, skill and patch on predictability in League of Legends

Last month, I used random forests to predict the winner of League of Legends games. Since then I have downloaded datasets from different regions, different ELOs, and on different patches, and checked how these factors influence predictability. This post will summarize the results, but for details of the analyses, please see this notebook.

Differences between regions

Korea is famed for its great players, and an "open mid" philosophy (in a normal game of League of Legends, you cannot surrender until 20 minutes into the game; in Korea, players accelerate this process by letting the other team win the game quickly through an "open mid"). Are we able to see those attributes in our model? As a first way to look at this, we can plot the length of games in different regions.

The EUW and NA have similar distributions of game lengths, with around 8% of games being surrendered at 20 minutes. The Korean games, on the other hand, have a few percent more games ending before 20 minutes, due to open mids, and a 14% of games ending right after 20 minutes. Since so many games are ending earlier, can we see this in the model's predictions?

Indeed we can, with games being a few percentage points more predictable for games that last 20 minutes or less. However, once the games last 25 minutes, all the regions are similarly predictable. This means that the Koreans are surrendering winnable games.

Skill and predictability

We can run the same type of analysis for skill. In the notebook I compare Bronze V games to challenger solo queue, and show that low skill games are slower, and less predictable than high skill games. Here, I will compare high skill solo queue games to master tier team ranked. The team ranked dataset is quite a bit smaller than the solo queue data (1,000 games vs 30,000), but in my tuning, I've found there is not a big difference in accuracy when the dataset is over 1,000 games.

We can start again by plotting game length.

Team ranked games are about two minutes faster than solo queue games. We can then run the prediction algorithm again on the team ranked games.

Team ranked games are much more predictable than solo queue games! (This is in fact the largest difference in predictability I have seen between different datasets). What is likely happening here is that coordinated teams are more able to capitalize on their advantages, and press them around the map. With fewer mistakes to allow comebacks, the games are faster, and more predictable. It would be interesting to further look at professional games to see how they compare.

Patches and predictability

In recent patches, Riot has made significant changes to the game, which makes it feel like the games are faster, and comebacks more difficult. I scraped challenger and master ranked games from the most recent patch, and compared them to ranked games from Season 5. We can again start with game length.

If you thought games were faster, your intuition was right, as games are around three minutes faster in preseason 2016. What about predictability?

As you'd expect given the previous relationships between speed and predictability, preseason 2016 is a few percentage easier to predict. In a previous blog post, I investigated the importance of different features on predictability, and found that dragons were not important in helping teams win. Putting on my amateur designer hat, this means that dragon is even less important, since games are less likely to last long enough for the accumulated advantages to matter.

In my next post, I'm going to go more in depth on the modeling, investigating random forest hyper-parameters, and maybe trying a few different models.

Visualizing champion difficulty in Jupyter

I've been playing around some more with League of Legends analysis and Jupyter. This time I scraped champion information from League of Graphs, and calculated which champions were the easiest / hardest to play, and which champions are best in the early / late game. Unfortunately, Blogger does not interact with Jupyter, so I have posted the notebook on nbviewer, if you are interested in taking a look!

Playing in random forests in League of Legends

I've wanted to learn more about machine learning, specifically python's scikit-learn module. I'm an avid League of Legends player (summoner names lemmingo and Umiy), and Riot Games provides a thorough API for querying game data, so I decided to explore machine learning using League of Legends (LoL). Specifically, I wanted to see if I could predict the eventual winner of a game long before the game finishes. In this post, I'm going to explore some features of the LoL dataset, describe what features are important in predicting the winner, show how the predictions change over time, and investigate how winnable surrendered games are. If you are interested in the details of how I did my analysis, go to the github page for this project, or this Jupyter notebook.

For those who don't know what League of Legends is, it's an online competitive game where teams of five players try to destroy each other's base. Some key things players do during the game are: 1. get gold; 2. destroy towers; 3. kill other players; and 4. kill boss monsters called dragons. Games usually last 25-40 minutes, and each game has a clear winner (no ties). Teams can surrender after twenty minutes if the the game is a rout.

Loading the data

The details of how I loaded the data are in the Jupyter notebook, but I will give a summary here. To get a list of players, I first queried the API for the list of featured games; from those feature games I extracted 50 player names.  Then I created a list of every ranked game those players were in during the year 2015, approximately 30,000 games in total. These should all be high skill-level games. I then queried the API for the first 6,000 of these games. This took a few hours because the API is limited to ~0.8 requests per second. A JSON with all of the data for 6,000 games takes up ~1GB (this is due to the JSON being text, and containing a lot of redundant information). Finally, I extracted features from the JSON. Now that I have my scripts more established, I can query games, extract their features, and save them directly to a (smaller) csv.

Exploring the features

As with any good data science project, the first thing I did was explore the features. I started by plotting a histogram of the game lengths:

As Riot says, the average game lasts between 25-35 minutes. Few games last less than 20 minutes, with a large spike of games ending right after 20 minutes, due to surrender. There are others spikes just after 30 and 40 minutes, which I don't have a clear explanation for. Perhaps large team fights break out around then.

The second thing I plotted was the average gold difference at 20 minutes.

This is about as normal a distribution as one could hope for, with a standard deviation of 6,300. Rather than plot each feature individually, we can plot how pairs of features are related to each other:

The features shown here are the gold difference between the teams, the kill difference, difference in number of towers destroyed, and the difference in dragons killed. Apologies for the ugly axes.

As you might expect, there is a large degree of collinearity between gold difference, kill difference, tower difference, and dragon difference. This would be a problem for linear regression, but I am going to use random forests, which are less sensitive to collinearity. If I were interested purely in prediction accuracy and generality, I would perform PCA on these components, but for now I'll just use them raw.

Feature selection

I was curious about which features are most predictive of the eventual game winner. One of the cool things about random forests is that they can identify which features are important based on how many trees they are found in. I created a random forest classifier and used it to predict the winner of the game at five minute intervals. Then for each timepoint, I extracted the feature importance, and plotted a heatmap:

Some features: Gold difference, kill difference, tower difference, dragon difference, and firsts of bunch of featues. Carry share is the max kills on a team divided by total team kills. 

As one might expect, gold difference is the most predictive feature, at every time point. Next most important are the kill and tower difference. Surprisingly, dragon difference is relatively unimportant. This is probably because killing dragons yields only a small advantage. If I were to put on my amateur designer hat, I'd recommend Riot decrease the number of dragons required to get the double dragon buff. Another note is that first blood, first dragon, and first tower are mostly uninformative.

To get a better look at how feature importances changes with time, let's take slices of feature importance at 20 and 35 minutes.

There are some significant changes in importance between these time points. Notably, barons and inhibitors gain importance at 35 minutes. To compensate for this, there is a loss of importance in the rest of the features. Once again, dragons are relatively unimportant, even at the late timepoints. Inhibitors may be ever so slightly more predictive than barons.

Accuracy over time

Given the above feature importance data, I reduced the number of features in the classifier to avoid overfitting the data, and only used the features for the differences, and the baron and inhibitor features. With these features, I then created a small random forest at each time point, and performed cross-validated predictions for the eventual winner of the game.

At the beginning of the game, the classifier isn't successful because there isn't enough information to work with. As the game goes on, the classifier improves, peaking at ~80% accuracy between 20-35 minutes. However, the accuracy drops for longest games. One possibility for this is that there are fewer games that last 40 minutes (less than 1000), which means there is less data to train the classifier. Another possibility is that games that last a long time are fairly close, and close games are harder to predict.

How winnable are surrendered games?

As one last fun thing to do, I wanted to investigate the games that were surrendered early. I separated the games into "early surrenders," and "close" games. To explore the surrendered games, I plotted the gold difference at twenty minutes. The gold difference is bimodal, with one team normally having a large gold lead:

I then created used a random forest to predict the winner of these games, and it did so with 99% accuracy. To see whether these surrendered games were really unwinnable, I trained a random forest on the close games, and then used that forest to predict the surrendered games. Here, it was only 94% accurate. My interpretation of this is that around 6% of surrendered games are winnable!

I have lots of ideas for how to expand on these initial results. I would like to train the model on low ELO games, and see how predictable those are in comparison to high ELO games. Riot has an API for professional games as well, and it would be fun to see if pro games are more (or less) predictable than amateur games. I could scrape games from different regions and compare them. One long term goal is to create a live predictor for LCS games as they happen. If you have any ideas, let me know in the comments!

Walk Along the Paper Trail: Garfield Gap

It's been three years since I did a Walk Along paper summary! Wow!

Recently in our journal club, we discussed a paper by Garfield et al from the Lowell lab. In discussion, some unusually interesting points were raised, and I'd like to think about them here.

Background

I've written about this before, but here is a quick refresher on hunger in the brain. Many types of neurons control metabolism, but the most famous are AgRP neurons in the arcuate nucleus of the hypothalamus. If you stimulate AgRP neurons with channelrhodopsin, or chemogenetically, you can make mice "voraciously feed," aka stuff food in their face. Notably, AgRP neurons are GABAergic, which means they are shutting down neurons in other areas.

While I've written about AgRP neurons before, I've generally ignored what AgRP itself is: a neuropeptide. AgRP does not bind to AgRP receptors, but is actually an endogenous antagonist for the melanocortin-4 receptor (MC4R), whose principle ligand is α-MSH. AgRP neurons cohabitate in the arcuate nucleus with POMC neurons that produce α-MSH; stimulation of POMC neurons can reduce feeding (albeit on a longer timescale than AgRP neurons).

AgRP neurons project to a lot of different brain areas. To see whether all of these projections can induce feeding, the Sternson lab stimulated axon terminals in a bunch of different brain regions, and found that stimulation of only some of these terminals (namely the PVH, aBNST, and LH) could induce feeding. One question Garfield et al wanted to answer was, "what is the molecular identity of these downstream targets?"

Is occlusion anything?

Since AgRP does not have any agonistic receptor, Garfield and colleagues investigated neurons expressing MC4R in various brain regions. They started by performing channelrhodopsin assisted circuit mapping (CRACM!) to see if AgRP neurons connect to MC4R neuons. To do this, they infected AgRP^Cre :: MC4R^Cre mice with channelrhodopsin in the AgRP neurons, and GFP in the MC4R neurons in the PVH. They sliced brains, patched onto PVH^MC4R neurons, and photostimulated the AgRP axon terminals (see diagram below). They found that 25/30 MC4R neurons received IPSCs following photostimulation, showing they were connected to AgRP neurons (panel A). They also patched onto non-MC4R neurons in the PVH, and found that only 2/10 neurons received AgRP input, showing that the AgRP-> PVH connection was fairly specific for MC4R neurons (panel B).

Patch recordings of MC4R neurons downstream from AgRP. AgRP neurons express ChR2-mCherry (red), and MC4R neurons express GFP (green). A. When you photostimulate AgRP neuron terminals, most MC4R neurons receive GABAergic inputs. B. When you photostimulate AgRP input to Non-MC4R neurons, most neurons do not receive input.

A previous paper by Atasoy and Sternson had claimed that AgRP neurons project to oxytocin or SIM1 neurons in the PVH, so Garfield investigated a few other neuron types in the PVH as well, but found no connections to any of them.

After showing the connection in-vitro, they wanted to show it functionally in-vivo using behaviour. They performed an occlusion study where they infected both AgRP and PVH^MC4R neurons with ChR2, then put an optic fibre over the PVH to stimulate the AgRP fibre terminals simultaneously alongside PVH^MC4R cell bodies (panel g, below). When they did this, they found the food intake was lower than AgRP neuron stimulation alone (panel h).

g. Diagram of experiment. AgRP neurons express ChR2. In different experiments, MC4R or OXT neurons also express ChR2. The optic fibre is placed over the PVH to stimulate cell bodies and AgRP terminals. h. Stimulation of AgRP terminals increases feeding. This is reduced ("occluded") by simultaneous stimulation of MC4R neurons. It is NOT reduced by simultaneous stimulation of OXT neurons.

I originally liked the idea of behavioural occlusion, perhaps because it reminded me of LTP occlusion. However, I'm not sure that it's informative in circuit mapping. First, my intuition is that direct excitation beats indirect inhibition. So if you stimulate AgRP terminals and MC4R neurons at same time, and direct excitation wins, it doesn't really tell you anything. Second, if you know two brain regions oppositely modulate behaviour, stimulating both of them does not tell you whether they directly interact. For example, stimulation of PKC-delta neurons in the CeA reduces feeding, and PKC-delta neurons are not connected to AgRP neurons. If you simultaneously stimulate AgRP and PKC-delta neurons, and one "occludes" the other, it won't mean they are directly connected. It only means one is stronger than the other!

In fact, I think the term "occlussion" is misleading, and not used in the same way as it was in LTP. In LTP, two protocols "occlude" each other if they both induce LTP alone, but stimulating both of them does not yield additional LTP. They are said to occlude each other because they use the same signaling pathway. In behaviour, "occlusion" has referred to stimulation of opposing pathways where one wins out. This experimental paradigm seems to be catching on, but I'm not sure it actually means anything.

Do all neuropeptides synapse on receptors?

Garfield next started looking for other AgRP-MC4R connections in other brain regions. As before, they infected AgRP neurons with ChR2-mCherry, and patched onto GFP-infected MC4R neurons in the anterior BNST, and the lateral hypothalamus (LH). Unlike before, there were no connections between AgRP neurons and MC4R neurons in these other brain regions.

Whole-cell patch onto neurons MC4R downstream from AgRP neurons expressing ChR2. No neurons, either in the aBNST or LH, were connected to AgRP neurons. Note the n's are not connected.

This raises question to me, how often do peptide neurons synapse onto peptide receptor neurons? (AgRP is certainly a strange case insofar as it doesn't have a natural receptor). There are hundreds of peptide-receptor pairs, and from the brief literature I've looked at, people don't always verify these cells are connected. For example, in the recent Dietrich paper about NPY5R (NPY is another neurotransmitter for AgRP neurons), they stimulated AgRP neurons and applied NPY5R antagonists, but never actually patched onto neurons to see if they were connected.

All neuropeptide neurons express multiple neurotransmitters, including classic ones and neuropeptides, and it's possible each transmitter work at different temporal and spatial scales. Fast neurotransmitters like glutamate or GABA are reuptaken quickly, and so cannot diffuse; in contrast, neuropeptides can last for minutes or hours. This would allow, for example, AgRP neurons to form GABAergic synapses on specific targets, and let their neuropeptides diffuse and act as paracrine [?] signaling.

In any case, I hope that as people explore these systems, they verify that the neurons we assume are connected, in fact are.

Collateral

Once they identified PVH^MC4R neurons as important for feeding, they wanted to know where they projected, and specifically if PVH^MC4R projected to multiple targets or single ones. They identified PBN as a major target of PVH^MC4R neurons, and used rabies virus to retrogradely label PVH^MC4R that project to the PBN. When they investigated other brain regions that PVH^MC4R projects to, they did not see axons, showing these neurons do not send collaterals.

(Top) Diagram of experiment. PVH^MC4R neurons are labeled in red. PVH^MC4R that project to the PBN are labeled in green. (Images) There are red and green cells in the PVH, and red and green terminals in the PBN. However, there are only red terminals in the vlPAG and NTS/DMV.

Previous research has shown that AgRP neurons do not have collaterals, and made me wonder whether this is a common feature of mid- or hind-brain neurons. However, a recent paper from Luqin Luo's lab mapped axons of locus coeruleus norepinephrine neurons, and found that those neurons do send collaterals widely, albeit biased towards specific areas. As we get more information about cell types, and perform more extensive tracing studies, we will get a better sense of what parts of the brain have discrete pathways versus overlapping projections.

The catch-22 of recording from identified cell populations

Recording from individual cells in genetically identified populations is the hottest technique in systems neuroscience right now (I am, of course, totally biased since that's what I'm trying to do). To record from identified populations, you first choose a mouse line that expresses Cre driven by a cell-specific marker like D1R. Then you transduce those cells with floxed ChR2 or GCaMP so you can phototag or image them. Finally, you run the mice through behaviours while recording to see how the identified neurons respond. If everything works out, you can directly link identified neurons' activity with specific behaviours.

There is, though, a catch-22 in interpreting these results. If all the cells respond the same way, then you have confirmed that your population is unitary, but the single cell nature of your recording yields no new information. On the other hand, if the cells you record from respond to a bunch of different things, they're not really a unified population, but rather a conglomeration of different neuron types. To illustrate these issue, I'd like to briefly show figures from two papers.

All together now

If you stimulate AgRP neurons in the hypothalamus, you can get a mouse to shove chow in its face. What remained unclear until this year, however, was how these neurons fire naturally. Some evidence gave hints; cFos staining had shown that these neurons are more active in hungry mice; in vitro recordings have shown that in hungry mice, these neurons receive more excitatory input, a cool form of short-term plasticity (Yang, ..., Sternson, 2011); and imaging has shown that these neurons undergo rapid spinogenesis and pruning when mice are hungry and fed (Liu, ...,  Lowell, 2012). In general, the working hypothesis was that AgRP neurons fire at a high rate when a mouse is hungry, which causes a mouse to seek food, or eat; when a mouse is sated, AgRP neurons turn off.

Given that basic model, there were many unanswered questions. How fast do AgRP neurons turn on and off? Do they turn off when you start eating, or do they take time to integrate enteric (gut) signals? What rate do they fire at? To answer these types of questions, we needed the development of easier in-vivo recording techniques for deep brain areas.

Earlier this year, the Knight lab at UCSF answered many of these questions by doing fibre photometry of AgRP and POMC neurons expressing GCaMP6s. (Chen, ..., Knight, 2015). They found that the activity of AgRP neurons in hungry mice actually decreases before mice start eating, when the mice first sense food (see below). In addition to receiving gut information, AgRP neurons receive fast input from brain areas that can identify food, which was unexpected. These results also question whether AgRP neurons are "hunger" neurons, or something slightly different like food seeking neurons.

AgRP neurons decrease their activity when mice see food. B. When a hungry mouse sees food (red trace), AgRP neuron fluorescence decreases. When it see an object (black trace), the neuron does not change activity. C. Summary of AgRP neuron fluorescence changes in fasted and fed mice responding to objects and chow. Only fasted mice that see chow decrease fluorescence.
From Chen, et. al., 2015.

Even knowing how AgRP neurons respond on average, it is possible that individual AgRP neurons respond differentially due to differences in protein expression or projections. AgRP neurons express variable levels of metabolic receptors like insulin or ghrelin, which could influence firing. Subsets of AgRP neurons project to different brain regions without collaterals; stimulation of some of these projections induces feeding while others do not, implying functional differences. Given these differences, it's possible some AgRP neurons respond to food cues, while other respond to enteric signals. To answer these questions, you would need to record from single cells.

Fortuitously, the Sternson lab did just that, using an in-vivo endomicroscope to image individual AgRP neurons expressing GCaMP6 (Betley, ..., Sternson, 2015). They found that all AgRP neurons act pretty much the same. They quantified fluorescence changes from AgRP neurons when a mouse was well fed, or food deprived; 54/61 neurons had brighter fluorescence when the mouse was food deprived (panel e, below). Like Chen et. al., they found that AgRP neurons decreased their activity before the mice started to eat (panel f); 96% of them to be precise (panel i).

AgRP neurons have higher activity when a mouse is hungry. e. Magnitude of fluorescence events for ad-libitum (AL) and food restricted (FR) mice. f. Single trial fluorescence traces from neurons during consumption. Most neurons decrease their activity before food is consumed. i. Magnitude of fluorescence before eating, after eating for one trial, and during satiety. 96% of traces decrease between the first trial base and first trial food.
From Betley, et. al., 2015.

I can tell you from personal experience these experiments are not trivial. The pessimistic interpretation of these results is that the technical prowess did not yield any new information. In talking to colleagues, however, that is probably unfair. Since we know that stimulation of different subsets of AgRP neurons can elicit different behaviour, the uniformity of their responses is surprising. This creates the question of how subsets of neurons which express the same protein and respond to the environment in the same way can elicit different behaviour.

How am I different?

In contrast to all the neurons acting the same, there is the possibility that all the neurons act differently. To illustrate this, I've selected a recent paper from the Stuber lab at UNC which investigated GABA neurons in the lateral hypothalamus (LH; Jennings, ..., Stuber, 2015). They used an in-vivo endoscope to image Vgat-Cre neurons expressing GCaMP6m. They had previously shown that these neurons are involved in consummatory behaviour.

During imaging, they ran the mice through two sets of behaviours. First, they let the mice eat in a cage with food located in two corners. If neurons had increased activity in the food zone, they were categorized as food zone excited (FZe); if they decreased activity, they were food zone inhibited (FZi). Around 10-15% of neurons were FZi or FZe (panel F, below). In a second set of behaviours, the mice were taught a progressive ratio task (PR3) where they could nose poke for food. Here they found some neurons responded during the nose poke (23%), while others responded during the consumption of food (10%; panel H, below). Finally, one might imagine that FZe or FZi neurons were correlated with nose poke or consumption activity, so they investigated the overlap between these populations. 28/40 FZe neurons responded during the PR3 task, split between consumption and nose poke; 12/40 FZi neurons responded during the PR3 task, again split between consumption and nose poke (panel J).

LH GABA neurons do all sorts of stuff. F. Histogram of change in neuronal activity when a mouse enters a food zone. H. Venn diagram of cell responses during PR3 task. J. Overlap of FZe and FZi responses with PR3 responses. There does not appear to be a consistent pattern of activity either in the tasks individually, or across tasks.

The authors highlight the diversity of responses in their discussion:

Our data suggest that separate subsets of appetitive-coding and consumption-coding ensembles exist within the LH GABAergic network. Thus, the LH GABAergic network can be viewed as a mosaic of functionally and computationally distinct cell types, requiring further definition. Nevertheless, these important computational differences among individual LH GABAergic neurons would have gone unnoticed if only bulk neuromodulatory approaches were employed, further underscoring the necessity of identifying the natural activity dynamics within a network to better understand the precise neural underpinnings of complex behavioral states.

The pessimist in me is frustrated by these results. Now we have to track down the neuronal subtypes, and repeat the experiments for each subtype (and lord knows I hate repeating experiments)! On the positive side, this could be a building block for future experiments. There is now a lower bound for the number of cell types to look for (at least five). I think single cell sequencing is the only way to identify these cell types reliably, and without recording.

Anyway, that is a long way of getting at what I see as the catch-22 of single cell identified neuronal recording: if they're all the same, you didn't need single cell resolution; and if they're all different, you don't have an strongly identified cell type.

References

Betley, J., Xu, S., Cao, Z., Gong, R., Magnus, C., Yu, Y., & Sternson, S. (2015). Neurons for hunger and thirst transmit a negative-valence teaching signal Nature, 521 (7551), 180-185 DOI: 10.1038/nature14416

Chen Y, Lin YC, Kuo TW, & Knight ZA (2015). Sensory detection of food rapidly modulates arcuate feeding circuits. Cell, 160 (5), 829-41 PMID: 25703096

Jennings, J., Ung, R., Resendez, S., Stamatakis, A., Taylor, J., Huang, J., Veleta, K., Kantak, P., Aita, M., Shilling-Scrivo, K., Ramakrishnan, C., Deisseroth, K., Otte, S., & Stuber, G. (2015). Visualizing Hypothalamic Network Dynamics for Appetitive and Consummatory Behaviors Cell, 160 (3), 516-527 DOI: 10.1016/j.cell.2014.12.026

Liu, T., Kong, D., Shah, B., Ye, C., Koda, S., Saunders, A., Ding, J., Yang, Z., Sabatini, B., & Lowell, B. (2012). Fasting Activation of AgRP Neurons Requires NMDA Receptors and Involves Spinogenesis and Increased Excitatory Tone Neuron, 73 (3), 511-522 DOI: 10.1016/j.neuron.2011.11.027

Yang, Y., Atasoy, D., Su, H., & Sternson, S. (2011). Hunger States Switch a Flip-Flop Memory Circuit via a Synaptic AMPK-Dependent Positive Feedback Loop Cell, 146 (6), 992-1003 DOI: 10.1016/j.cell.2011.07.039