Un algorithme pour mettre en rang une équipe de football
Réaliser un alignement, une évidence ? Pas si sûr... Du sport de ballon au sport cérébral, découvrez différentes méthodes pour y parvenir.
1. Aligner des joueurs sur un terrain
Lors de la dernière coupe du monde de football, l’équipe d’Allemagne a chuté en demi-finale mais a impressionné par sa qualité de jeu et par sa rigueur. Le sélectionneur avait mis au point une méthode infaillible pour aligner les joueurs avant d’écouter l’hymne national. Comme il n’a pas utilisé cet algorithme pour les matches, on n’a pas pu en admirer l’efficacité : merci au professeur Ulrich Rüde et à Christoph Freundl, de l'Université d'Erlangen, de nous l'avoir communiqué.
Tous les joueurs sont sur le terrain, en train de s'échauffer, et peuvent se déplacer sur toute la surface. Puis ils doivent former une ligne droite, matérialisée par des drapeaux aux extrémités. Ces drapeaux sont bien sûr retirés avant de jouer et l'alignement ne sert pas pendant la phase de jeu.
Les joueurs doivent se placer entre les deux drapeaux, pour former une ligne, et se positionner à intervalles réguliers. Ils portent un maillot avec un numéro de 1 à 11. Le joueur 1 doit se trouver près du drapeau de gauche, puis le joueur 2 à côté, et ainsi de suite, jusqu'au joueur 11, avant le drapeau de droite.
La méthode allemande
Au départ, les joueurs sont éparpillés sur le terrain. Intuitivement, la ligne sera réalisée si chaque joueur portant le maillot i est au milieu des joueurs voisins, avec les maillots (i-1) et (i+1), pour i variant de 2 à 10. Par exemple, le joueur 4 est au milieu des joueurs 3 et 5. Le joueur 1 est entre le drapeau de gauche et le joueur 2 ; le joueur 11 est entre le joueur 10 et le drapeau de droite.
Le sélectionneur agit du bord du terrain. Il appelle, avec son sifflet, les joueurs l'un après l'autre et leur dit de se placer au milieu des joueurs voisins : le joueur avec le maillot 1 se place au milieu du drapeau de gauche et du joueur 2, puis le joueur 2 se place au milieu des joueurs 1 et 3 ; ainsi de suite, jusqu'au joueur 11 qui se place au milieu du joueur 10 et du drapeau de droite. Les joueurs ne sont pas encore alignés, loin de là. Alors le sélectionneur recommence les déplacements. Il utilise ainsi un algorithme itératif. Chaque itération consiste à placer les 11 joueurs l'un après l'autre et nécessite ainsi 11 déplacements de joueurs.
Au bout de plusieurs itérations, les joueurs forment plus ou moins un rang. S'ils pouvaient continuer à se déplacer indéfiniment, ils finiraient par être tout à fait alignés. L'algorithme converge vers le résultat voulu, qui est une ligne droite. La convergence est garantie, quelle que soit la position de départ des joueurs. Le sélectionneur arrête de déplacer ses joueurs quand il considère que l'alignement est assez bon. Il utilise un critère d'arrêt de l'algorithme itératif.
Chaque itération prend un peu de temps, car chaque joueur i attend que le joueur (i-1) ait bougé pour se déplacer à son tour. C'est pourquoi le sélectionneur a imaginé une autre version. Il déplace d'abord les joueurs avec un numéro pair, puis les joueurs avec un numéro impair. Du coup, tous les joueurs pairs peuvent se déplacer ensemble, puisqu'ils se placent au milieu de joueurs impairs qui bougeront après eux. Ainsi, le joueur 2 se positionne entre le joueur 1 et le joueur 3, en même temps que le joueur 4 entre le joueur 3 et le joueur 5, etc. Puis tous les joueurs impairs peuvent se déplacer ensemble, puisqu'ils se placent au milieu de joueurs pairs qui ont fini de bouger. Les itérations peuvent également continuer jusqu'à former une ligne presque droite. On observe qu'il faut un peu plus d'itérations. Par contre, chaque itération prend moins de temps, parce que les joueurs peuvent se déplacer simultanément. Il y a ainsi un compromis à trouver entre la vitesse d'exécution de chaque itération et la vitesse de convergence de l'algorithme.
| Applet réalisée par Régis Monte, d'après Christoph Freundl. Si l'applet ne s'affiche pas correctement, vérifiez votre configuration technique |
 | |
| Applet réalisée par Régis Monte, d'après Christoph Freundl. Si l'applet ne s'affiche pas correctement, vérifiez votre configuration technique |
Tout le monde sait que l'équipe de France n'a pas brillé à la coupe du monde. Le nouveau sélectionneur décide de prendre les choses en main et de tester l'algorithme des Allemands. Pour un stage d'entraînement, il a sélectionné 31 joueurs avec les maillots numérotés de 1 à 31. La règle du jeu est la même, il faut former une ligne entre deux drapeaux, avec les joueurs espacés régulièrement. Les joueurs sont placés au hasard sur le terrain puis, au coup de sifflet, chacun doit se placer au milieu de ses voisins. Le sélectionneur choisit d'appeler les joueurs un par un, dans l'ordre de 1 à 31. On observe qu'il faut beaucoup d'itérations pour obtenir un alignement acceptable. L'algorithme converge toujours, mais beaucoup plus lentement. Pourtant, les Français ont obéi au sélectionneur. Mais ils sont plus nombreux que les Allemands. La vitesse de convergence de l'algorithme dépend du nombre de joueurs : plus les joueurs sont nombreux, plus il faut d'itérations.
La méthode espagnole
L'équipe d'Espagne est championne du monde. Est-ce parce que leur sélectionneur a adopté une méthode différente ?
Pour simplifier, on va supposer que les drapeaux sont sur la ligne de touche, qui est donc tracée. Le sélectionneur utilise des outils : avec un mètre, il mesure la longueur L de cette ligne, puis, avec une calculatrice, il calcule la distance d entre deux joueurs. Lorsqu'il y a 11 joueurs, on a d = L/12; lorsqu'il y a 31 joueurs, on a d = L/32. Ensuite, le sélectionneur prend un bâton, fait une marque sur le bâton à la distance d.
Au coup de sifflet, le joueur 1 prend le bâton, va se placer sur la ligne, près du drapeau de gauche; il mesure sa place grâce au bâton, il est ainsi à la distance d du drapeau. Au coup de sifflet suivant, le joueur 2 prend le bâton et va se placer sur la ligne, près du joueur 1, à une distance d. Ainsi de suite, jusqu'au joueur 11. Ainsi, tous les joueurs sont sur la ligne, matérialisée sur le terrain, et sont espacés régulièrement avec une distance d entre les joueurs. Si les mesures sont justes et si les joueurs ont bien utilisé le bâton, le joueur 11 est à une distance d du drapeau de droite.
Le sélectionneur espagnol a utilisé un algorithme direct : il n'y a pas d'itérations. Grâce au bâton étalonné, chaque joueur ne se déplace qu'une seule fois, soit au total 11 déplacements, pour obtenir un alignement parfait. Avec 31 joueurs, il y a au total 31 déplacements.
La méthode du XV de France
Le XV de France rend visite à l'équipe de foot. Les joueurs de rugby font le pari qu'ils peuvent s'aligner entre les drapeaux, sans faire de mesure, avec 15 déplacements de joueurs, mais en seulement 4 étapes. Pari tenu, les joueurs de rugby font la démonstration.
Le joueur 8 se place au milieu des drapeaux. Ensuite, le joueur 4 va se placer au milieu du drapeau de gauche et du joueur 8, tandis que le joueur 12 va se placer en même temps au milieu du joueur 8 et du drapeau de droite. Troisième étape, les joueurs 2, 6, 10 vont se positionner à leur place, en même temps, au milieu des joueurs déjà placés (par exemple, le 6 au milieu du 4 et du 8). Quatrième et dernière étape, les joueurs impairs vont se placer au milieu des joueurs pairs, tous en même temps.
| Applet réalisée par Régis Monte. Si l'applet ne s'affiche pas correctement, vérifiez votre configuration technique |
 | |
| Applet réalisée par Régis Monte. Si l'applet ne s'affiche pas correctement, vérifiez votre configuration technique |
Le XV de France a donc gagné son pari. L'équipe de rugby a utilisé un algorithme direct parallèle. Comme avec l'algorithme espagnol, il y a 15 déplacements, mais ces déplacements peuvent se faire simultanément, ce qui permet d'aligner parfaitement les joueurs en 4 étapes.
Le sélectionneur de foot veut essayer l'algorithme, encore mieux, avec 31 joueurs. En 5 coups de sifflet, le tour est joué :
- 1er coup de sifflet : joueur 16 au milieu des drapeaux.
- 2e coup de sifflet : joueurs 8 et 24 à leur place.
- 3e coup de sifflet : joueurs 4, 12, 20, 28 en poste.
- 4e coup de sifflet : joueurs 2, 6, 10, 14, 18, 22, 26, 30 sur la ligne.
- 5e coup de sifflet : joueurs impairs pour finir.
Le capitaine de rugby lance alors un nouveau défi : utiliser l'algorithme avec seulement une équipe de 11 joueurs. C'est parti :
- 1er coup de sifflet : joueur 6 au milieu.
- 2e coup de sifflet : joueurs 3 et 9 de chaque côté du joueur 6.
- 3e coup de sifflet : cela coince ! il faut utiliser un algorithme permettant de placer 2 joueurs entre 2 autres. Admettons que 2 joueurs sachent faire cela, avec un algorithme direct comme celui des Espagnols. Alors, les joueurs 1 et 2 vont se placer entre le drapeau et le joueur 3. En même temps, les joueurs 4 et 5 se positionnent, ainsi que les joueurs 7 et 8, et les joueurs 10 et 11.
Au prix d'une petite modification de l'algorithme, il fonctionne ainsi avec un nombre quelconque de joueurs. Il faut savoir placer un joueur au milieu de deux autres et aussi placer deux joueurs ensemble, chacun à une distance d/2 du milieu (d étant la distance entre deux joueurs). Ainsi, l'équipe de France de foot va se déplacer très rapidement sur le terrain et — qui sait ? — réaliser des prouesses.
Français