Swiss Tournament Pairing System - Relational Databases
After many weeks, I've finally been able to finish my Intro to Relational Databases class! It certainly didn't help that we've been dealing with moving apartments the last few weeks, but this class also kicked my butt big time! I've done plenty of work with WordPress databases, but honestly most of that is hidden from you, so I was excited to finally learn some real database stuff and get used to writing some SQL!
The class was well paced and covered everything really well. I honestly was able to fly through most of the class, but got caught up on the final project. We were asked to create a Python module that uses a PostgreSQL database to keep track of players in matches in a game tournament, particularly using the Swiss Pairing method. So rather than just eliminating players each round, you have to keep track of all previous matches, rank players and then pair them accordingly.
The initial implementation went pretty quick, but then I got the bright idea to challenge myself with all of the extra credit requirements as well, which took me twice as long to implement as the basic version! But hey, I learned a lot, and am now super proud of the result.
If you're interested, I'll walk you through my code, or you can check out the entire project on GitHub. It has the full versions of each file in addition to the unit tests I ran on the project. If you have any thoughts on how I did this or have any notes, as always, let me know!
Creating the Database
CREATE TABLE players ( id SERIAL,
name TEXT );
CREATE TABLE tournaments ( id SERIAL,
name TEXT );
CREATE TABLE matches ( matchid SERIAL,
tournament INTEGER,
winner INTEGER,
loser INTEGER,
draw BOOLEAN );
CREATE TABLE scoreboard ( tournament INTEGER,
player INTEGER,
score INTEGER,
matches INTEGER,
bye INTEGER );
So this is what I ended up with. Tables for players and tournaments that auto-increment as they sign up, a table to record the outcome of matches, and a table to keep track of players scores as they progress in their tournament.
tournament.py
Now for the actual Python module that interacts with the DB!
Database/Test Utilities
#!/usr/bin/env python
#
# tournament.py -- implementation of a Swiss-system tournament
#
import psycopg2
def connect():
"""Connect to the PostgreSQL database. Returns a database connection."""
return psycopg2.connect("dbname=tournament")
def deleteMatches():
"""Remove all the match records from the database."""
DB = connect()
c = DB.cursor()
c.execute("DELETE FROM matches")
DB.commit()
DB.close()
def deletePlayers():
"""Remove all the player records from the database."""
DB = connect()
c = DB.cursor()
c.execute("DELETE FROM players")
DB.commit()
DB.close()
def deleteTournaments():
"""Remove all the tournament records from the database."""
DB = connect()
c = DB.cursor()
c.execute("DELETE FROM tournaments")
DB.commit()
DB.close()
def deleteScoreboard():
"""Remove all the scoreboard records from the database."""
DB = connect()
c = DB.cursor()
c.execute("DELETE FROM scoreboard")
DB.commit()
DB.close()
These are basic utility functions used throughout the code and tests.
Create Tournament
def createTournament(name):
"""Create a new tournament.
Args:
Name of tournament
"""
DB = connect()
c = DB.cursor()
sql = "INSERT INTO tournaments (name) VALUES (%s) RETURNING id"
c.execute(sql, (name,))
tid = c.fetchone()[0]
DB.commit()
DB.close()
return tid
Now for the real stuff. First we need a way to create our first tournament. We connect to the database and do a simple INSERT statement with the given name. The database takes care of creating the id for us, which we return so we can store it for the rest of the functions.
Count Players
def countPlayers(tid):
"""Returns the number of players currently registered for a tournament.
Args:
tid: id of tournament
"""
DB = connect()
c = DB.cursor()
sql = """SELECT count(player) AS num
FROM scoreboard
WHERE tournament = %s"""
c.execute(sql, (tid,))
players = c.fetchone()[0]
DB.close()
return players
Now for a simple SELECT statement. Because the Swiss pairing system requires pairs, we will need this to know how many pairs to test for as well as if there is an odd number of participants.
Register Players
def registerPlayer(name, tid):
"""Adds a player to the tournament database.
The database assigns a unique serial id number for the player. (This
should be handled by your SQL database schema, not in your Python code.)
Args:
name: the player's full name (need not be unique).
tid: id of tournament they are entering.
"""
DB = connect()
c = DB.cursor()
player = "INSERT INTO players (name) VALUES (%s) RETURNING id"
scoreboard = "INSERT INTO scoreboard (tournament,player,score,matches,bye) VALUES (%s,%s,%s,%s,%s)"
c.execute(player, (name,))
playerid = c.fetchone()[0]
c.execute(scoreboard, (tid,playerid,0,0,0))
DB.commit()
DB.close()
You can't have a tournament without players, so we do another insert, similar to createTournament(). The difference here is that we also have to initialize the player on the scoreboard, so we return the id they are assigned at registration and add them to their tournament.
Player Standings
def playerStandings(tid):
"""Returns a list of the players and their win records, sorted by wins.
The first entry in the list should be the player in first place, or a player
tied for first place if there is currently a tie.
Args:
tid: id of tournament getting standings for
Returns:
A list of tuples, each of which contains (id, name, wins, matches):
id: the player's unique id (assigned by the database)
name: the player's full name (as registered)
wins: the number of matches the player has won
matches: the number of matches the player has played
"""
DB = connect()
c = DB.cursor()
players = """SELECT s.player, p.name, s.score, s.matches, s.bye,
(SELECT SUM(s2.score)
FROM scoreboard AS s2
WHERE s2.player IN (SELECT loser
FROM matches
WHERE winner = s.player
AND tournament = %s)
OR s2.player IN (SELECT winner
FROM matches
WHERE loser = s.player
AND tournament = %s)) AS owm
FROM scoreboard AS s
INNER JOIN players AS p on p.id = s.player
WHERE tournament = %s
ORDER BY s.score DESC, owm DESC, s.matches DESC"""
c.execute(players, (tid,tid,tid))
ranks = []
for row in c.fetchall():
ranks.append(row)
DB.close()
return ranks
The key to good pairings is knowing the rankings of each player. This was a little more complicated because it not only needed to be ranked by their overall score, but in case of a tie they were to be ranked by the total score of all of their opponents as well.
We use an INNER JOIN to add the players' names to their scoreboard, and then use a few sub-queries to grab the scores of each opponent they've played and pass them to the SUM function. We then return the ranks in a list.
Report Match
def reportMatch(tid, winner, loser, draw='FALSE'):
"""Records the outcome of a single match between two players.
Args:
tid: the id of the tournament match was in
winner: the id number of the player who won
loser: the id number of the player who lost
draw: if the match was a draw
"""
if draw == 'TRUE':
w_points = 1
l_points = 1
else:
w_points = 3
l_points = 0
DB = connect()
c = DB.cursor()
ins = "INSERT INTO matches (tournament, winner, loser, draw) VALUES (%s,%s,%s,%s)"
win = "UPDATE scoreboard SET score = score+%s, matches = matches+1 WHERE player = %s AND tournament = %s"
los = "UPDATE scoreboard SET score = score+%s, matches = matches+1 WHERE player = %s AND tournament = %s"
c.execute(ins, (tid, winner, loser, draw))
c.execute(win, (w_points, winner, tid))
c.execute(los, (l_points, loser, tid))
DB.commit()
DB.close()
Next we need to INSERT the results of each match. If it's a draw each player gets a point, otherwise the winner gets three points. We update the matches and scoreboard tables with the results.
Handle Byes
def hasBye(id, tid):
"""Checks if player has bye.
Args:
id: id of player to check
Returns true or false.
"""
DB = connect()
c= DB.cursor()
sql = """SELECT bye
FROM scoreboard
WHERE player = %s
AND tournament = %s"""
c.execute(sql, (id,tid))
bye = c.fetchone()[0]
DB.close()
if bye == 0:
return True
else:
return False
If we have an odd number of players, one will get a bye. But each player should only be allowed one bye per tournament, so we need a quick way to check if they do or not. Simple SELECT and returns true or false.
def reportBye(player, tid):
"""Assign points for a bye.
Args:
player: id of player who receives a bye.
tid: the id of the tournament
"""
DB = connect()
c = DB.cursor()
bye = "UPDATE scoreboard SET score = score+3, bye=bye+1 WHERE player = %s AND tournament = %s"
c.execute(bye, (player,tid))
DB.commit()
DB.close()
Once you know which player will get the bye, we do a similar operation to reportMatch(), updating the score and bye columns.
def checkByes(tid, ranks, index):
"""Checks if players already have a bye
Args:
tid: tournament id
ranks: list of current ranks from swissPairings()
index: index to check
Returns first id that is valid or original id if none are found.
"""
if abs(index) > len(ranks):
return -1
elif not hasBye(ranks[index][0], tid):
return index
else:
return checkByes(tid, ranks, (index - 1))
When pairing, this allows the program to loop throw the ranks, starting at the bottom, and moving up until a player without a bye is found. This way we can quickly iterate over the rankings to find the best candidate for the bye.
Prevent Rematches
def validPair(player1, player2, tid):
"""Checks if two players have already played against each other
Args:
player1: the id number of first player to check
player2: the id number of potentail paired player
tid: the id of the tournament
Return true if valid pair, false if not
"""
DB = connect()
c = DB.cursor()
sql = """SELECT winner, loser
FROM matches
WHERE ((winner = %s AND loser = %s)
OR (winner = %s AND loser = %s))
AND tournament = %s"""
c.execute(sql, (player1, player2, player2, player1, tid))
matches = c.rowcount
DB.close()
if matches > 0:
return False
return True
Another requirement is that there are no rematches. This function takes the ids of two players and sees if any previous matches are found.
def checkPairs(tid, ranks, id1, id2):
"""Checks if two players have already had a match against each other.
If they have, recursively checks through the list until a valid match is
found.
Args:
tid: id of tournament
ranks: list of current ranks from swissPairings()
id1: player needing a match
id2: potential matched player
Returns id of matched player or original match if none are found.
"""
if id2 >= len(ranks):
return id1 + 1
elif validPair(ranks[id1][0], ranks[id2][0], tid):
return id2
else:
return checkPairs(tid, ranks, id1, (id2 + 1))
Now we use that to loop over rankings until a valid pair is found in the rankings. If there isn't (which is very unlikely due to the nature of Swiss pairings) we handle that case by returning the original pair since they would be the most ideal match in that case.
The actual pairings
def swissPairings(tid):
"""Returns a list of pairs of players for the next round of a match.
Assuming that there are an even number of players registered, each player
appears exactly once in the pairings. Each player is paired with another
player with an equal or nearly-equal win record, that is, a player adjacent
to him or her in the standings.
Args:
tid: id of tournament you are gettings standings for
Returns:
A list of tuples, each of which contains (id1, name1, id2, name2)
id1: the first player's unique id
name1: the first player's name
id2: the second player's unique id
name2: the second player's name
"""
ranks = playerStandings(tid)
pairs = []
numPlayers = countPlayers(tid)
if numPlayers % 2 != 0:
bye = ranks.pop(checkByes(tid, ranks, -1))
reportBye(tid, bye[0])
while len(ranks) > 1:
validMatch = checkPairs(tid,ranks,0,1)
player1 = ranks.pop(0)
player2 = ranks.pop(validMatch - 1)
pairs.append((player1[0],player1[1],player2[0],player2[1]))
return pairs
Now we get to the function that puts everything together and actually returns the next set of pairs for the round.
First we check the number of players to see if a bye needs to be given, and then go through the rankings and generate the pairs.
And that's it!
I am glad to be finished with the project finally, but it was definitely a very good exercise. If you are looking to test your database skills, I definitely recommend the class and would love to see your project after you finish! It was cool looking in the forums and seeing how other people solved the same problems.
Again, if you want to look through the tests or the rest of the projects for the class, you can see it all on my GitHub profile.
