Very impressive work so far. If your program can handle interleague games and uneven divisions, it will be far ahead of OOTP's in-game scheduler. I hope it works out!

I have high hopes that it will, although I'm embarking on by far the most difficult part of the problem: scheduling is part of a class of computer science problems known to be at least as hard as the hardest problems of which we know.

If I were to spend a few hours right now, I could almost certainly have scheduling working for even-numbered teams and symmetrical structures, which is where I was with the old scheduler. Adding in the asymmetry and odd numbers makes things significantly harder.

The plan right now is to generate schedule blocks: self-contained collections of teams playing between themselves for a certain number of games. If I can do that such that every game is assigned, I can easily slot the schedule-blocks into a structure that matches their lengths.

Alrighty, another question for the people who do schedules by hand.

When you're planning a schedule, how do you go about it? You presumably have in mind the number of times each team needs to play each of its opponents, and how you're going to break those up into series, but where do you go next? What procedure do you follow to assemble those lists, which don't have dates or times associated, into dates and times?

Here is an example of a schedule I'm making right now.

20 teams, 4 divisions, 5 per division. They want 64 division games (team 1 plays 2-5 16 times each) Then they play every non division team 2 times..

So from that, I see that D games are 8H/8A vs all 4 teams, 16x4=64.
The Conference games, they play 15 teams 2 games = 30 games

But they cant play 7H series and 8A, uneven H/A

So I give each team 1 non division team to play 1H/1A. I just put those series first in the seaons. So you play 1H/1A vs a NonD team.

That leaves 28games(14 series) for Conference and 64 games ( 32 series) for division.

But with the 5 team divisions its tricky, you can't have all division games, 1v2 3v4 5v nobody.

So you need at least 2 conference series each schedule block. Using algebra I figured out I need x amount of blocks with 2 conference and x amount with 4 conference games.

Then I schedule all the conference games. So my schedule has 2 games or 4 games on each block.

When I get done with that, I'll go back and fill in the division series around the conference ones.

Its like Sudoku in a way.




For more generic schedules, like you have a 4 team league, 1 division, everyone plays everyone 12 times (6H/6A), I like to break things into rotations.

Block 1 1v2 3v4
Block 2 1v4 2v3
Block 3 1v3 2v4

This is obvious a pretty simple example, but you can just rotate though those lists until you get all the series scheduled.

I use excel and created a "calender" in a tab. I schedule games on specific days.

Once the whole schedule is done, I manually add the times to a column.


I created a thread in this forum not too long ago explaining how I create these things. You can check it out if you want more ideas.

Are you making some progress with the scheduler, Fishbreath?

(not meant to rush you into things, of course :flowers:)

It's coming along.

All of the work I've been doing lately has been under the hood: as I think through the way I want to handle the placing of games onto a calendar, I find myself needing information arranged in different ways. I've mainly been working on a representation for the calendar.

It used to be that the season schedule was tracked per team relative to opponents, and the final schedule was composed from that. Since I can't guarantee that every team will play the same kind of opponent for any given day, I need a central clearinghouse for information about when teams are available, and so I rewrote the code to have a central list of days, into which are plugged the series and games that occur on each day. Most recently, I've been writing utility methods to extract from the calendar information on when a team is available, and the common times that two teams are mutually available. I don't think I need any other information to move ahead.

Going forward, the scheduling logic needs to prevent two situations:

1) Scheduling such that, for a given matchup, the teams share no available times to play each other.
2) Scheduling such that, for odd-numbered substructures, there are insufficient non-substructure opponents available for those teams left out of their substructure to play, such that a minimum of extra time off is included.

I think I have a way to handle both of those issues. I should have progress to report in the next few weeks. It should be relatively easy to get to the point where the scheduler will at least generate schedules, albeit probably sub-optimal ones in terms of game timing, with significantly more empty space than is actually required for uneven league structures. It should be playable, though.

I'm also toying with the idea of creating some sort of CSV output for building custom schedules from an automatically generated starting point. How would it be best to format that information? Would it be helpful to release what I've done so far as a CSV-generating module? (To remind you, what's done right now is matchup generation, figuring out how many times each team needs to play each other team.)

Well, to my surprise, I have it sort of working—it assembles games into a schedule, albeit a bad schedule, which leaves some teams out to play alone at the end of the season, and is unable to shuffle teams around so as to make things work.

We'll get there, though. The main thing is that we're up to 'kind of working'. All the framework is complete, it's just the minutiae of actually arranging games. (Which is the hardest part, but it's nice that I don't have to worry about the structure around it anymore.)

Last night, I did a little work which moves some complexity around.

Before, I was representing the slots in which a team is free to play with a start day and a length, for every day on which a team is free to play. For instance, a slot of length 5 starting on D1 is also a slot of length 4 starting on D2, 3/D3, 2/D4, and 1/D5. This made it easy to decide whether teams had free slots in common, but difficult to compare entire schedules for multiple teams, because every top-level free slot was also (slot_length - 1) other slots. When you're sorting opponents based on the free slots they have with their opponents, the number of comparisons blows up really fast.

I've changed it to simply track the top-level slot. I have a little more work to do to make placing games in large slots work correctly, but that part is almost ready, and frees me to try a few things to make the placing of games work better. Ideally, I'll avoid having to look at each opponent pool and figure out which teams need to be left out at which step, instead capturing that requirement through emergent behavior, but we'll see.

As for a timeframe for finishing the new model altogether, your hometown Elsdorf Argonauts are 20% of the way through their fourth season in my fictional league. I'm planning to expand the league no later than the 8th season, and I'll need the generator done by then.

Or I can make you one :)

Thanks, but I need the motivation to work on this.

... if it gets dire in terms of timing, I might have a request for you, though. :P

Well, that work is done, but the emergent effects I was hoping for haven't materialized. Fortunately, the scheduling runs much faster now, which means I can do more cross-checking as I go along. I may gain some ground by breaking the schedule up into chunks, based on how many teams can play, and how many teams need to play in certain kinds of action.

I'm may have to buckle down and do it the hard way—there are a few academic papers on algorithmic scheduling of complicated, time-constrained sports leagues, and I'll might need to have a look at those.

I'm proud and somewhat surprised to report that the scheduler just managed to handle Hageneezz's test case (1 subleague, 4 divisions, 20 teams, 64 divisional games, 30 interdivisional games). Its output is included below.

It also figured out my easy test case (2 subleagues, 2 divisions each, 16 teams total, 50/30/20 games requested, adjusted to 51/36/24 to make even matchups possible), and my moderate test cases (2 subleagues, 2 divisions each, 20 teams total 4-4, 5-5 and 5-4, 5-4, 60/60/20 games adjusted to 60/60/24).

It failed my MLB test case: it can't hit a 162-game target, though it successfully schedules 212 instead. A success, of sorts, in that it was able to make a perfectly compact schedule with no gaps, and did so for a fairly difficult structure. It would probably get closer to 162 with better selection of series lengths required and target number of games. (It'll always look higher, rather than lower, at the moment.)

It also fails my brutal test case (two subleagues, 2-3-5 and 2-3-5, series lengths requested 3/3/3, few breaks/little extra room) most of the time, thought it does occasionally succeed. With the extra-brutal case (series lengths 3/3/2), it fails badly enough that I doubt it'll frequently happen upon a workable schedule, but I don't think any of you are looking for quite that odd a schedule. :P

I think it's fair to say that it stands a reasonable chance of generating a reasonable schedule for most reasonable league structures. I have two things left to do before I can release this version:
1. Improve home/away balancing to look per-opponent, per-category, and overall, instead of just per-opponent and overall.
2. Schedule games throughout the day, rather than scheduling all games at 9:00 a.m. (Heh.)
3. (I know I only said two, but as an option...) write a little progress bar so you can watch as it works things out.

Some future improvements in mind, post-release:
1. Mark some days of the week (or rather, some set of days per seven days) as off-limits, to allow for weekend-only scheduling, or guaranteed breaks every week.
2. Improve handling of non-equal requested schedule lengths.

For those of you following along at home, the insight that pushed me over the edge was this: at the end of previous, failed scheduling attempts, teams would often be left with a large number of games against a single opponent un-schedulable. I changed the code so that, at each scheduling step, each team is allowed to schedule one series against the opponent it needs to play the most, before yielding its turn to the next team. Requiring teams to share the limited resources (namely, days in the schedule) seems to have fixed a problem that boils down to impoliteness, hogging all the free slots before other teams have a crack at them.

Following with great interest :eatpop:

Oops. Looks like I'm not quite as done as I thought—lots of teams double-scheduled there.

Alrighty, I think I got it. There are a few issues remaining: sometimes, a few leftover games are scheduled at the end of the season, after most of the teams have finished playing, some structural/scheduling requirements will take a few tries to schedule, and a good bit of padding is required (a number of days on the order of 10% of the number of games for simple schedules with symmetrical structures, and on the order of 25%+ for very difficult schedules).

That said, I don't think any of those issues are worth blocking a release. My task list to wrap up this version is as follows:

1. Update documentation in the settings file to explain how options work now, since they've changed dramatically since the last release.
2. Improve home-away balancing. (Done)
3. Fix intra-day scheduling, so that games occur at different times through the day. (Done)
4. Fix sorting in the generated schedule file, and add blank lines or comments at day boundaries, so that the schedule can be shuffled by hand, if desired. (Done)
5. Move debug options behind a command-line flag, so as to generate less uninteresting output for people who aren't me. (Done)
6. Improve progress messaging, change the order of the schedule statistics currently displayed, add some statistics about the schedule generation process. (Done)

It may sound like a lot, but none of it should take all that long. Depending on how my free time this week shakes out, expect something this weekend, or possibly next week before Thanksgiving.

Does anyone know if XML comments of the form <!-- text --> are allowable in schedule files?

In case you didn't see it on the first page of the post, version 1.0 is released and available for download. Please give it a try and see what you think.

Absolutely!

Your schedule structure is actually the one I shipped in the default settings file.

I have been experimenting a bit, using 94 games, but changing the break days in the settings.ini, to stretch out the regular season a bit...Changed this value from 15 to 35 and let the program generate the schedule, everything worked out brilliantly and now the season ends in October, as far as i could see looking at the schedule grid everything was setup like it should be..Great work :flowers: