Sports Scheduling Sample

The SSCHED sample application is designed to both illustrate the use of Amzi! Prolog + Logic Server in scheduling applications and to provide a useful tool for anyone who has to schedule a round robin tournament. It is a simplified version of a program used to meet the extremely demanding constraints of scheduling the Atlantic Coast Conference college basketball schedule. (An article describing that application is available from the Amzi! web site.)

A round robin tournament is one in which each team/player plays each other team/player one or two times, and is the basis for regular season play for both professional and amateur sports. The problem is to create a schedule of games to be played each round so that no team has to play more than once a round and that at the end of N-1 rounds, where N is the number of teams, each team has played each other team exactly once. A round might correspond to a week with some sports, such as football, or a matter of hours in a table tennis tournament.

Using the Sports Scheduler - Details on how to use the Sports Scheduler to generate a schedule for your sporting events.

Application Architecture - Details, including full source code, of how the application is built.

www.amzi.com - Additional demos, articles, freeware, evaluation copies and information about Amzi! Prolog + Logic Server.

We welcome any and all comments about this demo, including suggestions for improvements from those who use it for generating sports schedules. Contact us at info@amzi.com


Using the Sports Scheduler

To use the Amzi! Sports Scheduler, simply follow the steps.

1. Select whether each team plays each other once or twice.

2. Select the number of teams. The maximum number allowed in the demo is 10.

3. Click the Setup Grids button. It determines the right number of rows for the teams grid box and the schedule grid box. It also creates default team names and default names for the rounds and fills them into the team and schedule grids.

4. Edit the team names (optional). You can click on any cell in the teams grid and then edit the name to be the name of a team/player in your tournament.

5. Edit the round names (optional). You can click on any cell with a round name in it in the schedule grid and change it to the name of the hour, day or week of the round in your schedule.

6. Click the schedule button. This fires up the heart of the application, which generates a schedule and fills in the schedule grid with the home and away teams for each match of each round.

7. The save button lets you generate a text file from the schedule. It contains the master schedule, as shown on the screen, as well as individual schedules for each team.

8. You can either exit the program, or go back to step 1 and generate a new schedule. The scheduler randomly scrambles the teams each time before it starts, so if you generate the same schedule again, you'll see different matches.


Application Architecture

The SSCHED demonstration is divided into two main components, the main scheduling logic and the user interface.

The scheduling logic is written in Prolog and is designed to be called from any user interface. In this case a GUI is provided using Delphi, but the same Prolog program can also be run from a Prolog listener using a simple scrolling interface written in Prolog.

Application Overview - An overview of the basic strategy of the application.

List Processing in Prolog - An overview of Prolog list processing, essential for understanding this application.

Sports Scheduler Prolog Source Code - The full annotated source of the Prolog scheduler.

Sports Scheduler Delphi Source Code - The full annotated source of the Delphi front end.


Application Overview

The Amzi! Sports Scheduling Demo is an abbreviated version of a program written to create schedules for the Atlantic Coast Conference (ACC) basketball season. The demo version does not enforce the strict constraints of the ACC application. It simply enforces the constraints of a valid round robin tournament, where each team plays each other once per cycle.

Problem Representation

The Prolog code relied heavily on lists to represent the games to be scheduled, the evolving schedule, and other items. Recursion is the primary control structure used, so, in essence, the main loop of the program is a classic recursion, with one Prolog rule for the boundary condition and one for the recursive case. The two main lists passed through the recursion are the list of games to be scheduled, and the evolving schedule.

Boundary Condition: When there are no more games to be scheduled, then the schedule passed to this point is the final schedule.

Recursive case: Take a days worth of games from the pending list and put them in the schedule list. Test to make sure no constraints are violated. If they are, backtrack, and if not make a recursive call with the rest of the pending list and the evolving schedule list.

Teams are represented by integers from 1 to N, where N is the number of teams. Games are represented by pairs of away and home teams separated by the '-' operator. For example 1-2 means 1 plays 2 at 2. If there are an odd number of teams, a special team 0 is added, called 'bye', which is included in the schedule.

Given this, one can write a first approximation of the main predicates.

This program has all of the control structure needed to search for a valid schedule. The partial schedule starts out as the empty list. At each level of recursion, games are picked to add to the schedule, and then tested. If the games selected cause a constraint fault, then the program backtracks into pick to get another possible set of games.

If there are no sets of games available for a day, then the program backtracks to the previous level of recursion, and tries a different set of games. In this way, program execution continues forward and back, until finally a valid schedule is produced or all the choices are exhausted. For the simple sports schedule, the program generates a valid solution without backtracking.

General Sports Schedule Constraints

There are some constraints that are inherent in a round robin scheduler. One is that each team play each other team, usually twice. In the first half of the season each team plays each other once, and in the second half they repeat with home and away teams reversed. Another is that no team can be playing two games at the same time. And another is that the schedule should be as compact as possible, so if there are eight teams, then there can be four games played each day.

The teams are represented by a list of integers. The games/1 predicate uses that list to generate a long list of all possible games. The generated list looks like

Because this list includes all of the games that need to be scheduled, the constraint about games is satisfied when all games on the list are scheduled.

One way to guarantee the right number of games for each day is to have the loop that picks games for each day programmed with this information. Another way is to provide a template for a day's games, in which the teams are represented by variables. This is the approach taken in the scheduling program.

The template for a days games is a Prolog pattern, or structure. If there were eight teams in the league, then a day's template would look like

Notice that the second argument is a list with four elements. Each is a possible game with different variables for each of the teams. The predicate that picks games walks this list of game templates, unifying the variables with actual teams. This guarantees each day has the right number of games.

The next constraint, that each team play each other once in the first half and once in the second half, leads to the first efficiency in the program. Because the first and second halves almost mirror each other, but have a slight difference, separate predicates are implemented for filling in each half.

The difference between the two halves is that, when a game is picked for the schedule in the first half, it's inverse game is also removed from the games-left-to-play list and put on a list of games to be scheduled in the second half. This ensures a rematch won't be considered during the first half.

The second half, of course, doesn't need to build this secondary list of games.

The overall structure of the program then looks like

A major efficiency is added to the search in the predicate that picks the games for a given day. It makes a copy of the list of games that it drastically trims as each game is selected. Once two teams are playing, all other possible games with those two teams can be removed from the list of potential games for that day. (Backtracking automatically restores those games if necessary for further search.) The deal/3 predicate deletes an AWAY-HOME pattern from the list of games, thus unifying the variables in the template with the value for AWAY and HOME. The clean/3 predicate then uses those values to remove all other possible games from the list of games that involves either of these teams.

This picking can be further improved by ensuring that the picks are combinations of games rather than permutations. That is, once a four game set has been picked for a day, there is no reason to try different arrangements of those same four games.

Useful Utilities for Scheduling

Two list utility predicates provide all of the power for the low level predicates. One is delete/3 which deletes an element from a list and returns the list of remaining elements. It, like member/2, is very useful for generating selections from a list, but with the added advantage that it returns the rest of the list as well, for further processing.

The pick/2 predicate is very similar, but has the useful behavior of not including any elements in the returned list that occur before the element selected. It is used to generate combinations, not permutations.

List Processing in Prolog

A list in Prolog is represented by elements separated by commas within square brackets. A list of four arbitrary numbers in Prolog looks like this: When working with lists, it is often convenient to be able to consider the head element or elements of a list as distinct from the tail, or rest of the list. The vertical bar is used for that effect. This notation, in conjuction with Prolog variables, provides a powerful way to describe list manipulation. Variables in Prolog, represented by an initial upper case letter, are not simply representations of computer memory locations as in most languages, but instead represent variables in patterns that take on values based on Prolog's pattern-matching, called unification.

The most general form of pattern for matching against a list has two variables, one which matches/unifies with the head element of the list, and the other which unifies with the rest of the list. [H|T] is that representation.

Two Prolog terms, of which lists are a subset, can be explicitly unified with the '=' operator. Given all this, the following Prolog statement

triggers pattern matching that unifies (temporarily sets) the two variables with these values: Note that a variable can unify with any arbitrarily complex Prolog term, including a list, as T does in this example.

The basic programmatic entity in Prolog is a predicate, which is composed of one or more clauses. Let's consider a simple recursive list processing predicate that checks if an element is a member of a list. It has the two clauses listed below. The first is the boundary condition and the second the recursive case.

The way Prolog executes, the first clause of a predicate is tried and if it fails then the next clause is tried. In this case, the boundary condition clause says that an element is a member of a list if its the head of a list. The recursive clause says an element is a member of a list if, the ':-' simple can often be read as 'if', its a member of the tail of the list.

One last note, if the value of a variable is not really needed, but must be expressed to complete a pattern, then a simple _ is used to indicate a variable whose value is unimportant. The member predicate is often written using these 'anonymous' variables.

You call a Prolog predicate by presenting it with a pattern that has the same name as the predicate. This is done implicitly after the ':-' symbol of a clause, but can also be done directly in a Prolog listener at the ?- prompt. For example will produce the answer yes right away, and will produce yes after two recursive calls from the second clause of member. On the other hand will produce no.

And now we get to the tricky part. In addition to the pattern-matching and recursion presented so far, Prolog has a feature called backtracking. Backtracking means that Prolog execution starts out in a forward direction, but if any calls fail, such as the third example of calling member above, execution backs up looking for other clauses in predicates that could be tried.

Backtracking, unification and recursion combine to provide some very powerful effects in Prolog. Consider

The first time it is called, X will be unified with '4', because of the first clause. If for some reason failure occurs further down the line, execution will backtrack to the call to member, and the second clause will be tried instead, which recursively calls member again. It succeeds the second time with X = '23', and, because it succeeds, execution restarts in a forward direction with the new value of X.

In this way, the member predicate can be used to generate values of X from a given list.

One more example will provide the foundation needed to understand the schedule program. It is a predicate that reverses a list. For example, if given the list [1,2,3,4] it will generate a new list [4,3,2,1]. Here is the definition of reverse.

reverse([], R, R).
reverse([H|T], PARTIAL, R) :- 
   reverse(T, [H|PARTIAL], R).
Like member, reverse works from the head of the list. Unlike member, reverse builds an output list as it works it way recursively down the input list. The second argument acts as an accumulator for the final result. When reverse is first called, it has an empty list as the second argument. Each level of recursion takes the head of the input list and makes it the head ot the partial list for the next call. In this way the partial list mirrors the input list, but in reverse. When the input list is empty, the boundary condition clause executes, forcing unification between the second and third arguments, thus setting the third argument to the reversed list.

This basic idea of using a accumulator list during recursion appears in many places in the scheduler code.


Copyright ©1996-2000 Amzi! inc. All Rights Reserved.