TrueSkill

TrueSkill es un sistema de clasificación basado en habilidades desarrollado por Microsoft para su uso en el emparejamiento de videojuegos en la red Xbox . A diferencia del popular sistema de clasificación Elo , que fue diseñado inicialmente para el ajedrez , TrueSkill está diseñado para admitir juegos con más de dos jugadores. ^{[ 1 ] [ 2 ] [ 3 ]} En 2018, Microsoft publicó detalles sobre una versión extendida de TrueSkill, llamada TrueSkill2. ^{[ 4 ]}

Se basa en un modelo thurstoniano con una distribución de puntuación gaussiana. No satisface el axioma de elección de Luce . ^{[ 5 ]}

TrueSkill fue desarrollado por investigadores de Microsoft Research como un sistema de calificación de habilidades bayesiano diseñado para juegos en línea en los que los jugadores suelen competir en equipos y las partidas pueden involucrar a más de dos jugadores o equipos. ^{[ 2 ]} En su primera descripción publicada del sistema, Ralf Herbrich, Tom Minka y Thore Graepel evaluaron el método utilizando datos de partidas recopilados por Bungie Studios durante la prueba beta de Halo 2 y describieron su funcionamiento en el servicio Xbox Live . ^{[ 2 ]}

Christopher Bishop escribió más tarde que TrueSkill se implementó en Xbox Live en 2005 y ha operado continuamente desde entonces, procesando millones de resultados de juegos por día. ^{[ 6 ]} Herbrich y sus colegas informaron que, a septiembre de 2005, Xbox Live tenía más de 2 millones de usuarios suscritos y que el servicio Xbox 360 Live usaba TrueSkill para la clasificación automática de jugadores y el emparejamiento, procesando cientos de miles de juegos por día. ^{[ 2 ]}

En un estudio sobre sistemas de clasificación para juegos y evaluaciones, los investigadores del Educational Testing Service describieron TrueSkill como una generalización de las clasificaciones tipo Elo para competiciones multijugador y por equipos, y señalaron su uso en los juegos en línea de Xbox de Microsoft. ^{[ 7 ]} Investigaciones posteriores de Microsoft propusieron revisiones y extensiones al modelo original, incluyendo TrueSkill2. ^{[ 4 ]}

En el modelo descrito por Herbrich, Minka y Graepel, la habilidad de cada jugador se trata como una cantidad no observada (latente), y el sistema mantiene una distribución de probabilidad sobre esa habilidad. ^{[ 2 ]} Se supone que la distribución a priori sobre las habilidades de los jugadores se factoriza entre ellos, y cada habilidad individual se modela como una distribución gaussiana con media${\displaystyle \mu _{i}}$y varianza${\displaystyle \sigma _{i}^{2}}$representando la incertidumbre del sistema sobre la habilidad de ese jugador. ^{[ 2 ]}

Los resultados de los partidos se modelan como resultado de actuaciones ruidosas. Para un juego dado, cada jugador${\displaystyle i}$genera un valor de rendimiento latente${\displaystyle p_{i}}$que normalmente se distribuye en torno a su habilidad${\displaystyle s_{i}}$, con un parámetro de varianza de rendimiento fijo${\displaystyle \beta ^{2}}$: ^{[ 2 ]}$${\displaystyle s_{i}\sim {\mathcal {N}}(\mu _{i},\sigma _{i}^{2}),\qquad p_{i}\sim {\mathcal {N}}(s_{i},\beta ^{2}).}$$ El parámetro${\displaystyle \beta }$controla cuán fuertemente se espera que varíe el resultado de un solo juego en función de la habilidad subyacente (menor${\displaystyle \beta }$implica menor aleatoriedad en los resultados). ^{[ 2 ]}

Para juegos con equipos, el modelo asume una estructura de rendimiento de equipo aditiva: el rendimiento latente${\displaystyle t_{j}}$del equipo${\displaystyle j}$es la suma de las actuaciones de sus miembros,${\displaystyle \textstyle t_{j}:=\sum _{i\in A_{j}}p_{i}}$, dónde${\displaystyle A_{j}}$es el conjunto de jugadores asignados a ese equipo. ^{[ 2 ]} El resultado de un partido se representa como una clasificación de los equipos (con la posibilidad de empates), y la probabilidad de la clasificación observada se define en términos de desigualdades entre las variables de rendimiento del equipo correspondientes. ^{[ 2 ]}

Los sorteos se incorporan mediante la introducción de un margen de sorteo.${\displaystyle \epsilon >0}$Para dos equipos adyacentes en la clasificación, una victoria se modela exigiendo que el equipo mejor clasificado supere al equipo peor clasificado por más de${\displaystyle \epsilon }$, mientras que un empate se modela exigiendo que su diferencia de rendimiento se encuentre dentro de${\displaystyle \pm \epsilon }$. ^{[ 2 ]} Herbrich y colegas relacionaron${\displaystyle \epsilon }$a una probabilidad de empate supuesta o estimada empíricamente, lo que permite calibrar la tasa de empate para un modo de juego determinado. ^{[ 2 ]}

TrueSkill representa el modelo conjunto de habilidades, desempeño y resultados observados como un grafo factorial . ^{[ 2 ]} La inferencia se plantea entonces como el cálculo de marginales aproximadas de una sola variable mediante el paso de mensajes utilizando el algoritmo suma-producto . ^{[ 2 ]} Para una sola coincidencia, la mayoría de los mensajes en el grafo pueden representarse como gaussianas unidimensionales, lo que hace que la actualización sea computacionalmente eficiente. ^{[ 2 ]}

Una dificultad clave es que las restricciones de resultados (victorias y empates) introducen términos no gaussianos. En el gráfico de factores, estos aparecen como factores de comparación que imponen desigualdades en las diferencias de rendimiento (y, para los empates, en un intervalo alrededor de cero). ^{[ 2 ]} Los mensajes exactos correspondientes no son gaussianos; el artículo de TrueSkill aplica la propagación de expectativas (EP) para aproximar estos mensajes mediante la igualación de momentos, reemplazando las formas gaussianas truncadas intratables con aproximaciones gaussianas que tienen la misma media y varianza. ^{[ 2 ] [ 8 ]} Debido a que los mensajes de comparación son aproximados, el algoritmo itera las actualizaciones de mensajes a lo largo de caminos que conectan las variables afectadas hasta que las marginales aproximadas se estabilizan. ^{[ 2 ]}

Tras la inferencia para un partido, la distribución marginal actualizada de cada jugador sigue siendo gaussiana y puede resumirse mediante una media actualizada.${\displaystyle \mu }$y desviación estándar${\displaystyle \sigma }$para su uso en partidos posteriores. ^{[ 2 ]} El sistema original también incluye un parámetro de varianza dinámica (a menudo escrito)${\displaystyle \tau ^{2}}$) para modelar los cambios de habilidad a lo largo del tiempo entre juegos. ^{[ 2 ]}

TrueSkill mantiene una distribución de creencias gaussiana.${\displaystyle {\mathcal {N}}(\mu _ {i}, \sigma _ {i}^{2})}$para la habilidad de cada jugador, pero las implementaciones prácticas también deben elegir una escala numérica y valores para parámetros del modelo como el ruido de rendimiento y la tasa a la que se permite que las habilidades varíen con el tiempo. ^{[ 2 ]} Herbrich y colegas informaron que Xbox Live utilizó una escala previa inicial con${\displaystyle \mu _{0}=25}$y${\displaystyle \sigma _{0}^{2}=(25/3)^{2}}$, correspondiente a una distribución a priori en la que las habilidades negativas son improbables. ^{[ 2 ]}

En la misma descripción de despliegue, la varianza del rendimiento de un solo juego se estableció en relación con la incertidumbre previa como${\displaystyle \beta ^{2}=(\sigma _ {0}/2)^{2}}$y la varianza de la dinámica entre juegos (que modela los cambios de habilidad a lo largo del tiempo) se estableció en${\displaystyle \tau ^{2}=(\sigma _{0}/100)^{2}}$. ^{[ 2 ]}

Para las pantallas orientadas al jugador, como las tablas de clasificación, Xbox Live mostraba una estimación conservadora en lugar de solo la media posterior. El documento TrueSkill describía la visualización de la habilidad de un jugador como el 1% del cuartil inferior de la distribución de creencias,${\displaystyle \mu _{i}-3\sigma _{i}}$. ^{[ 2 ]} Herbrich y sus colegas escribieron que esta elección tenía como objetivo asegurar que los primeros puestos en las clasificaciones fueran ocupados por jugadores que fueran altamente calificados y estimados con alta certeza, y señalaron que la previa implicaba un valor inicial mostrado de${\displaystyle 0=\mu _{0}-3\sigma _{0}}$. ^{[ 2 ]}

El siguiente ejemplo práctico ilustra cómo TrueSkill actualiza las clasificaciones después de una partida de todos contra todos de tres jugadores, utilizando el modelo y las ecuaciones de actualización de victorias descritas por Herbrich, Minka y Graepel. ^{[ 2 ]} En TrueSkill, cada jugador${\displaystyle i}$tiene una distribución de creencias de habilidad${\displaystyle {\mathcal {N}}(\mu _ {i}, \sigma _ {i}^{2})}$, dónde${\displaystyle \mu }$es la estimación media de habilidad y${\displaystyle \sigma }$es la incertidumbre.

Tras un partido, el sistema combina la creencia previa con el resultado del partido para obtener una nueva distribución de creencias (la posterior ). La media posterior es la media de esa distribución actualizada, es decir, la mejor estimación numérica del sistema sobre la habilidad del jugador, dada la evidencia disponible hasta el momento. ^{[ 2 ]}

En la escala original de Xbox Live descrita en el documento de TrueSkill, una opción común para el ruido de rendimiento es${\displaystyle \beta =25/6}$. ^{[ 2 ]} Este ejemplo utiliza ese valor y supone que no hay empates.

En 2018, investigadores de Microsoft publicaron TrueSkill2 como una extensión del modelo TrueSkill original que incorpora información adicional disponible en algunos juegos en línea, más allá del orden final de victorias y derrotas. ^{[ 4 ]} El artículo describe el uso de señales como la experiencia del jugador, la pertenencia a un escuadrón, las estadísticas individuales (por ejemplo, recuentos de bajas y muertes), el comportamiento de abandono y el rendimiento en otros modos de juego, con el objetivo de mejorar la precisión de las habilidades inferidas para el emparejamiento. ^{[ 4 ]}

Los autores describieron TrueSkill2 como un sistema que conserva la misma interfaz que el TrueSkill clásico, una calificación de habilidad numérica única diseñada para seguir siendo compatible con los sistemas de emparejamiento existentes, pero que cambia la forma en que se infieren las habilidades a partir de datos históricos. ^{[ 4 ]} Describieron la estimación automática de parámetros a partir de lotes de partidas históricas y dos modos de funcionamiento: un modo en línea que propaga las habilidades hacia adelante en el tiempo y un modo por lotes que infiere parámetros y habilidades a lo largo de todos los tiempos (conocido como TrueSkill Through Time ). ^{[ 4 ]}

En comparación con el TrueSkill clásico, el artículo enumera cambios en el modelo que incluyen: la incorporación de estadísticas individuales de los jugadores junto con las victorias/derrotas del equipo; el tratamiento del abandono de la partida a mitad de juego como una rendición a efectos de la clasificación; el intercambio de información entre modos de juego mediante el modelado de habilidades correlacionadas entre modos; y el modelado de la evolución de las habilidades con una tendencia a la mejora, especialmente en las primeras partidas de un jugador en un modo. ^{[ 4 ]} Añade un efecto de escuadrón explícito, modelando que los jugadores que juegan juntos rinden mejor que si lo hicieran individualmente. ^{[ 4 ]}

En los datos de partidas de Halo 5 , los autores informaron que TrueSkill2 mejoró la predicción de los resultados históricos de las partidas, obteniendo una precisión del 68% en su evaluación en comparación con el 52% del sistema TrueSkill original. ^{[ 4 ]}

TrueSkill forma parte de una familia más amplia de sistemas de clasificación estadística que se utilizan para inferir la fuerza relativa a partir de los resultados de las partidas. El sistema de clasificación Elo , desarrollado originalmente para el ajedrez, modela las probabilidades de victoria a partir de las diferencias de clasificación y actualiza las clasificaciones después de las partidas basándose en la diferencia entre los resultados observados y esperados. ^{[ 9 ]}

Glickman propuso posteriormente modelos dinámicos de comparación por pares que incorporan la incertidumbre en la fuerza estimada de un jugador y permiten que dicha incertidumbre cambie con el tiempo, motivado en parte por las limitaciones de las actualizaciones al estilo Elo para grandes poblaciones competitivas. ^{[ 10 ]} En un estudio de los sistemas de clasificación utilizados en juegos y evaluaciones, los investigadores de ETS describieron TrueSkill como una generalización al estilo Elo para competiciones multijugador y por equipos que mantiene estimaciones de incertidumbre junto con las puntuaciones. ^{[ 7 ]}

Algunos modelos probabilísticos relacionados tratan las clasificaciones como muestras de una distribución que satisface el axioma de elección de Luce . Guiver y Snelson señalan que un modelo thurstoniano con variables de puntuación independientes induce una distribución de Plackett-Luce si y solo si las puntuaciones siguen una distribución de Gumbel, y contrastan esto con TrueSkill, que utiliza variables de puntuación gaussianas. ^{[ 5 ]} Afirman que el modelo de puntuación gaussiana de TrueSkill no satisface el axioma de elección de Luce, al tiempo que señalan su uso en sistemas de calificación en línea a gran escala. ^{[ 5 ]}

Varias extensiones de investigación se basan en la formulación probabilística de TrueSkill. Dangauthier, Herbrich, Minka y Graepel propusieron TrueSkill Through Time , que reemplaza las actualizaciones originales de estilo filtrado con un suavizado sobre una serie temporal de habilidades de los jugadores, lo que permite la estimación retrospectiva de las trayectorias de las habilidades al tiempo que se conservan las estimaciones de incertidumbre y un modelo de sorteo explícito. ^{[ 11 ]}

TrueSkill está patentado, ^{[ 12 ]} y el nombre está registrado como marca comercial, por lo que su uso se limita a proyectos de Microsoft y proyectos comerciales que obtengan una licencia para utilizar el algoritmo. ^{[ 13 ]} La patente expirará el 9 de abril de 2029. ^{[ 14 ]}

• Patentes de software

• Página principal de TrueSkill de Microsoft Research
• El documento TrueSkill de Microsoft Research
• Explicación detallada de los fundamentos matemáticos.