Better schedule generation for non-standard leagues

[dumbmatter]

Currently an NBA-like schedule is generated if you have a league with 82 games, 30 teams, 2 conferences, and 3 divisions. Otherwise, season.newScheduleCrappy() is used. And as you can see, it's basically just totally random, which kind of sucks because it will result in unbalanced schedules.

It would be nice to do better. Even ignoring conferences and divisions, having all teams play each other an equal number of times (or as close to that as possible) would be a big improvement.

[dumbmatter]

@kgilbert-cmu I was thinking, this sounds like something that might interest you. If so, let me know. If not, I'll do it myself some time.

[kgilbert-cmu]

Side-bar: I can't believe you actually used the name "crappy" in the function name. Though I suppose it does help differentiate it.

Anyway, I'm wondering if this can be cleaned up if we allow the compromise that in League Settings, the user can specify how many games they want, but if it's an odd number or one that wouldn't be balanced, we "round" up or down to the nearest whole factor.

It looks like this function grabs the g.numGames and just runs with it, rather than reconsidering the number with respect to how many teams it has to work with.

Option 2: what about enumerating all of the possible games into the tids array and then just shuffling it? Don't need to deal with this random draw method. Again I'm sure this is overlooking something about the make-up of the game schedule, such as having repeat opponents within your division, etc, but we could rather easily write those rules into our generation logic.

[dumbmatter]

Side-bar: I can't believe you actually used the name "crappy" in the function name. Though I suppose it does help differentiate it.

You still have much to learn...

Anyway, I'm wondering if this can be cleaned up if we allow the compromise that in League Settings, the user can specify how many games they want, but if it's an odd number or one that wouldn't be balanced, we "round" up or down to the nearest whole factor.

There probably is some math that proves scenarios where it's possible to have balanced schedules, in which case we could use that, but I think it actually doesn't really matter. Maybe we could show it as a warning, but if users want to do weird shit, they should be able to. Most of the time, if it's only slightly unbalanced, that's fine. The problem is, now it can be way unbalanced because it's totally random.

Option 2: what about enumerating all of the possible games into the tids array and then just shuffling it? Don't need to deal with this random draw method.

Yeah, that's basically what I was thinking this morning. Something like:

1. enumerate all matchups (call this list of matchups "X")
2. shuffle X (so you don't always have the same games, in the case where season length is shorter than X)
3. concatenate X with itself until it's long enough to cover all the games in the season (TRICKY PART: if the cutoff point is not on an exact multiple of the length of X, do something clever with sorting the final partial X to ensure that the number of games remains as balanced as possible. I'm not sure if it'd be possible to always have every team with the same number of games - probably not. But if it is possible, it should always happen. And if it's not possible, it should be off by 1 at most, in number of games and number of times facing an opponent.)
4. shuffle it again at the end, so the pattern of games doesn't cycle

Also, this is probably all just a solved problem, but I haven't researched it.

having repeat opponents within your division

I would probably just ignore that and keep the special function for NBA-like leagues... but if you wanted to not ignore it... the holy grail would be an algorithm that, when given (82 games, 2 conferences, 6 divisions, 30 teams) would produce exactly the NBA scheduling constraints, and when the conditions deviate from that it would still produce something reasonable and NBA-like. That might not be a solved problem.

[scrandyb]

Hey guys,

Saw this project on r/nba today - awesome stuff! I think I may be able to contribute and help with your scheduling problem. Sorry in advance if this is super long - it's quite a complicated problem, I tried my best to keep my answer as simple as possible.

The solution I'm visualizing uses a sort of "building blocks" method of constructing a schedule. Imagine you have and unlimited amount of building blocks that come in three different sizes - division blocks, conference blocks, and league blocks. Each "block" involves every team in each group playing every other team in their group exactly once. Thus, the "division" block in a normal NBA league structure contains 4 games for every team, each "conference" block has 14, and each "league" block 29. If we have non-neat number of games in a season, we can cut the final block into a smaller piece to make it fit.

To get really close to a real NBA schedule with 30 teams/2 conf/6 div/82 games, we use the following set of blocks:
2 league blocks (29 x 2, or 58 games)
1 division block (4 games)
1 conference block (14 games) plus a fractional piece (for the 6 remaining games)

This ensures each team plays each team in their conference (but not in division) 3-4 times, each team in their division 4-5 times (not exact to NBA, but close), and each non-conference team 2 times. More generically, we can generalize the order we add blocks to be:

1. Conference block
2. League block
3. Division block
4. League block
5. Repeat

This formula allows us to deviate from the NBA structure while keeping "NBA like" scheduling. Basic example:
40 teams
2 conferences (20 teams each)
2 divisions per conference (10 teams each)
75 games
Would yield 3-4 games against each team in your division, 2-3 against each in your conference, and 1-2 against each non-conference team. A good approximation of the NBA I think.

If we get crazy with the structure, we see the schedule is good but definitely gets weird:
25 teams
3 conferences (c0, c1 and c2) with 13, 6, and 6 teams respectively
c0 has 2 divisions (d00 and d01) with 8 and 5 teams, respectively
c1 and c2 each have 2 divisions (d10, d11, d20, d21) with 3 teams each
65 games in a season
How do we handle a "conference block" even though the conferences have different number of teams? In my mind, we take the largest conference (in this case, 13 teams, or 12 opponents for each team in that conference) and make each conference block that size. Thus, for the 6 team conferences, each "conference block" involves each team playing each other team an average of 2.4 times ( or 12 / 5). Same rule for division blocks (each division block is 7 games, since the biggest division has 8 teams). Each league block contains 24 games.
With the above formula, division d00 would play each team in their division 3-4 times, each team in their conference 2-3 times, and each non-conference team 1-2 times. Division d10 would play each team in division 6-9 times, each team in conference 3-5 times, and each non-conference team 1-2 times.

I have ideas on how to handle home/away games and schedule randomization, but I've already written a novel here so I'll save it for later.

If you guys didn't die from confusion while reading and like the idea, I can take a stab at coding it (I'm a professional Python dev, so writing algos in JS might take me a hot minute)

Cheers

[dumbmatter]

You are welcome to try. It would be really cool to have an algorithm that produces an NBA schedule when given an NBA-like league but generalizes well to other scenarios. But if the end result is something ridiculously complicated, I might not be inclined to merge - I'm not trying to be negative, just want to be up front about it.

If you guys didn't die from confusion while reading and like the idea, I can take a stab at coding it (I'm a professional Python dev, so writing algos in JS might take me a hot minute)

I feel you, look far enough back in the commit history and you'll find this used to be a Python project, and it was my first serious work in JS :)

It'd also be fine if you do the algo in Python and want to leave the JS porting to me. Just assign each team an ID number from 0 to numTeams - 1 and output a list of games for the season like [[0, 4], [5, 2], ...] where the inner arrays represent matchups, first number for the home team and second for away.