## Optimizing Triple Knockout Tournaments in Curling

This post is about **Curling** - interested in giving it a try? You can try it for free on the **Family Day** on October 12th 2024 in Berne:

One common tournament mode in Curling is Triple Knockout. Triple Knockout is easy to explain for a single team: You start in the A road, and as long as you win your games, you stay there. If you lose, you drop to the B road, and if you lose again, you drop to the C road. If you lose again, you're out. That's why it is called "Triple Knockout" - you get 3 chances to make it to the last stage of the tournament.

For example, the yearly IBDC in Bern is held this way. There are 2 teams in the game A01. The winner will continue to A09, and the loser will drop to B01. There they will meet the loser from A02:

(The D-games are the "Consolation Cup" for the best teams that didn't make it to the Finals.)

As you can see, the tournament structure gets a bit complex. Above is the case for 16 teams, there are also brackets for 24 and 32 teams.

## Avoiding double encounters

During a tournament, it is generally being avoided (if possible) that teams play each other more than one time - teams don't want to play multiple times against the same opponent, and also for the audience it's more interesting to have different encounters every time.

To optimize for the least amount of those "double encounters", we can build the structure of the tournament accordingly, that the chances are as low as possible for double encounters.

If we have the tournament structure, we can simulate possible tournament progressions and check how many double encounters will happen on average (Monte Carlo method).

To describe the tournament structure, I use a simple text format. It the tournament above:

```
*A01 A09 B01
*A02 A09 B01
...
A09 A13 B07
...
A13 - B10
...
B01 B05 C01
B02 B05 C01
...
B05 B09 C05
C01 C03 -
C02 C04 -
...
C06 - -
```

(You can find the complete file here.)

- Each row has 3 components: Name of the game, follow-up game for winner, follow-up game for loser. These are separated by a space. For example "A09 A13 B07" means, the name of the game is A09, the winner will go to A13, the loser to B07.
- If the row starts with an asterisk, it will be "seeded" with teams on Simulation start.
- An empty line means that a new "block" starts, which is only used for optimization. It defines the games that can be exchanged. For example from A01, the winner team could go to A12 (instead of A09) as above, but not to A13.
- A "-" means, the team is out or no longer relevant for the simulation (e.g. D-Road or consolidation cup).

## Running a tournament simulation

With the tournament structure at hand, we can now simulate many tournaments and see how many encounters we get on average. We can just create a lot of tournaments (for example one million) and toss a coin for every outcome when two teams meet.

You can check out the source code here: github.com/akleemans/curling-triple-ko.

If we now let the simulation run, we get the following result:

```
Executing ':Main.main()'...
roadRoundMap:{B01=3, B02=3, C02=6, B03=3, C01=6, B04=3, C04=7, B05=4, C03=7, *A05=0, B06=4, C06=8, *A06=0, B07=4, C05=7, *A07=0, A09=1, B08=4, C08=8, *A08=0, B09=5, C07=8, *A01=0, *A02=0, *A03=0, *A04=0, A10=1, A11=1, B10=5, A12=1, B11=5, A13=2, A14=2}
16_ibdc22.txt got score: 1.0001719
```

So on average, there would be 1 double encounter on the IBDC 2022!

## Optimization

With the tournament structure in text format, we can make changes to it (for example swap two teams) and let the simulation run again, to see if the structure is better than before. If we repeat the process, we can optimize for the lowest possible "double encounter"-score that we can find this way. (One caveat is that the structure must still be valid though.)

This is somewhat a very simple version of a Genetic algorithm, and doesn't guarantee to find the best score, but it let's us start quickly and see if we can improve.

To try it yourself, you can run a pre-built docker image:

`docker run -d -p 8080:8080 adrianus/curling-triple-knockout:latest`

Once started, you can open http://localhost:8080 and it will greet you with a UI:

You can then enter the tournament structure, some additional parameters (like how many tournaments to simulate) and let it run:

If we try it with the tournament above, it finds out that we get better results by swapping where the losers of B01 to B04 land:

These small changes give a new score of around 0.3755. That means we were able to **reduce the number of double encounters by 62%!**

You can find the complete optimized tournament structure here.

## Results with other tournaments

Using a simple text permutation, I was able to optimize the following tournament structures to have less double encounters:

- 16 teams - IBDC 2022: 1 → 0.3755 double encounters
- 24 teams - IBDC 2019: 0.96 →0.665 double encounters
- 32 teams - GP Inter 2022: 1.562 →0.978 double encounters
- 32 teams - IBDC 2020: 1.975 →0.99 double encounters

The source code and tournament structures are available here: github.com/akleemans/curling-triple-ko.

Happy optimizing!