A couple of friends and me are working on a small online game, in which 1 player fights another player and a winner is decided.
I have a queuing problem, but to understand it, I have to first explain what is happening:

Now we wanted to make the players match equal opponents and create rankings. To create fair match ups and create rankings we use the glicko v1 system, which is described here:
http://math.bu.edu/people/mg/glicko/glicko.doc/glicko.html (and yes we are aware of the limits of this system in means of judging skill correctly.)
Here is a small summary of how it works:
new players will have a rating of 1500
if the player wins a match the rating will rise.
if the player looses a match the rating will drop.
after several matches players have a normal distributed rating in a range from 0 to 3000.


Match ups will happen dependent on each players rating.

The first implementation looks like this in psuedo code (it's missing some special cases, but the overall logic should be clear):
We have a list called QueuedTeams, in which every team that wants to join a fight is enlisted. The queuing system is called whenever a team is enlisted in QueuedTeams.

ratingDifferenceLimit = 150;for(Team t1 in QueuedTeams){   for(Team t2 in QueuedTeams)   {       if(abs(t1->rating - t2->rating) <= ratingDifferenceLimit)       {             MatchUp(t1, t2);             QueuedTeams->RemoveTeams(t1,t2);       }   }}

We ran some tests and this works very well, as long as you have enough teams througout ratings. If you only have a small amount of teams, they won't get match ups at high ratings or have to wait really long. The simplest way to get match ups would be to increase the ratingDifferenceLimit. But this makes matches unfairer, even if there should be enough players for a close match-up. Basically, I rather want a dynamic system, which queues player rather according to their closest possible rating.

In total it's a problem dependent on 3 variables:
Minimizing rating difference.
Minimizing queuing time.
Maximizing the amounts of match-ups.

Here comes the first question: Are there articles on this problem somewhere on the net? What do I have to look for? Are there books which describe these problems? (Since I did not find anything on the problem using google, I looked through different queuing problems, for example queuing processes, but all the systems i could find do not need a match up.)


PS.: Please move this thread, if this should be the inappropriate forum.

[Edited by - myro on October 27, 2010 2:42:12 PM]

"It's lonely at the top." - Sorry, couldn't resist.

I don't know of any articles on match making with an unevenly distributed set, just a thought I had while reading the post that may inspire you to a solution.

An idea would be to use time in the queue to decay a player's actual rating to a virtual rating. The longer they are in the queue the more likely they will be matched up with whomever is the best player below them. virtual ratings would be compared to actual ratings when determining a match. At the end of the match the participants ratings are adjusted by the amount of time based decay that occurred to make the match occur. Meaning that player A with a rating of 2655, who is matched up with player B whose rating is 2044 would only gain maybe a single point for a win, while player B would only lose a single point. Conversely, if player A loses to Player B, then Player A loses the same amount of points as if they had lost a match at there level, and player B gains points equal to them having won a match at there level.

The upside of this is that top ranked players would eventually be queued against someone. The downside is that it would be for little gain.

Something else you may want to take into consideration when match making is the time other players have been in the queue. Simply generating a set of matches based on the threshold, then choosing the player in that set with the longest queue time.

--Z

The problem is more complex than perhaps you realise. If you give people the ideal match then there's a risk of giving them the same few opponents over and over again, when you'd probably find better gameplay in widening the opponent pool even if the rating difference is slightly bigger. It's hard to know how 'fair' this is in general terms because obviously the rating system is entirely dependent on the type of game. If the game was a simple 'coin flip' then a difference of 1000 is not really unfair, but if it is chess then it's very unfair.

I wouldn't change too much. I'd ensure that I was iterating over the teams in order from the one that has been waiting the longest to the one that has joined most recently. This means the ones who've waited longest get a chance to match up first. Then, I would simply add time_in_queue (in seconds) to ratingDifferenceLimit when calculating the match threshold so that people who have waited longest are matched up more leniently than those who have just joined. You might want to scale up the time_in_queue value by a factor of 2 or 3 so that after a minute or so the matching is very lenient, but it depends on how you want to balance it. Presumably you will want to clamp this to a maximum if you don't ever want to see the 2800-scoring teams playing the 200-scoring teams.

we were discussing the problem as well and yes, we realized that it's rather a complex problem...

First we have to note that an increase of the Rating Difference above 500 wouldn't make sense, since the glicko v1 system will not reward "fair" then. For example the higher winning team would get 0 for a win and the chance of winning for the lower team would drop below 3% (This is the "QQ i am getting farmed by some super pro nolifers hardcore gamers" case.)

We had 3 suggestions:

1. suggestion:
Increasing the Rating Difference Limit according to the time queued. This is basically what you 2 suggested as well. Limiting it at 500, no further increase after.

I, for myself, did not like the idea that much. Because during the increase time, there could have been closer match ups:
For example:
Team0 at 2300 queues
Team1 at 2000 queues

after 1min both teams rating difference limit will be increased by 100.

Team2 at 2050 queues
Team3 at 1900 queues

=> Team1 and Team2 get matched up.

after several more increases Team0 and Team3 get matched up.
Basically, the system does not prefer better matching teams.

2. suggestion:
We do not start matching players immediately when they enqueue, but after an arbitrary discrete time frame. For example 2mins.

Thus the matching system will only be called every 2mins.

Then the search for an opponent would work like this:
We select the first team.
Then we make a sorted list with possible opponents according to their rating difference (from lowest to highest). We select one team from the opponents list randomly, but the team with lowest rating difference has a higher probability. The biggest rating difference team has the lowest probability. The teams in between are linear less probable.

=> This system would prefer closer match ups, if they are possible. But it would require an unnecessary waiting time to have a certain amount of opponent teams in the list, which we could base our decision on. The waiting time is required, because otherwise teams will always match up immediately and practically use always 500 limit.


3. suggestion:
We implement a "controlling" system for the rating difference.
The system would contain for each bracket the highest possible rating difference:
0-500
500-1000
....

This controlling system will be on a fixed timer, 1 min for example.
It will count the matches taking place in each bracket. If for example 6 games happen in a bracket, it will divide this bracket into 2 brackets. Let's say 500-1000 had 6 games. The brackets would then look like this:
0-500
500-750
750-1000
1000-1500

That way we getter "fairer" match ups, if matches occur in a certain bracket.
(The surrounding brackets can only choose teams from the nearest bracket as well. aka 499vs990 cannot happen.)

After a certain amount of time frames passing (i.e. 2) with < 3 matches the bracket will be doubled again: Let's say in the 500-750 bracket is 1 match and 1 in the 750-1000 bracket.
Thus, the rating range there will get doubled again. The brackets would again look like this:
0-500
500-1000
1000-1500

I would be interested in your opinions on these 3 suggestions. Atm the last suggestion is our latest idea, thus we haven't thought of trouble with it yet.

PS.: Skill should matter, maybe not as much as in chess, but it should matter.

Instead of looking at max rating differences, you should look at percentiles, and match players who are with X% of each other. In effect this is really your solution 3 where the rating difference is determined automatically, based on the distribution of ratings.
In case what I am saying is unclear, for example, a player who is in the top 10% of ratings should only be matched with a player who is between top 5% and 15% of ratings. You could force a redraw (or a few) if you match up players who played against each other in the last X matches.

Quote:Original post by BTownTKD
Why not come up with a "weight" system, instead of relying solely on "player rating."

For any given player looking for a match, every other potential player would have a "weight," determining the likelyhood of the 2 players being paired up.

"Player ratings" would effect the weight the most, so players with a large rating difference will have (virtually) no chance of playing each other, and the likelihood increasing as player skill-levels become closer. However, other things will effect the weight to a lesser degree;

• "wait time" - how long a player has been waiting for a match.


• "recent-ness" of a partner-pairing - How recently have these 2 players been paired together? This effect will slowly dissipate after a few matches with other players.

This would ideally create kind of a bell curve, with players of identical skill levels being paired up most often, with the likelihood decreasing quickly as skill-levels differ.

The thing is, that I don't have a list of players that I could base my decision on, without an arbitrary waiting time for the whole system. Let's assume I have a weight system:
Player0 at 0 Rating
Player1 at 1000 Rating
=> Match (only 2 teams in the list, which means their probability to match is 1)
The same will happen for every match-up. There will be no decision made, but teams will always match immediately every opponent.
The only way to make a decision here, is by making the whole system wait for an arbitrary time frame, to have a list of players queuing and then make a proper decision. This is somewhat my suggestion 2 since I will make there a probability distribution, which is in this case only weighted on rating difference.

Quote:Original post by hplus0603
My observation: In general, the way you do these matches is very similar to a broad-phase collision test: You want to find overlaps among ranges of values. You could view the allowable match set as a volume in a multi-dimensional parameter space, and you want to find all intersections within that space. Thus, I would imagine that various broad-phase algorithms would work well, assuming you can adopt them to having different types among different axes.

I would probably start with sweep-and-prune. Put all the teams on a single axis (the score). Sort the axis. Then walk along that axis, collecting teams into a "potential match pool" as you enter their "lower" range, and removing them from the pool as you leave their "upper" range. I would probably start by trying to find the best possible match for the team as it's being removed from the match pool, by examining each other team in the pool at the time.

I would increase the "size" of the "match shape" by age in the queue. You could run the algorithm once a second, say, and remove any matches made during each run from the list of potential candidates.

If I understood this idea correctly (sorry, I am not that familiar with collision detection.), this idea would also require an arbitrary time frame, to create a list of players and then make a decision based on that list of players. Thus, I would need to wait for several players joining (the time frame can be reduced, by calling the system after a certain amount of players are in the list as well.). The overall idea to use a "collision system" to find matches, if I have a player list is pretty nice though.

If I look at this problem in a more abstract way:
I can only make a proper decision, if I have a list of players I can choose from (aka arbitrary time frame) or if I have a "game history" I can base my decision on. (The case of simply increasing the rating difference with a timer is ignored here, since a decision based on that is simply not a good decision and leaves expert and "noob" players at very long waiting times.)

The idea of an arbitrary time frame(i.e. 2 min) would increase the waiting times for several cases quite a lot, but somewhat average it over all ratings:
Player0 at 1500 rating queues
Player1 at 1500 rating queues

They now have an average waiting of 1 min, which is really unnecessary.

The "game history" idea (my suggestion 3), would base it's decision on games that previously took place and shape the rating differences accordingly. It's based on the idea that usually players will not only queue once, but several times in a row and thus they will be matching at a similar rating for quite a while.

Quote:Original post by Hazerider
Instead of looking at max rating differences, you should look at percentiles, and match players who are with X% of each other. In effect this is really your solution 3 where the rating difference is determined automatically, based on the distribution of ratings.
In case what I am saying is unclear, for example, a player who is in the top 10% of ratings should only be matched with a player who is between top 5% and 15% of ratings. You could force a redraw (or a few) if you match up players who played against each other in the last X matches.

Do you have other ideas on how to "transfer" the percentile idea into a "game history"? I tried looking at it from the percentile idea itself, but I ran into several dead ends like that. If I look at it from the "suggestion 3", I run into a very complex implementation.


PS.: Thanks for all the ideas presented. I think it's somewhat strange that there are no articles about this topic, since this should be a very common problem, solved in several professional games.

PPS.: The more I think about this problem, it seems to get more and more complex....

These problems have been sort of solved in professional games, just no one seems to write about them. World of Warcraft has had it's arena match making system modified multiple times. It operates very similarly to what you are after ( matching teams based on ratings ). They may not publish is though because they don't want players to know the inner workings so they can't game the system.

Another possibility to consider that hasn't been brought up is the idea of applying a handicap to the better player ( or a buff to the less skilled player ) in an attempt to even the match through altered game mechanics. This may not apply to your game mechanics, and you would want to be upfront about it in the match making.

--Z