Logo FFG Recherche sur le site Menu du site Revue Française de go

Echelle de niveau : algorithme 2012

1- Description de l'algorithme
2- Ajustements
3- Justifications
4- Comparaison avec d'autres algorithmes de calcul

Cette page décrit l'algorithme qui a été utilisé par la Fédération Française de Go de 2003 à fin 2012, et le compare avec d'autres.

1 - Description de l'algorithme

NB = Niveau de Blanc à l'échelle  (100..199 = 2d, 0..99 = 1d, -100..-1 = 1k)
NN = Niveau de noir à l'échelle
H  = Nombre de pierres de handicap
     (H = 1 pour une partie à sen avec komi de 0,5)

NFB = Niveau Fictif de Blanc =  NB Niveau de l'échelle
NFN = Niveau Fictif de Noir 
    = NN Niveau de l'échelle si la partie est a égalité
      NN + 100*(H - 0,5) sinon.

NFG = Niveau Fictif du Gagnant
NFP = Niveau Fictif du Perdant

Etape 1: variation brute

La variation "brute" du niveau du gagnant est 15 + (NFP-NFG)/15 limitée à l'intervalle [1 .. 40]. La variation "brute" du niveau du perdant est l'opposé de la variation du gagnant, mais limitée à l'intervalle [-15 .. -1].

Si le gagnant a un niveau supérieur à 400, la variation brute de son niveau est limitée à l'intervalle [0 .. 40].

Si le perdant a un niveau inférieur à -2000, la variation brute de son niveau est limitée à l'intervalle [-1 .. 0].

La variation brute du niveau d'un joueur de niveau supérieur ou égal à -2000 rencontrant un joueur de niveau inférieur à -2000 est limitée à l'intervalle [-1 .. 1].

Etape 2: parties à handicap

Les variations calculées à l'étape 1 sont multipliées par 1 - H/10 pour les deux joueurs. Les parties à plus de 9 pierres de handicap ne comptent pas.

Pour les joueurs de niveau inférieur à -2000, le coefficient est 1 quel que soit le handicap

Etape 3: parties 9x9 ou 13x13

Les variations calculées à l'étape 2 sont multipliées par 0,2 pour les parties 13x13 ou par 0,1 pour les parties 9x9. Les parties autres que 19x19, 13x13 ou 9x9 ne comptent pas. (Pour les parties 13x13 et 9x9, des tables de conversion des handicaps peuvent être trouvées ici) .

Pour les joueurs de niveau inférieur à -2000, le coefficient est 1 quelle que soit la taille du GoBan.

Etape 4: parties rapides

Les parties avec un temps d'une heure par joueur plus byo-yomi de 5 minutes pour 15 coups sont comptées normalement avec un coefficient 1. Pour les parties plus rapides, mais avec un temps minimum de 30 minutes par joueur, les variations calculées à l'étape 3 sont multipliées par 0,5 pour les deux joueurs. Les parties très rapides (moins de 30 mn par joueur) ne comptent pas pour l'échelle.

Pour les joueurs de niveau inférieur à -2000, le coefficient est 1 quel que soit le temps de réflexion.

Etape 5: pondération en fonction du niveau

Les variations calculées à l'étape 4 sont multipliées par 1 - N/1000, limité à l'intervalle [0,1 .. 2,5] pour chacun des deux joueurs, avec N = NB pour blanc et N = NN pour noir. Enfin les nouveaux niveaux NB et NR sont calculés comme la somme des anciens niveaux et des variations, et utilisés pour la ronde suivante du tournoi.

Etape 6: plancher 

Lorsque le niveau calculé à l'étape 5 descend en dessous de -2950 celui ci est ramené à -2950.

2 - Ajustements

Deux cas font l'objet d'un traitement particulier:
- Les joueurs qui ne sont pas connus de l'échelle. Leur niveau initial est alors le niveau d'inscription au tournoi (1d = 50, 1k = -50). Mais si après le traitement (étapes 1 à 6) de toutes les parties d'un joueur inconnu, la variation de niveau de ce joueur est supérieure à 50 points en valeur absolue (0,5 pierre en plus ou en moins), alors le niveau d'inscription est considéré comme incorrect (trop optimiste ou trop pessimiste), on procède alors à un ajustement préalable.
- Les joueurs connus qui ont beaucoup progressé ou régressé. C'est un cas qui se produit typiquement pour les joueurs débutants ou ceux n'ayant pas participé à des tournois depuis un certain temps. Comme pour les joueurs inconnus, si le calcul montre une variation importante, on procède à un ajustement. Pour eux le seuil est fixé à 100.

L'algorithme d'ajustement: Un calcul complet est fait. Puis, pour tous les joueurs dont la variation delta dépasse le seuil (50 ou 100), le niveau de départ est corrigé de delta-seuil. Cet algorithme est éventuellement répété jusqu'à convergence. Cette convergence est réputée atteinte lorsque les variations entre deux itérations successives des niveaux calculés restent en deça de 10.

Dans les deux cas, ces ajustements permettent de ne pas pénaliser les adversaires des joueurs dont le niveau de départ était manifestement incorrect. Par exemple si un 5k se fait battre par un ex-7k qui a en fait progressé jusqu'au niveau 4k depuis son dernier tournoi, alors le 5k ne perdra pratiquement rien à l'échelle. De même si un nouveau joueur résolument optimiste s'inscrit 7k alors qu'il n'est que 10k, il ne va pas gonfler de manière artificielle le niveau d'un 9k qui l'aurait battu.

L'algorithme converge assez rapidement, en quelques itérations généralement. Chaque itération se fait sur l'ensemble des rondes du tournoi. Cet algorithme itératif permet d'ignorer les niveaux d'inscription fantaisistes. Le niveau des nouveaux joueurs dépend de leurs résultats réels dans le tournoi et non de leur niveau d'inscription. Ceci est important en particulier pour les étrangers qui participent à des tournois français mais qui ont une échelle dans leurs pays surévaluée par rapport à l'échelle française.

3 - Justifications

Une partie à sen (sans komi) correspond à un avantage pour noir d'une demi-pierre seulement, ce qui est aussi la valeur du komi dans une partie à égalité. Soit P la valeur d'une pierre (le nombre de points supplémentaires obtenus en jouant cette pierre), et V la valeur du trait (être le prochain à jouer), en supposant que V varie très peu d'un coup à l'autre. Jouer le premier coup vous fait gagner P points, mais c'est alors à votre partenaire de jouer, ce qui vaut V points. Donc la valeur du trait V est égale à P-V: 
   V = P - V
   P = 2*V ou V = P/2
L'avantage initial de noir dans une partie sans komi (h1) est égal à V, et aussi égal au komi dans une partie à égalité: V=7,5 points (en prenant la valeur utilisée le plus souvent pour le komi). La valeur d'une pierre est égale à 2*V, soit 15 points.

L'avantage initial de noir dans une partie à h2 est égal à l'avantage de noir dans une partie à h1 plus une pierre, c'est à dire V+P ou 1,5*P. Ceci est la raison de la règle NFN = NN + 100*(H - 0,5)

L'étape 1 peut sembler causer une inflation du niveau moyen dans l'échelle (si le gagnant gagne plus que 15 points), mais en fait ceci est compensé par l'arrivée de nouveaux débutants. De plus certains joueurs en kyu progressent rapidement, et l'algorithme doit pouvoir s'adapter à de telles progressions sans trop pénaliser les adversaires. C'est pourquoi la variation du vainqueur peut être supérieure en valeur absolue à celle du perdant.

L'étape 2 réduit l'impact des parties à fort handicap. Le jeu à fort handicap est très différent du jeu à égalité, et moins fiable comme mesure de la force réelle d'un joueur. Cependant les parties à handicap restent importantes pour l'échelle; elles tendent à garder le système proche d'un point optimal où une différence de niveaux de 100 points correspond bien à une différence de handicaps d'une pierre. Cela permet de calculer le handicap normal pour une partie: soustraire les niveaux et arondir à la centaine supérieure (par exemple h2 pour une différence de niveaux de 120).

L'étape 3 permet de prendre en compte les tournois officiels joués sur des gobans réduits, ce qui est souvent le cas pour des tournois de jeunes. Cela permet de motiver les jeunes en leur donnant un classement. Cependant l'impact de telles parties sur l'échelle de niveaux est très réduit en raison du faible coefficient multiplicateur.

L'étape 4 permet de prendre en compte les parties rapides de manière très simple. La fédération Européenne a une règle similaire mais plus complexe.

L'étape 5 permet une progression rapide des joueurs en kyu tout en assurant une stabilité du niveau des joueurs en dan. Ceci reflète le fait qu'il est bien plus facile de progresser de 10k à 8k que de 4d à 6d. Les joueurs les plus forts dont le niveau est stable servent ainsi d'ancrage pour l'ensemble de l'échelle.

4 - Comparaison avec d'autres algorithmes de calcul

L'algorithme décrit ci-dessus a des avantages importants par rapport à d'autres méthodes, telles que celle utilisée par IGS (Internet Go Server) ou l'AGA (American Go Association), décrite ici (voir aussi le pseudo-code et le logiciel AccelRat ):
  • Simplicité: il n'utilise que des opérations élementaires. N'importe qui peut faire le calcul pour prédire ou vérifier une variation de niveau après une partie. Ceci est impossible avec l'algorithme AGA/IGS.

  • Prévisibilité: la variation de niveau due à une partie ne dépend que de cette partie. Le gagnant progresse toujours au moins un peu, le perdant régresse toujours au moins un peu. Avec l'algorithmes AGA/IGS, le gagnant peut tout à fait voir son niveau baisser. (Cela arrive effectivement sur IGS, ce n'est pas une simple curiosité). Ceci est du à l'effet de mémoire de ces algorithmes: toutes les parties antérieures ont un effet sur la variation de niveau. Considérez le scénario suivant:
    • A (1k) perd contre B (1k)
    • B (1k) perd contre C (3k)
    • A (1k) gagne contre D (3k)
    La première partie fait peu varier les niveaux, A et B restent 1k. Suite à la deuxième partie, B voit son niveau nettement baisser, par exemple de 1k à 2k. Quand A gagne la troisième partie, l'algorithme reprend en compte la perte contre B qui est maintenant 2k. Donc malgré la victoire contre D, naturelle mais qui rapporte peu à l'échelle, le niveau de A se met à baisser suite à cette victoire.

  • Variations bornées: la variation de niveau due à une seule partie est toujours limitée à des valeurs raisonables, même en cas de résultat vraiment inattendu. Avec l'algorithme AGA/IGS, des variations importantes peuvent arriver initialement, quand très peu de parties ont été jouées par un joueur donné. NNGS résoud ce problème en n'affectant aucun niveau jusqu'à ce qu'un nombre suffisant de parties aient été jouées.

  • Variations graduelles: pour un résultat inattendu, l'algorithme AGA/IGS donne généralement une variation constante du niveau, indépendament de la différence des niveaux. (Ceci est du à la forme particulière de la fonction de probabilité utilisée par cet algorithme.) Avec l'algorithme français, battre quelqu'un plusieurs pierres au dessus de soi rapporte plus de points que battre quelqu'un juste 0,1 pierre au dessus.
L'algorithme utilisé par l'Association Tchèque de Go est assez similaire au système français.

Aucun algorithme n'est parfait et certains peuvent trouver plus logique de reprendre en compte toutes les parties plutôt que la dernière seulement lors du calcul de l'effet d'une partie. Cependant l'algorithme de la FFG a fait ses preuves et les avantages décrits ci-dessus me semblent décisifs.


Un problème sur cette page? : julien.derveeuwlifl.fr
Dernière modification : 12/04/2006