file Optimal seatings : the return of the mutant

30 Nov 2018 16:21 - 30 Nov 2018 16:25 #92162 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:
N22
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 relationshipOK

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:
N22
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 relationshipOK

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...

Prince of Paris, France
Ratings Coordinator, Rules Director
Last edit: 30 Nov 2018 16:25 by Ankha.
The following user(s) said Thank You: hardyrange, lionel, ResurrectioN, kschaefer

Please Log in or Create an account to join the conversation.

More
30 Nov 2018 20:12 #92164 by Bloodartist

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.

More
01 Dec 2018 01:57 #92172 by Boris The Blade
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.

More
01 Dec 2018 10:28 #92176 by jamesatzephyr

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.

More
03 Dec 2018 09:02 #92210 by Ankha
Swiss rounds wouldn't work well on a 3 rounds tournaments.

Prince of Paris, France
Ratings Coordinator, Rules Director

Please Log in or Create an account to join the conversation.

More
03 Dec 2018 09:05 - 03 Dec 2018 09:17 #92211 by Ankha
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
N22
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 relationshipOK

Prince of Paris, France
Ratings Coordinator, Rules Director
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.

More
Moderators: AnkhaKraus
Time to create page: 0.121 seconds
Powered by Kunena Forum