Le site de DarkOli - Programmation - Organisation des rencontres lors d'un tournoi

• Accueil =
• Programmation =
• Échecs =
• Linux =
• Recettes =
• Divers

Organisation des rencontres lors d'un tournoi

  Actuellement je travaille sur un petit programme qui doit générer la liste des rencontres lors d'un tournoi toutes rondes. Les participants doivent tous se rencontrer.

  Par exemple, huit personnes participent à un tournoi d'échecs. Au total chacun aura sept matchs à réaliser. Le but est de trouver de quelle façon ordonner les matchs pour qu'en sept tours le tournoi soit terminé. À chaque tour, tout le monde joue, deux participants ne peuvent se rencontrer qu'une seule fois lors du tournoi.

  Cas particulier : si le nombre de participants est impair, il suffit d'ajouter un participant "bidon". La personne qui rencontre le joueur "bidon" se repose !

  Quand j'avais écris ce petit article, je ne connaissais pas le système (ou les tables) de Berger. Ce sytème permet de définir la liste des rencontres ronde par ronde de façon très simple !

  Les tables de Berger :

  Pour cela on utilise un tableau de N/2 lignes (nombre de rencontres par ronde) et de 2 colonnes. Le tableau est initialisé de la façon suivante :

  Le joueur #1 rencontre le joueur N, le joueur 2 rencontre le joueur N-1, ...

  Pour le tour suivant, il suffit de faire tourner les joueurs dans le sens inverse des aiguilles d'une montre sauf le joueur N qui ne bouge pas.

  Voilà, il suffit de répéter l'opération autant de fois que nécessaire : N-2.

  Comme pour la première rencontre de chaque ronde, le joueur N est toujours en deuxième position, il faut le passer en première position une fois sur deux.

  Les sites reprennant les tables de Berger liste les rondes en fonction du joueur rencontré par le joueur #1. La ronde où le joueur #1 rencontre le joueur #3 est la troisième ronde ! La ronde où le joueur #1 rencontre le joueur N est la première ronde.

Ancien article

  Premièrement, il faut lister toutes les possibilités de rencontres. N est le nombre de joueurs, si ce nombre est impair, il est incrémenté de un, donc N est pair !

  Comment représenter les rencontres ? Sachant que le tournoi est composé de N-1 tour et qu'à chaque tour il y a N/2 rencontres j'ai tout simplement décidé d'utiliser un tableau de N cases pour représenter un tour et un deuxième tableau de N-1 tableaux de tour pour le tournoi. Je vais représenter le contenu d'un tableau de tour par une suite de N nombres (les numéros des joueurs). Un tour est donc simplement une suite de nombres. Dans un même tour, chaque nombre apparaît une seule fois. Les nombres étant compris entre 1 et N. Voilà un exemple de tour (N=4) :

  Dans cet exemple, le joueur #1 rencontre le joueur #2 et le joueur #3 rencontre le joueur #4. Le joueur #1 est le premier joueur de la rencontre #1, il en est de même pour le joueur #3 mais pour la rencontre #2. Les joueurs #2 et #4 sont donc les deuxièmes joueurs des rencontres #1 et #2.

  Il suffit maintenant de déterminer toutes les possibilités de rencontres. En premier lieu, j'ai pensé à une fonction récursive qui placerait le joueur #1 sur l'une des cases vides du tableau, ensuite il faudrait faire de même avec le joueur #2, et ensuite de suite jusqu'à arriver à placer tous les joueurs. À ce moment là, on a un tour "possible".

  Avant d'aller plus loin, il est important de savoir où l'on va ! En effet, combien existe t-il de suites possibles avec N joueurs ? Le but est d'estimer le nombre d'itérations nécessaires lors de notre recherche. Le calcul est très simple, il suffit de penser à la façon dont on va placer les joueurs dans le tableau. Pour le premier, toutes les cases sont vides, nous avons donc N choix possibles, pour le second, une des cases est occupée, il reste donc N-1 choix, pour le troisième il en reste N-1 et pour le dernier il ne reste plus qu'une case vide !

  Pour N=4, il y a donc 4x3x2x1 = 24 tours possibles, soit N!. Voilà donc la liste des tours possibles pour N=4 :

  Toujours pour N=4, il faut donc 3 tours pour réaliser tous les matchs nécessaires pour notre tournoi. Comment trouver 3 tours "compatibles" ? Chaque rencontre ne doit avoir lieu qu'une seule fois, sachant que si le joueur #1 rencontre le joueur #2 il n'est pas nécessaire que le joueur #2 rencontre le joueur #1 ! Pour diminuer la quantité de tours possibles à analyser, nous allons d'abord "supprimer" les tours "équivalents".

  Dans notre exemple, les tours #00 et #01 sont équivalents mais il y a encore d'autres tours équivalents au tour #00. À partir d'un tour donné il nous faut déterminer le nombre de permutations équivalentes. Premièrement, nous pouvons déjà intervertir les joueurs de chaque rencontre. Cela donne 2^(N/2) possibilités :

  Deuxièmement nous pouvons aussi intervertir les rencontres elles-mêmes. Cela donne (N/2)! possibilités :

  En combiant, les deux types de permutations vues ci-dessus cela nous donne P = (2^(N/2))*((N/2)!) possibilités. "Des possibilités de quoi ?" vous allez me dire ! Tout simplement lorsque que l'on sélectionne un tour pour le tournoi, nous en utilisons P sur les N! disponibles. Pour en finir avec les équivalences, voici toutes les possibilitées de tour (N=4) mais regroupées par tours équivalents (même couleur) :

  Donc pour N=4, il existe seulement 3 tours réellement différents, les tours #00, #02 et #03. Tous les autres tours sont équivalents à l'un de ces trois tours. Alors lorsque j'ai écris ma fonction récursive qui génère la liste des tours possibles j'ai ajouté deux règles :

• Le premier joueur d'une rencontre doit avoir le plus petit numéro,
• Les rencontres doivent être classées de la plus petite à la plus grande.

  Première règle : juste avant d'attribuer un joueur à une case vide dont le rang est pair, je vérifie (dans le cas où la case suivante n'est pas vide) que son numéro est bien inférieur à celui-de l'autre joueur. Si ce n'est pas le cas, j'arrête de constituer cette pérmutation et je reviens en arrière d'un niveau. Maintenant si je veux attribuer un numéro de joueur à une case vide dont le rang est impair (et si la case précédante n'est pas vide), le numéro du joueur doit être supérieur au numéro qui se trouve dans la case précédante. Prenons en exemple le tour #01 (N=4). Je place le numéro #1 dans la case #0, la case #1 est vide donc je continue. Je place le numéro #2 dans la case #1, 2 est bien supérieur au numéro contenu dans la case #0, je continue. Je place 4 dans la case #2, la case #3 est vide, je continue. Je veux placer 3 dans la case #3, mais comme la case #2 contient 4 je ne peux pas le faire !

  Ci-dessus j'ai utilisé le terme rang pour désigner le numéro d'une case, ceci afin de ne pas utiliser le terme numéro que je réserve pour les joueurs. La première case du tableau est la case #0 (de rang 0).

  Comment trier les rencontres ? Les numéros des joueurs sont triés deux par deux (dans chaque rencontre), il suffit d'utiliser le premier numéro de chaque rencontre pour pouvoir les ordonner. Le principe utilisé est le même que pour la première règle. Lorsque je place un numéro pour un rencontre donnée, si ce numéro est le premier joueur de la rencontre et s'il est inférieur au premier numéro de la rencontre précédante, je passe à la permutation suivante, et je fais de même dans le cas où le premier numéro de la rencontre suivante est inférieur au numéro que je veux placer actuellement. Attention, avant de réaliser ces deux tests il faut vérifier que l'on ne sorte pas du tableau de tour !

  Il est aussi possible d'ajouter une troisième règle : lorsque nous ajoutons un numéro en deuxième position d'une rencontre, il doit déjà y avoir un numéro en première position sinon cela veut dire que la première règle (tri des numéros d'une rencontre) ne sera pas respectée. En effet, la fonction récursive place d'abord le joueur numéro #1, puis le deuxième jusqu'à arriver au dernier joueur. Par exemple, si 1 est placé dans la case #1, la case #0 sera obligatoirement occupée par un numéro plus grand !

  Quelle est l'impact des règles sur le nombre d'appels de la fonction récursive. Le but est de trouver toutes les permutations possibles en évitant au maximum les permutations équivalentes !

  Ce tableau contient le nombre d'appels récursifs pour générer tous les tours possibles. On s'aperçoit que la règle la plus efficace est la règle #3 (c'était donc une bonne idée !!!). Elle est même plus efficace que les règles #1 et #2 utilisées ensembles jusqu'à N=8 et cerise sur le gâteau c'est la règle la plus simple à coder. Ensuite le meilleur couple est composé des règles #2 et #3, ces deux règles sont vraiement complèmentaires. Utiliser les trois règles ensembles est inutile.

  Pour information, sur un Athlon XP 2100+, il faut plus de 151 secondes pour générer tous les tours possibles sans utiliser de règles (N=12). Avec la règle #2 (la moins efficace) on passe à 12 secondes pour arriver à moins d'une seconde avec les règles #2 et #3 utilisées ensembles.

  Pour N=10, il existe N! pérmutations possibles. Mais combien de permutations sont réellement intéressantes ?

À suivre !!!

  Définir le vocabulaire utilisé de façon à être rigoureux bordel !!! Permutation = ..., tour = ...

• Le nombre de tours possibles (hors équivalence) et les règles,
• Le code de la fonction récursive commenté (sans règles),
• Le code ajouté pour mettre en place les règles,
• Comment tester la compatibilité d'un tour avec ceux déjà prévu pour le tournoi (les joueurs doivent se rencontrer une seule fois, ...),
• Trouver une possibilité de tournoi,
• Trouver toutes les possibilités,
• Nouvelle méthode plus rapide (constatation déduites à partir des règles),
• Relire mon texte,
• Rerelire mon texte,
• Rererelire mon texte.

La page respecte le standard XHTML 1.0 Strict.
-- Darkoli, dernière mise à jour le 14 mai 2007 [23:37] --