Data mining in online games

In all online services and games, the largest share of the audience goes right at the start - in the first minutes and hours of familiarity with the product. Hundreds of books and articles are already devoted to this topic with a variety of hypotheses of success and reasons for audience loyalty - uniqueness, simplicity, usability, gratuity, training or instruction, emotionality, and many more factors are considered extremely important.

We wanted to know why the players are leaving and whether their withdrawal can be predicted . The subject of the research is MMORPG Aion, however, our results were applicable to a wide range of games and online services.

Almost British scientists found that the user has a very short memory. Today he left the game, but tomorrow he will not remember that he installed it at all. If the player is gone, then you must act immediately . But how can we determine whether a person has really left, or is he just drinking beer with friends tonight and will not appear in the game? The ideal case would be a prediction of potential withdrawal even before the user left us. And even before the thought arose in his mind that Aion did not look like a cake. Probably, such a task is also solved, but we set a more realistic goal - to promptly predict the departure of the game on the day of the last login . As a departure, we’ll call a person’s inactivity during the week - and we don’t want to wait for these 7 days, but we want to know as soon as possible that the player will not return. We want to know the future!

Technical side

For analysis, we had a sea of ​​information - Aion has the best logging system that I saw among the Korean games, we literally know about the player his every move, every sneeze and every trace he left on the server. The period for analysis - the first nine levels in the game, about 10 starting hours of gameplay - for this period about half of all beginners fell off.
')
A part of the resources of our analytics system was allocated for the project - two Dual Xeon E5630 32Gb RAM server blades, 10 Tb cold storage for source and intermediate data, 3 Tb hot storage in a RAID10 SAS array for business data. Both servers for MS SQL 2008R2 are one for the database and one for Analysis Services. The software part of the solution is Microsoft's standard Business Intelligence package included in SQL Server.

Phase 1 - I know everything!

Since I was a game designer for many years and spent under a hundred playtests, I was sure that even now expert opinion will give 90% of the answers why the players are leaving. I did not learn how to use teleportation, I got tired of running around with my legs - I left. He died from the first monster in the game - left. I did not fulfill the second mission, I was stuck and I don’t know what to do - I left. Aion, with all its quality and manufacturability, is not the most beginner-friendly game. This is a feature of all Korean games designed for the hardcore and hypersocial environment of Korean players, and not the lonely bored Russian casual users.

I put on the hat of the “ordinary user” and went through the free start of the game for both races and several classes, writing out all the clumsiness, illogicalities and problems, having formed the first list of hypotheses to test:

• Race and class of characters. It was assumed that the class will be the strongest factor, since the gameplay for the Healer is very different from the mage squinting all right and left.
• If a person has played other games - we have a single account for all projects, so it is easy to follow the cross-conversion.
• Did the player try more than 1 character - did the other classes and race know it?
• How many times he died at levels 1-4, 5-7 and how many times he died during the trial.
• Did you join groups with other players, including high-level ones (i.e., obviously familiar with other games or in real life)
• How much computer memory, because Aion is resource intensive
• Whether the character received mail and entered the guild is a clear sign of "twinks", secondary characters created by already active and experienced players.
• How many tasks did the character perform to this level, how many tasks did he cancel and how many did not he simply take
• Does the player pass in-game polls for which give good buns
• What skills does a character use in combat and kill monsters

The list turned out to be impressive, detailed to the point, and a number of ways were found to upset the novice before losing the desire to play. We get into the model the first couple of hypotheses, we predict the boolean variable is_leaver - will the player leave right now, at the 7th level:


How to read a lift chart: the lower oblique straight line is the result of a random number generator that predicts our boolean variable using the scientific method of throwing a coin. The top line, quickly reaching 100%, is the oracle, the ideal predictor of the future. Between them there is an uneven, trembling thread - this is our model. The closer the graph is to the ideal line, the higher the predictive accuracy of the model. The graph is for level 7, but the picture is similar from first to ninth.

Fatality! Our first model predicts players leaving a little bit better than heads and tails. We send the remaining hypotheses to the models, clean the data, process it:


Already better, but still the accuracy is slightly above 50%. And if you look at recall (errors of the second kind), then the picture is sad:


The same table is in Russian - out of every 100 predicted by the model of departures, 49 will be false (the player will not go anywhere), the accuracy of the model will be 1008 / (1008 + 982) = 51%. At the same time, the model will completely miss some of the actual departures - approximately 28% of the truly departed [391 / (391 + 1008) = 28%]. Attention, this is not a canonical definition of recall, but this formula is clearer.

The result of phase 1 : all the original ideas failed, the prediction does not work. Chef, it's all gone!

Phase 2 - we know nothing

Full defeat and flight from the battlefield, and the eternal question "What to do?". The naive Bayes algorithm comes to the rescue - the most human-readable and understandable of all data mining classifiers. The Bayes analysis showed that the selected hypotheses rather poorly characterize the players who left and remain, that is, I was mistaken with the choice of the initial premises. But, having played with the depth and sensitivity of another algorithm, a decision tree , it became clear that there are correct hypotheses, the tree branches along them, but there are definitely not enough factors - the growth of the tree is interrupted by a 2-3 branch.

Without getting into the wilds of mathematics, which I myself don’t understand, it’s simplistic - the decision tree algorithm divides the source data into segments with the lowest possible total entropy, that is, the most dissimilar data sets. If the tree stopped branching, it means that we need new hypotheses and new metrics in the original data in order for the tree to deeper divide the input data stream and better predict the future.

I gathered a brainstorm with the project team, where we gushing ideas - who our beginners are, how they play, how they differ from each other. They remembered the stories of how our friends and wives got to know Aion, and what came of it. The result of the brainstorm was a supplemented list of individual hypotheses (did the player use teleportation, expanded his inventory, attached a resurrection point, etc.) and a new idea - it would be nice to see how much the activity is different from those who remain in the game.

To study the average activity, we calculated several metrics:

• the number of monsters killed at this level
• number of tasks completed at the level
• time in minutes spent at each level

At this stage, at the same time, the ETL part of the project (loading, transforming and clearing data) was redone. Our SQL guru Ilya made an analyzer-designer on SSIS, which easily connects new events from the game logs. Logs gigabytes, so there was no lack of information, and new hypotheses were invented every day.

Downloaded, trained, verified, analyzed. I will not load you by sea lift charts for each level and each model, I will cite immediately processed and analyzed data:


The peak of accuracy at level 9 was associated with the internal feature of the game at the time of the study.

In general, the picture has improved in the area of ​​2-4 levels, but 6-8 below the baseboard, with such accuracy, the data we simply useless.

The decision tree cheerfully shows that activity factors are most important for predicting care. In fact, three quantities — time at the level, dead monsters, and quests done — determine the lion's share of the departures. The remaining factors add no more than 5% accuracy. Also, the tree is still bare, the crown is cut off on the third branch - that is, the model craves for more relevant metrics. What is still not clear - the accuracy of the three algorithms varies greatly from level to level.

The outcome of phase 2 : the success of the idea of ​​measuring average activity, rather than individual factors. But the prediction accuracy is still unsatisfactory. The path along the rake brought to the correct sequence of analysis of the results - first the factors and correlations (Bayes), then their influence on the result (the decision tree).

Phase 3 - we know where to dig

Inspired by the progress, I outlined three vectors for the development of the project — more metrics of total activity, more specific metrics of individual effectiveness, and a deeper study of Microsoft BI tools.

Experimenting with activity, we stopped at the following set:

• Spent time at the current level, at the previous level and the total time in the game to the current moment
• The rate of killing monsters - pieces per minute at the current level, the previous and all.
• The speed of completing tasks per minute is similar to mobs.
• The average time in the game on the game day, days spent in the game and unformed days (for example, a person entered on Monday and Wednesday - 1 day is missing).

These metrics gave a good reduction in missed cases, almost one and a half times. The decision tree began to branch up to 9 nodes, which shows the relevance of the metrics. Plus, the unification of trees for different levels was a good sign - if in the last phase, as I wrote, the accuracy of algorithms strongly jumped from level to level, now it was clearly visible - the tree beats on the first, second, and third nodes according to exactly the same indicators regardless of character level. And naive Bayes is already 5-10 percent behind the tree and neural network.

I had to tinker with new individual metrics related to the depth of the gameplay and the effectiveness of the game, for example, the percentage of auto-attacks. We segmented the characters into classes (warriors to the right, healers to the left) and for each class calculated the 25th, 50th and 75th percentiles of the %% auto-attack distributions, and divided them into 4 categories. Now the data is normalized , and game classes can be compared with each other - the number of the category goes to the input of data mining models.

In online games, characters kill enemies with different spells and abilities. An auto-attack is a free, very basic (and weak) blow given from birth. If a player is effective, then he applies the abilities of his character - and %% autoattacks among all his strokes will not be very high. However, it depends strongly on the game mechanics what kind of percentage for different classes. In Aion there was a spread from the median of 5% for a mage, up to 70% for a warrior, and even within the class the dispersion is high.

Individual metrics were fixed at the depth of the seventh-ninth node of the tree, i.e. they added a couple of percent to the accuracy of the prediction, but did not improve the situation drastically. The next step was to study the Data Mining with Microsoft SQL Server 2008 book on the subtleties of working with Analysis Services. By itself, the book helped only with setting the sensitivity of the tree (on the strength plus one or two percent increase in accuracy), but suggested the idea of ​​correct discretization.

In the example above with auto-attack, we did manual data sampling - categorization according to some features. SQL Server automatically performs sampling in several ways. Experimentally, I quickly realized that the partitioning algorithm and the number of segments greatly influence the predictive power of the model. Manual change of the number of segments strongly influences the shape and accuracy of the tree. I spent a week on manual adjustment, scrupulously for each structure of each level (and these are 9 levels with 30+ metrics) experimenting with the number of segments. For some metrics, 7 segments were optimal (for example, time at the current level ), for some 12 ( total time in the game ), for some more than 20 ( number of dead monsters ).

Manual tuning gave a strong increase in the predicted values ​​- the accuracy did not increase much, but the models began to make noticeably fewer gaps, and the results of the tree became equal to the neural network:

The result of phase 3 : we reached acceptable levels of accuracy and accuracy and learned a lot of interesting things about our game and our players.

Phase 4 - Win Only

I honestly thought that the ceiling had been reached - the tree branches to a depth of 9-12 knots, the accuracy was greatly improved. New hypotheses do not increase accuracy; new factors do not provide any information. In principle, the overall accuracy of 78% and recall of 16% is satisfactory to start working with players. I probably would not, with such figures, give a free subscription to keep in the game, but you can already inform the player of relevant information without any special errors.

Help came unexpectedly - as the data mining project lasted for the third month, our logs were somewhat outdated - the game changed during that time. After loading a little fresh data, and at the same time once again finalizing the ETL procedure, we noticed changes in the models. On the new data, they behaved differently - with, in general, the same accuracy and accuracy, the partitioning of the tree was different. At this stage, all three algorithms were trained very quickly - a minute for each level of 9, and it is easy to feed them with an additional set of data.

It is said - done, we unload in general all the data accumulated over 3 months and in one fell swoop we send models to study (the process began to take not a minute, but as many as five for each level is not critical). Another round of manual fit, and here's the result:



Increasing the amount of training data, we made the process longer, but what an excellent result!

With the first level, unfortunately, a little can be done - about half of the departures, as Avinash Koshik would say, “ I came, I puked, I left ”. We have data about literally a couple of player actions - and then he closes the game client and never returns.

I remind you that all the studies above are training on accumulated historical data. Now I want a battle check! We check on live data - we take fresh, today's users, we run through the model and save the result of the prediction. A week later, we compare the predictions of the model with the objective reality - who of the newcomers a week ago did indeed go away, and who remained in the game:

The most interesting

The first goal of the project - predicting the departure of a novice from the game - has certainly been achieved. With such accuracy, it is already possible to make decisions on the return of the player, to communicate with him, to motivate him, to give buns. And this prediction is almost on the day of leaving: a person left the game tonight - tomorrow at 5 am the data were processed and the probability of leaving is already known with high confidence.

Has the second goal been reached, do we now know why the players are leaving ? Not. And this is the most strange result for me - with an excellent probability of a prediction of leaving, the question “Why?” Remains unanswered. Remember, I started the project with writing out hypotheses about individual factors, like:

• Race and character class
• Did the person play other Innov games?
• Has the player tried more than 1 character
• How many times has he died at levels 1-4, 5-7 and how many times has he died
• Have you joined groups with other players?
• How much computer memory
• Did the character receive mail and joined the guild
• How many tasks did the character perform to this level, how many tasks did he cancel and how many did not he simply take
• Does the player pass in-game polls
• What skills does a character use in combat and kill monsters

Such factors have been tested a lot - more than 60. None of them is any significant and decisive player care. No one! We did not find in the game some kind of magic barrier that causes the outflow of players.

The most important factor? Has the player gone through the first 7 levels on the very first day of his acquaintance with the game (7 levels are approximately 3 hours of play). This is a key predictor of care - if in the first session the player did not get carried away and did not spend 3 hours, then it is very likely that he will quit the game. The next group of factors is the total player activity :

• Spent minutes in the game at the current level, past and total
• Minutes of being in the game on average per game day
• Dead monsters per hour at the current level, past and total
• The speed of assignments - pieces per hour

Summary : we got two completely different results - predicting a player’s departure based on total activity metrics, and a detailed analysis of the individual playing style. We accurately predict the departure of each newcomer, and we are able to tell each newcomer a dozen ways how personally he can improve his style of play, how he could play more effectively, use all the features of the game, and have more fun.

Victory!

For two months, from scratch - none of us have ever even come close to data mining, - with the help of two books and a desire to try something new, based on the powerful, but passive analytics system in Innova, we made the tool, actively looking to the future . Unlike conventional reporting and analyzing trends in historical data, at 6 am we already almost certainly know about our yesterday's newcomers in Aion - whether we will see them in the game today or not. And we can act before it is too late.

The analysis was performed for an online game, but as you can see, the main contribution to the prediction accuracy was from generalized activity metrics - and I am sure that the approach will work for any of your product or service that users are actively working with, unless of course you have desire to reach a new level.

Ps. If the topic is interesting to habravchanam, then we can continue - about the prediction of old people leaving, segmentation and clustering, migration between clusters and other data mining projects that we did in the outgoing year.

PS2. The second book, I recommend to absolutely everyone - we program the collective mind