Discussion :

[maniacs]

Bonjour,

Suite à mon questionnement on m'a redirigé ici. Je réécris ma recherche. J'ai commencé à apprendre vba pour excel et je me suis mis en tête de mettre au point un système de ronde suisse pour un nombre variable de joueurs entre 2 et 32 histoire de mettre en pratique ce que j'apprends sur mon temps libre.

J'ai déjà toutes mes feuilles prêtes en ce qui concerne les différentes formules pour gérer les rencontres et le classement qui en découlera. Une feuille par ronde

J'ai réussi à automatiser la ronde 1, bon ok c'est la plus simple vu que je pars sur un tirage aléatoire entre les participants. J'ai mis un peu de temps pour tout mettre en place mais comme indiqué plus haut, je me suis entêté

Par contre, je bloque sur la ronde 2 (et les suivantes mais ça devrait être presque identique pour les rondes suivantes) qui doit prendre en compte ce qui suit:
- chaque joueur ne peut se rencontrer que une fois maximum sur toute la durée du tournoi (j'ai mis en place un tableau qui inscrit un 1 au croisement de ligne et colonne des joueurs qui se sont rencontrés pour l'aspect visible en un clin d'oeil, je me demande si je ne devrais pas créer une matrice à 2 dimensions et remplir par un 1 les rencontres, ça servirait pour contrôler si les joueurs ne se sont pas déjà rencontrés par la suite)
- le premier rencontre le second puis le troisième rencontre le quatrième etc...
- si le 1er et le 2nd se sont rencontrés, je prend le 3ème, je vérifie et si ok je passe au match suivant et ainsi de suite
- pour trouver les joueurs restants, je pense utiliser une matrice à une dimension et en bouclant je devrais pouvoir m'en sortir enfin je crois.

Je pense que cela parait possible sur le papier pour les rondes 2 voir 3 mais sur les rondes suivantes si il ne me reste plus que 2 joueurs qui ont préalablement joué ensemble, je ne vois pas comment relancer le calcul (peut-être en partant du bas du classement)
5 rondes pour 32 joueurs (plus il y a de joueurs moins le problème devrait être présent)
4 rondes pour 16 joueurs
3 rondes pour 8 joueurs
2 rondes pour 4 joueurs (ici pas vraiment de sujet sauf si match nul sur 1 ou les 2 matchs)

Auriez-vous une idée d’algorithme efficace pour gérer les rondes suisses en fonction du classement?

[EricDgn]

Voir si ces 2 adresses ne pourraient pas vous donner des idées:
la ronde suisse
tournoi suisse
Cordialement

[tbc92]

Les nombres que tu as choisis ( 4rondes pour 16 joueurs, 5 pour 32 joueurs) ne sont pas vraiment réalistes.
5 tours pour 32 joueurs, c'est ce qu'on a dans une compétition de type 'coupe' : à chaque tour, les vainqueurs continuent entre eux, et les perdants sont éliminés (ou jouent une consolante).
7 ou 8 tours pour 16 joueurs, c'est ce qui se fait, et ça donne un classement assez représentatif de la valeur des joueurs.

En terme de programmation, je pense qu'il faut parler 'récursivité'.
Exemple avec 8 joueurs, à la fin du tour 3.
1 joue contre 2
3 a joué contre 4, donc on le fait jouer contre 5
4 joue contre 6
Et problème, 7 a déjà joué contre 8

On est obligé de revenir en arrière. Le match 4 contre 6 qui semblait valide, il génère un blocage. On ne fait pas jouer 4 contre 6, mais 4 contre 7 (et on vérifie si les 2 joueurs restants n'ont pas déjà joué ensemble).
Eventuellement, on doit revenir loin en arrière.
On peut éventuellement être amené à annuler aussi la rencontre 3 contre 6, et faire jouer 3 contre 6.

Quand je dois programmer des trucs de ce type, en fait, je ne fais pas de la récursivité, je gère une 'Pile'.

Par exemple, si 1 a déjà joué contre 3, 4 et 6, je vais mettre dans ma pile :
(1,8)
(1,7)
(1,5)
(1,2)

Je les mets dans cet ordre. 1 va devoir jouer contre 8, 7, 5 ou 2,mais de préférence contre 2, éventuellement contre 5 , ... et en dernier recours contre 7 ou 8.
Puis je prends le dernier élément de la pile, (je le supprime de la pile) et j'insère les scénarios compatibles avec ce dernier élément.
Ici, le dernier élément de la pile est (1,2) ; on doit donc faire jouer 3 ; imaginons que 3 a déjà joué contre 1, 4 et 6, il peut donc jouer contre 5, 7 ou 8. Mais de préférence contre 5
Dans ma pile, je vais donc avoir :
(1,8)
(1,7)
(1,5)
(1,2)(3,8)
(1,2)(3,7)
(1,2)(3,5)

Et je continue ... Si j'ai jes matches (1,2) et (3,5), quels sont les matches possibles pour le joueur 4. Si par hasard il n'y a aucun match possible, parce que 4 a déjà joué contre 6, 7 et 8, je n'insère aucune ligne dans ma pile. Et donc je me retrouve à analyser le scénario (1,2)(3,7)
Quand je trouve un scénario où les 8 joueurs sont casés, c'est bon, je lance le tour suivant, et j'attends les résultats des 4 matches pour programmer le tour suivant.

J'ai fait des dizaines de petits programmes de ce type. Mais je ne sais pas du tout si VBA permet de manipuler des structures de ce genre.

[EricDgn]

Juste pour info, le fichier offert dans ce forum signalé précédemment fonctionne vraiment. J'arrive avec un temps raisonnable à préparer 18 tours avec 32 joueurs. A partir du 19e tour cela commence à prendre beaucoup de temps: 3' pour le 18e tour, 18' pour le 19e tour, et me suis arrêté là. C'est exponentiel!
Cdt

[maniacs]

merci pour vos retours, je vais tâcher de regarder cela

[Guesset]

Bonjour,

Je reprendrais la logique proposée par tbc92 en la dotant d'un peu d heuristique. Pour chaque joueur restant, on dresse son potentiel d'association avec les joueurs encore en lice. On trie les joueurs, de celui qui a le moins d'associations jusqu'à celui qui en a le plus. Il est possible de refaire un (ou plus) passage pour les ex-aequo en tentant compte du premier tri : celui qui est plus présent dans les positions premières passe avant l'autre.

On applique ensuite l'algorithme proposé par tbc92 selon l'ordre résultant.

Le but est double, reporter l'explosion combinatoire et donc la diminuer (quand on arrive plus tard sur un joueur riche en associations, il y a alors une grande chance que son potentiel soit déjà bien entamé), et optimiser les chances de succès (ce second objectif peut aussi être vu comme un effet de la tenue du premier).

Salutations

[tbc92]

Oui et non.
Certes, on ne veut pas que le système mette 10 minutes pour trouver la mise en place du tour à venir.
Mais aussi, on a une contrainte.
La mise en place solution du cahier des charges est unique.
Oui, généralement, il y a plein de mises en place qui respectent les contraintes (personne ne rejoue contre un adversaire qu'il a déjà rencontré).
Mais parmi ces différentes solutions, la mise en place choisie n'est pas aléatoire. Il n'y en a qu'une qui correspond au cahier des charges complet.
Le joueur en tête du championnat doit jouer contre le joueur le mieux placé parmi ceux qu'il n'a pas déjà rencontré, sauf si ça crée un blocage.
Idem, le joueur classé n°2, soit il joue contre le n°1 et l'affaire est réglée, soit il joue contre le joueur le mieux placé parmi ceux qu'il n'a pas déjà rencontré, sauf si ça crée un blocage.

Si les mises en place (1,2)(3,5)(4,8)(6,7) et (1,2)(3,6)(4,5)(7,8) sont les seules possibles, l'algorithme devra impérativement choisir la 1ère, car le joueur 3 ne doit pas jouer contre 6 alors qu'il peut jouer contre 5.

Dans les faits, si on est au jeu d'échecs par exemple, on a systématiquement beaucoup d'ex-aequo. Tous ceux qui ont 3 victoires sont (a priori) ex-aequo. Donc qui est 3ème , qui est 4ème, c'est aléatoire.
Il y a un outil utilisé pour départager (partiellement) les ex-aequo. Si A et B ont tous les 2 3 victoires, on va regarder le nombre de points des joueurs rencontrés par A et par B. Et on va utiliser ce nombre de points pour départager A et B.

[Guesset]

Bonjour,

Dont acte s'il y a d'autres règles à intégrer.

Cependant, pour clarifier, les ex-aequo dont je parle ne le sont pas au sens du jeu mais au sens du tri, c'est à dire au nombre de joueurs qu'ils peuvent encore affronter.

Salutations

[maniacs]

Bonjour,

Je vais tâcher de bien assimiler ce que vous proposer et je vais essayer de tâtonner étape par étape et voir ce que je peux arriver à pondre.
Le système de pile est un point que je ne sais pas du tout utiliser, à voir ce que je peux trouver comme info.
Je pense que l'utilisation de matrice ou tableau sera mon point de départ.
Dès que je trouve un peu de temps, je me lance dans des tentatives.
En tout cas, je vous remercie d'avoir pris un peu de temps pour m'éclairer