Optimal seatings : the return of the mutant
30 Nov 2018 16:21 - 30 Nov 2018 16:25 #92162
by Ankha
Optimal seatings : the return of the mutant was created by Ankha
More than three years ago,
I started the quest for the optimal seatings
. As you all certainly know (*cough*), the Archon uses a table of precomputed seatings to distribute the players across the rounds. It can't be done real-time because of the very long computation times as soon as there are more than 18 players (it's exponential).
With the help of some distributed computation, we managed to solve the problem (or more exactly find the absolute best solution) for 21 players. It took a few days to a dozen of computers.
Unable to go further in exhaustive search, I gave up after that. There are some clever ways to optimize the algorithm, but since it's a non-polynomial problem, it only pushes back the limits a little.
A few days ago, I started playing with genetic algorithm that are good alternative to the resolution of NP problems. They usually don't find the absolute best solution, but find some "local" best solutions. And much to my surprise, it seems to be working
Here are the current "optimal" seating for 22 players (3R+F).
I highlighted the pair of players that meet each other more than once.
This is the report about the seating:
9 occurence(s) of players meeting each other 2 times: 2 and 5, 3 and 4, 6 and 9, 7 and 8, 11 and 12, 15 and 18, 16 and 17, 19 and 21, 20 and 21
Here's the new seating found:
The first cool thing is that there aren't any pair of players that meet each other more than once
Here's the report:
You can notice that 9 is now the only player that plays on the three tables, but since that rule priority is lower than rule 2, it is tolerated.
As I said, the algorithm finds only a local best answer, so running it again can give a different (and better) result, but until now, it is the best seating we have.
To be continued...
With the help of some distributed computation, we managed to solve the problem (or more exactly find the absolute best solution) for 21 players. It took a few days to a dozen of computers.
Unable to go further in exhaustive search, I gave up after that. There are some clever ways to optimize the algorithm, but since it's a non-polynomial problem, it only pushes back the limits a little.
A few days ago, I started playing with genetic algorithm that are good alternative to the resolution of NP problems. They usually don't find the absolute best solution, but find some "local" best solutions. And much to my surprise, it seems to be working
Here are the current "optimal" seating for 22 players (3R+F).
I highlighted the pair of players that meet each other more than once.
This is the report about the seating:
N | 22 | |
1. No pair of players repeat their predator-prey relationship. This is mandatory, by the VEKN rules. | OK | |
2. No pair of players share a table through all two rounds, when possible. (N/A in some 2R event.) | KO (player 3 shares a table with player 4 on round 2): 96 (once), 9 (twice) | |
3. Available VPs are equitably distributed. | KO. Absolute deviation is: 0,190082644628099 => 1, 3, 5, 7, 9, 10, 12, 13, 14, 15, 17, 19, 20, 22 have 13 VP | 2, 4, 6, 8, 11, 16, 18, 21 have 14 VP | |
5. A player doesn't sit in the fifth seat more than once. | OK | |
6. No pair of players repeat the same relative position[*], when possible. | OK | |
7. A player doesn't play in the same seat position, if possible. | OK | |
8. Starting transfers are equitably distributed. [NOAL] | KO. Absolute deviation is: 0,752066115702479 => 8 have 6 transfers | 1, 5, 6, 9, 11, 12, 14 have 7 transfers | 3, 4, 13, 15, 17, 19, 21 have 8 transfers | 2, 7, 10, 16, 18, 20, 22 have 9 transfers | |
Extra1. Inversions in the prey/predator relationship | OK |
9 occurence(s) of players meeting each other 2 times: 2 and 5, 3 and 4, 6 and 9, 7 and 8, 11 and 12, 15 and 18, 16 and 17, 19 and 21, 20 and 21
Here's the new seating found:
The first cool thing is that there aren't any pair of players that meet each other more than once
Here's the report:
N | 22 | |
1. No pair of players repeat their predator-prey relationship. This is mandatory, by the VEKN rules. | OK | |
2. No pair of players share a table through all two rounds, when possible. (N/A in some 2R event.) | OK: 114 (once) | |
3. Available VPs are equitably distributed. | KO. Absolute deviation is: 0,297520661157025 => 12, 17, 21 have 12 VP | 4, 8, 10, 11, 13, 15, 18, 20, 22 have 13 VP | 1, 2, 3, 5, 6, 7, 14, 16, 19 have 14 VP | 9 have 15 VP | |
5. A player doesn't sit in the fifth seat more than once. | OK | |
6. No pair of players repeat the same relative position[*], when possible. | OK | |
7. A player doesn't play in the same seat position, if possible. | KO (player 20, table 2, position 2) | |
8. Starting transfers are equitably distributed. [NOAL] | KO. Absolute deviation is: 0,669421487603306 => 17 have 6 transfers | 7, 8, 11, 12, 13, 16 have 7 transfers | 1, 2, 5, 6, 9, 10, 15, 19, 20, 21 have 8 transfers | 4, 14, 18, 22 have 9 transfers | 3 have 10 transfers | |
Extra1. Inversions in the prey/predator relationship | OK |
You can notice that 9 is now the only player that plays on the three tables, but since that rule priority is lower than rule 2, it is tolerated.
As I said, the algorithm finds only a local best answer, so running it again can give a different (and better) result, but until now, it is the best seating we have.
To be continued...
Last edit: 30 Nov 2018 16:25 by Ankha.
Please Log in or Create an account to join the conversation.
30 Nov 2018 20:12 #92164
by Bloodartist
Next episode: solving P=NP while at it..
"Do you believe in the power of the night?
If you want to go with me, refuse the light"
- Blutengel, Soultaker
Replied by Bloodartist on topic Optimal seatings : the return of the mutant
Ankha wrote: To be continued...
Next episode: solving P=NP while at it..
"Do you believe in the power of the night?
If you want to go with me, refuse the light"
- Blutengel, Soultaker
Please Log in or Create an account to join the conversation.
- Bloodartist
- Offline
- Antediluvian
Less
More
- Posts: 640
- Thank you received: 92
01 Dec 2018 01:57 #92172
by Boris The Blade
Replied by Boris The Blade on topic Optimal seatings : the return of the mutant
Why look for a static seating arrangement in the first place? To me, a rule that makes each table as competitive as possible, as measured by the current score, would have higher priority than your rule 2.
Please Log in or Create an account to join the conversation.
- Boris The Blade
- Offline
- Antediluvian
Less
More
- Posts: 1151
- Thank you received: 240
01 Dec 2018 10:28 #92176
by jamesatzephyr
The two (or three, or however many) preliminary rounds are intended to be on an equal footing. They contribute the same amount to you getting into the final. A game win that's been won on a table that has been specifically and intentionally crafted to have the 'worst' five players in the tournament on it probably shouldn't count as much as the game win on a table that has been specifically and intentionally crafted to have the 'best' five players in the tournament.
Additionally, this sort of thing can cause a whole heap of trouble when players start calculating "Oh, but if I get two VP on this table, then that puts me on the same footing as Sally who's brought her Turbo-Shamblers deck and that absolutely creams me. But if I only get 1.5 VP now by encouraging us towards the time-out then I can't be on her table, so I stand a much better chance of doing well next round." And many similar outcomes.
Don't think that sort of thing happens? Here's it happening in the 2012 Olympics: www.theguardian.com/sport/2012/aug/01/olympic-badminton-players-charged-lose
Replied by jamesatzephyr on topic Optimal seatings : the return of the mutant
Boris The Blade wrote: To me, a rule that makes each table as competitive as possible, as measured by the current score, would have higher priority than your rule 2.
The two (or three, or however many) preliminary rounds are intended to be on an equal footing. They contribute the same amount to you getting into the final. A game win that's been won on a table that has been specifically and intentionally crafted to have the 'worst' five players in the tournament on it probably shouldn't count as much as the game win on a table that has been specifically and intentionally crafted to have the 'best' five players in the tournament.
Additionally, this sort of thing can cause a whole heap of trouble when players start calculating "Oh, but if I get two VP on this table, then that puts me on the same footing as Sally who's brought her Turbo-Shamblers deck and that absolutely creams me. But if I only get 1.5 VP now by encouraging us towards the time-out then I can't be on her table, so I stand a much better chance of doing well next round." And many similar outcomes.
Don't think that sort of thing happens? Here's it happening in the 2012 Olympics: www.theguardian.com/sport/2012/aug/01/olympic-badminton-players-charged-lose
Please Log in or Create an account to join the conversation.
- jamesatzephyr
- Away
- Antediluvian
Less
More
- Posts: 2625
- Thank you received: 867
03 Dec 2018 09:02 #92210
by Ankha
Replied by Ankha on topic Optimal seatings : the return of the mutant
Swiss rounds wouldn't work well on a 3 rounds tournaments.
Please Log in or Create an account to join the conversation.
03 Dec 2018 09:05 - 03 Dec 2018 09:17 #92211
by Ankha
Replied by Ankha on topic Optimal seatings : the return of the mutant
Here's an even better result for 22 players :
R2: 10 19 11 15 1 | 12 8 5 20 17 | 13 18 3 6 | 4 14 7 22 | 21 2 9 16
R3: 5 7 15 13 21 | 22 18 10 12 2 | 9 20 4 11 | 3 16 8 19 | 17 14 6 1
R2: 10 19 11 15 1 | 12 8 5 20 17 | 13 18 3 6 | 4 14 7 22 | 21 2 9 16
R3: 5 7 15 13 21 | 22 18 10 12 2 | 9 20 4 11 | 3 16 8 19 | 17 14 6 1
N | 22 | |
1. No pair of players repeat their predator-prey relationship. This is mandatory, by the VEKN rules. | OK | |
2. No pair of players share a table through all two rounds, when possible. (N/A in some 2R event.) | OK: 114 (once) | |
3. Available VPs are equitably distributed. | KO. Absolute deviation is: 0,272727272727273 => 14, 16 have 12 VP | 3, 4, 6, 9, 11, 13, 17, 18, 19, 20, 21, 22 have 13 VP | 1, 2, 7, 8, 12, 15 have 14 VP | 5, 10 have 15 VP | |
5. A player doesn't sit in the fifth seat more than once. | OK | |
6. No pair of players repeat the same relative position[*], when possible. | OK | |
7. A player doesn't play in the same seat position, if possible. | KO (player 7, table 1, position 2) | |
8. Starting transfers are equitably distributed. [NOAL] | KO. Absolute deviation is: 0,330578512396694 => 3, 7, 12, 19 have 7 transfers | 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21 have 8 transfers | 1, 22 have 9 transfers | |
Extra1. Inversions in the prey/predator relationship | OK |
Last edit: 03 Dec 2018 09:17 by Ankha.
The following user(s) said Thank You: lionel
Please Log in or Create an account to join the conversation.
Time to create page: 0.121 seconds
- You are here:
- Home
- Forum
- V:TES Discussion
- Generic V:TES Discussion
- Optimal seatings : the return of the mutant