Improve clan balance

[GoogleFrog]

https://zero-k.info/Battles/Detail/1653856

Soridian and Omega[TheEnd] left this game after suggesting it be exited because they were on VC and had already played a few split games, so gave up on being balanced to the same team and did something else with their evening. I feel like the balancer could have tried harder to put clans together in the game. Perhaps the clan balance fallback should be restricted in the case of clan-pairs in a sufficiently large game. Also ideally, if clan balance is not accepted by the balancer then it could drop the clans that cause issues, rather than ignoring all clans.

[Licho1]

Does it happen more often? Max cbalance difference is set to 70.
By dropping clans that cause the problem you mean to try them randomly and see when balancing without them works?

[sprunk]

Yeah, let's say there's clan A (with 2 players), clan B (with 2 players), and clan C (with 3 players) in the room. Then the idealized algorithm would be:

1. try a balance where A is kept together, B is kept together, and C is kept together. If this is under cbalance threshold, use that.
2. otherwise, keep A together and B together, but split C, because they're the largest clan. If this is under cbalance threshold, use that.
3. otherwise, try (keeping A together and C together but splitting B) and (keeping B together and C together but splitting A), since that still only splits 1 clan. If the best of these two is under cbalance threshold, use that.
4. otherwise, try (keeping A together but splitting B and splitting C) and (keeping B together but splitting A and splitting C), since that keeps a small clan together. If the best of these two is under cbalance threshold, use that. If the best is under cbalance threshold, use that.
5. otherwise, try keeping C together but splitting A and splitting B. If this is under cbalance threshold, use that.
6. otherwise, split all clans (ie. use regular balance).

Current does 1 and then immediately 6 without any of the steps inbetween.

This is the idealized version so in practice will probably not be attainable because it grows exponentially with the number of clans. On the other hand if there are many clans then splitting the largest one should already grant good results, and keeping the smaller clans together means there's far fewer permutations to try? Hard to tell. Still, picking the clan to split randomly or via some simple algorithm would still be an improvement.

Alternatively, a comparator for permutations, so the permuting would be done once (current does twice if cbalance doesn't give good enough results the first time) but more calculations done per each:

1. if new permutation is below cbalance threshold and current is above, new is better.
2. if new keeps more clans together than current (by happenstance, clanmates would still be permuted individually as in regular split balance) and both are above or both below the threshold, new is better.
3. if new keeps as many clans together as current, but fewer clanmates in total, new is better (prefer smaller clans).
4. if new has smaller difference or deviation (in whatever way these two are weighted against each other currently), new is better.