dan in each team, 5k in each team,
4k in one, 3k in other
looks almost perfect to me
3k+5k+2d is stronger than 5k+4k+1d.
Teams would have been more balanced by reversing dan players, for example.
Nothing too serious, I just wanted to report that the proposed solution is not the best one IMHO 
3 Likes
Trying to minimize the difference of average ranks would require a more complicated algorithm. The current algorithm is good enough to avoid severe imbalances.
3 Likes
I think the current algorithm does attempt to minimize difference in average ranks. While it’s nearly impossible to design a perfect (and efficient) algorithm I think it’s productive to bring up this relatively simple counterexample.
Edit: might help to gather relevant details (rating AND rank, and share them on the PR)
5 Likes
Done
3 Likes
Are you sure?
@Groin pretty sure.
That said, there’s no harm in trying for a better algorithm. Perhaps something like Thue-Morse, where white gets the top player, black gets the next two, white gets the next two and so on…
3 Likes
With small quantities seems easy and it is where it matters
2 Likes
correct.
It is not necessarily the case that the smallest difference is obtained that way.
1-4-5 vs 2-3-6 can be worse than 1-2-6 vs 3-4-5.
For example with these ratings 2100-2100-1600-1600-1600-600 the difference is 0 with my random example and 1000 with the algorithm you suggested.
3 Likes
An improvement over the current algorithm would be, after application of the current algorithm, would be:
for k from 1 to min(size of team A, size of team B)
if exchanging player k of team A with player k of team B improves team balance, then make that exchange.
3 Likes
Have you looked at the current algorithm? I think it (tries to) do that
I see. So I think one can fix that by trying all possible partitions. This works for 6 players, but after a certain point (say you have 20 players on a team) it’s computationally infeasible, and we have to be okay with an imperfect-but-good-enough algorithm.
Options I’m aware of:
- Thue-Morse
- random
- current algo
1 Like
I haven’t read all of the recent discussion, but I just wanted to comment on this.
Thue-Morse is just a heuristic method and does not always properly solve the partition problem.
Example: partition the set { 6, 5, 4, 3, 3, 1 } into two groups of three with the same average (or sum).
- Thue-Morse selection yields the unbalanced sets { 6, 3, 1 } and { 5, 4, 3 }
- A greedy scheme (“smaller selects next”) also yields unbalanced partitioning
- The optimal and balanced partition is { 6, 4, 1 } and { 5, 3, 3 }
Adapted from relevant discussion here: Thue-Morse (Fair Sharing) Sequence: A possible alternative to komi? - #69 by yebellz
From the Wikipedia article:
Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called “the easiest hard problem”
Of course, a whole other question is how to characterize and compare the strengths of two teams made up of mixed ranks. It’s not necessarily the case that a simple average fully captures this. However, even with such a simplifying assumption, the computation problem is non-trivial.
5 Likes
Here’s how the current balancing algorithm works for reference:
-
Sort list of all participants by rating. Later, the players at even positions will form one team and the players at odd positions will form the other team [1].
-
Iteratively improve the balance by making some of the players switch teams. This is similar to what @jlt suggested, except the current algorithm only switches adjacent players that would yield the biggest decrease in the rating difference. My thinking was that after step 1, the teams are already somewhat balanced, so maybe only players of similar strength (e.g. adjacent in the list) have to switch teams?
-
Assign the team (even or odd) with the lower average rating to black, and the other team to white.
[1]: After step 1, there’s already an upper bound for the (average) rating difference between the two teams: |d|, where d is the max rating difference between adjacent players in the sorted list.
For large team games, |d| is negligible, so the algorithm should be good enough for those cases.
For smaller games (maybe up to 4-vs-4?), the teams could be balanced by brute force.
4 Likes
It looks like there are many other algorithms to choose from.
2 Likes
I guess one thing I’m wondering is why @_Sophiam’s game with the
5k 5k 4k 3k 1d 2d
B W B W B W
Why didn’t the 3k and 4k (or the 1d and 2d) get switched during step (2)?
Or I guess I’m asking is that the expected behavior?
I tried to run the algorithm on @_Sophiam’s example, but I was getting a different result (the same as the expected result). I’m thinking there might be another problem involved, like the displayed ratings being different from the ratings used by the algorithm or something.
I’ll check again later.
2 Likes
Ah I see, well thanks for trying it out. I wouldn’t be surprised by a case of “different ranks show up in different places” so if it’s hard to reproduce don’t worry too much heh
1 Like
Let’s see…
Game 41546691 started at Unix time 1645735127. Use that to get initial ratings from the rating API, in case players finished other games during this one:
| player | rating | rank |
|---|---|---|
| He Who Walks In Shadows | 1603.93 | 4.1k |
| Vladimir Lukic | 1642.16 | 3.6k |
| Decros | 1929.46 | 1.1d |
| Black average: | 2.5k | |
| Sofiam | 1736.56 | 2.3k |
| PopcornCzar | 1577.82 | 4.5k |
| NateC89 | 2042.15 | 2.4d |
| White average: | 1.8k |
Does that help at all? Switching Sofia and Vladimir still does seem to make it a lot closer.
4 Likes