# Algorithm to "reverse" search/match pairs from results

Sorry, I don't know how to title it clearly.

There is a game, where players can send their units to attack another player's units (weeell, there is a lot of games like that). Each unit has some value. After the fight, for each participant, the values of destroyed and lost units are added to their account totals (total destroyed, total lost).

There is an API updated around every hour. So I can get hourly deltas of each player. I would like to "reverse-engineer" from that data, who fought who.

Seemingly it's simple, just search where P1.destroyed = P2.lost and P1.lost = P2.destroyed. However, the player can attack another player multiple times (these can be joined, no way or need to separate them anyway). One player can be attacked by multiple players (joint or not), one player can attack multiple players (joint or not) and multiple players can attack multiple players (joint or not). It may also happen that values in two fights come out exactly the same, so they can't be distinguished.

I don't really care if the results come out as joined or separated (separated is preferred, the chance of that is higher than a joint attack, especially multi vs multi).

Is there an algorithm that would somehow try to compute that? Of course brute search, generate all possible groups of players (sounds like n!, Bell number?) and try to compare each with each...

Finally, if there are implementations, I would prefer MySQL or Python.

Edit To answer some of the questions.

@Highheath There are around 1k "live" players. Maybe 10% of that is active at any given time (averagely). Each player can have around 10 simultaneous attacks (but it's pretty rare, just an upper bound), which take usually around 2 hours roundtrip (the fight itself is instant and the stats are updated instantly for all participants). However, fights so big that they are easily visible in main scoreboard happen maybe once per day, and maybe a 100 of somewhat smaller ones (f.e. from weaker players). And I am most interested in these, the rest can be skipped.

@D.W. I thought about it too. Usual fights are not like that, but there is another source (let's call it "catching spies") which generates a lot of 0 vs k "fights" where k is usually between 1 and 100 points. And in an hour they can add up to not-so-small lost value, so probably anything below 1k can be treated as noise. So I thought about filtering out deltas below certain threshold, and then comparing the remaining big ones with some margin of error. But this again complicates the algo and possibility of mismatches.

Edit 2: Here is an example of hourly deltas. A lot of these don't seem to match, but for example, there is one clear joint attack: 111463&111466 vs 105877. Sums almost perfectly.

• How many matches will someone be able to play in an hour? And how big is the player base? Apr 18 at 21:34
• You're going to need to make some statistical assumptions. Do you have any data on the distribution of the number of matches per hour? Do you have data on the distribution of value destroyed in a single match, over all matches, and the same for value lost? If so, please add that to your question. Without any assumptions, there are too many possibilities (it is possible that every fight led to 0 or 1 unit of value destroyed and 0 or 1 unit of value lost, which is going to make matching incredibly painful).
– D.W.
Apr 18 at 23:00
• I answered both your questions in the post. Looking at how complex this quickly becomes, I think the best solution is to filter out anything below certain threshold. Apr 19 at 9:49
• Again, can you show us a histogram showing each of these distributions?
– D.W.
Apr 19 at 17:27
• I dont have that part written yet :) But I will and will try to generate some. Apr 19 at 17:53