Behind the making of the NFL schedule | Hacker News Reader

Behind the making of the NFL schedule

bostonglobe.com

This is a really interesting engineering problem. You have plenty of constraints with competing interests with a defined set of inputs (teams) & sets (weeks). There needs to be parity within the matchups and across the season. Teams must play the other teams in their division twice. Stadiums may not be available due to concerts or other sporting events. Beyond that, you have the human factor of high-leverage games & television networks. It's also something that's quite testable against many of the non-human constraints.

The NFL actually has quite a prolific GitHub organization [0]. I recommend looking through if you have a few minutes.

[0]: https://github.com/nfl

Sounds like a job for Prolog. Maybe Prolog to make a list of schedules, and something else to sort that list?

I think SAT-solvers and other constraint solvers might be a better fit. They can use clever algorithmic search technique like clause learning, non-chronological backtracking and so on to achieve big speedups compared to naive backtracking, which is what Prolog would do in this case. And we also don't need the full turing-completeness that Prolog provides.

I agree completely that SAT solvers and constraint solvers are a great choice for this.

However, SAT solvers and constraint solvers blend in naturally and in fact even ship with many Prolog implementations! Thus, you can have the best of both worlds by simply using Prolog together with such solvers. Thus, using Prolog gives you both a Turing-complete programming language and a highly optimized constraint solver for combinatorial tasks, assuming you choose an implementation that is sophisticated enough. For example, in SICStus Prolog, check out CLP(B) and CLP(FD) for combinatorial tasks involving Boolean and integral variables.

You seem to know a lot about this space - how would you rank Racket's offerings, like miniKanren and Rackalog?

I regard miniKanren, Racklog, core.logic, and many other Prolog-style implementations and embeddings of logic programming as extremely valuable and useful contributions that are both of academic and practical importance. They also serve the important strategic purpose of drawing more attention to logic programming languages in general.

However, these implementations, although elegant and admirable in their own right also due to their innovative approaches, cannot yet compare in terms of features or performance with what a full-fledged modern Prolog system offers. In my experience, the main attraction of a professional Prolog system is often found precisely in its _constraint solvers_, and it is in these areas where professional Prolog implementors compete extremely vigorously, and more simplistic implementations currently fall short either in terms of features or performance.

Still, even a very simplistic Prolog implementation can definitely be very useful, and if you do not need sophisticated constraints, then you may not need a commercial Prolog system. This situation arises for example in parsing, web applications, rule-based systems and other tasks where Prolog can help a lot, and constraints are not primarily needed.

For a use case like sports scheduling and combinatorial tasks in general, I definitely recommend a Prolog system with very strong support of constraints, since what you can do with constraints in this application area by far exceeds the possibilities of "plain" Prolog, both in terms of performance and convenience.

Definitely! Prolog is extremely well suited for solving such tasks.

For example, one of the most highly rated Prolog question on Stackoverflow is about a related task involving Tennis match scheduling:

http://stackoverflow.com/questions/4747498/tennis-match-sche...

The posted Prolog solution is quite concise and very efficient, thanks to the built-in constraint solvers that most Prolog systems provide nowadays.

It gets really fun for sports with lots of games and shared stadiums (NHL and NBA). The Staples Center hosts the Lakers, Clippers, Kings, and Sparks.

New York Giants / Jets comes to mind as well.

On top of that, there are other competitive factors involved, e.g., in Baltimore, the Orioles and Ravens generally can't be playing mass-attendance games at the same time because they are too close together, and share parking infrastructure. That of course has to be scheduled around.

Beyond that, there's the rather mundane reality that stadiums aren't just used for sports. Even during football season, megastars like Beyonce and the Rolling Stones need venues to play in. And of course, stadiums are loaned / leased out for a panoply of other reasons as well.

Interesting--I hadn't thought of the parking matter in Baltimore.

I didn't know about it until a couple of years ago, the Ravens were the defending Superbowl champions, which usually entitles one to a home opener, but because the Orioles were still contending for the playoffs, the Ravens had their first game away at Denver.

It's amazing how quickly they manage to turn around those arenas for the different sports: https://www.youtube.com/watch?v=v4rZjGNYxuo

>There needs to be parity within the matchups and across the season.

I'm not sure how widely known this is, but the actual matchups, not order and dates, are completely deterministic.

Teams play their division twice for six games. They play the other three teams in their conference with the same division standing last season (e.g. division champs will play each other). They play four teams from a rotating division in the other conference. And finally they play the remaining three teams from a rotating division in their conference.

I've always been a football fan but it took me a while to realize the NFL doesn't actually schedule rivalries like Brady/Manning every year, they just happen because those teams consistently win their division.

I didn't realize that.

The workflow would be interesting. Presumably you have some hard and fast rules and then you try to encode bad/good/better rules. Let the computers churn out options. Maybe iterate with some new rules. The start going through the options manually.

I've worked on conference schedules :-) We don't use computers but it usually goes something like heuristics -> coarse optimization -> hand-tuning.

The matchups are deterministic. When they happen, however, is not. When making the schedules, they need to take into account rivalries (you probably don't want to have Cowboys/Redskins, Packers/Vikings, and Steelers/Bengals all happening on the same weekend), traveling, and potential playoff contenders. A game between two teams fighting for a playoff spot or division title is much more exciting in December than it is in October.

Also, for teams in the opposite conference, 2 are home and two are away. So, every team plays each team in the opposite conference every four years, but only plays them each at home every 8 years.

> I would say that we’ve done our job if everybody’s disappointed, but only a little bit, and hopefully equally.

Not many "secrets" revealed, but I love this quote. It could be applied to the culmination of a lot of software projects.

This reminds me of The Schedule Makers[1], a 30 for 30 mini documentary about a couple that has been making baseball schedules for 25 years.

1: https://www.youtube.com/watch?v=yT0CMOGKKhU

Nice piece. I like this bit in particular:

“The beauty of the computer is it can do in seconds what it would take us a lifetime,” North said. “But it’s a machine. It will only do what it is told.

Always important to recognize that "the computer" reflects the values and the judgements of its programmers. It's not inherently objective.

'Computers are dumb, they only know what you tell them' -the fly (1986)

On a related note, the BBC made a very interesting article about how the Premier League fixture list is created each season.

"...The whole process starts upwards of a year in advance when Fifa and Uefa release their match calendars but work starts in earnest in the final months of the previous season..."

http://www.bbc.co.uk/blogs/paulfletcher/2009/06/secrets_of_t...

Up until just recently there was one guy who figured out the NBA schedules for home and away games for the entire league, manually. 30 teams playing 82 games. Pretty crazy: http://bleacherreport.com/articles/2552322-as-nba-schedule-m...

Fun fact: The New York Jets have never beaten the Philadelphia Eagles

Well, they presumably only play once every four years.

And also... it's the Jets :)

Yea, it's only been 10 games. Even for perfectly random coin tosses, the chance that you get the same result 9 times as the result of the first toss is 1 in 2^9 = 512. With lots of potential team pairings, and the obvious fact that teams can be above/below average over 4+ years (correlating the outcomes), this isn't that crazy.

http://www.footballdb.com/teams/nfl/philadelphia-eagles/team...

There's only 496 pairings with 32 teams.

The number of pairings between teams that play infrequently will be quite a bit smaller.

And never played in the Super Bowl...because Eagles :)

Had to google to see this in real internet life. It is true. Insane.

I'm an Eagles fan and I did not know this. I used to end up spending time with an amazingly annoying Jets fan, this would have been a fun tidbit to bring up repeatedly.

Brett Favre and Peyton Manning are the only quarterbacks to have beaten all 32 NFL teams.

Reply on news.ycombinator.com