Who would have thought the world of Pickleball is so interesting it deserves two blog posts? The last time we looked at pickleball it was to determine the optimal mixed double tournament structure to maximize fairness. This time, we're going to solve for the match pairings without the gender distinction, but still as a doubles tournament. Also, we want to solve the matches so that we maximize court usage throughout the tournament. (Okay, this doesn't relate specifically to Pickleball, but whatever.)
The Problem
Put another way, how to optimally choose matchups for a doubles tournament of n people, where each person plays n-1 matches, to optimize pairing so that each person is only paired with another once, and plays against another person at most twice. Also want to solve as a tournament so we can maximize court usage (e.g., if there are 8 players, at each round we should be using two courts.)
Again, we're trying to solve this in the ballpark of n=8.
Approach
This is still an exact cover problem, but with different constraints as last time. We could still use the grid style structure, but it becomes awkward when trying to implement the court usage constraint.
Let's first generalize our exact cover solver, then restructure our "board state" data structure to implement the above contraints.
Exact Cover Problems
Last time, the heart of our constraint-propogating depth-first over-hyphen-using exact cover solver was this function:
def chooser(g, pm, n):
if unable_to_solve(g):
return None
if is_solved(g, pm):
return g
iplace = canplace(g, pm)
if iplace is not None:
return chooser(*place(iplace, g[iplace], g, pm, n))
# Have to make a choice
ichoice = findfirst(g, lambda x: len(x) > 2)
for v in aschoices(g[ichoice]):
gcopy = chooser(*place(ichoice, v, deepcopy(g), deepcopy(pm), n))
if gcopy:
return gcopy
return None
The arguments are the "board state", representing what choices we've made so far and what choices remain. We first check to see if the current board state is in an end condition - either unsolvable or solved. If it's neither of those, we check if there are any automatic choices to be made - choices with only one option. This is the second half of constraint propogation. If there is only one choice to make, choose that choice in the board state (which should internally enforce some constraints on the other choices), then continue.
If there aren't any freebie choices to make, we need to continue with the depth first search. Here is where we:
- Save the board state
- Try the choice and recurse
- If that choice didn't result in a solution, undo the choice, and try the next one
This is a similar structure to most depth first solvers. The tricky part is the undo step - because internally there could be lots of changes resulting from the constraint propogation, it's often easier to just store a copy of the board state before making the choice, then revert back to that copy if that branch didn't work out. This can be slow, however, since you are always copying chunks of memory. Also, to make sure you take advantage of constraint propogation, you need to make sure it is not taking the same code path as that copy.
Other approaches remove the need for saving the board state by allowing an undo choice operation, or "backtracking". This can result in large speed increases by reducing the memory footprint. The best example of this is Knuth's Dancing Links (DLX) technique for solving exact cover problems. Maybe we'll do a pickleball solver with DLX some other time.
So, how do we generalize this thing? It's pretty close already - we just need to implement the interface functions
- unable_to_solve - is the board state unsolvable?
- is_solved - is the board state solved?
- canplace - is there an automatic choice to make?
- findfirst - find the first position that has multiple choices
- place - make a choice in a certain position
That sounds like a class. So, rewriting assuming a BoardState interface:
def chooser(board):
if board.unable_to_solve():
return None
if board.is_solved():
return board
constrained_pos = board.canplace()
if constrained_pos is not None:
return chooser(board.place(constrained_pos, board.choices(constrained_pos)[0]))
# Have to make a choice
pos = board.first_position_with_choices()
for choice in board.choices(pos):
boardcopy = chooser(deepcopy(board).place(pos, choice))
if boardcopy is not None:
return boardcopy
return None
Again, this assumes we are using the "copy" method of backtracking, instead of an explicit undo operation. Also, the "place" method contains the clever constraint propogation parts. This seems okay, since if we had less clever constraint propogation, we'd just do more depth first searching, without any changes to this code.
Pickleball Specifics
Now let's write the pickle ball board state class. As I mentioned before, the grid-style representation last time doesn't work as well when you only have players in a single category, as opposed to split into two distinctly competing groups (gender), and you also want to solve for the actual court usage during the tournament.
After thinking this over for a while, let's try representing our board state as an actual tournament bracket, like so:
Court 1 Court 2
+----+ +----+
| | | |
|----| |----| Match 1
| | | |
+----+ +----+
+----+ +----+
| | | |
|----| |----| Match 2
| | | |
+----+ +----+
+----+ +----+
| | | |
|----| |----| Match 3
| | | |
+----+ +----+
...etc.
With n=8 players, we'll need 8/4 = 2 courts and 8-1 = 7 matches for the tournament.
The goal will be to fill in each court in each match to meet all of our constraints. Namely:
- Each player is paired on the same team with every other player exactly once
- Each player will never play against another player more than twice
So, our finished solution will look something like:
Court 1 Court 2
+----+ +----+
| AB | | EF |
|----| |----| Match 1
| CD | | GH |
+----+ +----+
+----+ +----+
| AC | | FG |
|----| |----| Match 2
| DE | | BH |
+----+ +----+
...etc.
meaning that in Match 1, player A and player B play against player C and player D, and player E and player F play against player G and player H, and so on.
Note that we are not restricting the court and the position on the court (for now). So, for this solution, we are just trying to get the pairing for each match - which court and position each pair ends up on doesn't matter (can easily be switched at game time). Put another way, we are assuming that each position on each court are exactly the same (which is a pretty big assumption if you know that Court 1 is nearer to the door, so it's really drafty, but we have to start somewhere.)
So, without loss of generality, we can assign one player to the same position in each court for each match on initialization, and cycle through all partners:
Court 1 Court 2
+----+ +----+
| AB | | |
|----| |----| Match 1
| | | |
+----+ +----+
+----+ +----+
| AC | | |
|----| |----| Match 2
| | | |
+----+ +----+
+----+ +----+
| AD | | |
|----| |----| Match 3
| | | |
+----+ +----+
...etc.
How are we going to represent this in code? Let's try representing the tournament as a list of matches, and each match as a list of pairs, where pairs[0] plays pairs[1] on Court 1 and pairs[2] plays pairs[3] on Court 2. Actually, each pairs entry will be a list of remaining pairs that can go in that position. Something like:
matches = [
# Match 1
[['AB'], ['BC', 'BD', ...], # Choices for court 1
['EF', 'EH', ...], ['FG', 'FH', ...]], # Choices for court 2
# Match 2
[['AC'], ['BD', 'BE', ...], # Choices for court 1
['EF', 'EH', ...], ['FG', 'FH', ...]], # Choices for court 2
...
]
Implementation
Now we're getting somewhere. So, the board state class will look something like:
PLAYER_IDS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
class PickleBallBoardState(object):
def __init__(self, n):
allpairs = []
for i in xrange(n):
for j in xrange(i+1, n):
allpairs.append(PLAYER_IDS[i] + PLAYER_IDS[j])
print allpairs
n_courts = n / 4
positions_per_court = 2
n_matches = n - 1
self.matches = []
for i_match in xrange(n_matches):
match = []
for i_position in xrange(n_courts * positions_per_court):
match.append(list(allpairs))
self.matches.append(match)
I've found that a "is_placed" data structure is helpful when doing these problems, to easily distinguish the case where a position has a single choice available, but hasn't yet had the constraints propogated. So, let's add a placed structure of boolean values with a similar match/position structure:
self.placed = []
for i_match in xrange(n_matches):
self.placed = [False] * n_courts * positions_per_court
Finally, let's fill in those initial choices that prevent certain types of duplicate solutions. Meaning, AB will always be in match 1, AC in match 2, AD in match 3, and so on. We'll use the "place" function which will start removing constrained choices.
for i_match in xrange(n_matches):
self.place((i_match, 0), PLAYER_IDS[0] + PLAYER_IDS[i_match + 1])
Now for some of the good stuff. Let's do some easy functions first, then come back to the constraint enforcing place function.
def unable_to_solve(self):
return any(not choices for choices in iflatten2d(self.matches))
def is_solved(self):
return all(len(choices) == 1 for choices in iflatten2d(self.matches)) \
and all(iflatten2d(self.placed))
Okay, I can't resist a little premature pythoptimization. I've used a little flatten utility that returns an iterator so we don't have to double loop through matches then positions. For the following functions, we'll actually need to do the double loop, though:
def canplace(g):
for i_match, match in enumerate(self.matches):
for i_pos, choices in enumerate(match):
if len(choices) == 1 and not self.placed[i_match][i_pos]:
return (i_match, i_pos)
return None
def first_position_with_choices(self):
for i_match, match in enumerate(self.matches):
for i_pos, choices in enumerate(match):
if len(choices) > 1:
assert not self.placed[i_match][i_pos]
return (i_match, i_pos)
return None
def choices(self, location):
i_match, i_pos = location
return self.matches[i_match][i_pos]
Now it's just the place function. It should consist of setting the fixed choice for that position, then removing all the other choices due to the constraints. It gets a little complicated, though, since one of the constraints depends on the number of times one player has played another. So, lets add that as a member variable and only update it when place is called
def _filter_out_players(self, i_match, i_pos, players):
if not self.placed[i_match][i_pos]:
self.matches[i_match][i_pos] = filter(
lambda c: (c[0] not in players) and (c[1] not in players),
self.matches[i_match][i_pos])
def _blocked_players(self, players):
blocked_set = set()
for player in players:
blocked_set.update(p for p, count in self.play_counts[player].iteritems() if count >= 2)
return blocked_set
def place(self, location, choice):
placed_match, placed_pos = location
assert not self.placed[placed_match][placed_pos]
# First check if we are completing a versus match
opposing_pos = placed_pos + 1 if placed_pos % 2 == 0 else placed_pos - 1
completing_versus = self.placed[placed_match][opposing_pos]
# Place the choice
self.matches[placed_match][placed_pos] = [choice]
self.placed[placed_match][placed_pos] = True
# Remove all other instances of this pairing
for i_match, match in enumerate(self.matches):
for i_pos, choices in enumerate(match):
if not self.placed[i_match][i_pos]:
try:
choices.remove(choice)
except ValueError:
pass
# Remove all choices containing these players from this match
for i_pos in xrange(len(self.matches[placed_match])):
self._filter_out_players(placed_match, i_pos, choice)
# Make sure person only plays against another player maximum twice
if completing_versus:
self._update_play_counts(placed_match, placed_pos)
for i_match, match in enumerate(self.matches):
for i_pos, choices in enumerate(match):
opposing_pos = i_pos + 1 if i_pos % 2 == 0 else i_pos - 1
if self.placed[i_match][opposing_pos] and not self.placed[i_match][i_pos]:
self._filter_out_players(
i_match, i_pos,
self._blocked_players(self.matches[i_match][opposing_pos][0]))
return self
That's pretty much it. A quick little pretty printer and solver function and we're done.
def solnstr(self):
lines = []
for i_match, match in enumerate(self.matches):
lines.append(('Match %d: ' % (i_match + 1)) + \
', '.join(match[ipos][0] + ' vs ' + match[ipos+1][0]
for ipos in xrange(0, len(match), 2)))
return '\n'.join(lines)
def solve(n):
board = PickleBallBoardState(n)
return chooser(board)
Results
Running
print solve(8).solnstr()
gives
Match 1: AB vs CD, EF vs GH
Match 2: AC vs EG, BD vs FH
Match 3: AD vs EH, BC vs FG
Match 4: AE vs BF, CG vs DH
Match 5: AF vs CH, BE vs DG
Match 6: AG vs DF, BH vs CE
Match 7: AH vs BG, CF vs DE
Great! It worked. All pairings are represented and no player plays another one more than twice.
Trying with n=12 looks to be too slow to finish quickly, and require some more cleverness. Maybe have to do that in a future post. Some quick tests imply that the deepcopy operation is pretty slow, especially with the overly-clever nested datastructures.
You can get the full source here.
