5 ms·

This is a really interesting engineering problem. You have plenty of constraints with competing interests with a defined set of inputs (teams) & sets (weeks). T

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 https://github.com/nfl

deleted 9y ago
[deleted]
idoh 9y ago
Sounds like a job for Prolog. Maybe Prolog to make a list of schedules, and something else to sort that list?
- ufo 9y ago
  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.
  - zmonx 9y ago
    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.
    - idoh 9y ago
      You seem to know a lot about this space - how would you rank Racket's offerings, like miniKanren and Rackalog?
      - zmonx 9y ago
        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.
- zmonx 9y ago
  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-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.
jonknee 9y ago
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.
- bmelton 9y ago
  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.
  - cafard 9y ago
    Interesting--I hadn't thought of the parking matter in Baltimore.
    - bmelton 9y ago
      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.
- iamatworknow 9y ago
  It's amazing how quickly they manage to turn around those arenas for the different sports: https://www.youtube.com/watch?v=v4rZjGNYxuo https://www.youtube.com/watch?v=v4rZjGNYxuo
dnackoul 9y ago
>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.
- ghaff 9y ago
  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.
- s73ver 9y ago
  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.
- sjs382 9y ago
  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.

deleted 9y ago

[deleted]

idoh 9y ago

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

ufo 9y ago
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.
- zmonx 9y ago
  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.
  - idoh 9y ago
    You seem to know a lot about this space - how would you rank Racket's offerings, like miniKanren and Rackalog?
    - zmonx 9y ago
      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.
zmonx 9y ago
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-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.

jonknee 9y ago

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.

bmelton 9y ago
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.
- cafard 9y ago
  Interesting--I hadn't thought of the parking matter in Baltimore.
  - bmelton 9y ago
    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.
iamatworknow 9y ago
It's amazing how quickly they manage to turn around those arenas for the different sports: https://www.youtube.com/watch?v=v4rZjGNYxuo https://www.youtube.com/watch?v=v4rZjGNYxuo

dnackoul 9y ago

>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.

ghaff 9y ago
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.
s73ver 9y ago
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.
sjs382 9y ago
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.