IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

Au Pied Levé - À Main Levée

[TUTORIEL] Tournoi entre 16 joueurs (4 joueurs/table)

Noter ce billet
par , 01/04/2021 à 10h15 (348 Affichages)
À chaque nouvelle partie d’un tournoi, les joueurs (1 à 16) doivent être affectés à l’une des 4 tables (lignes horizontales) de façon à ce qu’aucun joueur ne rencontre deux fois un même autre joueur.

Première partie

Table N° 1
1
2
3
4
Table N° 2
5
6
7
8
Table N° 3
9
10
11
12
Table N° 4
13
14
15
16
Il s’agit d’un simple exercice de réflexion et non d'un algorithme à programmer en logique combinatoire… sauf si l’exercice vous inspire.

Nom : Tournoi.jpg
Affichages : 16
Taille : 353,8 Ko

Avant-propos

Chaque joueur devant rencontrer les quinze autres, trois par trois, cinq parties sont nécessaires pour que chaque joueur rencontre tous les autres joueurs du tournoi (3 x 5 = 15).

Les tableaux 1, 3, 5 et 7 sont les copies respectives des 1ère, 2ème, 3ème et 4ème parties. Chaque copie d’une partie permet d’organiser la partie suivante.

L’organisation de la partie N + 1 se fait en deux temps :

  1. Sélection des joueurs depuis la copie de la partie N.

    La sélection est verticale pour la 2ème partie, en diagonales pour les autres parties.

    Chaque sélection a pour objectif d’affecter les joueurs à l'une des 4 tables de la partie N + 1.

  2. Copie horizontale, table par table, de chaque sélection.

Conventions d’organisation de la partie N + 1 depuis la copie de la partie N :

Les couleurs jaune, vert, bleu et marron symbolisent la sélection des joueurs depuis la copie de la partie N, à affecter respectivement et chronologiquement aux 1ère, 2ème, 3ème, et 4ème tables de la partie N + 1.

Conventions du sens des sélections à adopter :

Copie 1ère partie - Organisation de la 2ème partie : Sélection verticale des joueurs
Copie 2ème partie - Organisation de la 3ème partie : Sélection diagonale des joueurs
Copie 3ème partie - Organisation de la 4ème partie : Sélection diagonale des joueurs
Copie 4ème partie - Organisation de la 5ème partie : Sélection des joueurs ne s’étant pas encore rencontrés

IMPORTANT :

La sélection dans le sens des diagonales se fait d’abord sur les grandes diagonales d’angle à angle puis sur les petites de côté à côté, toujours chronologiquement et sur des lignes différentes, bien sûr.

  1. La 1ère grande diagonale permet d’affecter les joueurs à la 1ère table.
  2. La 2ème grande diagonale permet d’affecter les joueurs à la 2ème table.
  3. Les deux premières demi-diagonales permettent d’affecter les joueurs à la 3ème table.
  4. Les deux dernières demi-diagonales permettent d’affecter les joueurs à la 4ème table.

Ces dispositions étaient dictées à l’origine par l’instinct, la simplicité et la facilité. Les deux grandes diagonales se perçoivent immédiatement. Les demi-diagonales nécessitent une fraction de seconde de réflexion supplémentaire. Rien de plus, mais efficace sans en comprendre la dynamique.

Pour organiser la 3ème partie, il peut être tentant d’affecter les joueurs d’une diagonale ou de deux demi-diagonales à la table 1, 2, 3 ou 4 en fonction du premier joueur 1, 2, 3 ou 4. L’organisation de la 4ème partie à partir de la matrice obtenue fera hélas se rencontrer des joueurs s’étant déjà rencontrés.

Les étapes :

  • 1ère partie : Colorisation en jaune, vert, bleu et marron des cellules horizontales représentant le placement initial des joueurs à chaque table.

  1. Copie 1ère partie : Colorisation des cellules verticales de la 1ère partie en jaune, vert, bleu et marron selon une logique simple, on est sûr que les joueurs de chaque colonne ne se rencontreront qu’une seule fois lors de la prochaine partie.

  2. 2ème partie : Depuis la copie de la 1ère partie, les cellules verticales d’une même couleur sont copiées horizontalement et chronologiquement dans le tableau de la 2ème partie.

  3. Copie 2ème partie : Colorisation des cellules de la 2ème partie en jaune, vert, bleu et marron selon une autre logique, d’abord les cellules en grandes diagonales puis deux fois les cellules en petites diagonales sur des lignes (tables) différentes.

    Chaque groupe d’une même couleur est ainsi constitué d’un joueur de chaque table. À noter que la répartition des joueurs dans ce tableau aurait pu être constituée à partir du premier tableau. On est sûr que les joueurs choisis en diagonales ne se rencontreront qu’une seule fois lors de la prochaine partie.

  4. 3ème partie : Depuis la copie de la 2ème partie, les cellules d’une même couleur sont copiées horizontalement et chronologiquement dans le tableau de la 3ème partie.

  5. Copie 3ème partie : Colorisation des cellules de la 3ème partie en jaune, vert, bleu et marron selon la même logique qu’en 3. Chaque groupe d’une même couleur est ainsi constitué d’un joueur de chaque table.

    Aucune réflexion rationnelle n’étaye ce choix de sélection en diagonales à l’identique du choix précédent ayant permis l’organisation de la 3ème partie. Il peut certainement se justifier à postériori mais à l’origine, c’est juste une répétition du choix précédent avec 50 % d’intuition et 50 % de chance.

  6. 4ème partie : Depuis la copie de la 3ème partie, les cellules d’une même couleur sont copiées horizontalement et chronologiquement dans le tableau de la 4ème partie.

  7. Copie 4ème partie : La démarche logique utilisant les diagonales pour organiser la partie N + 1 ne fonctionne plus car elle reconstituerait en fait la deuxième partie. Cette démarche constitue un processus itératif. Il est nécessaire d’utiliser une autre logique pour organiser la dernière partie.

    Chacun des joueurs 1, 2, 3 et 4 n’a plus qu’à rencontrer trois derniers joueurs. La colorisation en jaune, vert, bleu et marron de chacun de ces joueurs et des trois derniers joueurs qu’ils n’ont pas encore rencontrés révèle une certaine logique symétrique.

  8. 5ème partie : Depuis la copie de la 4ème partie, les cellules d’une même couleur sont copiées horizontalement et chronologiquement dans le tableau de la 5ème partie.

Suite de la démarche algorithmique

La démarche algorithmique a permis d’organiser les cinq parties mais rien n’empêche de la poursuivre pour voir comment elle évolue.

Appliquée sur la 5ème partie, la démarche recrée la 2ème partie qui permet elle-même de recréer soit la 1ère partie, soit la 3ème partie selon que l’on choisit des sélections verticales ou des sélections diagonales. Étonnant ! Non ?

Liste des joueurs / partie, pour chaque joueur

Les tableaux Joueurs N° 1 à Joueurs N° 16 affichent pour chacun des joueurs les autres joueurs qu’il rencontre à chaque partie.

Pour créer le tableau récapitulatif d’un joueur, il suffit de copier la ligne de chaque partie citant le joueur.

Liste des joueurs de chaque partie / table

Pour créer le tableau récapitulatif du tournoi pour chaque table, il suffit de copier depuis chaque partie la ligne correspondant à la table.

Conclusion

C’est juste un exercice de réflexion faisant appel à l’imagination, à l’intuition, à la chance et à la logique séquentielle.

Cette simulation se suffit à elle-même mais rien n’empêche maintenant d'en programmer l'algorithme qui ne serait qu’une liste d’instructions d’affectation équivalentes à ce qui a été fait sous Excel.

L’Intelligence Artificielle via ChatGPT tente d’apporter une solution à cette problématique par la logique combinatoire mais ne finalise pas…

Je ne suis pas sûr que ce soit facile à informatiser dans une logique combinatoire. Je ne trouve pas vraiment de logique itérative susceptible d’être traduite par un algorigramme.

Le sujet a été proposé sur le forum Algorithmes et structures de données

Envoyer le billet « [TUTORIEL] Tournoi entre 16 joueurs (4 joueurs/table) » dans le blog Viadeo Envoyer le billet « [TUTORIEL] Tournoi entre 16 joueurs (4 joueurs/table) » dans le blog Twitter Envoyer le billet « [TUTORIEL] Tournoi entre 16 joueurs (4 joueurs/table) » dans le blog Google Envoyer le billet « [TUTORIEL] Tournoi entre 16 joueurs (4 joueurs/table) » dans le blog Facebook Envoyer le billet « [TUTORIEL] Tournoi entre 16 joueurs (4 joueurs/table) » dans le blog Digg Envoyer le billet « [TUTORIEL] Tournoi entre 16 joueurs (4 joueurs/table) » dans le blog Delicious Envoyer le billet « [TUTORIEL] Tournoi entre 16 joueurs (4 joueurs/table) » dans le blog MySpace Envoyer le billet « [TUTORIEL] Tournoi entre 16 joueurs (4 joueurs/table) » dans le blog Yahoo

Mis à jour 30/06/2024 à 11h40 par APL-AML

Catégories
■ ALGORITHMIQUE

Commentaires

  1. Avatar de APL-AML
    • |
    • permalink
    Réponse de ChatGPT :

    Le problème que vous soulevez est celui de la répartition de joueurs en rotations pour des parties de jeu, avec la contrainte que chaque joueur doit changer de table à chaque partie et ne doit pas rejouer avec les mêmes joueurs dans les parties successives.

    Pour une solution structurée, nous pouvons nous inspirer des concepts de la théorie des graphes et des permutations. Une approche courante pour ce type de problème est l'utilisation d'un calendrier tournant qui s'assure que chaque joueur joue avec tous les autres joueurs au moins une fois, et que les rotations respectent les contraintes données.

    Pour commencer, posons les bases :

    1. *Nombre de joueurs :* 16 (4 tables de 4 joueurs).

    2. *Nombre de parties :* Assez pour que chaque joueur change de table et rencontre des combinaisons différentes.


    ### Étapes de résolution :

    1. *Établir une première répartition aléatoire des joueurs :

      * Assigner 4 joueurs à chaque table de manière aléatoire pour la première partie.

    2. *Définir les permutations pour les parties suivantes :

      * Utiliser des permutations pour réassigner les joueurs à différentes tables tout en respectant les contraintes.

    3. *Créer un calendrier de rotation :

      *Créer un calendrier de rotation :* Assurer que chaque joueur change de table et de partenaires de jeu à chaque partie.


    ### Exécution de l'algorithme :

    Nous allons créer un algorithme simple pour illustrer ce processus. Commençons par une répartition initiale des 16 joueurs (nommés A1 à A16) et appliquons une rotation pour plusieurs parties.

    python

    import random

    # Initialisation des joueurs

    joueurs = [f'A{i}' for i in range(1, 17)]


    # Mélanger les joueurs aléatoirement pour la première partie

    random.shuffle(joueurs)


    # Afficher la répartition initiale

    tables = [joueurs[i:i+4] for i in range(0, 16, 4)]
    print("Première partie:")
    for i, table in enumerate(tables):
    print(f"Table {i+1}: {table}")


    # Nombre de parties

    n_parties = 5 # Ajustez en fonction des besoins


    # Fonction pour générer des permutations pour les parties suivantes

    def generer_permutations(joueurs, n_parties):
    permutations = [joueurs[:]]
    for _ in range(1, n_parties):
    random.shuffle(joueurs)
    permutations.append(joueurs[:])
    return permutations


    # Générer les permutations pour les parties suivantes

    permutations = generer_permutations(joueurs, n_parties)


    # Afficher les rotations des tables pour chaque partie

    for partie in range(1, n_parties):
    tables = [permutations[partie][i:i+4] for i in range(0, 16, 4)]
    print(f"\nPartie {partie + 1}:")
    for i, table in enumerate(tables):
    print(f"Table {i + 1}: {table}")


    ### Explications :

    1. *Initialisation et répartition initiale :* Nous créons une liste de joueurs et la mélangeons pour la première partie.

    2. *Génération des permutations :* Pour chaque partie suivante, nous mélangeons les joueurs et créons de nouvelles répartitions.

    3. *Affichage des résultats :* Nous affichons les tables pour chaque partie, illustrant ainsi la rotation des joueurs.


    Cet exemple simple utilise une méthode de permutation aléatoire pour illustrer le concept. Pour une solution optimale, il peut être nécessaire d'utiliser des algorithmes plus sophistiqués qui garantissent qu'aucun joueur ne joue deux fois avec le même partenaire dans les parties successives. Des algorithmes tels que le "Round-robin" ou des techniques de la théorie des graphes peuvent être utilisés pour améliorer cette solution.