Optimal seatings : the return of the mutant
30 Nov 2018 16:21 - 17 Jun 2019 13:57 #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.
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...
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.
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...
Last edit: 17 Jun 2019 13:57 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..
A heretic is a man who sees with his own eyes.
—Gotthold Ephraim Lessing
Replied by Bloodartist on topic Optimal seatings : the return of the mutant
To be continued...
Next episode: solving P=NP while at it..
A heretic is a man who sees with his own eyes.
—Gotthold Ephraim Lessing
Please Log in or Create an account to join the conversation.
- Bloodartist
- Offline
- Antediluvian
Less
More
- Posts: 941
- Thank you received: 157
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: 1221
- Thank you received: 256
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
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
- Offline
- Antediluvian
Less
More
- Posts: 2788
- Thank you received: 958
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.126 seconds
- You are here:
- Home
- Forum
- V:TES Discussion
- Generic V:TES Discussion
- Optimal seatings : the return of the mutant