etopiei's blog

A blog about minimalism, programming, productivity and happiness.
All Posts - RSS Feed

Solving Netball Positions for Fun And Winning?

I recently started a netball team with a group of friends. This has been a tremendous experience. The team culture is awesome, we have lots of fun (despite our limited success) and I've really enjoyed meeting new people and bringing groups together.
That aside, I found early in our first season some stress around setting the positions for everyone. Initially the team was small enough that everyone could basically work it out among themselves. However the team quickly grew, and managing the positions so they were fair, as well as playing to people's strengths quickly became a chore.
Thankfully, I saw this as an opportunity, and spent the next week hacking away.

The Idea

The idea was pretty simple. I figured there were two things we wanted to solve for:

  1. Equal Game Time (or as near as possible)
  2. People playing in positions they like

Having worked with MiniZinc a little bit in university I was confident hopeful that I could write a solution relatively easily.

Intro to MiniZinc

MiniZinc is a 'constraint modelling' programming language (developed at my Alma Mater - Monash University). It's unlike any other language I've really worked with, in that it is primarily declarative. Meaning that you only tell the computer 'what' you want not 'how' to do it. This is quite an adjustment in thinking compared to regular programming, however thankfully this sort of thing is a well-suited problem, so there were many examples online of similar enough problems to get me most of the way there.
Let's take a look at a simple MiniZinc example first to get a taste of it:

var 1..3: x;
var 1..3: y;
constraint x + y > 2;
solve satisfy;

(Unfortunately highlight.js - the syntax highlighter used by my blog does not support MiniZinc yet)
While this code might look a little funny at first, given some time you may be able to make a reasonable guess at what it does. And you'd be right!
This type of problem (solving linear equations) is MiniZinc's bread and butter. Let's give a quick run-down of this example
We first define two variables (x and y) - these are variables in the more mathematical sense (compared to the programming sense). We also define their bounds to be between 1 and 3.
We then set a 'constraint' on these variables that 'x' + 'y' must be greater than 2. This is where MiniZinc's magic really kicks in.
The final directive solve to 'satisfy' is what sets MiniZinc going. It will attempt to find compatible values for all variables, such that all the constraints are satisfied.
In this case there are lots of options, MiniZinc will simply output the first solution it finds.

Side Note: There are several types of ways to solve. The main ones are: 'satisfy', 'maximise' and 'minimize' and each of these do more or less what it sounds like.

Modelling Netball Positions

So, now we have a bit more of an idea of how MiniZinc works - how do we translate this method of problem solving onto our netball team dilemma?
There are a couple of constraints on the netball team. Let's map these out one by one and see how they translate to MiniZinc's declarative syntax.
1. We have 7 positions to assign to players:

enum positions = { GS, GA, WA, C, WD, GD, GK }
enum people;
array[people] of var positions: assigned;

2. No person can be in more than one position

constrain alldifferent(p in people) (assigned[p]);

(Note: MiniZinc has some built in helpers - `alldifferent` is one of these.)
3. No more than 1 male per third (this was the tricky one!)

var int: malesInForward;
var int: malesInCentre;
var int: malesInDefence;

var int: maleInGS;
var int: maleInGA;
var int: maleInWA;
var int: maleInC;
var int: maleInWD;
var int: maleInGD;
var int: maleInGK;

constraint maleInGS = if exists (m in Males) (assigned[m] = GS) then 1 else 0 endif;
constraint maleInGA = if exists (m in Males) (assigned[m] = GA) then 1 else 0 endif;
constraint maleInWA = if exists (m in Males) (assigned[m] = WA) then 1 else 0 endif;
constraint maleInC = if exists (m in Males) (assigned[m] = C) then 1 else 0 endif;
constraint maleInWD = if exists (m in Males) (assigned[m] = WD) then 1 else 0 endif;
constraint maleInGD = if exists (m in Males) (assigned[m] = GD) then 1 else 0 endif;
constraint maleInGK = if exists (m in Males) (assigned[m] = GK) then 1 else 0 endif;

constraint malesInForward = maleInGA + maleInGS;
constraint malesInCentre = maleInWA + maleInWD + maleInC;
constraint malesInDefence = maleInGK + maleInGD;

constraint malesInForward < 2;
constraint malesInCentre < 2;
constraint malesInDefence < 2;

Honestly, this is a little verbose, I'm sure there would be a better way to do this, but I couldn't work it out. So instead I used this, and it works well enough.
4. We want to maximise people getting the positions they would like

array [people] of var int: score;
constraint forall(p in people) (
  score[p] = pref[p, assigned[p]]

solve maximize sum(score);
This one is a little trickier. Basically what I did was ask everyone in the team to rate their preferred positions. Giving a higher score to their favourite position and a lower score for their dis-liked positions.
This meant we wanted the model to find a valid combination (taking into account rules 1->3) that gets the best score in overall team happiness.
There are a couple of details I skimmed over a little bit - for instance you may have noticed the 'people' enum is blank, as a group of 7 is selected at a time and the best team found from these.


It took me quite a few hours to build this model (as I've not worked with MiniZinc much before) but since then it has been pretty smooth sailing.
To generate all the team combinations I wrote a python script that iterates over all possible valid team combinations and runs the MiniZinc model to find the best positions, it looked something like this (simplified):

for court_players in itertools.combinations(people, 7):
    # We are only interested in combinations with >= 4 women
    court_females = [player for player in court_players if player in females] 
    if len(court_females) >= 4:
        # Find the best court positions for this combination.
        court_males = [player for player in court_players if player in males] 
        court_preferences = []
        for player in court_players:
            court_index = people.index(player)
        result = findBestPositionsForPlayers(court_players, court_males, court_females, court_preferences)
        results["positions"].append({"sorted_team": sorted(court_players), "team": court_players, "positions": parts[0], "match": match})

I then attached this to a website (whose design I won't subject you to) where you can select 7 players and it will spit out the pre-generated best team. The problem with this is that with ~18 people having filled out the survey there is ~14k possible teams (last I checked) and all these calculations take about 3 hours. This is fine for now, because once it's calculated we are all good. But should the team grow much bigger this may become infeasible.


The results have been good overall I think. We now make the team on the morning of the game, using the website and some handy excel to work out who will play where each quarter. (this painstaking work is done by two of my fantastic team-mates - did I mention yet how great this team is?)
It has made things much clearer, ensured people get a fair amount of game time and has reduced the management effort on game day.
There are two issues that I see with this approach however:

  1. The model doesn't yet handle quarters/bench
  2. If someone is injured (an unfortunately regular occurrence) it falls down
For 1, I think with a little more tweaking the model could handle the bench and assigning positions over quarters, but this is work that I haven't had sufficient time/motivation for.
On the second point, I think there's not much to do. Unfortunately no matter how nicely you craft a solution, it must, at one point or other deal with the messiness of the real world. Which is a lesson in and of itself.
I think that about wraps it up. It's been fun making this little tool. I really enjoy making tools that are useful in little niches and this one certainly scratched one of my itches.
Oh, and for those playing at home, I'm afraid this did not effect our win percentage, which remained at zero for quite some time. Turns out there's not an algorithm for everything...

Also See

If this post interested you at all, please check out MiniZinc, it is a super awesome, and you'd be surprised the problems you can solve with it, that were previously out of reach.
Thanks for reading.

- etopiei (31/05/21)

< Previous Post Next Post >

Post History