Create Hungarian-based two-team draw generator

[tienne-B]

To have a more powerful conflict avoidance than one-up-one-down, a Hungarian draw generator similar to the one for BP could be created using penalties as costs. The penalties could then be balanced with the allocation method (slide, fold, etc.) if necessary.

[czlee]

Ah, this would be quite the project 😅 but I guess it's not too dissimilar in principle to the BP draw generator.

[austinredmond]

Thanks for opening an issue. I have some done some hand draws assisted by whatever algorithm chutabs uses. What materials should I familiarize myself with if I wanted to attempt some work on this project?

[tienne-B]

ChuTabs uses a similar algorithm to the one we currently use to resolve conflicts, but continues trying to swap until a pairing is found without conflict. In that, there is no concept of "penalties" in ChuTabs and will attempt to resolve any conflict. The code in ChuTabs is in lib/inc.pairing.cp.php if you want. (I just downloaded it from SourceForge; hadn't looked at its code until now) To implement such a system in Tabbycat, you'd need to adapt tabbycat/draw/generator/one_up_one_down.py (in a new generator) to want to swap to the closest "unencumbered" team (or where the conflict is strictly less than in the current matchup, although that'd be more hybrid). This would be simple enough to implement, with the swapping mechanism already there, and lots of comments to explain what the code does. You'll then want to add the feature in tabbycat/draw/generator/powerpair.py (with "avoid_conflicts"), add a few flags to tabbycat/draw/generator/init.py and finish it off by adding it as a preference (and document, of course): https://github.com/TabbycatDebate/tabbycat/blob/fde12c67b626e44c6eb8d0fda100326c02ba909c/tabbycat/options/preferences.py#L223-L234

For random draws where ranks are less important, you could take a look here: https://github.com/TabbycatDebate/tabbycat/blob/fde12c67b626e44c6eb8d0fda100326c02ba909c/tabbycat/draw/generator/random.py#L47-L70

However, I feel that this proposed solution is a somewhat crude heuristic, without assigning any cost to upending the pairing method, and not trying to minimize the "global" conflict cost, where it could leave big conflicts over solving smaller ones. This is why I proposed adapting the BP draw generator to 2-team formats, giving costs to pairing/position imbalances and countering with conflict costs. Your (/ChuTabs's) approach could well be useful though; and don't hesitate to ask if you encounter any problem!

[czlee]

Yeah, it's worth adding, the draw generator code is one of the more intricate parts of our code base, so definitely don't be afraid to ask if anything's unclear. To elaborate a little on what @tienne-B said:

The basic structure should, in principle, go like this (with reference to the code block below):

1. Write a new method in PowerPairedDrawGenerator (probably insert it just after _one_up_one_down())
2. Add it to the AVOID_CONFLICT_METHODS dict in the same class. The key is a sort of reference name not seen by humans. The key is the name of the method you just wrote (but as a string).
3. Add it to DrawAvoidConflicts.choices in tabbycat/options/preferences.py (as noted by @tienne-B above).

https://github.com/TabbycatDebate/tabbycat/blob/fde12c67b626e44c6eb8d0fda100326c02ba909c/tabbycat/draw/generator/powerpair.py#L352-L389

Your new method should take and return a list of Pairing objects. It's totally cool (and expected) to modify the Pairing objects in-place. It's a good idea to add flags to affected pairings, as we do in lines 383–389 above. If you do, add the human-readable names of said flags to DRAW_FLAG_DESCRIPTIONS: https://github.com/TabbycatDebate/tabbycat/blob/fde12c67b626e44c6eb8d0fda100326c02ba909c/tabbycat/draw/generator/__init__.py#L13-L17

The existing _one_up_one_down() method delegates the algorithmic part to a different class in tabbycat/draw/generator/one_up_one_down.py. This isn't strictly mandatory, though the one-up-one-down method does this because the algorithm's so complicated that it would clutter the draw generator class. (Well, sort of—the real reason is that it was its own file when we inherited Tabbycat, and I wasn't inclined to change that.) Since your conflict avoidance method will probably be at least as complex as one-up-one-down, I recommend doing similarly.

I agree with @tienne-B that adapting the principle behind the BP draw generator is likely to be a better solution, and/but also agree that you should run with whatever approach you have in mind if you think it'll work!

I'd suggest starting by just verifying that you can add a trivial conflict avoidance method first—like, one that does nothing, or just randomly flags and swaps one debate for no reason, so that you can choose this new method under preferences. When you have that going, you'll know you understand the framework, and can get on with the fun stuff 🙂

[austinredmond]

@czlee @tienne-B Thanks for the advice. I might have to try both. It would be simpler for me to port over the chutabs algorithm because it has already been written. A good first step for me. Given the more complete and long term solution is to figure out the Hungarian draw generator then I am going to have to attempt that too.

[austinredmond]

Is it possible to force perfect position balance too? Especially because a lot of tournaments call for teams to debate both sides of a prepared topic before moving to bracketed rounds.

[tienne-B]

With an even number of rounds, yes. In your method, this would require teams to be assigned the position least debated and swapped only with teams on that side. However, that does halve the available teams to avoid instututional/history conflicts. To mitigate that, you would try to have the most teams of each institution on particular sides.

For the Hungarian method, you would create a "side penalty" and apply it to the side most debated (and you could do cool tricks to magnify the penalty).

[czlee]

Is it possible to force perfect position balance too?

It depends what you're willing to sacrifice. As well as the reduced conflict avoidance options @tienne-B raises, you'll probably also be forced to break brackets for this to work. For example, if after some number of rounds, three of the four teams on 4-1 have affirmed three times, and the fourth team has affirmed twice, do you take two pull-up teams to negate from the 3-2 bracket, or do you let one team affirm a fourth time?

Heads-up: The current draw generation system for two-team formats works on the assumption that first you pair teams (and avoid conflicts), then you assign sides, taking pairings as fixed. But this doesn't necessarily prevent you from taking side history into account when you pair teams. It just won't assign sides until later in the process.

Also, I just realized something we forgot to mention. The Hungarian method on which the BP draw generator is based replaces everything in the draw generation process after making brackets (so: make pairings, conflict avoidance, side assignment), because it does all those three steps at once. When you get round to that route, it'd basically be writing a new version of bphungarian.py for two-team formats.

(Some of that might not make sense before you dive into the code and start trying things out, so if any of it flew over your head, just ignore it for now and we can discuss again when the time comes 🙂)

[austinredmond]

Given the requirements it seems to be a larger departure from the draw generation system than anticipated. The requirements I mentioned only apply to the first two rounds of a tournament. Someone on the Tabbycat group asks for similar features.. There is a hand-tabbing workaround but I would like to automate the process within Tabbycat. Prioritizing position balance as the first requirement and then doing pairings might be a second issue to be opened.

To illustrate, if there are 30 teams and 9 win on prop and 6 win on opp in the first round, then there would be two scenarios. One, bracketing is present, so 3 teams that lost on opp are pulled-up to 1-0 bracket. Two, bracketing is not present (by generating the draw before round 1 is completed), and then the full pool of teams is used and every team will debate the position least debated (I hope this is possible).

I am going to create my own branch and start messing around with the code. That might spawn some new questions!

[czlee]

You might be able to get some inspiration from the classes RandomWithAllocatedSidesDrawGenerator and PowerPairedWithAllocatedSidesDrawGenerator. They don't quite do the same thing—they're for tournaments where sides are allocated before the tournament starts. (As in, the tournament is fully prepared, so teams are told both motions and sides for all rounds before the tournament begins, and pairings are power-paired but have to respect side allocations as a hard constraint.) Your situation is a little different, in that sides are only locked after the previous round is drawn, but I think the underlying principles should be the same… like, I think the actual pairing logic is identical, it's just changing how/when the side lock is noted.

Bonus points if you can figure out how to subclass those classes (or add a parent class or whatever) to add only the logic you need. 😀

Feel free to ask questions whenever suits! We can rename this issue if necessary when things clear up.

[tienne-B]

As an update, a Hungarian-type draw generator would also be beneficial for APDA, especially for the first round which is seed-based (#2165). This optimisation problem should be done after deciding on pull-ups (and byes if implemented).

The assignment matrix would be all teams as both rows and columns, so the axis can represent the side the team will debate. These are the components to be considered for the cost calculation between teams (+ sides) for the best pairings in an approximate order of importance:

• Same team Assign $M$ to forbid.
• Seen opponent before (history) Check previous draws for history between teams (done in DrawManager and placed as team.side_history attribute). If seen, assign team_history_penalty ($P{history}$) as $P{history} \times n_{seen}$
• Institution-institution conflicts Check between TeamInstitutionConflicts of both teams for a non-null intersection. Assign team_institution_penalty preference value.
• Re-hitting pull-up This is not currently taken into consideration anywhere in Tabbycat, but seems important for APDA (see MIT-Tab docs). Check history if any opponent has the pullup draw flag and if so, apply a new penalty (to add to preferences) where it meets the pull-up team.
• Side imbalance If assigning a team to the side would exaggerate an existing imbalance, add the existing imbalance, say for $T1$ where $S{gov}=0$ and $S{opp}=2$, assigning them as "opp" would have the following calculation: $$\text{abs}(S{gov}-(S_{opp}+1))-1=2$$ Add both team-side's calculations to the cost, and multiply by a new preference coefficient. Note: This penalty only applies if using "balance" draw_side_allocations.
• Draw pairing deviation Depending on the draw_pairing_method preference, the penalty should be the difference of the intended pairing times a coefficient, e.g. if folding between 8 teams, the 1-8 would have a difference of 0 while 1-6 would have a difference of 2. A new preference should be added as a penalty coefficient value here.

If using preallocated sides, the matrix can be set for the teams to only be on the axis of their assigned side. Otherwise, sides could either be assigned from the result of the optimisation, or passed along, which would likely have the same assignations if set for balance.