8 coaches online • Server time: 02:42
* * * Did you know? 196 games were played yesterday.
Recent Forum Topics  How do you beat Tomb... | Convince a friend to... | Norse coach looking ... |
2024-06-25 11:47:16
9 votes, rating 6
9 votes, rating 6
Steel Gauntlet qualifying algorithm
There's a thread on the forum with a suggestion for a change of how the wildcard slots are picked for the Steel Gauntlet tournament. In this thread, the question came up of how the wildcard slots work currently which is a pretty complicated algorithm. Instead of describing it in a forum thread, I'll do a longer write-up here to make it slightly easier to refer to.
Background
The Steel Gauntlet is a tournament that takes place at the end of a Blackbox Trophy (BBT) season, pairing the best performing teams for each roster against each-other in a play-off.
Given that there are currently 29 rosters in the game, I chose to aim for a 32 team tournament filling up the remaining slots with "wildcards" that are picked as the best over-all performing team in the BBT season.
Core constraints
There are some inherent restrictions to a system like this. As per the core design choice, we want one team of each roster in the tournament (if possible).
It is fairly common for the strongest coaches to have multiple qualifying teams, and the site allows coaches to set up a priority for which team they would rather bring should they have the choice. It is also possible to completely opt out of a spot with a team, whould it be too broken to feel competitive.
Algorithm
The way the pairings work is based on the Stable marriage problem, and fundamentally uses a modified version of the Gale-Shapley algortihm. I will explain how the site does it here, but if you want more "formal" descriptions, the linked Wikipedia articles are a good place to begin.
We begin with some definitions:
- Each of the 32 spots get defined as "acceptors" (as per the Gale-Shapley algorithm). This means that the spot is the side that decides which of the offers it should accept. The first 29 are "locked" into a specific roster, while the remaining 3 accept any team.
- Each participating coach get defined as "proposors". This means that a coach will send out offers to each spot as the algorithm progresses.
With each coach having potentially multiple teams, and these are all set up in a priority list, it gets a little bit complicated to understand how that maps to the above. So, here's an example:
Coach Alice has two teams they wish to bring to the Gauntlet: Underworld and Orcs, in that order of priority.
The pairing algorithm sets up priority lists as follows:
Alice:
- Underworld to the Underworld slot
- Underworld to wildcard slot 1
- Underworld to wildcard slot 2
- Underworld to wildcard slot 3
- Orcs to the Orc slot
- Orcs to wildcard slot 1
- Orcs to wildcard slot 2
- Orcs to wildcard slot 3
You'll notice that each team Alice wishes to bring will create multiple offers (one offer per eligible slot it could be accepted into).
The core algorithm itself has two steps that get repeated until there are no remaining offers:
1. Offers
Each coach that isn't currently matched (meaning they have an offer that is currently "selected" by a slot, more on this in step 2), takes their topmost offer and sends it to the slot.
2. Selection
Each slot takes the list of offers and picks the best one (by score and tie-breakers), and compares it to their currently selected offer (if any). If the new one is better, the previous offer is dropped and the new one is "selected". An offer that is not selected, or is dropped will be removed from the owning coach's list.
As simple as that looks, that's it. When there are no longer any new offer sent out in step 1 (meaning all unselected coaches have zero items remaining in their lists), the selected teams for each slot is the teams that qualified to the tournament.
If there are any slots that have no offers (which happened when gnomes were given a slot), the whole process is run again with only those remaining slots, setting them to wildcards that accept any roster.
Hopefully, this was interesting to some of you :)
Background
The Steel Gauntlet is a tournament that takes place at the end of a Blackbox Trophy (BBT) season, pairing the best performing teams for each roster against each-other in a play-off.
Given that there are currently 29 rosters in the game, I chose to aim for a 32 team tournament filling up the remaining slots with "wildcards" that are picked as the best over-all performing team in the BBT season.
Core constraints
There are some inherent restrictions to a system like this. As per the core design choice, we want one team of each roster in the tournament (if possible).
It is fairly common for the strongest coaches to have multiple qualifying teams, and the site allows coaches to set up a priority for which team they would rather bring should they have the choice. It is also possible to completely opt out of a spot with a team, whould it be too broken to feel competitive.
Algorithm
The way the pairings work is based on the Stable marriage problem, and fundamentally uses a modified version of the Gale-Shapley algortihm. I will explain how the site does it here, but if you want more "formal" descriptions, the linked Wikipedia articles are a good place to begin.
We begin with some definitions:
- Each of the 32 spots get defined as "acceptors" (as per the Gale-Shapley algorithm). This means that the spot is the side that decides which of the offers it should accept. The first 29 are "locked" into a specific roster, while the remaining 3 accept any team.
- Each participating coach get defined as "proposors". This means that a coach will send out offers to each spot as the algorithm progresses.
With each coach having potentially multiple teams, and these are all set up in a priority list, it gets a little bit complicated to understand how that maps to the above. So, here's an example:
Coach Alice has two teams they wish to bring to the Gauntlet: Underworld and Orcs, in that order of priority.
The pairing algorithm sets up priority lists as follows:
Alice:
- Underworld to the Underworld slot
- Underworld to wildcard slot 1
- Underworld to wildcard slot 2
- Underworld to wildcard slot 3
- Orcs to the Orc slot
- Orcs to wildcard slot 1
- Orcs to wildcard slot 2
- Orcs to wildcard slot 3
You'll notice that each team Alice wishes to bring will create multiple offers (one offer per eligible slot it could be accepted into).
The core algorithm itself has two steps that get repeated until there are no remaining offers:
1. Offers
Each coach that isn't currently matched (meaning they have an offer that is currently "selected" by a slot, more on this in step 2), takes their topmost offer and sends it to the slot.
2. Selection
Each slot takes the list of offers and picks the best one (by score and tie-breakers), and compares it to their currently selected offer (if any). If the new one is better, the previous offer is dropped and the new one is "selected". An offer that is not selected, or is dropped will be removed from the owning coach's list.
As simple as that looks, that's it. When there are no longer any new offer sent out in step 1 (meaning all unselected coaches have zero items remaining in their lists), the selected teams for each slot is the teams that qualified to the tournament.
If there are any slots that have no offers (which happened when gnomes were given a slot), the whole process is run again with only those remaining slots, setting them to wildcards that accept any roster.
Hopefully, this was interesting to some of you :)
Comments
Posted by Candlejack on 2024-06-25 14:12:41
"An offer that is not selected, or is dropped will be removed from the owning coach's list."
Dropped means dropped by the last slot that was accepting that offer? As an offer can be proposed to multiple slots it might be accepted by multiple slots, correct?
Dropped means dropped by the last slot that was accepting that offer? As an offer can be proposed to multiple slots it might be accepted by multiple slots, correct?
Posted by Christer on 2024-06-25 15:16:12
Dropped in that context means canceling an offer that was made in the previous iteration.
An offer is specifically one team to one slot, and never changes. To handle the multiple slots, you have the 4 offers per team (main slot, 3x wildcard slots). So an offer is made once, and if rejected (immediately, or in a later round) it's discarded and ignored for the rest of the process.
An offer is specifically one team to one slot, and never changes. To handle the multiple slots, you have the 4 offers per team (main slot, 3x wildcard slots). So an offer is made once, and if rejected (immediately, or in a later round) it's discarded and ignored for the rest of the process.
Posted by Garion on 2024-06-25 15:42:12
Perfect :)
If/When GW release a new Team/Roster, will the Wild card number be reduced to 2?
If/When GW release a new Team/Roster, will the Wild card number be reduced to 2?
Posted by Carthage on 2024-06-25 16:18:34
I love these technical posts from you Christer. Its like a cliffnotes from a lecture in a collegiate math class.
Posted by The_Murker on 2024-06-25 16:56:46
Fixing the tournament code must be like tidying up my basement. I'd say, 6 of 7 days a week, I'd rather enjoy writing a blog post like this rather than clean up my basement, which the wife says is a priority.
(Or maybe Big C finished the re-code.. or maybe this post is like his pre-breakfast brain warm-up!!)
@Carthage.. I like them too.
(Or maybe Big C finished the re-code.. or maybe this post is like his pre-breakfast brain warm-up!!)
@Carthage.. I like them too.
Posted by Christer on 2024-06-25 19:33:40
The tournament re-work is mostly done, except for some inevitable bugfixes. This was just a distraction while I switch my head back into the re-drafting context.
Posted by Igralius on 2024-06-26 11:33:17
This maybe be a stupid question but what happens in the following scenario? I got first in for example amazons. Now I delete the Team because Reason XYZ. Even though the Team no longer exists (under active teams) it is still listed in Blackbox team rankings. Does it still send an offer and if so is there a chance that a slot gets occupied by a deleted team? Haven't checked if you can still change preferences once you deleted a team or if it automatically goes to "not interested in qualifying"
Posted by Christer on 2024-06-26 13:36:53
Only "eligible" teams are considered. Retiring a team inherently makes it ineligible, as does playing additional matches, or leaving it in post-match state.