Cette page décrit l'algorithme utilisé par la Fédération
Française de Go, 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.
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? :
Dernière modification : 12/04/2006
