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.
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.
main :- schedule([1-2, 1-3, 1-4, ... 2-1, 2-3, ...], [], SCHEDULE) output(SCHEDULE). schedule([], SCHEDULE, SCHEDULE). schedule(GAMES, PARTIAL_SCHEDULE, SCHEDULE) :- pick(GAMES, DAYS_GAMES, GAMES_LEFT), test(DAYS_GAMES, PARTIAL_SCHEDULE), schedule(GAMES_LEFT, [DAYS_GAMES|PARTIAL_SCHEDULE], SCHEDULE).pick - select match ups for a day in the schedule, and return the games left to play. Each day has enough games so that every team is playing, unless there is an odd number of teams, in which case the odd team out has a bye.
test - make sure the selected day's games combined with the partial schedule so far don't violate any of the constraints. (This is not used in the simple sports scheduler, but would be in one with more constraints.)
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.
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
[1-2, 1-3, ...2-1, 2-3, ...9-8]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
day(N, [T1-T2, T3-T4, T5-T6, T7-T8])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
schedule(SCHEDULE) :- games(GAMES), first_half(GAMES, [], SCHEDULE_1, [], GAMES_2), second_half(GAMES_2, SCHEDULE_1, SCHEDULE).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.)
get_games([], _).
get_games([AWAY-HOME|GAMES], PICK_LIST) :- deal(AWAY-HOME, PICK_LIST, PICKS_LEFT), clean(AWAY-HOME, PICKS_LEFT, CLEANED_PICKS), get_games(GAMES, CLEANED_PICKS).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.
delete(A,[A|X],X).
delete(A,[B|X],[B|Y]) :- delete(A,X,Y).
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.
pick(A,[A|X],X).
pick(A,[B|X],Y) :- pick(A,X,Y).
[4, 23, 8, 17]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
[H|T] = [4, 23, 8, 17]triggers pattern matching that unifies (temporarily sets) the two variables with these values:
H = 4
T = [23, 8, 17]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.
member(H, [H|T]).
member(H, [X|T]) :- member(H, T).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.
member(H, [H|_]).
member(H, [_|T]) :- member(H, T).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
?- member(4, [4, 23, 8, 17])will produce the answer yes right away, and
?- member(8, [4, 23, 8, 17])will produce yes after two recursive calls from the second clause of member. On the other hand
?- member(6, [4, 23, 8, 17])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
member(X, [4, 23, 8, 17])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 (c)1996 Amzi! inc. All Rights Reserved.