file Optimal seatings : the return of the mutant

30 Nov 2018 16:21 - 17 Jun 2019 13:57 #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.


If you want to contribute or to play with the seatings, you just have to download and unzip www.vekn.net/images/stories/downloads/VtesSeatings.zip

There are two programs:

1) genetics.exe
This command-line program tries to find the best seating for a given number of players.
To use it, you have to run it through a command line with two parameters:
- the first one is the number of players (eg., 51)
- the second one is the size of the "population" that will breed and mutate to give the best results. Typical value is 1000.
The program will create a population for each of your logical processor. On my computer, it means 8*1000 individuals. If you have only 4 logical processors, you may want to double the population size. You can run the program in background since it has a very low priority and won't block your computer.



2/ RuleChecker.exe
You simply run it by double cliking on it. It always assume that the R1 seating is 1, 2, 3, ..., n so for 2R+F tournaments, you have to fill the first line only, and for 3R+F tournaments, two lines.
It can also import from your clipboard your seating if you copied it from the Archon file (by selecting the player numbers in the Optimal Seatings sheets) or from the Genetic program.
It will indicate if the rules are enforced or not.



To be continued...

Prince of Paris, France
Ratings Coordinator, Rules Director
Last edit: 17 Jun 2019 13:57 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..

"Plenty of little men tried to put their swords through my heart. And there's plenty of little skeletons buried in the woods."
- Tormund Giantsbane, Game of Thrones

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.149 seconds
Powered by Kunena Forum