Optimal seatings : the return of the mutant

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:

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

Swiss rounds wouldn't work well on a 3 rounds tournaments.

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

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