Swiss tournament pairings generator

Language: Python

Task:

In a chess Swiss system tournament players and drawn against those who have the same number of points. These drawings are also made in an order that makes sure players do not oppose each other twice and, as far as is possible, each player is black/white an even number of times.

Each round sees those with equal points put to one side, those who have played each other kept apart, and decisions made according to player colours. However, after numerous rounds it can often be difficult to find pairings for those with equal points as they have often played each other.

This program creates all possible pairings for n number of people so that each pairing can be assessed and the best combination found that meets all the necessary criteria.

To calculate the possible fixtures, the process carries out the following procedure:

1. The list of players is set out with odd numbers playing white and even playing black.

W B

1 v 2

3 v 4

5 v 6

7 v 8

etc

As variables, this is written in two formats: pairings_list (a list which would show [1,2,3,4,5,6,7,8] and split_pairings(pairings) (a list of two element lists where each element represents a game [[1,2],[3,4],[5,6]].

2. The bottom two must be rotated and the new fixture combinations recorded ie.

1 v 2 1 v 2

3 v 4 3 v 4

5 v 6 5 v 6

7 v 8 8 v 7

3. When the pairing returns to its original position, the entire bottom four must be rotated, 5 moving to where 6 is, 6 moving to where 8 is and so on:

1 v 2

3 v 4

7 v 5

8 v 6

4. For the new position, the bottom two are rotated. This process continues so that the for (in the case above) there are eight rotations of the overall numbers, six rotations of the bottom six for each one of these, four rotations of the bottom four for each of these, and two rotations for each of the bottom two. In this example, it would give 384 possible combinations.

5. Carrying out the rotation involves the creation of two lists, one of the white players and one of the black:

List two 2 4 5 6

List one 1 3 7 8

6. If all the numbers were to be rotated then the first element from list one becomes the first elements of list two, all the other elements of list two move up, the last element of list two becomes the last element of list one, and finally the elements of list one move down.

List two 1 2 4 5

List one 3 7 8 6

7. The two lists can then be joined back together, list one containing the odd numbered elements and list two containing the even numbered elements. This gives a new combination that pairings can be created from.

3 1 7 2 8 4 6 5

This program does not draw for a fixed number of players. To do this, the main function has a loop and is recursive. It deducts two off the number players that needs to be rotated and causes the function to be run for these. This terminates and records the pairings when it reaches the last two. As a result, the following number of combinations are created:

n = 2 2 2

n = 4 4 x 2 8

n = 6 6 x 4 x 2 48

n = 8 8 x 6 x 4 x 2 348

n = 10 10 x 8 x 6 x 4 x 2 3840

n = 12 12 x 10 x 8 x 6 x 4 x 2 46080

n = 14 14 x 12 x 10 x 8 x 6 x 4 x 2 645120

The final data is presented as a list of possible pairing fixtures in the variable all_games. Using the first index of all_games provides one possible combination of pairings e.g. all_games[0] could give [[1,2],[3,4],[5,6]]. On the other hand, the second index provides individual games within the pairing e.g. [1,2] or [5,6].

Efficiency and improvement

The areas I would look to improve and expand are:

  1. Use of tuples instead of lists. After 14 players the program cannot cope with the exponential increase in data (there are over 10 million combinations with 16 players). The use of tuples instead of lists might help to eliminate some of this problem.
  2. A second program needs to be created that uses Swiss Tournament Pairings Generator to actually create pairings (rather than a full list of theoretical pairings)
def pairings(pairings_list):
# Shuffles the list so that the first half are lined up next to the second half. This is only used in the first
# round as chess pairings line up the highest graded half against the lowest graded half
temp_list = []
halfway = int(len(pairings_list)/2)
for i in range (0, halfway):
player_one = pairings_list[i]
temp_list.append(player_one)
player_two = pairings_list[i+halfway]
temp_list.append(player_two)
return temp_list

def split_pairings(pairings_list):

#This turns the list into pairs with 1 v 2, 3 v 4 and so on. It is represented by a list of lists, each list/element
#being a pairing. It is used in all but the first round which pairings using the 'pairings' function
games = []
for i in range (0,len(pairings_list),2):
player_one = (pairings_list[i])
player_two = (pairings_list[i+1])
pairing = [player_one,player_two]
games.append(pairing)
return games

def rotate(pairings_list,m):
# Rotates the pairings. To do this the linear list of players (pairings_list e.g. 1, 2, 3, 4, 5, 6) is turned into
#two lists, the first representing 'white' players in pairings and the second representing 'black' players e.g.
#1, 3, 5 and 2, 4, 6 (where 1, 2, 3, 4, 5, 6 in pairings_list represents 1 v 2, 3 v 4 etc). It then rotates the
#required number by moving the first value from list one into list two, moving all the list two numbers down,
#moving the last list two number into the the last list one index, and moving all the list two up in the opposite
#direction
temp_list = []
for i in range ((len(pairings_list)-m),len(pairings_list)):
temp_list.append(pairings_list[i])
for i in range (0,m):
pairings_list.pop()
list_one = []
list_two = []
for i in range (0, len(temp_list),2):
list_one.append(temp_list[i])
for i in range (1, len(temp_list),2):
list_two.append(temp_list[i])
temp = list_one [0]
for i in range (1, len(list_one)):
list_one[i-1] = list_one[i]
list_one[-1] = list_two[-1]
for i in range (1, len(list_two)):
list_two[-i]=list_two[-(i+1)]
list_two[0]=temp
temp_list=[]
for i in range (0,len(list_one)):
temp_list.append(list_one[i])
temp_list.append(list_two[i])
pairings_list = pairings_list+temp_list
return pairings_list

def main(all_games, pairings_list, m):

#The recursive part of the program. See full details in the program description.

#A loop to make the function run for m number of times for m last players in the pairings list
for i in range (0, m):
#With the function recalling itself, the point at which m = 2 (only the last two numbers being rotated) is the
#finishing point. These positions are recorded and the
if m==2:
all_games.append(split_pairings(pairings_list))
pairings_list = rotate(pairings_list,m)
all_games.append(split_pairings(pairings_list))
return all_games, pairings_list
#Deducting two to make the next loop out of two fewer players
m-=2
#Recursive to call as many layers as is needed
all_games, pairings_list = main(all_games,pairings_list,m)
#Return m back to its original value so that the rotation is of the correct amount when new list has been
#returned
m+=2
#Rotate the pairings_list
pairings_list = rotate(pairings_list,m)
return all_games, pairings_list

def create_list(n):
#Creates a list of numbers from 1 to the number of players
number_list = []
for i in range (1,n+1):
number_list.append(i)
return number_list

n=int(input("How many players are there?"))
pairings_list = pairings(create_list(n)) #List of the players from 1 to 8
all_games = [] #All the possible combinations of a specific pairing set
all_games, pairings_list = main(all_games, pairings_list, n)
question = ("Which fixture do you want? There are", len(all_games),"fixture combinations.")
answer=int(input(question))
print (all_games[answer-1])