| 1 |
I am of the opinion that improving how the algorithm chooses permutations to check the balance of is a far more productive line of optimisation than improving how fast each permutation is checked, which is I suppose what you have said.
|
1 |
I am of the opinion that improving how the algorithm chooses permutations to check the balance of is a far more productive line of optimisation than improving how fast each permutation is checked, which is I suppose what you have said.
|
| 2 |
\n
|
2 |
\n
|
| 3 |
Something as sophisticated as GAs or simulated annealing seems like overkill but I guess it would get the job done.
|
3 |
Something as sophisticated as GAs or simulated annealing seems like overkill but I guess it would get the job done.
|
| 4 |
\n
|
4 |
\n
|
| 5 |
EDIT - I believe the following algorithm will yield a good starting point:
|
5 |
EDIT - I believe the following algorithm will yield a good starting point:
|
| 6 |
\n
|
6 |
\n
|
| 7 |
1) Order the players by rating.
|
7 |
1) Order the players by rating.
|
| 8 |
2) Pair the players off (#1 with #2, #3 with #4, #5 with #6, etc.)
|
8 |
2) Pair the players off (#1 with #2, #3 with #4, #5 with #6, etc.)
|
| 9 |
3) Order the pairs by the difference in their rating.
|
9 |
3) Order the pairs by the difference in their rating.
|
| 10 |
4) Take the pair with the highest difference in rating and allocate them to separate teams.
|
10 |
4) Take the pair with the highest difference in rating and allocate them to separate teams.
|
| 11 |
5) Take the pair with the next highest difference in rating and allocate them to separate teams such that the difference in the current teams' average skill is minimised.
|
11 |
5) Take the pair with the next highest difference in rating and allocate them to separate teams such that the difference in the current teams' average skill is minimised.
|
| 12 |
6) Return to (5) until all pairs are allocated.
|
12 |
6) Return to (5) until all pairs are allocated.
|
| 13 |
\n
|
13 |
\n
|
| 14 |
This solution will typically not be too bad (since we use the highest-difference pairs to offset one another first, they cannot ambush us later) and has the desirable property that no team is overloaded with players of high or low skill (since each consecutive pair is allocated to a different team). Searching the neighbourhood of that point by swapping players according to some heuristic (which I think need not be complicated, preferring to make small swaps in the correct direction might be enough) ought to end up with a reasonable solution in any reasonable situation, assuming the above algorithm hasn't already found one.
|
14 |
This solution will typically not be too bad (since we use the highest-difference pairs to offset one another first, they cannot ambush us later) and has the desirable property that no team is overloaded with players of high or low skill (since each consecutive pair is allocated to a different team). Searching the neighbourhood of that point by swapping players according to some heuristic (which I think need not be complicated, preferring to make small swaps in the correct direction might be enough) ought to end up with a reasonable solution in any reasonable situation, assuming the above algorithm hasn't already found one.
|
| 15 |
\n
|
15 |
\n
|
| 16 |
Happily, (based on a bit of test code) I think this algorithm will tend to perform best for large numbers of players - the larger the game, the less swapping will be necessary to end up with an adequate solution.
|
16 |
Happily, (based on a bit of test code) I think this algorithm will tend to perform best for large numbers of players - the larger the game, the less swapping will be necessary to end up with an adequate solution.
|
| 17 |
\n
|
17 |
\n
|
| 18 |
Notes:
|
18 |
Notes:
|
| 19 |
[spoiler]
|
19 |
[spoiler]
|
| 20 |
An odd number of players could be dealt with by taking the player with the closest-to-average skill, allocating them to the larger team, and then
|
20 |
An odd number of players could be dealt with by taking the player with the closest-to-average skill, allocating them to the larger team, and then
|
| 21 |
More than two teams could be dealt with by taking triplets, etc. instead of pairs, but I have not thought about how well this will work.
|
21 |
More than two teams could be dealt with by taking triplets, etc. instead of pairs, but I have not thought about how well this will work.
|
| 22 |
This algorithm does not take clans into account. It could be made to do so but would become messier and less effective in its goals.
|
22 |
This algorithm does not take clans into account. It could be made to do so but would become messier and less effective in its goals.
|
| 23 |
[/spoiler]
|
23 |
[/spoiler]
|
| 24 |
\n
|
24 |
\n
|
| 25 |
I ran my proof-of-concept code on the example game in the OP and ended up with the following teams:
|
25 |
I ran my proof-of-concept code on the example game in the OP and ended up with the following teams:
|
| 26 |
\n
|
26 |
\n
|
| 27 |
1988 1868
|
27 |
1988 1868
|
| 28 |
1852 1774
|
28 |
1852 1774
|
| 29 |
1681 1673
|
29 |
1681 1673
|
| 30 |
1665 1623
|
30 |
1665 1623
|
| 31 |
1587 1588
|
31 |
1587 1588
|
| 32 |
1494 1580
|
32 |
1494 1580
|
| 33 |
1392 1492
|
33 |
1392 1492
|
| 34 |
1315 1332
|
34 |
1315 1332
|
| 35 |
1236 1293
|
35 |
1236 1293
|
| 36 |
1202 1184
|
36 |
1202 1184
|
| 37 |
\n
|
37 |
\n
|
| 38 |
The difference in the average ELOs of the two teams is 0.25. Swapping the 1492 with the 1494 (an insignificant change in terms of the distribution of elo within the teams) reduces this to 0.05. The latter solution has the same average-ELO difference as the one in the OP, but presumably the brute force algorithm found the "bad" one first (20-choose-10 is still a fair bit less than two million I believe).
|
38 |
The difference in the average ELOs of the two teams is 0.25. Swapping the 1492 with the 1494 (an insignificant change in terms of the distribution of elo within the teams) reduces this to 0.05. The latter solution has the same average-ELO difference as the one in the OP, but presumably the brute force algorithm found the "bad" one first (20-choose-10 is still a fair bit less than two million I believe).
|
|
|
39 |
\n
|
|
|
40 |
(Another note: the problem in the OP was partially caused by Sprung and Brofessional being the two highest-rate players and in the same clan.)
|
Balancer broken?