Group finder algorithm complexity

[Ilintar]

There was a discussion in the maintenance thread that was locked down, so I figured I'd post this for anyone interested:

 

So it wasn't a bug in the code that caused all this mess, it was a feature.

 

And if it is because the grouping algorithm had high order complexity (as a outlined in another thread, it could be as bad as N! complexity) and therefore consumed a lot more resources the more people joined the queue, I can see why maybe nothing but running it on a fully-loaded server would reveal it.

 

It would be horrible if the algorithm actually was O(n!), but I see no way that it would be implemented thus.

 

The algorithm for a group finder is actually simple. You keep 3 priority queues (heal, tank, damage), you implement them in Fibonacci heaps since you want remove to be relatively cheap (you will remove overlaps). You also keep information about the number of overlapping entries in the queues (so, tank-damage and heal-damage).

 

Now, a key part of the algorithm is that as long as you have the required number of people on each queue (minus the overlap), overlaps don't matter since there are no 3-way overlaps (tank-heal-damage) to resolve. Let's say you have 10 dps, 5 healers and 5 tanks and you have 3 dps-heap overlaps and 1 dps-tank overlap. So, you have 6 pure dps, 1 tank-dps, 4 pure tanks, 3 heal-dps and 2 pure healers. What you do is you first assign the pure roles (so you need 2 more dps, 2 more healers and 0 more tanks). You're left with 3 heal-dps and 1 tank-dps. You assign the 2 heal-dps as healers, 1 of them as dps and the tank-dps as dps.

 

So, whenever num(heals) >= 4 and num(dps) >= 8 and num(tanks) >= 4 and num(tanks) + num(heals) + num(dps) - num(tank-dps-overlap) - num(heal-dps-overlap) >= 16, you pop the respective people from the priority queues (and remove duplicates).

 

If it turns out that some people resign, no problem - since this is a priority queue, you just insert the people back into the queue with their original insertion time as the sorting key (so they land on top).

 

Since the queue size is constant (= 16), at no point does the algorithm have a complexity worse than O(log n) (at most you do 16 removes on a Fibonacci heap).

 

So, there might be other factors involved (synchronization issues, for example), but the very algorithm's complexity should be negligible (say even 300 people are in the queue at once - that's a laugable computational cost).

[Jerba]

At first, I also thought it is a simple priority queue, but the more I think about it, I understand that it is way more complex than that.

You also need to keep track of:

• Players that queue as a premade group and as such need to be placed in the same group
  
• Players that have each other on the ignore list and cannot be placed in the same group
  

I can easily see how you can get to a n^2 complexity since you need to compare every player with everyone else.

Sometimes, players with a lower priority will get placed before everyone else. E.g. assume a DPS queues together with a tank. Even though there are already 10 dps in queue, this dps will get picked if the queue has been waiting for one tank.

 

The lag issues we experienced probably happened everytime the queue was changed, specifically whenever:

• A new player joined the queue
  
• A player in the queue changed his roles (e.g. from tank to dps)
  
• A player added/removed someone to/from his ignore list
  
• Someone leaves the queue
  
• A match has been found and those players get removed from the queue
  

Shortly later, the lag was gone and everything working correctly again, until the next time the queue needed to be refreshed.

Edited June 13, 2014 by Jerba

[Bstr]

num(dps) >= 8 and num(tanks) >= 4

 

Number of DPS in 16 man is 10. Number of tanks is 2.

 

This is the reason behind going to 16 GF: You can take more DPS than 2 8 man Ops and need half the amount of tanks.

 

The algorithm could be much simpler than the above:

 

When someone queues as a tank, put them into a "tank" queue. If they queue as "tank" and "DPS," put them in both queues. Whenever the tank queue has 2, the healer queue has 4, the DPS queue has 10, and the total across queues is 16, assign everyone a role and pull them first set of people out of their queues. In my experience with FP GF, it seems to put those that sign up as "tank / DPS" as a "tank" unless there are enough tanks in the tank queue before the "tank/DPS," then it puts them as DPS. Same with "healer / DPS."

 

EDIT: This doesn't account for Premade groups, which might be the problem with why 16 man GF is slowing everything down.

Edited June 13, 2014 by Bstr

[Ilintar]

Number of DPS in 16 man is 10. Number of tanks is 2.

 

Yeah, stupid mistake.

 

This is the reason behind going to 16 GF: You can take more DPS than 2 8 man Ops and need half the amount of tanks.

 

The algorithm could be much simpler than the above:

 

When someone queues as a tank, put them into a "tank" queue. If they queue as "tank" and "DPS," put them in both queues. Whenever the tank queue has 2, the healer queue has 4, the DPS queue has 10, and the total across queues is 16, assign everyone a role and pull them first set of people out of their queues. In my experience with FP GF, it seems to put those that sign up as "tank / DPS" as a "tank" unless there are enough tanks in the tank queue before the "tank/DPS," then it puts them as DPS. Same with "healer / DPS."

 

This is basically the same algorithm, apart from the way of picking the overlaps (and you're basically right).

[DOHboy]

I would highly doubt they would have a O(n!) or even O(n^2) , both would indicate an exponential search (latter being embedded loops).

 

its is probably more the number of resources allocated per queue and having to perform a check on various queues each time someone added/removed themselves from the queue or each time a queue popped. It isn't so much the numbers and the details that need to be stored and sorted (person only wants one PVP, other wants PVP and PVE 16man but not HM flashpoints etc.)

[Ilintar]

At first, I also thought it is a simple priority queue, but the more I think about it, I understand that it is way more complex than that.

You also need to keep track of:

• Players that queue as a premade group and as such need to be placed in the same group
  
• Players that have each other on the ignore list and cannot be placed in the same group
  

I can easily see how you can get to a n^2 complexity since you need to compare every player with everyone else.

 

Actually, a reasonable ignore table should be at most O(log n) complexity for lookups, and is probably statistically faster than that (a hashtable with ignores will be really sparse unless you have half your server on ignore). However, I agree that this is hard since it requires a graph algorithm - you have to pick a strongly disconnected component of the ignore graph (which is simply a strongly connected component of the inverse graph) of size at least 16. However, the cost of scanning such a graph for connected components is at most O(n^2) (since the number of ignores can be O(n^2) and efficient algorithms are O(|V| + |E|)).

 

The premades are another problem whatsoever. However, they are much more easily solvable. The algorithm works as follows:

* pop people as before

* check if there are any premades that were split

* for each premade that was split and is missing X people, check if it is possible remove the bottom X people from the group and reinsert them into the queue (note that there are no people between the admitted members of the premade and the omitted members of the premade, since the entire premade has the same sorting key in the priority queue).

* if such a switch is impossible (for example, because there are 2 healers from the premade missing and the only free non-premade spots are for dps), then pick more people from the queue to provide reserve spots. If it is possible to replace the addmited members of one of the premades with freelancers to find a solution, do it.

* if there are not enough people in the queue to find a solution, cache the number of missing roles and do not run the algorithm again until the queue is properly filled

 

For example, say that a premade with 3 healers, 4 dps and 2 tanks queues and another premade with 2 healers, 1 tank and 8 dps queues. Say there are 2 freelance healers, 4 freelance dps and 1 freelance tank in the queue. Say that the 2 freelance healers queued first, then the first premade, then the other premade, then the other freelancers. We pop 4 healers (2 from premade A), 10 dps (4 from premade A, 6 from premade B) and 2 tanks (from premade A).

 

Now, it is possible to get premade A in full by replacing the one freelance healer. So now the entire premade A is in, but premade B only has 6 dps in.

 

Since it is not possible to remove 2 dps, 1 tank and 2 healers to make place for the second premade, we add reserves. We have 2 success scenarios - either we get 6 freelance dps in the queue and we remove premade B or we get 2 freelance dps, 1 tank and 2 healers and we remove premade A. Since the second scenario is obtainable, we pop the freelancers and reinsert premade A into the queue. All of this is really cheap because, again, the operation of removing a queue element is cheap.

 

So, the algorithm that addresses both problems (premades and ignores) is still at worst O(n^2) (because of the ignores).

[Ilintar]

I would highly doubt they would have a O(n!) or even O(n^2) , both would indicate an exponential search (latter being embedded loops).

 

Just a technicality, but "exponential search" means that something is at least of complexity 2^n (so the variable is actually in the exponent). O(n^2) is polynomial and not exponential complexity. Factorial complexity is also not technically exponential complexity - it's a higher class still (a factorial is somewhere around (n/2)^(n/2)).

[TUXs]

Number of DPS in 16 man is 10. Number of tanks is 2.

 

This is the reason behind going to 16 GF: You can take more DPS than 2 8 man Ops and need half the amount of tanks.

I can't even get a HM FP to pop in GF...that only requires ONE tank...there were a number of reasons that 16man should have been their ONLY goal. Dropping it to 8 makes it worthless imo.

[Kantaso]

Wow some deep stuff here. Edited June 13, 2014 by Kantaso

[DOHboy]

Just a technicality, but "exponential search" means that something is at least of complexity 2^n (so the variable is actually in the exponent). O(n^2) is polynomial and not exponential complexity. Factorial complexity is also not technically exponential complexity - it's a higher class still (a factorial is somewhere around (n/2)^(n/2)).

 

yes i know, bit rusty on my "technicality' for BigO and BigTheta notation, sure it was a nit pick but probably needed correction. The fact that we're dropping Big O notation and expecting "average people" to understand is surprising. Lucky you didn't get a WTH is "O" and "n!" some probably can't even do factorials let alone BigO notation.

 

we could start doing log (n^2) or nlog(n) and confuse them even more

[BuriDogshin]

There is another complexity not mentioned: people who queue for two roles (tank/damage, heal/damage).

 

So, I have a Jug set up to tank or DPS. My wife has an Operative who can heal/DPS, and we have a friend with Sorc with full Heal and DPS gears, and a guild mate with another well geared Jug tank/DPS. We each have ignore lists. We queue for 16-man op as a premade: 2 potential tanks, 2 potential heals, 4 potential DPS. Please match us to a group.

 

You really want to make the best use of those tanks and healers so the queue pops faster, right? But if there are group forming in the queue that needs one tank, or one healer, or one of each, do you put this premade in that group? Or do you wait for a group that needs two tanks, if your tank population is low? And if you could complete a group by adding this premade to it but only if you kick one or two players already allocated to the group (because they have a member of the premade on ignore), do you do that? Are you even checking for that?

 

And you are doing it in an environment where people are entering and leaving the queue all the time, and where individuals in the queue can also be queue for a WZ as well.

 

So this problem may not be as simple as you might first think - sort of like the knapsack problem:

Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

...

The knapsack problem is interesting from the perspective of computer science for many reasons:

• The decision problem form of the knapsack problem (Can a value of at least V be achieved without exceeding the weight W?) is NP-complete, thus there is no possible algorithm both correct and fast (polynomial-time) on all cases, unless P=NP.
  
• While the decision problem is NP-complete, the optimization problem is NP-hard, its resolution is at least as difficult as the decision problem, and there is no known polynomial algorithm which can tell, given a solution, whether it is optimal (which would mean that there is no solution with a larger, thus solving the decision problem NP-complete).
  

[DawnAskham]

While I love reading some of the arm chair comments about how the GF queue handles complexity, as a paying customer the only thing I care about is does it work reasonably well.

 

And sadly the answer in no when compared to queue systems already in place in other games that can handle queuing for events that require more than 16 players while still facing similar complexity constraints such as players queuing for multiple events, with multiple roles, as individual and as groups, and with ignore lists.

 

These other queue systems also handle the load of all players queuing from within a region (e.g. North America) versus a small subset (single server), provide estimated wait times, provide visibility into roles filled / not-filled, and can keep players queued for multiple events even after finding a match for one event.

 

Basically Bioware needs to hire the talent required to make GF work at least as well as what is already live in other games (and thus is certainly possible to achieve), and stop making excuses for their failures.

Edited June 13, 2014 by DawnAskham

[BuriDogshin]

While I love reading some of the arm chair comments about how the GF queue handles complexity, as a paying customer the only thing I care about is does it work reasonably well.

This is a thread full of CompSci geeks having fun discussing the problem of group-forming from the stand point of potential algorithms and their computational complexity. It is not "armchair," because the complexity of the problem depends entirely on the problem itself, not on BW, the SWTOR engine, the competency of the coders, or anything else. It's mathematics. You can prove things bout this stuff, rigorously, if you want to go to the effort.

 

Noone can know what "work reasonably well" is until they understand the issues being discussed here. Expecting fast simple solutions to inherently hard problems is not "reasonable."

 

Not your cup of tea? Well, you have already voiced essentially the same complaint in another thread, right?

[Bstr]

There is another complexity not mentioned: people who queue for two roles (tank/damage, heal/damage).

 

I answered it earlier in the thread with a much easier way of doing it (and how the game seems to behave for FP GF) and the OP made a comment on how he had a different way of doing this type of matching.

 

Mine was that any people that queue for two roles are primarily tank / heal. If there are already enough of those in the group, then go DPS.

 

For example, a tank/DPS joins a regular FP GF queue and can get an instant pop. 2 of the other players are a healer and a DPS. If the third is a tank, then the tank/DPS is a DPS. If they are a DPS (more likely scenario,) then the tank/DPS is a tank.

 

Another example: 4 players get into the queue: 2 Tank/DPS and 2 heal/DPS. The first Tank/DPS in the queue is the tank; the second falls back to DPS. The first healer in the queue is a healer; the second falls back to DPS.

[Joesixxpack]

While I love reading some of the arm chair comments about how the GF queue handles complexity, as a paying customer the only thing I care about is does it work reasonably well.

 

And sadly the answer in no when compared to queue systems already in place in other games that can handle queuing for events that require more than 16 players while still facing similar complexity constraints such as players queuing for multiple events, with multiple roles, as individual and as groups, and with ignore lists.

 

These other queue systems also handle the load of all players queuing from within a region (e.g. North America) versus a small subset (single server), provide estimated wait times, provide visibility into roles filled / not-filled, and can keep players queued for multiple events even after finding a match for one event.

 

Basically Bioware needs to hire the talent required to make GF work at least as well as what is already live in other games (and thus is certainly possible to achieve), and stop making excuses for their failures.

 

Good luck the folks you're talking to haven't a clue about other aspects of organizational management, or managing customer expectations and experiences in general, and will reply from their view looking through a toilet paper roll tube. Somehow they think such a one-dimensional view is all-encompassing. Keep pressing though if you're bored and find broken record replies amusing.

[BuriDogshin]

Another example: 4 players get into the queue: 2 Tank/DPS and 2 heal/DPS. The first Tank/DPS in the queue is the tank; the second falls back to DPS. The first healer in the queue is a healer; the second falls back to DPS.

That heuristic simplifies things, but then your 4-person premade won't be able to complete a group that needs 2 tanks and/or two more heals.

 

Plus, pugs with both tanks in the same guild (or at least the same mumble/ts/raidcall) tend to do better, all else being equal, so it might be better to take a premade with two (or more) potential tanks and make them both tanks.

 

Lots of issue to consider.

[StrikePrice]

Many games are scaling out using the cloud these days. Might want to look into that.

[BuriDogshin]

Many games are scaling out using the cloud these days. Might want to look into that.

Physically remote storage and computation has higher latency, which is not something a real-time MMO wants.

[Bstr]

That heuristic simplifies things, but then your 4-person premade won't be able to complete a group that needs 2 tanks and/or two more heals.

 

Plus, pugs with both tanks in the same guild (or at least the same mumble/ts/raidcall) tend to do better, all else being equal, so it might be better to take a premade with two (or more) potential tanks and make them both tanks.

 

Lots of issue to consider.

 

Note that my example was for either a premade or single players queuing for FP GF, which only requires 4 players.

 

If either group was the last 1 or 4 of a 16 man GF:

 

For the first if there are 2 tanks, the tank / DPS is a DPS. If not, he is a tank.

 

For the second:

• Group needs 2 tanks, 2 heals: This group becomes 2 tanks and 2 heals.
  
• Group needs 2 tanks, 1 DPS, and 1 heals: Tank/DPS become tanks. First heal/DPS that queues (or some other methods of determining first if both heal/DPS queued together) becomes a healer; the second a DPS.
  
• Group needs 4 DPS: All are DPS
  

 

If a premade cannot pop all people in the premade, then it waits. People already in progress for a FP or Op are considered a premade, but they are always before those without any progress.

 

Not that much to consider if you do not factor in ignores. For ignores, if A ignores B, then only take the first player that queued. If A ignored B who ignored C, then only take the first that queued. If it was B, then A and C does not join. If not B, then A and C can join.

 

The queueing algorithm can be simple and optimal. I believe that this was not the problem with the 16 man GF. Something else was the problem.

Edited June 13, 2014 by Bstr

[Bstr]

Many games are scaling out using the cloud these days. Might want to look into that.

 

"Scaling out to the cloud" just means that they are allowing someone else to build, maintain, and run their servers instead of doing it in-house. You still have the same problems, but new ones with not having absolute control over your server. Many games are doing this because it is cheaper for small studios to do, not because it gives them more power / better performance.

[StrikePrice]

Physically remote storage and computation has higher latency, which is not something a real-time MMO wants.

Matchmaking is not real time. Latency is not relevant in this calculation. They could spin up 10,000 VMs on AWS or Azure to do all their matchmaking computation if they wanted to.

 

"Scaling out to the cloud" just means that they are allowing someone else to build, maintain, and run their servers instead of doing it in-house. You still have the same problems, but new ones with not having absolute control over your server. Many games are doing this because it is cheaper for small studios to do, not because it gives them more power / better performance.

No, it just means there is virtually unlimited, elastic compute capacity. Titanfall, for example, used over 100,000 VMs on it's launch day. They could spin up VMs when the need to do a lot of match making (primetime) then spin them down.