Natural selection for ingame character build optimisation
Context. Dead by Daylight is a 1v4 computer game, where one hunter tries to prevent 4 survivors from escaping death. The game has 34 killer characters to choose from, each has his own 20 addons (from which he can take 2 into the trial), and any character has 4 slots for additional superpowers/skills (115 perks to choose from).
That creates an optimisation problem: What combination of those things I could pick to increase chances of winning?
If you happen to like playing hunter, there are more than 2e12 possible combinations to build your character. Currently the community goes primarily by intuition: read description of a perk, play it couple times, make a conclusion about its possible synergies, make a tierlist, use the S or A tier every game. But those conclusions are always truncated—I cannot trust myself to predict all possible synergies and would like to get rid of opinion effect on the results. If I decided to use statistical methods to discover correlations, then I would need to either play N of matches before making any conclusions, or to collect data from the community. The problem with the first approach is time—it just takes too long with 20 minutes per match, and the N is huge (because it is a function of accepted confidence level). The problem with the second is called “meta stagnation”. Gamers in the community usually do not experiment with builds and trust conclusions made by predeccessors, which creates a skew in perk usage. Even though some people adapt their build slightly, in majority of cases it is the same set of synergies used and the data will not contain anything else.
Here is how I will optimise my build for each character. Each will have two pools of entities (pool for addons and pool for perks). There will be X entities of each kind in pools at the start. Amount of entities (lets call it tickets) will be proportional to the chance I will play that entity the next match. After a win (4k) with an entity, I add 1 ticket to it in the according pool, after a loss I substract 1. That creates an environmental pressure, because after reaching 0 the entity will not be tested again. That leaves a chance of losing a good perk after just X unlucky matches, but those who stay for long in the population and whose tickets increase will at least be consistent in their effect on the match, and they will reflect my personal playstyle.
So, I expect to land at not The best build, but at a build of consistently positively interacting perks and addons. The more likely to survive are the entities, which either are good by themselves, or have a bigger count of possible synergies with other entities.
After the pools are greatly reduced in size or there appear ~6 dominant species, I may consider the search completed.
I suspect that if synergies and play-style variations (how you actually use the options) are significant, you won’t get much improvement by this mechanism. Without some analyitic or large-simulation scoring of combinations BEFORE you randomize variations of promising starting intuitions, you’re trying to test too big a space of possibilities in too few trials.
Also, if synergies are the key thing, it’s not clear that any improvement is “a step in the right direction” which can be further improved, or just “a lucky combo”, which stands alone.
The evolution is meant to quickly reduce the space of search. If every perk in the pool starts with just 1 ticket, then most of perks will only be tested once (because they lead to a loss and their population immediately got to zero). If the very first run is a loss, then the true-unknown winrate of a perk is likely not a 90%, so we should not regret throwing it away.
The synergies will have effect on the populations sizes later. Those pairs that synergise are slightly more likely to lead to a win and to increase tickets of both in the pool. After some weak perks fell off and the total amount of species in the pool was reduced, we expect potential synergy-makers to “meet” more often. That is a step in the right direction. If their win was just a lucky coincidence when the perks are not consistently good, they will die out a bit later.
Of course, if the very best build relies purely on synergy and is a combination of very-bad-in-solo perks, it will not be found. I acknowledge there is no way to find the true best combination, that search would require bruteforce playing all possible combinations 20+ times. The aim is to find a managable algorithm which does not rely on personal evaluation at all (because opinions is partially the reason of “stagnation of meta”).
I anticipate that if your experiment is successful in discovering underrated synergies between perks, your new perk combos will be adopted more widely, which will affect perk selection behavior in your opponents, which will in turn affect the efficacy of the new synergies.
If you were crowdsourcing the perk combo experiments across many players, the experiment’s complexity would explode when you try to control for the impact of player skill or individual playstyle preferences on the quality of a build.
I wonder if you could simplify the combinatorics of perk combo testing by grouping and rating perks by category of theme. For instance, it may be much better to factor each specific perk or item by its mechanical impact, when there can be multiple impacts per item. Maybe perk X increases your shooting accuracy while decreasing your move speed. When you discover synergies with it, framing those synergies as “with anything that increases accuracy” or “with anything that decreases speed” or “with anything that both increases accuracy and decreases speed” will give you a better “shopping list” in the perk tree. “oh, I know the thing that increases my damage dealt when I’m moving slower works well with anything that makes me move slower”, flavor of insights.
The problem space here also reminds me of a video I saw awhile back: https://www.youtube.com/watch?v=5oULEuOoRd0&ab_channel=NightHawkInLight
Part 1. That is a good analitical approach to split into groups and then synthesize the build. But let me give an example of how one unexpected/unconventional synergy looks.
Perk 1: You see blood drops on the ground better. Perk 2: You get a notification whenever a bird is disturbed by an enemy, and you can pinpoint the direction.
Both these perks would fall into general and quite a big bin of “information perks”. Both their descriptions do not give any hint that they would work together. Here is the scenario which happened a lot in my games: You damage one opponent and leave immediately without tracking him down. The opponents will communicate between themselves that you changed your plans, and they will react accordingly by changing positions. Their relocation likely disturbes a bird and you can quickly find and damage the second opponent. The first would likely find a hiding spot to heal, but you switch targets again and track the first guy by his blood drops. But switching targets again encouraged opponents to take strategically better spots and disturb birds, giving you information again. That creates a loop, where you flip flop between reacting to the info those 2 perks give, AND creates a bit of confusion and inefficiency in the opponent team AND they waste time (which is a limited resource) by responding to your changes of targets. (If you were hunting just the first player, like if you had no info perks and were afraid to lose track of the injured guy, all 3 other players would sit on their tasks and feel safe).
Many perks in the game are not like “get +x% to y stat”. They introduce a new mechanic. If all perks woul give some numerical benefit to the stats, I think it would be possible to use Wolfram language to solve a system of 100+ equations.
Part 2. Thanks for the video right on topic. I did not know the problem is called Full factorial analysis.
The video shows a problem with 3 slots and 2 possible values for each slot. Those values can repeat (LHH). In my problem there are 4 slots, and 116 possible unique categorical values, which cannot repeat from slot to slot. I do not understand the principles of scaling here. Soo, I build a table, such than any column contains equal observations while having and not having a perk. I don’t quite understand how the table is generated, but thanks for the food for thought, I’ll dig in this direction.
http://neilsloane.com/doc/cent4.html According to this page, all tables have unsuitable “orientation”. For example, there is a table with 99 factors and 2 levels, but the task would need 4 factors and 116 levels. The amount of levels must be much bigger.