Archon - Optimal Seating

Vous souhaitez parler du jeu, discuter tactique, commenter l'utilité d'une carte, dévoiler un de vos decks favoris, etc., vous êtes au bon endroit.

Modérateurs : Modérateurs, V:EKN France

Répondre
Avatar de l’utilisateur
Franck
Methuselah
Methuselah
Messages : 2923
Inscription : 14 juin 2002, 13:13
Localisation : Warzone Hunting Ground
Contact :

Archon - Optimal Seating

Message par Franck »

Je suis en train de regarder le "Optimal Seating" défini dans l'Archon. Je suppose qu'il a été fait manuellement. Je sais pas s'il est optimal mais il est sacrément déséquilibré.

Je regarde le seating 10 joueurs.

Il propose

1,2,3,4,5 | 6,7,8,9,10
10,1,9,8,2 | 5,6,4,3,7
4,7,10,3,1 | 9,2,5,8,6

Si on additionne les points de transfert T1 des joueurs on va de 7 (joueur 1 et 6) à 11 (joueur 3 et 8 ), les autres ont 8. Je trouve l'écart (7,11) hallucinant !

Si on fait ce placement par exemple :
1,2,3,4,5 | 6,7,8,9,10
4,7,5,3,6 | 10,2,9,1,8
9,3,10,7,1 | 5,8,4,2,6

6 joueurs auront eu 8 points et 4 joueurs auront eu 9 points : ça semble plus équitable mais sur cette dispo particulière, y'a un autre soucis (4 et 5 qui font les 3 rondes ensemble).

J'ai pas regardé les autres config, et probablement que maintenant que le jeu n'est plus aussi actif qu'avant, on s'en tape un peu, mais en l'état actuel y'a clairement des tirages favorables.

Je ne sais pas si y'a des algos de répartition qui pourraient résoudre le schmilblik et pondre un truc un peu plus équitable (et prenant en compte les relations proies/pred et qui joue avec qui).

Je continue de creuser.
Dernière modification par Franck le 27 mars 2015, 10:01, modifié 1 fois.
ZBA
Rapide comme le Vent
Silencieux comme la Forêt
Dévastateur comme le Feu
Immuable comme la Montagne
derjudge
Elder
Elder
Messages : 1045
Inscription : 25 décembre 2008, 10:53

Re: Archon - Optimal Seating

Message par derjudge »

Ankha travaille la dessus activement.
L'algorithme c'est de bruteforcer les combinaisons pour que tout le monde aient (à peu près) le même nombre de transfert au début sur trois rondes, pas de réplication proie-pred et chacun voit un maximum de monde.
Avatar de l’utilisateur
Franck
Methuselah
Methuselah
Messages : 2923
Inscription : 14 juin 2002, 13:13
Localisation : Warzone Hunting Ground
Contact :

Re: Archon - Optimal Seating

Message par Franck »

Je pense qu'il y a moyen de dégager des axes quand même.

En gros, j'arrive aux combinaisons de points de transfert suivante

1-4-4
2-2-4
3-4-2
4-1-3

pour arriver a des distributions à 8 et 9 points

après il faut jouer sur les permutations et sur le fait que 4 transfert correspond à une place 4 ou 5 pour optimiser les relations proie-pred et le facteur "joue avec un maximum de monde"

La première ronde étant toujours déterminée, puisqu'elle se fait dans l'ordre des joueurs.

On peut, en fonction des transferts d'un joueur à la première ronde, en déduire ses transferts ronde 2 et 3.

C'est sur l'automatisation du dispatching sur les tables que je coince.
ZBA
Rapide comme le Vent
Silencieux comme la Forêt
Dévastateur comme le Feu
Immuable comme la Montagne
Avatar de l’utilisateur
Ankha
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Messages : 8420
Inscription : 13 décembre 2003, 22:31
Localisation : Loin dans le vide en-dessous

Re: Archon - Optimal Seating

Message par Ankha »

Il y a d'autres problèmes avec le seating 3R+F pour 15 joueurs: la règle 6 (pas deux fois la même relation) ainsi que la règle 7 (ne pas commencer deux fois à la même position) sont violées.

Pour ceux qui veulent suivre l'avancement :
http://www.vekn.net/forum/5-generic-vte ... 0&start=30

15 players (3R): in progress
Rule 2 KO.
(Current seating violate rule 6 and 7: player 8, table 1, position 3)
Rule 8 KO.
(Current seating has an absolute deviation of 1,12)

Ta remarque sur les transferts trouve son explication dans la déviation absolue calculée ci-dessus. Elle est à 1,12 alors qu'elle devrait être à beaucoup moins.
3 tables (14 transferts) * 3 rondes = 126 transferts à diviser entre 15 joueurs = 8,4 transferts par joueur. Par exemple 9 joueurs avec 8 transferts et 6 avec 9 transferts pour une déviation de : (9*0,4+6*0,6) / 15 = 7,2 / 15 = 0,48

Pour l'instant, mon algo permet de trouver les solutions jusqu'à 13, après les combinatoires explosent. Il faut que je travaille sur des astuces permettant de réduire le nombre de calculs comme ce que j'ai fait pour le 2R+F.
Ratings coordinator et Rules Director - BCP
Prince de Paris
REINS!
Avatar de l’utilisateur
Stone
Prince
Prince
Messages : 5126
Inscription : 14 juin 2002, 15:10

Re: Archon - Optimal Seating

Message par Stone »

la violence de l'explosion des combinatoires est-elle comparable à celle causée par l'ouverture de la boîte du DEKOX ULTIMUX ?
a priori, je dirais non. la 1ere fait fizzle cerveau d'Ankha, tandis que la 2nde détruit le tissu de la réalité.
mais bon, je dis ça, hein...c'est pour faire avancer le débat. voyez ?
Stone
ouais, j'ai 2 extensions de retard, et alors? LoB, t'en as vite fait le tour. Il y a Leibon et il y a les méchants.
Pétition contre le ban d'Anthelios/ToGP/Seeds
Avatar de l’utilisateur
Franck
Methuselah
Methuselah
Messages : 2923
Inscription : 14 juin 2002, 13:13
Localisation : Warzone Hunting Ground
Contact :

Re: Archon - Optimal Seating

Message par Franck »

Y'a un outil qui permet de vérifier si un seating est conforme aux règles ou non, et qui calcule la déviation ? Ou faut faire des vérifs manuelles à chaque fois ?
ZBA
Rapide comme le Vent
Silencieux comme la Forêt
Dévastateur comme le Feu
Immuable comme la Montagne
Kamel
Elder in training
Elder in training
Messages : 466
Inscription : 28 août 2011, 23:22

Re: Archon - Optimal Seating

Message par Kamel »

Stone a écrit :la violence de l'explosion des combinatoires est-elle comparable à celle causée par l'ouverture de la boîte du DEKOX ULTIMUX ?
a priori, je dirais non. la 1ere fait fizzle cerveau d'Ankha, tandis que la 2nde détruit le tissu de la réalité.
mais bon, je dis ça, hein...c'est pour faire avancer le débat. voyez ?
Je crois que jusqu'à 13 c'est 87693 combinaisons (environ, je fais ça de tête).
A 14, c'est déjà 6,1 x10 puissance 22 (environ)
A 15, on est à 10 puissance 83.
A 16, c'est 10 puissance 103, ce qui est supérieure au nombre de particules dans l'univers.
derjudge
Elder
Elder
Messages : 1045
Inscription : 25 décembre 2008, 10:53

Re: Archon - Optimal Seating

Message par derjudge »

De tête je dirais:
nbre de joueurs///nb possib// log_2(nb possib)
13 538552611717120000 40.8276615872
14 105556311896555520000 46.1057762465
15 23750170176724992000000 51.5218766487
16 6080043565241597952000000 57.0670540931
17 1757132590354821808128000000 62.7334807813
18 569310959274962265833472000000 68.5142242971
19 205521256298261377965883392000000 74.4031022554
20 82208502519304551186353356800000000 80.3945668025
21 36253949611013307073181830348800000000 86.4836116779
22 17546911611730440623420005888819200000000 92.6656965847
23 9282316242605403089789183115185356800000000 98.9366850165
24 5346614155740712179718569474346765516800000000 105.292792677
25 3341633847337945112324105921466728448000000000000 111.730544327
derjudge
Elder
Elder
Messages : 1045
Inscription : 25 décembre 2008, 10:53

Re: Archon - Optimal Seating

Message par derjudge »

Tu fais juste des recherches exactes ou te fais des metaheuristiques d'optimisation? (recuits simulés, algo génétiques...)
Avatar de l’utilisateur
Ankha
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Messages : 8420
Inscription : 13 décembre 2003, 22:31
Localisation : Loin dans le vide en-dessous

Re: Archon - Optimal Seating

Message par Ankha »

derjudge a écrit :Tu fais juste des recherches exactes ou te fais des metaheuristiques d'optimisation? (recuits simulés, algo génétiques...)
De la recherche exacte, mais je limite le nombre de combinaisons par construction (par exemple, sur une table de 10, les joueurs 1 et 6 sont similaires, on peut donc éliminer certaines permutations). Après, sur les gros calculs, il m'arrive de m'intéresser au meilleur résultat trouvé pendant le calcul, avant que celui-ci ne soit terminé.
Ratings coordinator et Rules Director - BCP
Prince de Paris
REINS!
Avatar de l’utilisateur
Ankha
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Messages : 8420
Inscription : 13 décembre 2003, 22:31
Localisation : Loin dans le vide en-dessous

Re: Archon - Optimal Seating

Message par Ankha »

Montjoie! Saint-Denis! Pour ceux que ça intéresse, j'ai trouvé un meilleur seating pour 15 joueurs.
Le voici:

15 players (3R): 7 11 6 2 13 | 9 4 1 8 14 | 5 10 15 12 3 / 13 15 2 5 11 | 14 3 10 1 6 | 12 8 4 7 9
Rule 2 KO.
Rule 8 KO. Absolute deviation is: 0,72 => 1, 6, 13 have 8 transfers | 2, 3, 4, 5, 8, 9, 10, 14, 15 have 9 transfers | 7, 11, 12 have 7 transfers
(Current seating has an absolute deviation of 1,12)
(Current seating also violate rule 6 and 7: player 8, table 1, position 3)


Vos avis éclairés sont les bienvenus!
Ratings coordinator et Rules Director - BCP
Prince de Paris
REINS!
Avatar de l’utilisateur
Lestat
Prince
Prince
Messages : 1692
Inscription : 03 octobre 2003, 09:46
Localisation : Marseille

Re: Archon - Optimal Seating

Message par Lestat »

Il n'y a que deux rondes là !
Avatar de l’utilisateur
Ankha
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Messages : 8420
Inscription : 13 décembre 2003, 22:31
Localisation : Loin dans le vide en-dessous

Re: Archon - Optimal Seating

Message par Ankha »

Lestat a écrit :Il n'y a que deux rondes là !
Je vais t'aider : la première ronde est toujours 1 2 3 4 5 6 ... ;)
Ratings coordinator et Rules Director - BCP
Prince de Paris
REINS!
Avatar de l’utilisateur
Lestat
Prince
Prince
Messages : 1692
Inscription : 03 octobre 2003, 09:46
Localisation : Marseille

Re: Archon - Optimal Seating

Message par Lestat »

Ankha a écrit :
Lestat a écrit :Il n'y a que deux rondes là !
Je vais t'aider : la première ronde est toujours 1 2 3 4 5 6 ... ;)
Il y a des tables à 6 ?
Avatar de l’utilisateur
Lestat
Prince
Prince
Messages : 1692
Inscription : 03 octobre 2003, 09:46
Localisation : Marseille

Re: Archon - Optimal Seating

Message par Lestat »

Lestat a écrit :
Ankha a écrit :
Lestat a écrit :Il n'y a que deux rondes là !
Je vais t'aider : la première ronde est toujours 1 2 3 4 5 6 ... ;)
Il y a des tables à 6 ?
Bon, je vais arrêter. Je vais vraiment passer pour un con.
Avatar de l’utilisateur
Lestat
Prince
Prince
Messages : 1692
Inscription : 03 octobre 2003, 09:46
Localisation : Marseille

Re: Archon - Optimal Seating

Message par Lestat »

C'est mieux que le truc déjà en place qui donne :
7 points de transfert pour les joueurs 1, 3, 6, 8, 11 et 13
8 points de transfert pour aucuns joueurs
9 points de transfert pour les joueurs 2, 4, 7, 9, 12 et 14
10 points de transfert pour les joueurs 5, 10 et 15

Donc un vrai gros écart.

Après, je ne connais pas très bien les restrictions de placement, mais en partant du postulat de départ que tu ne peux pas rencontrer tout le monde (maximum 12 joueurs), j'ai fait 5 groupes de 3 personnes qui ne se rencontreront jamais (ceux qui ont le même seating en première ronde) et qui bougeront de la même façon sur les différentes tables.
Groupe 1, 6, 11 qui ne bouge jamais de table et qui font les seating suivants 1 3 5
Groupe 2, 7, 12 qui bouge tout le temps de table (Pour le 2 table 1, 2, 3) et qui font les seating suivants 2 4 2 (Là, ai-je le droit de me mettre 2 fois en 2 ?)
Groupe 3, 8, 13 qui bouge tout le temps de table (Pour le 3 table 1, 3, 2) et qui font les seating suivants 3 5 1
Groupe 4, 9, 14 qui bouge une seule fois de table (Pour le 4 table 1, 2, 2) et qui font les seating suivants 4 2 3
Groupe 5, 10, 15 qui bouge une seule fois de table (Pour le 5 table 1, 3, 3)et qui font les seating suivants 5 1 4

Ca donne :
1 2 3 4 5 | 6 7 8 9 10 | 11 12 13 14 15
10 14 1 12 8 | 15 4 6 2 13 | 5 9 11 7 3
13 7 14 10 1 | 3 12 4 15 6 | 8 2 9 5 11

Et là on a :
8 points de transfert pour les joueurs 1, 2, 3, 6, 7, 8, 11, 12, 13
9 points de transfert pour les joueurs 4, 5, 9, 10, 14, 15

Après, reste ce fameux seating du Groupe 2, 7, 12 qui est deux fois 2ème. Il y a peut être moyen de l'intervertir avec un autre groupe, mais je n'ai pas encore cherché comment on peut faire sans passer un groupe à 7 points.
Avatar de l’utilisateur
Ankha
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Messages : 8420
Inscription : 13 décembre 2003, 22:31
Localisation : Loin dans le vide en-dessous

Re: Archon - Optimal Seating

Message par Ankha »

Lestat a écrit : Ca donne :
1 2 3 4 5 | 6 7 8 9 10 | 11 12 13 14 15
10 14 1 12 8 | 15 4 6 2 13 | 5 9 11 7 3
13 7 14 10 1 | 3 12 4 15 6 | 8 2 9 5 11
Ton seating donne :

N 15
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 2 shares a table with player 4 on round 2)
3. Available VPs are equitably distributed. OK OK
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,48 => 1, 2, 3, 6, 7, 8, 11, 12, 13 have 8 transfers | 4, 5, 9, 10, 14, 15 have 9 transfers
Ratings coordinator et Rules Director - BCP
Prince de Paris
REINS!
Avatar de l’utilisateur
Lestat
Prince
Prince
Messages : 1692
Inscription : 03 octobre 2003, 09:46
Localisation : Marseille

Re: Archon - Optimal Seating

Message par Lestat »

Ankha a écrit :
Lestat a écrit : Ca donne :
1 2 3 4 5 | 6 7 8 9 10 | 11 12 13 14 15
10 14 1 12 8 | 15 4 6 2 13 | 5 9 11 7 3
13 7 14 10 1 | 3 12 4 15 6 | 8 2 9 5 11
Ton seating donne :

N 15
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 2 shares a table with player 4 on round 2)
3. Available VPs are equitably distributed. OK OK
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,48 => 1, 2, 3, 6, 7, 8, 11, 12, 13 have 8 transfers | 4, 5, 9, 10, 14, 15 have 9 transfers
Tu as un outil pour vérifier ? Si oui, tu as moyen de nous le faire passer ?
Je ne piges pas la règle 2, tu es bien obligé, non ? Fort probable que je traduis mal.
Pour la règle 7, j'avais un doute.
Je ne piges pas non plus pourquoi la règle 8 est KO. Bon, je n'ai pas fait les calculs d'écarts type tu me diras.
Avatar de l’utilisateur
Ankha
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Messages : 8420
Inscription : 13 décembre 2003, 22:31
Localisation : Loin dans le vide en-dessous

Re: Archon - Optimal Seating

Message par Ankha »

L'outil est ici : http://www.vekn.fr/Tournois/RuleChecker.7z
La règle 2 est systématiquement violée s'il y a moins de 25 joueurs.
La règle 8 n'est OK que si tout le monde a le même nombre de transferts (uniquement sur certains configurations donc, notamment 16 joueurs). Ce n'est pas grave, il faut juste que la déviation soit la plus petite possible.
Ratings coordinator et Rules Director - BCP
Prince de Paris
REINS!
derjudge
Elder
Elder
Messages : 1045
Inscription : 25 décembre 2008, 10:53

Re: Archon - Optimal Seating

Message par derjudge »

Tu n'aurais pas du code plutôt? (dans un pastebin ou autre).
Avatar de l’utilisateur
Ankha
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Messages : 8420
Inscription : 13 décembre 2003, 22:31
Localisation : Loin dans le vide en-dessous

Re: Archon - Optimal Seating

Message par Ankha »

Tout le code est là :

http://www.vekn.fr/Tournois/ArchonSeatings.7z

C'est en chantier, mais le code correspondant est dans le projet RuleChecker (qui s'appuye sur les classes de génération qui se trouvent dans le SeatingsGenerator).
Le projet SeatingsGenerator crée des fichiers de résultats qui sont aggrégés par le projet Reunite.
Les autres projets n'ont pas d'intérêt particulier ici.
Ratings coordinator et Rules Director - BCP
Prince de Paris
REINS!
Avatar de l’utilisateur
Ankha
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Administrateur & Inner Circle - Rule monger & Ratings Coordinator
Messages : 8420
Inscription : 13 décembre 2003, 22:31
Localisation : Loin dans le vide en-dessous

Re: Archon - Optimal Seating

Message par Ankha »

J'ai les résultats pour 17 joueurs:

17 players (3R): 9 14 10 15 7 | 5 12 4 2 | 3 13 17 6 | 16 1 11 8 / 13 8 6 11 16 | 15 5 14 3 | 7 4 1 12 | 2 17 9 10
Rule 3 KO. Absolute deviation is: 0,145328719723183 => 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16 have 13 VP | 12, 17 have 12 VP
(Current seating has an absolute vp deviation of 0,145)
Rule 8 KO. Absolute deviation is: 0,865051903114187 => 1, 14 have 6 transfers | 2, 5, 7, 13, 15 have 7 transfers | 3, 6, 9, 10, 16 have 8 transfers | 4, 8, 11, 12, 17 have 9 transfers
(Current seating has an absolute transfer deviation of 0,98)

For 17 players, I had to "cheat" a little by entering manually some seatings (otherwise it would take 1 year to compute), so I don't know if there is a better solution. Anyway, this seating is slightly better.
What I did is that I chose 2 players that will never be seated on the only 5-players table (since only 15 players can be seated there through the 3 rounds). I chose players 12 and 17. I seated them in 4th, 3rd, 2nd position so they get in exchange the most transfers. The other players can only be seated once on the 5-players table, and I limited the number of players with 6 transfers to two.
Players 1 and 14 are 1st, 2nd and 3rd (6 transfers) but some players are necessarily disadvantaged.

J'ajouterais que si j'ajoute la contrainte "un seul joueur avec 6 transferts", il n'y a pas de solution qui ne violerait pas la règle 7 "A player doesn't play in the same seat position, if possible." par exemple
Ratings coordinator et Rules Director - BCP
Prince de Paris
REINS!
Répondre