Actually on the topic of improvements, I think you still use a greedy algo for pairing based on the old GitHub code on Deadman1. If that's the case, I wrote a small utility library called pair (you can find it on PyPI and the source/basic documentation on my GitHub). You should be able to integrate it in seconds. Also lets you do more interesting things with non-binary template preferences. Let me know if you're interested in integrating it and would like help setting up. It's got full test coverage but the codebase is not great on style or documentation (beyond Python docstrings) so I can't guarantee the absence of bugs but it's pretty small and easy to fix when things go wrong.

Just guarantees optimal pairings and template assignments at every batch (although since combinatorial optimization is generally NP-hard for >2 dimensions, I can't guarantee both at once) so you can pair your teams better system-wide.

Edited 4/14/2017 06:27:43

Can you please explain hiw the pairing works and why you think it's the "most optimal way" to do pairings?

I used to play a game online where ranking was as follows :

- everybody starts at 1000
- wins bring between 1 and 6 points depending on your current ranking and on rating of your opponent
- losses cost between -6 and -1 points depending on the same criterias
- it seems points won or lost doesn't just look at rating differential, but look first at your rating, to put you in a bracket of possible points to win or lose for the game, then look at your opponent rating to assign the high or low margin in the bracket. For example, I remember that top player would make either 1 or 2 points systematically (bracket), and it would be 1 or 2 depending on your opponent's ranking (1 if opponent is too far behind, 2 if he has a decent ranking)
- Also, in every game, sum of points won and lost cancel each other (if team A wins 3, team B loses 3)
- And sum of possible points won (or lost) by both teams equal 7 (or -7) : in a game where top player can make either 1 or 2 points, opponent can make either 6 or 5 points.
- Every 30 days (or was it 90? forgot) rankings would reset to 1000.
- there was an inflation of up to 2000 / 2200 for top player every season, and it didnt take too long to top the league if you missed the start with this rating system (so yeah was probably more 90 than 30 days season).
- Oh and each game would notify you at the end how much points both teams made or lost (transparency), and ranking doesn't move over time, so is relevant at any time you look at it.

All that to say that this rating was awesome and was making things very addictive, which you may need. Well, this may not be too far from your current rating system.

Is that a specific rating system which has a name to your knowledge ?

Edited 4/14/2017 10:04:33

@mod: Whoops, thanks for bringing that up.

For assigning templates, the library treats the task as an isomorphism of the (linear) assignment problem. E.g., you have x players and y templates and costs for each combination (as well as some combinations that are disallowed). You can use one of a class of well-known algorithms to generate assignments such that the total cost is minimized. I modified an O(n**3) implementation of the classic algorithm for this problem (Kuhn-Munkres) to do this because it was the easiest to modify to support disallowed assignments (vetos in this ladder). You're able to mathematically guarantee that, at each batch, the total (sum) cost is minimized.

It's only super-worthwhile to use the templates part, though, if you're also interested in giving people more flexibility when it comes to expressing template preferences- but I explained it first since it helps explain the player pairing.

Pairing uses a similar principle, except you're working on connections within one group instead of connections between 2. So while template assignment is analogous to running a taxi company, getting 3 calls, having 3 taxis at different locations such that they don't have the same distance to each customer, and figuring out which taxi to send to which customer such that timeliness (or total customer satisfaction) is best maintained; player pairing is like running a student dormitory and trying to build roommate pairs such that, say, the total happiness of all these students over the year is maximized.

So we have a single graph (not bipartite) where each player is connected to any players that they're allowed to have games with and each of these edges has a score. Using NetworkX's implementation of Edmonds' Blossom algorithm and some other network matching algorithms (suggested to me by Derfellios), we're able to find the player pairings that maximize the total score (and don't match players that you don't want to get matched- like players they just played).

You get to assign the weights (for templates) or supply a scoring function (for players/teams) so it doesn't have to be strictly linear- you can make the scores you supply exponential, for example, if you prefer matchings that (based on Elo parity/quality calculations) are 2x as good, 4x as much.

But at the end of pairing and assignments, we're able to extend guarantees that whatever you chose was, given the scores/weights you supplied, the optimal set of assignments/pairings within the space you provided. If you're still using a greedy algorithm to pair teams, you likely cannot extend that same guarantee and will sometimes perhaps even have cases where your system either had to give up some pairings or create some bad pairings when you didn't actually need to do so- there's certainly at least a wide space of conceivable edge cases where a greedy algorithm only yields terrible results and just breaks down. You might also find this pairing guarantee useful for the more interesting problem space of the Team Ladder- pairing 2 players, then pairing 2 teams, and assigning each resulting matching to a template is exactly within the sweet spot of this utility library.

(Also, like I said, this whole space of algorithms tends to break down after 2 dimensions, so I do not offer any guarantees if you're grouping teams for FFA or building teams of 3 or more players using software. You *can* secure those guarantees, though, but unless you're familiar with combinatorial optimization and can find algorithms that retain polynomial time and space complexity as dimensions increase, your solution will likely be O(n!), O(n**n), or something else that leaves you wondering why you got the solution in .2s for 10 teams but your algorithm has yet to stop running for 11.)

@knyte; to sum up, you are saying Motd is using a greedy algorithm for pairings and there is a better way of doing it.

@rouxburg: If MotD is using a greedy algorithm and wants to instead have optimization guarantees, then he can simply install (via pip) and import the pair library (https://pypi.python.org/pypi/pair) and add some helper functions to use its pair_teams, pair_players, and assign_templates functions.

Edited 4/15/2017 01:25:40

@knyte

Actually on the topic of improvements, I think you still use a greedy algo for pairing based on the old GitHub code on Deadman1. If that's the case, I wrote a small utility library called pair (you can find it on PyPI and the source/basic documentation on my GitHub). You should be able to integrate it in seconds. Also lets you do more interesting things with non-binary template preferences.

But at the end of pairing and assignments, we're able to extend guarantees that whatever you chose was, given the scores/weights you supplied, the optimal set of assignments/pairings within the space you provided. If you're still using a greedy algorithm to pair teams, you likely cannot extend that same guarantee and will sometimes perhaps even have cases where your system either had to give up some pairings or create some bad pairings when you didn't actually need to do so- there's certainly at least a wide space of conceivable edge cases where a greedy algorithm only yields terrible results and just breaks down. You might also find this pairing guarantee useful for the more interesting problem space of the Team Ladder- pairing 2 players, then pairing 2 teams, and assigning each resulting matching to a template is exactly within the sweet spot of this utility library.

I think this would have more application in cases like the seasonal ladder where you are trying to create a lot more pairings at a time. An update cycle on MDL has an average of 2 games finished(max 4-5). A greedy approach works quite well as two opponents can face each other once in 5 days(so the combinations disallowed are very few). Once a pair is picked, there is always a large pool of permissible templates( 51 - 2 * max veto count - 2 * last 5 templates = 27 in the worst case). At this point, picking a template at random is the best option in order to ensure players can experience all the templates with equal probability.

If we have 4-6 players who need to be allotted a game in a cycle, and make early pairings such that some later players cannot get a game on that cycle, it is still not a big problem. The next update cycle will run in 2 hours and will mostly give a legitimate pair for the ignored player.

This is just my gut feeling here. I'll implement some telemetry to figure out how many players are ignored in a cycle on an average and let that guide my ultimate decision. Looks like a neat library.

Edited 4/15/2017 05:57:13

@Mike

I used to play a game online where ranking was as follows :
- everybody starts at 1000

Everyone starts with a rating of 1500 on MDL.

wins bring between 1 and 6 points depending on your current ranking and on rating of your opponent

Wins bring between 1 and 32 points depending on your current ranking and on rating of your opponent on MDL

losses cost between -6 and -1 points depending on the same criterias

losses cost between -32 and -1 points depending on the same criterion.

it seems points won or lost doesn't just look at rating differential, but look first at your rating, to put you in a bracket of possible points to win or lose for the game, then look at your opponent rating to assign the high or low margin in the bracket. For example, I remember that top player would make either 1 or 2 points systematically (bracket), and it would be 1 or 2 depending on your opponent's ranking (1 if opponent is too far behind, 2 if he has a decent ranking)

The top players usually make about 3-4 points on a win, and lose about 28-29. Elo takes care of how that number is determined.

Also, in every game, sum of points won and lost cancel each other (if team A wins 3, team B loses 3)

True on MDL as well(subject to rounding).

And sum of possible points won (or lost) by both teams equal 7 (or -7) : in a game where top player can make either 1 or 2 points, opponent can make either 6 or 5 points.

True on MDL as well(subject to rounding).

Every 30 days (or was it 90? forgot) rankings would reset to 1000.

This is handled a bit differently on MDL. I don't think it is a rewarding experience to see something you have worked hard for, get wiped every 30 days. To keep ratings relevant to the present, we have the concept of game expiration instead. Any game older than 5 months will not impact ratings. This is a concept which works well as proven on WL ladders.

- there was an inflation of up to 2000 / 2200 for top player every season, and it didnt take too long to top the league if you missed the start with this rating system (so yeah was probably more 90 than 30 days season).

MDL's rating system can provide similar guarantees. This player cracked 1700+ with just 20 games - http://md-ladder.cloudapp.net/player?playerId=611489923

Oh and each game would notify you at the end how much points both teams made or lost (transparency), and ranking doesn't move over time, so is relevant at any time you look at it.

This is a bit tricky as the "worth" of a game will always change given our concept of game expiration. A game worth 3 points to me today may be worth 10 points two months later if some of my older games expire. Therefore it is hard to show such a number. However if you track the rating charts, it is usually quite clear how much you gain or lose. You can also use this site(http://www.3dkingdoms.com/chess/elo.htm) to predict the impact of a game. Use k=32 and the ratings of the players at game creation time.

All that to say that this rating was awesome and was making things very addictive, which you may need. Well, this may not be too far from your current rating system.

Is that a specific rating system which has a name to your knowledge ?

You have described something very similar to the Elo rating. In short, MDL has everything your game had.

Edited 4/15/2017 05:58:28

Added a new leaderboard page which contains the following:

• Players with most all-time games
  
• Players with most unexpired games.
  
• Players with most wins
  
• Players with best win rate
  
• Players who have spent the longest consecutive days ranked as #1 on MDL
  
• Players who have spent the longest consecutive days ranked in the top 5 on MDL
  
• Players who have spent the longest consecutive days ranked in the top 10 on MDL
  
• Players who have spent the longest consecutive days ranked on MDL
  
• Players with the longest consecutive win streak
  
• Players with the least number of vetoed templates

If you spot any errors in the data or have any suggestions, let me know. I plan to add more charts and statistics in the next update. I'll also introduce "achievements" which can be earned on MDL and will be listed on your MDL profile.

Some of these leaderboards require continuity on the ladder, so hopefully it helps keep people engaged!



Edited 4/15/2017 12:40:18

Wohooo fucking awesome!!

Kezzo +1 :D

And MotD, I think you forgot to highlight something in the picture.
As I know, you are the first player who break the 1900 limit :O
(ah, and forgot to create this type of leaderboard (highest ranks) too where I would check this ;) )
Congrats for this 1900+ record!

And congrats for these very cool leaderboards!
I adore this type of statisctics a lot what you made now :D

This is when you own the database (and own the necessary programming skills), make new statistics very very easy (and automatic refreshing!). Compared to my AWP World Tour possibilities (everything manually...) like a spaceship vs. a dinghy :O
I wish I had more time... (to learn programming and making an own CLOT for the Tour)

How the hell you have so many times that you can create "fucking awesome" stuff like MDL (btw, why not MTL (multi-template ladder) its name as Ƨillynamenace asked? :D ) and the Clan League, plus besides those (!), you can play at a very high level and reach first position in MDL?! :O

Browsing these new leaderboards I realized something: MoD isn't a human :D :P
Not only his brutal stats in the MDL but in the Tour as well :O
And I can see his name approx. in EVERY competitive events :O
He must be a competitor machine :D

Thanks for clarification MotD :), also this is quality addition. No way to add a "show all" button to go further top 10's on those stats ?

@MotD re:pair- Good point re:randomization. It's still random from the perspective of players but since the templates and players are ordered using the hashes of their IDs, there are some edge cases where things can go very wrong (if you repeatedly have to create N assignments, where N is the number of templates, and people's conflicts and vetos don't change between iterations). I'll add in some ID randomization into the mix.

(EDIT: added, as well as some other improvements to assigning templates. I'll probably make a separate Programming forum thread about it after the next release.)

Also, Leaderboard page is a nice feature. :P I knew y'all were gonna add something major before the 6mo anniversary.

Edited 4/15/2017 19:37:15

I think you forgot to highlight something in the picture.
As I know, you are the first player who break the 1900 limit :O
(ah, and forgot to create this type of leaderboard (highest ranks) too where I would check this ;) )

Yes. I have a work item for adding highest ratings achieved on MDL.

I'm looking to add most of the items on this list. If you have any other suggestions, let me know!
https://goo.gl/O7AdZp

No way to add a "show all" button to go further top 10's on those stats ?

I made a conscious decision to display only top 10. This will encourage people to break into the top 10 in respective categories. I will add all these stats on the player profiles as well so that you can keep track of what you need to get into the top 10.

Edited 4/15/2017 19:39:17

Or they'll give up bothering with any of the awesome new stats because they aren't anywhere close to competing for a top 10 spot in any tracked category. It would be a much greater benefit to a much larger number of players to include access to complete rankings for these categories.

Minor Bug:

The Leaderboard for "Least Vetoed" shows 1, when in fact it should be 0. (But hey, at least I topped a leaderboard!)

@Dogberry,

You can see more then top10, by clicking "next". It is fine to show only top 10 on that main page. Through, a Show All will be needed if the ladder reaches the number of members it deserves ;)

When I posted my message, there were no next or previous buttons. Additionally his post seems to clearly indicate that only information on the Top 10 would be available. However, I did just receive confirmation from another source that more than just the top 10 would be searchable, so my concern is moot.

Since you replied, I guess I won't be editing my post after all :-P

@Tbest

Minor Bug:

The Leaderboard for "Least Vetoed" shows 1, when in fact it should be 0.

Thanks for the catch. I was making another incorrect assumption as well which lead to incorrect data. This should be fixed now.

@Dogberry

Or they'll give up bothering with any of the awesome new stats because they aren't anywhere close to competing for a top 10 spot in any tracked category. It would be a much greater benefit to a much larger number of players to include access to complete rankings for these categories.

Fair enough. The leaderboards will now show a larger number of players. However, I imposed certain restrictions to feature in a leaderboard. This is to make the standings more meaningful.

Restrictions:

• Longest Win Streak requires a minimum of a three games.
  
• Least Templates Vetoed requires you to be active on the ladder.(Or people will cancel all their vetoes and leave the ladder.)
  
• Requires a min of 20 total games.
  
  • Most Unexpired Games
    
  • Most Games Played
    
  • Most Wins
    
  • Best Win Rate

Edited 4/16/2017 03:42:30

People near/close/middling might be encouraged by seeing their stats approaching the top 10. What about the people near the bottom? Not everyone will care, but I can't think they would be encouraged.

If you don't show it as a top 10, what if it was something amounting to around 2/5 or 1/3 of the active base? Obviously, you could also have an all-time section.

(at the risk of looking like an idiot, I haven't been keeping up with this thread. I'm only dropping comments)