Au Pied Levé - À Main Levée

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

Public :

• étudiants
• débutants
• et pourquoi pas, enseignants

Contenu :

• Réflexion IN (Intelligence Naturelle)
• Intuition
• Imagination
• Logique séquentielle
• ChatGPT

Exercice corrigé d'algorithmique (Force 3/7)

■ ■ ■ SOMMAIRE DU BILLET ■ ■ ■

• AVANT-PROPOS
  
  • Présentation du sujet
  • Motivations et raisons ayant poussé à étudier le sujet
  • Objectifs poursuivis
  • Difficultés rencontrées
  • Documents publiés
  • Discussions similaires

1. Tournoi entre 16 joueurs (4 joueurs/table)
2. Analyse de la problématique
3. Simulation
4. Algorithme
5. Suite de la démarche algorithmique
6. Conclusion

• ANNEXE : Version ChatGPT

■ AVANT-PROPOS

• Présentation du sujet
  
  Chaque partie d’un tournoi oppose 4 joueurs par table. 16 joueurs sont en lice autour de 4 tables. À chaque nouvelle partie du tournoi, les 16 joueurs doivent être affectés à l’une des 4 tables de façon à ce qu’aucun joueur ne rencontre deux fois un même autre joueur.
  
  
• Motivations et raisons ayant poussé à étudier le sujet
  Intéressé par cet exercice découvert au hasard de mes navigations sur internet, j’ai cherché la solution en utilisant mon IN (Intelligence Naturelle).
  
  Ma solution est peu orthodoxe mais je manque d’imagination pour concevoir un algorithme faisant appel à une logique combinatoire.
  
  
• Objectifs poursuivis
  
  Proposer l’exercice sur DVP avait pour objectif l’espoir d’un retour susceptible de servir de tutoriel d’algorithmique avec un algorigramme facile à programmer.
  
  
• Difficultés rencontrées
  
  Commenter la simulation en pseudocode est une chose mais traduire le pseudocode en un algorigramme à programmer en est une autre.
  
  ChatGPT dit pouvoir s’inspirer des concepts de la théorie des graphes et des permutations, et évoque l'utilisation d'un calendrier tournant.
  
  Pour ChatGPT, cet exemple est simple et utilise une méthode de permutation aléatoire pour chaque nouvelle partie.
  
  Si ChatGPT le dit…
  
  ChatGPT propose du code Python malheureusement impossible à vérifier.
  
  
• Documents publiés
  
  Le présent Billet de mon Blog logique Algorithmique et ce même tutoriel au format PDF :
  
  
  [TUTORIEL] Tournoi entre 16 joueurs.pdf
  
  Cet exercice a fait l’objet d’une discussion ouverte le 25/12/2021 sur le Forum Algorithmes et structures de données :
  
  
  Tournoi entre 16 joueurs (4 joueurs/table)
  
  
• Discussions similaires
  
  
  Rotations pour un tournoi
  

  Par Ogival dans le forum Forms

§ 1. Tournoi entre 16 joueurs (4 joueurs/table)


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

§ 2. Analyse de la problématique

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 (en jaune) permet d’affecter les joueurs à la 1ère table.
2. La 2ème grande diagonale (en vert) permet d’affecter les joueurs à la 2ème table.
3. Les deux premières demi-diagonales (en bleu) permettent d’affecter les joueurs à la 3ème table.
4. Les deux dernières demi-diagonales (en marron) 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.

§ 3. Simulation



§ 4. Algorithme

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.

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.

§ 5. 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 ?



§ 6. Conclusion

C’est juste un exercice de réflexion faisant appel à l’intelligence naturelle qu’est le raisonnement, à 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 manuellement 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.

Seuls les processus d’affectation des joueurs pour la troisième et la quatrième partie sont identiques. Difficile d’en conclure un algorigramme vraiment intéressant.

Cet exercice a fait l’objet d’une discussion ouverte le 25/12/2021 sur le Forum Algorithmes et structures de données :

Tournoi entre 16 joueurs (4 joueurs/table)

L’intervention d’un membre dans cette discussion a saboté l’exercice en dévoilant le résultat final : Sur ce lien, page 13, on a une solution.

L’objectif n’était pas de trouver la solution sur internet mais de comprendre le problème et trouver soi-même la solution.
Le résultat final n’explique pas comment on arrive à ce résultat.

---

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

---