Optimal seatings: the return of the vengeance
27 Mar 2021 09:25 #101947
by lip
Optimal seatings: the return of the vengeance was created by lip
Hello, fellow Methusalahs!
TL;DR
I contribute a new Archon seating for 4-60 players 3R+F. Link to the full data and comparison is in the conclusion.
Mathematics and prickly discussions about the measure and optimality of seating charts ensue. You've been warned.
Two years ago, in this thread , Ankha developped a very cunning solution to the optimal seating problem.
I had a look at this these last few days, and I did come up with some interesting findings I wanted to share.
For now, I focused on the 3R+F format, which is the hardest problem. I also provide "3-rounds played" solutions for 6, 7 & 11 players (where Archon only provides 2-rounds played over 3 rounds seatings for those cases).
Findings about the problem
Small tournaments seating improvements proposal
On Archon current version (v1.5i), seating may not be optimal for small tables (< 20 players).
Some are straightly sub-optimal, for example the 12-players seating where the Archon has:
With 9 pairs of players meeting twice and players 4 & 7 playing cross-table twice.
Where a better solution can be found, for example:
With also 9 pairs of players meeting twice, but no duplicate in players relationships.
Others are more debatable, like for example the 13-players seating, where Archon has:
An alternative could be:
Big tournaments seating improvements proposal
For tables bigger than 20 players, I present what I think are better seatings in some cases.
Some are straight better like the 31-players seating where Archon has:
With 10 pairs of players sharing a table twice
And I found a solution with nobody sharing a table twice, the same VPs repartition and a better transfers repartition:
Others are debatable or marginal improvements, for example the 28-players seating where Archon has:
With 4 players having access to 15 VPs (the others 14) and 25 players having not 8 starting transfers: 6 have 6, 15 have 7 or 9, 1 has 10, 3 have 11.
And I found:
With 6 players having access to 15 VPs and 3 to only 13, but only 20 players having not 8 starting transfers, all 7 or 9.
I'd argue the far better transfers repartition is worth the minor increase in VPs repartition discreptancy:
for the 3 lucky players, having 4-4-3 starting transfers sounds like a definitive advantage.
Discussion about the "optimal" criteria
The criteria that has been applied to generate the archon seatings are defined in this post :
I think they deserve a second look, or at least a bit of a discussion now that we know the problem (and its solutions) better.
Finally, to do some clever computation on such a criteria list, we need to assign relative weights to the rules, in order to produce a score to compare different solutions.
This is the score I used in my computations (the higher the score, the worse the seating):
I think a discussion on those weights can be worth it. The current score translates for example to:
An interesting idea would be to compute an "advantage" score by player to encompass
both the transfers and the access to VPs. That way, a "good" solution would compensate a player having access to less VPs with more transfers overall.
For now, we compute deviation independently for VPs and transfers, which means some "good" solutions can advantage or disadvantage some players on both fronts.
Conclusion
For those interested, my proposal for new seatings for 12 to 60 players on 3R+F, with a comparison to the current Archon, is available here .
@Ankha I hope you'll have time to take a look into that and that it can help better the Archon. I can provide JSONs or CSVs of the solutions if you like. I'd be happy to have a discussion about the score/criteria, I think the community would benefit from an updated and precise seating score formula. For one, it would enable us to provide a website or webservice to compute seatings with a precise and official guideline.
@Tournament organizers: If you ever organize a tournament with more rounds (remember the 2020 Worlds Championship?), I can run the algorithm to produce an optimal seating for any number of rounds, any number of players. Please do not hesitate to reach out.
For the geeks / mathematicians around, I used a simulated annealing algorithm to produce the results. This is very similar to what Ankha has done previously - simulated annealing and genetic algorithms are basically the same thing when it comes down to it.
AFAICT the differences in the solutions are about how you interpret and measure the criteria more than about the algorithm used for exploration. In fact, for more than 60 players, the solutions I get are equivalent to the Archon tables.
TL;DR
I contribute a new Archon seating for 4-60 players 3R+F. Link to the full data and comparison is in the conclusion.
Mathematics and prickly discussions about the measure and optimality of seating charts ensue. You've been warned.
Two years ago, in this thread , Ankha developped a very cunning solution to the optimal seating problem.
I had a look at this these last few days, and I did come up with some interesting findings I wanted to share.
For now, I focused on the 3R+F format, which is the hardest problem. I also provide "3-rounds played" solutions for 6, 7 & 11 players (where Archon only provides 2-rounds played over 3 rounds seatings for those cases).
Findings about the problem
- For 3R+F with more than 20 players, there is always a solution where you never meet the same opponent twice.
- The more players there are, the more "easy" it is to find a good seating: it is long to compute, but the quality of the solution is very stable. That makes sense to me on a very instinctive level: the more players you have, the more options you have to devise a good seating.
- With enough players, the good solutions are sparse in the space of possible seatings. Pardon my maths - this means you cannot get a good seating with just a random pick, but there are many equivalent good seatings (also instinctively makes sense because of the hypersymmetry of the problem)
Small tournaments seating improvements proposal
On Archon current version (v1.5i), seating may not be optimal for small tables (< 20 players).
Some are straightly sub-optimal, for example the 12-players seating where the Archon has:
Round 1: [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
Round 2: [[6, 9, 5, 1], [11, 8, 10, 3], [2, 4, 12, 7]]
Round 3: [[8, 1, 9, 2], [7, 5, 4, 11], [12, 3, 6, 10]]
With 9 pairs of players meeting twice and players 4 & 7 playing cross-table twice.
Where a better solution can be found, for example:
Round 1: [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
Round 2: [[7, 9, 8, 3], [10, 4, 2, 6], [11, 5, 12, 1]]
Round 3: [[3, 12, 10, 5], [2, 8, 6, 11], [4, 7, 1, 9]]
With also 9 pairs of players meeting twice, but no duplicate in players relationships.
Others are more debatable, like for example the 13-players seating, where Archon has:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10, 11, 12, 13]]
Round 2: [[12, 10, 1, 6, 8], [11, 4, 2, 7], [13, 5, 9, 3]]
Round 3: [[9, 13, 7, 1, 11], [5, 6, 10, 2], [3, 8, 4, 12]]
- 12 pairs of players meeting twice
- a very smooth VPs distribution (13 for everybody, except player 1 who has access to 15)
- 3 pairs of players playing with the same position group (3-5, 7-9 and 11-13 are non-neighbour twice)
An alternative could be:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10, 11, 12, 13]]
Round 2: [[4, 9, 13, 3, 6], [8, 5, 2, 12], [11, 1, 10, 7]]
Round 3: [[12, 10, 6, 8, 1], [5, 3, 9, 11], [7, 13, 4, 2]]
- Also 12 pairs of players meeting twice
- a flatter, but more expanded VPs distribution ([7, 11] have 12, [1, 3, 4, 6] have 14)
- No pair of players playing with the same position group
Big tournaments seating improvements proposal
For tables bigger than 20 players, I present what I think are better seatings in some cases.
Some are straight better like the 31-players seating where Archon has:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19], [20, 21, 22, 23], [24, 25, 26, 27], [28, 29, 30, 31]]
Round 2: [[25, 20, 12, 8, 4], [5, 6, 21, 18, 28], [26, 11, 19, 7, 31], [23, 1, 29, 13], [14, 16, 2, 30], [9, 24, 17, 3], [27, 10, 15, 22]]
Round 3: [[17, 27, 14, 1, 30], [2, 22, 9, 16, 29], [13, 3, 24, 10, 23], [31, 18, 6, 11], [7, 26, 4, 20], [12, 19, 5, 21], [8, 15, 28, 25]]
With 10 pairs of players sharing a table twice
And I found a solution with nobody sharing a table twice, the same VPs repartition and a better transfers repartition:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19], [20, 21, 22, 23], [24, 25, 26, 27], [28, 29, 30, 31]]
Round 2: [[19, 9, 31, 12, 21], [17, 4, 20, 28, 24], [26, 14, 7, 29, 22], [10, 11, 27, 1], [15, 18, 2, 8], [23, 16, 25, 3], [30, 5, 6, 13]]
Round 3: [[8, 20, 1, 16, 30], [27, 23, 5, 18, 29], [22, 19, 11, 25, 6], [21, 15, 28, 26], [13, 31, 4, 7], [12, 3, 10, 17], [14, 24, 9, 2]]
Others are debatable or marginal improvements, for example the 28-players seating where Archon has:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24], [25, 26, 27, 28]]
Round 2: [[2, 21, 20, 27, 9], [15, 25, 16, 3, 24], [8, 11, 22, 5, 28], [17, 10, 26, 23, 14], [19, 1, 7, 13], [4, 6, 12, 18]]
Round 3: [[12, 20, 1, 22, 25], [5, 19, 6, 21, 26], [27, 4, 24, 10, 13], [23, 18, 28, 15, 7], [9, 3, 17, 11], [14, 16, 2, 8]]
With 4 players having access to 15 VPs (the others 14) and 25 players having not 8 starting transfers: 6 have 6, 15 have 7 or 9, 1 has 10, 3 have 11.
And I found:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24], [25, 26, 27, 28]]
Round 2: [[13, 21, 5, 10, 16], [4, 28, 24, 11, 8], [18, 6, 12, 1, 25], [15, 23, 2, 26, 17], [3, 20, 9, 27], [22, 19, 14, 7]]
Round 3: [[9, 15, 28, 18, 22], [19, 27, 4, 13, 6], [20, 25, 7, 2, 21], [14, 24, 26, 16, 3], [8, 5, 17, 12], [10, 1, 11, 23]]
With 6 players having access to 15 VPs and 3 to only 13, but only 20 players having not 8 starting transfers, all 7 or 9.
I'd argue the far better transfers repartition is worth the minor increase in VPs repartition discreptancy:
for the 3 lucky players, having 4-4-3 starting transfers sounds like a definitive advantage.
Discussion about the "optimal" criteria
The criteria that has been applied to generate the archon seatings are defined in this post :
- No pair of players repeat their predator-prey relationship. This is mandatory, by the VEKN rules.
- No pair of players share a table through all three rounds, when possible.
- Available VPs are equitably distributed.
- No pair of players share a table more often than necessary.
- A player doesn't sit in the fifth seat more than once.
- No pair of players repeat the same relative position (prey, predator, cross-table-of-four, grand-prey, grand-predator), when possible.
- A player doesn't play in the same seat position, if possible.
- Starting transfers are equitably distributed. [NOAL]
- No pair of players repeat the same relative position group (adjacent, non-adjacent), when possible.
I think they deserve a second look, or at least a bit of a discussion now that we know the problem (and its solutions) better.
- (Prey-Predator) Is mandatory and can always be satisfied, but does not need to be checked if #4 is satisfied.
- (Share table through all rounds) Can always be satisfied, and could be rewritten as "No pair of players share a table through more than two rounds if possible".
- (Available VPs) Can only be optimized, rarely fully satisfied (only when you have a multiple of fives of players). Also, we need to define precisely what "equitably" means. @Ankha used absolute deviation to measure that, I used standard deviation, which gives worse score to wider gaps.
- (Share a table twice) This can be optimized for tournaments with 20 players or less, it can always be satisfied for tournaments with more than 20 players. In my opinion it has to be seen as "more important" than rule #3 that can rarely be fully satisfied.
- (Fifth seat) This rule should be removed as already included in #7, which can already be satisfied in most case.
- (Relative position) Can be ignored when rule #4 is satisfied. It is complicated to compute but makes the difference for less than 21 players.
- (Same seat) Looks redundant with #8 but is in fact useful: without it, playing seats 1-1-4 is more likely to happen (a bummer!) or, even more likely playing 2-2-4 instead of 1-3-4, which you could complain of if you play 7-capacity vampires, but not 6.
- (Starting transfers) Can only be optimized, never fully satisfied. As for VPs, "equitably" needs definition, and I used standard deviation instead of absolute (standard means 1 player having 2 less starting transfers is worse than 2 players having 1 less, where in absolute it's the same)
- (Relative position group) An additional criteria useful for less than 21 players
Finally, to do some clever computation on such a criteria list, we need to assign relative weights to the rules, in order to produce a score to compare different solutions.
This is the score I used in my computations (the higher the score, the worse the seating):
- 3 points per occurence (in addition to rules #4, #6 and #9)
- 3 points per occurence (in addition to rule #4)
- twice the standard deviation (to make it more important than rule #8)
- 1 point per occurence
- 1 point per occurence (this could be removed without impact)
- 1 point per occurence (in addition to rules #4 and #9)
- 2 points per occurence (experimentally, it feels like the additional weight is needed to make it relevant)
- standard deviation
- 1 point per occurence (in addition to rule #4)
I think a discussion on those weights can be worth it. The current score translates for example to:
- One player having a 1-VP difference is the same as 2 players having a 1-transfer differences
- Having a player seating in the same seat twice is worse than having the same pair of players on a table if they changed relationship
An interesting idea would be to compute an "advantage" score by player to encompass
both the transfers and the access to VPs. That way, a "good" solution would compensate a player having access to less VPs with more transfers overall.
For now, we compute deviation independently for VPs and transfers, which means some "good" solutions can advantage or disadvantage some players on both fronts.
Conclusion
For those interested, my proposal for new seatings for 12 to 60 players on 3R+F, with a comparison to the current Archon, is available here .
@Ankha I hope you'll have time to take a look into that and that it can help better the Archon. I can provide JSONs or CSVs of the solutions if you like. I'd be happy to have a discussion about the score/criteria, I think the community would benefit from an updated and precise seating score formula. For one, it would enable us to provide a website or webservice to compute seatings with a precise and official guideline.
@Tournament organizers: If you ever organize a tournament with more rounds (remember the 2020 Worlds Championship?), I can run the algorithm to produce an optimal seating for any number of rounds, any number of players. Please do not hesitate to reach out.
For the geeks / mathematicians around, I used a simulated annealing algorithm to produce the results. This is very similar to what Ankha has done previously - simulated annealing and genetic algorithms are basically the same thing when it comes down to it.
AFAICT the differences in the solutions are about how you interpret and measure the criteria more than about the algorithm used for exploration. In fact, for more than 60 players, the solutions I get are equivalent to the Archon tables.
The following user(s) said Thank You: Lönkka
Please Log in or Create an account to join the conversation.
27 Mar 2021 21:11 #101948
by Ankha
1/ it's hard to find correct weights
2/ there's always a risk that multiple minor rules outweigh a major one.
Replied by Ankha on topic Optimal seatings: the return of the vengeance
Cool!Mathematics and prickly discussions about the measure and optimality of seating charts ensue. You've been warned.
Correct. There was a mistake in my code checking Rule 6 (some missing parentheses around a modulus). Basically, rule 6 would fail when comparing relative positions on R2 and R3, so there are probably other erroneous seatings in the Archon 1.5i.Some are straightly sub-optimal, for example the 12-players seating where the Archon has:
Round 1: [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] Round 2: [[6, 9, 5, 1], [11, 8, 10, 3], [2, 4, 12, 7]] Round 3: [[8, 1, 9, 2], [7, 5, 4, 11], [12, 3, 6, 10]]
With 9 pairs of players meeting twice and players 4 & 7 playing cross-table twice.
Where a better solution can be found, for example:
Round 1: [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] Round 2: [[7, 9, 8, 3], [10, 4, 2, 6], [11, 5, 12, 1]] Round 3: [[3, 12, 10, 5], [2, 8, 6, 11], [4, 7, 1, 9]]
With also 9 pairs of players meeting twice, but no duplicate in players relationships.
The current seating rules are sorted by priority. I think it is very important that the VPs are "equally" distributed since they have a direct impact on the final result.Others are more debatable, like for example the 13-players seating, where Archon has:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10, 11, 12, 13]] Round 2: [[12, 10, 1, 6, 8], [11, 4, 2, 7], [13, 5, 9, 3]] Round 3: [[9, 13, 7, 1, 11], [5, 6, 10, 2], [3, 8, 4, 12]]
- 12 pairs of players meeting twice
- a very smooth VPs distribution (13 for everybody, except player 1 who has access to 15)
- 3 pairs of players playing with the same position group (3-5, 7-9 and 11-13 are non-neighbour twice)
An alternative could be:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10, 11, 12, 13]] Round 2: [[4, 9, 13, 3, 6], [8, 5, 2, 12], [11, 1, 10, 7]] Round 3: [[12, 10, 6, 8, 1], [5, 3, 9, 11], [7, 13, 4, 2]]
- Also 12 pairs of players meeting twice
- a flatter, but more expanded VPs distribution ([7, 11] have 12, [1, 3, 4, 6] have 14)
- No pair of players playing with the same position group
It's plainly better indeed, I couldn't find that one (perhaps because of the mistake on rule 6).Big tournaments seating improvements proposal
For tables bigger than 20 players, I present what I think are better seatings in some cases.
Some are straight better like the 31-players seating where Archon has:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19], [20, 21, 22, 23], [24, 25, 26, 27], [28, 29, 30, 31]] Round 2: [[25, 20, 12, 8, 4], [5, 6, 21, 18, 28], [26, 11, 19, 7, 31], [23, 1, 29, 13], [14, 16, 2, 30], [9, 24, 17, 3], [27, 10, 15, 22]] Round 3: [[17, 27, 14, 1, 30], [2, 22, 9, 16, 29], [13, 3, 24, 10, 23], [31, 18, 6, 11], [7, 26, 4, 20], [12, 19, 5, 21], [8, 15, 28, 25]]
With 10 pairs of players sharing a table twice
And I found a solution with nobody sharing a table twice, the same VPs repartition and a better transfers repartition:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19], [20, 21, 22, 23], [24, 25, 26, 27], [28, 29, 30, 31]] Round 2: [[19, 9, 31, 12, 21], [17, 4, 20, 28, 24], [26, 14, 7, 29, 22], [10, 11, 27, 1], [15, 18, 2, 8], [23, 16, 25, 3], [30, 5, 6, 13]] Round 3: [[8, 20, 1, 16, 30], [27, 23, 5, 18, 29], [22, 19, 11, 25, 6], [21, 15, 28, 26], [13, 31, 4, 7], [12, 3, 10, 17], [14, 24, 9, 2]]
I tend to disagree. 13 VPs means twice a 4-players table and a single 5-players table. It's always more enjoyable to play on a 5-players table for a start, and it means one can score more VPs on the whole tournament.Others are debatable or marginal improvements, for example the 28-players seating where Archon has:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24], [25, 26, 27, 28]] Round 2: [[2, 21, 20, 27, 9], [15, 25, 16, 3, 24], [8, 11, 22, 5, 28], [17, 10, 26, 23, 14], [19, 1, 7, 13], [4, 6, 12, 18]] Round 3: [[12, 20, 1, 22, 25], [5, 19, 6, 21, 26], [27, 4, 24, 10, 13], [23, 18, 28, 15, 7], [9, 3, 17, 11], [14, 16, 2, 8]]
With 4 players having access to 15 VPs (the others 14) and 25 players having not 8 starting transfers: 6 have 6, 15 have 7 or 9, 1 has 10, 3 have 11.
And I found:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24], [25, 26, 27, 28]] Round 2: [[13, 21, 5, 10, 16], [4, 28, 24, 11, 8], [18, 6, 12, 1, 25], [15, 23, 2, 26, 17], [3, 20, 9, 27], [22, 19, 14, 7]] Round 3: [[9, 15, 28, 18, 22], [19, 27, 4, 13, 6], [20, 25, 7, 2, 21], [14, 24, 26, 16, 3], [8, 5, 17, 12], [10, 1, 11, 23]]
With 6 players having access to 15 VPs and 3 to only 13, but only 20 players having not 8 starting transfers, all 7 or 9.
I'd argue the far better transfers repartition is worth the minor increase in VPs repartition discreptancy:
Standard deviation is probably better. I don't remember why I picked up the absolute one.[*](Starting transfers) Can only be optimized, never fully satisfied. As for VPs, "equitably" needs definition, and I used standard deviation instead of absolute (standard means 1 player having 2 less starting transfers is worse than 2 players having 1 less, where in absolute it's the same)
I'm not a big fan as:Finally, to do some clever computation on such a criteria list, we need to assign relative weights to the rules, in order to produce a score to compare different solutions.
1/ it's hard to find correct weights
2/ there's always a risk that multiple minor rules outweigh a major one.
For me, it shouldn't be equivalent.[*]One player having a 1-VP difference is the same as 2 players having a 1-transfer differences
No idea.[*]Having a player seating in the same seat twice is worse than having the same pair of players on a table if they changed relationship
[/list]
This is an area of improvement, right.An interesting idea would be to compute an "advantage" score by player to encompass
both the transfers and the access to VPs. That way, a "good" solution would compensate a player having access to less VPs with more transfers overall.
For now, we compute deviation independently for VPs and transfers, which means some "good" solutions can advantage or disadvantage some players on both fronts.
Please Log in or Create an account to join the conversation.
28 Mar 2021 07:41 #101949
by lip
I was thinking one could very well adjust a player's tournaments points (TPs) by the proportion of VPs he has access to compared to the mean (multiply them by {tournament_mean}/{available_vps}):
If I program an absolute priority of each rule over the following ones, it goes down mathematically to scoring the following at their maximum without checking (to translate the "no minor rule can outweigh a major one": there is still a weight, I just choose one that never let minor rules compensate a major one). But this gives such a weight to the major rules that it creates very high crests in the scoring. Given the hypersymmetry of the problem, this means it makes it very difficult for any heuristic to go over those crests for exploration, and I'm more likely to get stuck on a local minimum (I would draw a picture at that point, but maybe we should do a call ☺︎ I guess you get the point: a scoring function with many high peaks, some valleys lower than others, we're searching for the lowest valley)
I tried it, and giving reasonable weights leads to better results faster (because of the lower crests). Still, weights can easily be adapted. I can for example try a weight of 3, 5 or 10 on the VPs (compared to the transfers) and see what it yields. We can probably find satisfactory values experimentally: ones avoiding worse VPs repartition but yielding better transfers results.
Replied by lip on topic Optimal seatings: the return of the vengeance
Well, you're probably right - you have more experience running tournaments. Still, for most tournament sizes (non-multiple of 5), VPs cannot be equal for all - we can only optimise the deviation.
I tend to disagree. 13 VPs means twice a 4-players table and a single 5-players table. It's always more enjoyable to play on a 5-players table for a start, and it means one can score more VPs on the whole tournament.I'd argue the far better transfers repartition is worth the minor increase in VPs repartition discreptancy:
I was thinking one could very well adjust a player's tournaments points (TPs) by the proportion of VPs he has access to compared to the mean (multiply them by {tournament_mean}/{available_vps}):
- If you play 4-4-5 and sweep it, you get 3GW13, but if you play 4-5-5, you get 3GW14
- If you adjust the score to a tournament mean, both players would get 3GW{tournament_mean}VPs, an equality that would reflect their performance.
- The downside would be that a player doing only 1VP on a 4 players table will get a bit more points than a player doing the same on a 5 players table. Not sure it's an issue (maybe surviving a 4 players table is harder), but could be adjusted if it is (for example only adjust VPs by tournament mean in case of a GW)
Well, when using a heuristic, it always goes down to this. Wether I'm doing genetic algorithm or simulated annealing, the idea is to authorise some non-optimal changes (worse score) in order not to get stuck on local minima that are globally bad. But I would not authorise too bad a score (either I kill the worse scores in my population or I discard the possibility in the annealer depending on the temperature)
I'm not a big fan as:lip wrote: Finally, to do some clever computation on such a criteria list, we need to assign relative weights to the rules, in order to produce a score to compare different solutions.
1/ it's hard to find correct weights
2/ there's always a risk that multiple minor rules outweigh a major one.
If I program an absolute priority of each rule over the following ones, it goes down mathematically to scoring the following at their maximum without checking (to translate the "no minor rule can outweigh a major one": there is still a weight, I just choose one that never let minor rules compensate a major one). But this gives such a weight to the major rules that it creates very high crests in the scoring. Given the hypersymmetry of the problem, this means it makes it very difficult for any heuristic to go over those crests for exploration, and I'm more likely to get stuck on a local minimum (I would draw a picture at that point, but maybe we should do a call ☺︎ I guess you get the point: a scoring function with many high peaks, some valleys lower than others, we're searching for the lowest valley)
I tried it, and giving reasonable weights leads to better results faster (because of the lower crests). Still, weights can easily be adapted. I can for example try a weight of 3, 5 or 10 on the VPs (compared to the transfers) and see what it yields. We can probably find satisfactory values experimentally: ones avoiding worse VPs repartition but yielding better transfers results.
Please Log in or Create an account to join the conversation.
29 Mar 2021 07:49 #101955
by Timo
Replied by Timo on topic Optimal seatings: the return of the vengeance
/applause !
Sorry, I like those kind of discussions even if I can't really participate due to lack of knowledge ^^
But still, I kind of agree that : VP repartition is way more important than transfer repartition and also that a criteria giving a rule "by player" could lead to better seating but I don't think the new criteria should not only compute VP and transfer but also distribution of seatings and relative position with other players (for 20- players tournament).
Sorry, I like those kind of discussions even if I can't really participate due to lack of knowledge ^^
But still, I kind of agree that : VP repartition is way more important than transfer repartition and also that a criteria giving a rule "by player" could lead to better seating but I don't think the new criteria should not only compute VP and transfer but also distribution of seatings and relative position with other players (for 20- players tournament).
Please Log in or Create an account to join the conversation.
29 Mar 2021 12:03 - 29 Mar 2021 13:51 #101956
by lip
Replied by lip on topic Optimal seatings: the return of the vengeance
I agree.
But do you think getting access to one more VP is worth meeting a player twice when you could have met them only once? We can discuss for example the 17 players seating.
Archon has this:
Where I found this one, for example:
But do you think getting access to one more VP is worth meeting a player twice when you could have met them only once? We can discuss for example the 17 players seating.
Archon has this:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10, 11, 12, 13], [14, 15, 16, 17]]
Round 2: [[17, 13, 11, 6, 8], [3, 1, 7, 15], [5, 9, 2, 12], [4, 10, 14, 16]]
Round 3: [[15, 12, 9, 7, 10], [11, 3, 6, 14], [16, 8, 1, 5], [13, 17, 4, 2]]
- R3 (available vps: 13) [14, 16] have 12
- R4 (opponent twice: 13) 1-3, 1-5, 2-4, 2-5, 6-8, 6-11, 7-9, 7-15, 9-12, 10-12, 11-13, 13-17, 14-16
- R8 (starting transfers: 8) [1, 3, 11] have 6, [10, 13, 15, 17] have 7, [2, 5, 7, 8, 9, 12] have 9.
- R9 (position group: 4) 1 is 5 neighbour twice, 2 is 5 non-neighbour twice, 10 is 12 non-neighbour twice, 13 is 17 neighbour twice
Where I found this one, for example:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10, 11, 12, 13], [14, 15, 16, 17]]
Round 2: [[8, 12, 5, 15, 1], [17, 9, 4, 10], [16, 6, 13, 2], [7, 3, 14, 11]]
Round 3: [[13, 4, 15, 8, 3], [9, 1, 11, 16], [2, 17, 7, 12], [5, 10, 6, 14]]
- R3 (available vps: 13): [6, 7, 9, 10, 11, 14, 16, 17] have 12, [1, 3, 4, 5, 8, 15] have 14
- R4 (opponent twice: 3): 1-5, 3-4, 8-15
- R8 (starting transfers: 8): [6, 7] have 6, [1, 2, 9, 10, 17] have 7, [3, 4, 11, 12, 15] have 9
- R9 OK (position group)
I'd argue the second is better: only 3 pairs of players meeting twice instead of 13, with no repetition in the position, sounds better to me. That's why I would argue rule 4 should be before rule 3, or weighted against it, not just after it.
Last edit: 29 Mar 2021 13:51 by lip.
Please Log in or Create an account to join the conversation.
29 Mar 2021 16:53 #101957
by Ankha
"[6, 7, 9, 10, 11, 14, 16, 17] have 12" => this means all those players never get to play on the only table with 5 players, which is a bad thing VP-wise and fun-wise.
Playing with the same on a 5-players table and a 4-player table is unfortunate, but not as bad (especially with different relative positions).
Replied by Ankha on topic Optimal seatings: the return of the vengeance
I agree.
But do you think getting access to one more VP is worth meeting a player twice when you could have met them only once? We can discuss for example the 17 players seating.
Archon has this:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10, 11, 12, 13], [14, 15, 16, 17]] Round 2: [[17, 13, 11, 6, 8], [3, 1, 7, 15], [5, 9, 2, 12], [4, 10, 14, 16]] Round 3: [[15, 12, 9, 7, 10], [11, 3, 6, 14], [16, 8, 1, 5], [13, 17, 4, 2]]
- R3 (available vps: 13) [14, 16] have 12
- R4 (opponent twice: 13) 1-3, 1-5, 2-4, 2-5, 6-8, 6-11, 7-9, 7-15, 9-12, 10-12, 11-13, 13-17, 14-16
- R8 (starting transfers: 8) [1, 3, 11] have 6, [10, 13, 15, 17] have 7, [2, 5, 7, 8, 9, 12] have 9.
- R9 (position group: 4) 1 is 5 neighbour twice, 2 is 5 non-neighbour twice, 10 is 12 non-neighbour twice, 13 is 17 neighbour twice
Where I found this one, for example:
Round 1: [[1, 2, 3, 4, 5], [6, 7, 8, 9], [10, 11, 12, 13], [14, 15, 16, 17]] Round 2: [[8, 12, 5, 15, 1], [17, 9, 4, 10], [16, 6, 13, 2], [7, 3, 14, 11]] Round 3: [[13, 4, 15, 8, 3], [9, 1, 11, 16], [2, 17, 7, 12], [5, 10, 6, 14]]
- R3 (available vps: 13): [6, 7, 9, 10, 11, 14, 16, 17] have 12, [1, 3, 4, 5, 8, 15] have 14
- R4 (opponent twice: 3): 1-5, 3-4, 8-15
- R8 (starting transfers: 8): [6, 7] have 6, [1, 2, 9, 10, 17] have 7, [3, 4, 11, 12, 15] have 9
- R9 OK (position group)
I'd argue the second is better: only 3 pairs of players meeting twice instead of 13, with no repetition in the position, sounds better to me. That's why I would argue rule 4 should be before rule 3, or weighted against it, not just after it.
"[6, 7, 9, 10, 11, 14, 16, 17] have 12" => this means all those players never get to play on the only table with 5 players, which is a bad thing VP-wise and fun-wise.
Playing with the same on a 5-players table and a 4-player table is unfortunate, but not as bad (especially with different relative positions).
The following user(s) said Thank You: Vlad
Please Log in or Create an account to join the conversation.
Time to create page: 0.139 seconds
- You are here:
- Home
- Foro
- V:TES Discussion
- Generic V:TES Discussion
- Optimal seatings: the return of the vengeance