The Leaguevine Blog

The Leaguevine Blog entries labeled with the tag 'features'

Easily viewing your Twitter history

Posted on August 16th, 2011 by Mark "Spike" Liu
We've gotten some requests to do some more interesting things with the all of the Twitter data we've collected. I just checked, and we now have over 50,000 tweets in our database to work with! It's about time we organized these tremendous updates better.

As of today, when you click on a twitter link within Leaguevine, you will be taken to a brand new Leaguevine page just for that Twitter user. You can view what teams that account is associated with, view all of the games that this account gave updates for, and when you click on those links, you can get a timeline of only the relevant tweets for that game. Here's an example page of what I'm talking about:

With this new functionality, it is even easier to go back in time and look back at the point by point history of your favorite games. If you click on the link to look at a single game's history, you get the full Twitter feed for that whole game.

Please keep the suggestions coming!

Swiss Tournament Scheduling: Leaguevine's New Algorithm

Posted on August 10th, 2011 by Mark "Spike" Liu

Mark_at_wisconsin_swiss

This post is geared towards those of you who are curious about Swiss style tournaments, and want to learn more about Leaguevine's new algorithm. For even more information on the swiss format, Christian from the Windmill Windup has put together a great wiki page.

For the recent Madison Swiss Tournament, the tournament director Chris Olig decided to use Leaguevine exclusively for the score reporting. A swiss format is totally different from a regular Ultimate tournament, and thus the regular pools and bracket scheduling techniques do not apply. Nonetheless, we decided to build a swiss tournament generator into Leaguevine. We used an innovative approach to build this scheduler, so I thought I'd share it here.

If you do a simple google search or look through one of several lists of swiss tournament scheduling programs out there, you'll find that there is no shortage in this arena due to the abundance of chess, go, and card tournaments using this format. Swiss scheduling is clearly a difficult problem and is one that a lot of people attempt to build programs for. My first instinct was thus to use an existing program and just manually add a bunch of games to Leaguevine each round during the tournament. Yeah, I know, keeping track of games on both Leaguevine and an external scheduler sounds awful. What makes this approach even worse is that after looking into these existing programs, they tended to do a very poor job of scheduling because they did not ensure that there were no rematches.
Thus, we built our own.

Before I explain our solution, I should briefly explain how a swiss tournament works. Each round, all of the teams are matched up with another team based on a pairing method that the tournament director chooses. The winners of that round received points which are used to rank the teams. Typically, a team is rewarded one point (we'll refer to this as a "swiss point") for a win, but there also exist variations based on point differential. If multiple teams have the same number of swiss points, the tiebreaker is usually how many swiss points each team's opponents have scored, which essentially rewards teams for their strength of schedule.

To schedule a round of matchups, the teams are first separated into groups based on either their win/loss record or swiss points. Unless point differential is taken into account, the groups will likely be the same for win/loss record and for swiss points. If point differential is taken into account, then the groups are formed based off of win/loss record and the point differential (aka swiss points) determines the team's ranking within that group. The teams will then play the other teams in this group. If a group has an odd number of teams, a team must be added or removed from that group. For deciding which team plays which other team within the group, there are four common group pairing methods.

The difficulty in scheduling occurs when we introduce two almost universally accepted constraints:

  1. No team should play another team more than once during the tournament
  2. No team should have more than one bye during the tournament

Because of this, the matchups that are generated by a tournament scheduler using any of the group pairing techniques will result in matchups that violate either of these two constraints. Almost every piece of existing software I've seen simply points out which ones violate the constraints, but leave it entirely up to the tournament director to resolve the problems. There does appear to be one program   out there that resolves these conflicts, but I didn't notice it until well after I finished coding the algorithm up. Luckily it only took a couple days!

I've seen many articles explaining how to resolve any conflicts with these constraints. They tend to list a sequence of steps for either changing the matchups until you find something that works or reordering the standings until you find something that works. However, at the end of these steps usually comes a line that says "this approach usually works but doesn't work all of the time.". Another problem I see with these approaches is that it is very difficult for a person to manually change a matchup and have that change be the optimal possible change. There is just too much room for error.

Leaguevine's Algorithm

The approach taken by the Leaguevine scheduler is much more mathematically sound. First, the Leaguevine scheduler builds a set of "weights" that determines a cost penalty for each team playing against each other team for that given round. The penalty is zero for matchups between sets of teams that are supposed to play each other (according to whatever group pairing algorithm is used) and whose matchups are not rematches. The penalty increases for matchups that are not ideal according to the pairing algorithm.

Let's take a look at a sample vector of weights for a given team in a given round. Lets say there are currently 8 teams, and fold pairing (aka. slaughter pairing) is used (FYI, Slide pairing was used for Wisconsin Swiss). If the teams have an initial seeding of team 1 being ranked 1st through team 8 being ranked 8th, team 1's weight vector for this first round will simply be [100000000, 6, 5, 4, 3, 2, 1, 0]. We see that the preference for team 1 is to play team 8, it's second preference will be team 7, it's third will be team 6, and so on. The penalty for team 1 playing itself is set outrageously high to ensure that this never happens. For this same round, team 2's weight vector for this round will be [6, 100000000, 4, 3, 2, 1, 0, 1]. Since team 2 should ideally play team 7, the weight for that matchup is 0, meaning it is team 2's first preference.

After all of these weight vectors are created for a given round, each corresponding pair of weights is added to make the matrix of weights symmetrical. In other words, the weight for team 1 playing team 6 will be added to the weight for team 6 playing team 1 and vice versa. Finally, these weights are squared for added effect. For this first round, the matchups will come out to be 1 vs 8, 2 vs 7, 3 vs 6, and 4 vs 5.

Now that we have a symmetric matrix, this matrix represents an undirected graph where each node is a team and each edge is a weight. Finding the ideal solution then boils down to finding the set of edges that splits this graph into pairs of nodes and has the smallest possible combined weight. Thankfully, this is a well studied problem in graph theory. Leaguevine uses a minimum weight maximum matching algorithm to determine to solve this problem and arrive at the final matchups. Thanks to Abraham Flaxman, this algorithm has already been coded up in Python!

Okay, so now that we've generated the initial matchups for this 8 team tournament, how do we generated for the second round? First, we should note there will be four 1-0 teams, and four 0-1 teams. We can assume that there is some tie breaker that ranks the teams within these two groups. The default tie breaker for Leaguevine is Victory Point scoring conceived by Christian Schaffner (edit: Christian tells me it was actually created by Michael Cummings and/or his Australian Ultimate buddy). Further, if there are still ties after sorting by the number of wins and the number of victory points, the next tie breaker is the team's strength of schedule determined by the sum of all previous opponents' victory points.

So getting back to scheduling matchups for these teams after the first round is over, we assume the teams are again ranked 1-8 and we will continue using the fold pairing grouping method. The ideal matchups will be 1 vs 4, 2 vs 3, 5 vs 8, and 6 vs 7. The weight vector for team 1 will look like [100000000, 2, 1, 0, 23, 22, 21, 20]. The weights against teams 2-4 are self explanatory. The weights against the teams in the 2nd group were calculated by determining what the weight would be if that team were moved down as the top seed in the 2nd group, and adding a penalty of 20 for each group it had to move down which in this case was just one. As a second example, the weight vector for team 2 would be [2, 100000000, 0, 1, 23, 22, 21, 20]. After calculating all of these vectors, they are again run through the minimum weight maximum matching algorithm and the output is the ideal matchups for the next round. 

There are a couple of other finer points of interest that make the lives of schedulers difficult if they are doing this by hand. First, if there are an odd number of teams, then the groups will be odd and on top of that there is still a chance that teams will have to switch groups to avoid rematches or double byes. The Leaguevine algorithm makes these groups even by creating groups of the same record starting with the highest ranked group, and if a group size is odd, the highest ranked team outside that group is then added to the group. This continues until all groups have been created. To ensure that teams do not play the same team twice and do not have more than one bye in the tournament, a large number (100000) is added to the already calculated weight of the matchup.

Determining optimal matchups as rigorously as this by hand is nearly impossible and certainly not practical, which gave me the motivation to build this algorithm. Because Leaguevine's internal framework had already been built, and a python version of the maximum matching algorithm was available for free, the entire process of devising this algorithm and coding it up took only two days, which I am really happy about.

We were very pleased with how well it performed at Wisconsin Swiss, as all of the teams kept telling us how difficult and evenly matched all of their games were after the 2nd round. In fact, if you look at the results, 11 of the 15 games in the 5th round were "close" if we define close to mean 13-8 or closer. We were really happy with this considering the pool of teams ranged from Drag'n Thrust who finished 3rd at Nationals last year all the way to MUFA recreational pickup teams that were not playing in the competitive division.

One Final Note

While all of this scheduling might sound complicated, from a user's perspective it couldn't be easier. Since Leaguevine takes care of all of this programmatically, all a user has to do is click "create next round" and wait a few seconds.

Leaguevine Mobile

Posted on March 17th, 2011 by Mark "Spike" Liu
Leaguevine has gone mobile! We've made it as easy as possible to send and receive score updates using your smartphone. Just visit m.leaguevine.com in any mobile browser.

To kick things off, two large Ultimate tournaments this weekend will be using Leaguevine Mobile for their score reporting. You can follow along with the live updates from Easterns or Steakfest either from your home browser or from Leaguevine Mobile. If the players at this tournament actively report their updates (and we really hope they do!) then we could see some of the best and most easily available Ultimate updates ever. Many of you players and tournament directors have been calling for a Mobile app to take care of this real time reporting, so we hope that Leaguevine Mobile lives up to your expectations!

So, what exactly does Leaguevine Mobile do? We have a bunch of information on our site at http://leaguevine.com/mobile/ but the best way to learn about its capabilities is just to play with it yourself. Even if you do not currently have a smart phone, you can still visit it in a regular web browser and get the same experience. Basically, the web app allows you to update game scores, and since Leaguevine and Leaguevine Mobile are synced, everyone at home or at the fields will see your update immediately. Further, you can optionally have these updates posted to Twitter so you can kill two birds with one stone - reporting official score updates, and informing your fans.

If you would like to have this kind of functionality at your next tournament, you are free to create an account on leaguevine.com and simply enter the team and game information for your tournament. It takes just a few minutes and will allow all of the players at your tournament to have access to real time score updates from all the fields, assuming you tell other teams to use it too.

We hope you enjoy this major addition to Leaguevine and please tell your friends about it!

-Mark

New Feature: Retweet Buttons Next to Every Tweet

Posted on October 29th, 2010 by Mark "Spike" Liu
I got a lot of good feedback from lots of people yesterday. The traffic spiked as soon as USAU Club Nationals started thanks to a lot of people spreading the word about Leaguevine. As the traffic went up, so did my list of user suggestions.

The one suggestion that I figured I could implement quickly last night was retweet buttons on every tweet. Now if you want to share a twitter update, you can just click on the "tweet" button that shows up when you hover over any tweet on Leaguevine. It'll jump to twitter for you and enter the text RT @someuser: (text of the tweet you want to retweet). Further, it'll append a link back to Leaguevine to help spread the word about the site. You are welcome to delete this link if your tweet is too long or you think it makes your tweet look ugly.

I hope this is useful to a bunch of you!

-Mark