Cómo funciona el equipo equilibrador en World of Tanks Blitz

WoT Blitz es un juego de disparos de tanques móvil en el que los jugadores luchan en un formato 7 contra 7.
Un emparejador, o equilibrador, es un mecanismo que, basado en la alineación de jugadores que desean ingresar a la batalla, forma la composición de los equipos.

Los tanques tienen los siguientes parámetros importantes para el emparejamiento:

• Nivel Dependiendo del nivel, cambian las diferentes características de los tanques (por ejemplo, velocidad, penetración de la armadura). En el primer nivel, los tanques más débiles, en el décimo, el más fuerte.
  
• Tipo Hay 4 tipos de tanques en WoT Blitz: destructores ligeros, medios, pesados ​​y tanques (artillería autopropulsada antitanque)
  

La implementación más simple de un emparejador es lanzar jugadores aleatoriamente en equipos. Pero en este caso, los jugadores en niveles bajos no tendrán ninguna posibilidad de causar al menos algo de daño, y será poco interesante jugar.

Requisitos

La lista de requisitos para el equilibrador se formó sobre la base de los comentarios de la comunidad de jugadores y se actualiza periódicamente hasta el día de hoy.

Al momento de escribir el artículo para batallas regulares, la lista constaba de los siguientes elementos:


Desarrollar un emparejador, especialmente teniendo en cuenta tantas restricciones, es una tarea muy interesante. Y los enfoques para su solución pueden ser bastante.

Balanceador formando un par de jugadores

Inicialmente, en tanques móviles, se utilizó un equilibrador, que heredó de su hermano mayor: tanques de escritorio. En general, trabajó bastante bien, pero tuvo varios problemas: en primer lugar, no dio garantías claras para satisfacer los requisitos; en segundo lugar, agregar nuevos requisitos fue bastante difícil.


Comienzo de la batalla

Por lo tanto, se escribió otro equilibrador, que funcionó de acuerdo con el siguiente algoritmo:

• Dividimos a los jugadores en grupos según el nivel y el tipo de equipo;
• De los jugadores resultantes formamos pares;
• Dispersamos pares para diferentes equipos: tome cada par, arroje al primer jugador al primer equipo, el segundo al segundo;
• En los equipos recibidos, hacemos el reequilibrio final: para satisfacer la mayoría de los requisitos, reemplazamos a algunos de los jugadores de un equipo con jugadores de otro equipo.

El equilibrador resultante funcionó 5-10 veces más rápido que la versión anterior e inicialmente reunió equipos que cumplían todos los requisitos en ese momento. Se agregaron nuevas reglas al escribir pases de reequilibrio adicionales.

Al principio, todo funcionó bien. Pero con el tiempo, mientras más reglas se agregaban, más difícil era escribir el reequilibrio. Como resultado de su trabajo, el nuevo reequilibrio no debe interrumpir el trabajo de los anteriores. Quedó claro que este es el camino a ninguna parte.


Error en el emparejador: un equipo de 9 contra 9 se reunió

Equilibrador de recocido simulado

En la versión final, nos decidimos por un equilibrador que funciona de acuerdo con el siguiente algoritmo. Todos los jugadores que hacen clic en el botón "A la batalla" entran en la cola general. Un equilibrador de bucle sin fin hace lo siguiente:

• Selecciona parámetros de batalla aleatorios (nivel de batalla aleatorio (de 1 a 10), modo aleatorio, mapa aleatorio);
  
• Encuentra en la cola a todos los jugadores que coinciden con los criterios seleccionados anteriormente (entraron en batalla en un tanque de un nivel adecuado, habilitaron el modo seleccionado, cargaron el mapa seleccionado);
  
• Intentar formar equipos que satisfagan todos los requisitos anteriores (descripción a continuación);
  
• Si fue posible formar un equipo, arroja a estos jugadores fuera de la línea de espera y comienza la batalla.
  

Para formar equipos de la lista de jugadores adecuados, se utiliza el método de simulación de recocido. Lea más sobre el método en sí aquí .


Busque un máximo global simulando recocido

En el contexto de la aplicación a la formación de equipos, el algoritmo es el siguiente:

• Comienza con dos equipos vacíos;
  
• En cada iteración, cambia aleatoriamente el estado de los comandos. Para hacer esto, realiza una de las siguientes operaciones:
  
  
  • Agrega un jugador aleatorio de la lista de jugadores adecuados al primer o segundo equipo (también tomamos un equipo aleatorio);
    
  • Elimina a un jugador aleatorio de un equipo aleatorio;
    
  • Reemplaza a un jugador aleatorio de la lista de jugadores adecuados con uno de los existentes en el primer o segundo equipo;
    
  • Cambia a un jugador aleatorio del primer equipo a un jugador aleatorio del segundo equipo.
    
  
  
• Obtiene una estimación del estado resultante. Para hacer esto, llama a la función de evaluación. La función pasa por la lista de requisitos y por la violación de cada elemento aumenta la penalización. Cuanto más se viole el punto, mayor será la penalización. Por ejemplo, la penalización para un equipo de 2x2 será mayor que la penalización para un equipo de 6x6;
  
• Dependiendo del cambio en el valor de la función estimada y la temperatura actual, determinamos la probabilidad de una transición a un nuevo estado;
  
• Continuamos el proceso hasta que la temperatura alcance el mínimo establecido o el valor de la función de evaluación llegue a cero (en este caso, se cumplen todos los requisitos y se puede comenzar la batalla).
  

La principal ventaja de este enfoque: para agregar nuevos requisitos, es suficiente modificar la función de evaluación. No hay necesidad de escribir código que describa cómo obtener exactamente lo que queremos. Simplemente agregue una regla que mire al equipo formado y diga si está bien equilibrado o no.

Un buen ejemplo de agregar tales reglas es calificar las batallas. Al clasificar las batallas en el emparejador, aparecieron varias reglas nuevas a la vez:

• Los equipos deben estar equilibrados en términos de calificación (la diferencia en la calificación total de jugadores entre equipos no debe exceder un valor dado);
  
• La diferencia en la calificación entre los jugadores debe ser mínima (los jugadores de la liga de bronce no deben pelear con los jugadores del diamante).
  

Ejemplo de perfil de jugador de Diamond League

La primera regla se implementa modificando la función de evaluación: se agregó una penalización por exceder la diferencia máxima permitida en la calificación. La segunda regla se implementa cambiando la función que saca a los jugadores adecuados de la cola.

La desventaja de este enfoque es la baja velocidad. En comparación con la versión anterior, la actual comenzó a funcionar 10 veces más lento, incluso a pesar de una serie de optimizaciones. Por cierto, sobre la optimización. La mayor parte del servidor (excepto la red y la física) para el juego está escrito en Python. El equilibrador fue reescrito en C ++ y paralelo a muchos hilos. Desde Python, una solicitud para formar un comando llega en el código más. Además, cada uno de los flujos inicia independientemente el método de recocido. Tan pronto como un subproceso encuentra una solución, el resto de los subprocesos detienen el proceso de búsqueda y la solución encontrada se devuelve a Python.


Tiempo de espera y tamaño de la cola en el servidor RU (5 segundos en batallas normales y 10 en batallas de clasificación)

A medida que creció el crecimiento en línea, también lo hizo la carga en el equilibrador. Este otoño, cuando el servidor en línea en el servidor RU alcanzó 120 mil (durante el evento Mad Games), el equilibrador dejó de funcionar. Como medida temporal, deshabilitamos algunas de las reglas, esto nos permitió reducir la carga. Para evitar tales problemas en el futuro, distribuimos el emparejador.

Sistema de calificación

Los mejores jugadores de la liga de diamantes, 21 de abril de 2019

En muchos juegos MMO, además de las peleas aleatorias, también hay clasificación / clasificación / etc. La idea principal de este modo: los oponentes no se buscan al azar, sino que son adecuados en habilidad. Si eres un jugador de habilidad, jugarás con los mismos jugadores de habilidad, y viceversa, si no sabes cómo jugar, te encontrarás con los mismos recién llegados.

Al comienzo de la temporada, el jugador pasa por una serie de peleas de calibración, cuyos resultados determinan su posición inicial. Luego, dependiendo del mayor éxito del juego, el jugador sube o cae en el ranking. El sistema de calificación en Blitz fue creado, en primer lugar, para un equilibrio adecuado. Se agudiza en la habilidad de los jugadores y es prácticamente independiente del número de juegos jugados.

Para implementar las batallas de clasificación, era necesario resolver dos problemas a la vez. En primer lugar, era necesario elegir un sistema de clasificación (según qué principio deberían clasificarse los jugadores). En segundo lugar, era necesario refinar el equilibrador para que recolecte peleas teniendo en cuenta las restricciones de calificación.

El requisito principal para el sistema de clasificación es la capacidad de determinar con precisión el nivel del jugador. Para evaluar la precisión con la que funciona uno u otro sistema de calificación, se creó un simulador, en cuya entrada se envió el historial de batallas y el sistema de calificación seleccionado, y la salida fue la precisión del sistema.

La precisión se calculó de la siguiente manera:

• A todos los jugadores se les asignó una calificación inicial;
  
• Con base en los resultados de cada una de las batallas, la calificación de los jugadores que participaron en esta batalla se recalculó de acuerdo con el sistema seleccionado;
  
• Antes de cada batalla, el sistema intentaba predecir qué equipo ganaría;
  
• Como resultado, se calculó el porcentaje de batallas para las cuales el sistema dio la predicción correcta.
  

Los sistemas de cálculo de calificación más populares: winrate, Elo , Glicko , TrueSkill . Winrate es el porcentaje habitual de victorias. Elo es un sistema de clasificación, creado originalmente para juegos con dos personas (ajedrez, etc.). En este sistema, un jugador recibe / le quita un cierto número de puntos por ganar / perder, dependiendo de la calificación del oponente. Glicko es generalmente similar a Elo, pero también tiene en cuenta el tiempo que el jugador ha estado inactivo. TrueSkill es un sistema de calificación patentado de Microsoft, en el que cada jugador tiene dos parámetros: la calificación y la confianza del sistema en esta calificación.

Durante el desarrollo de la primera versión de las batallas de clasificación, consideramos winrate y Elo (varias opciones adaptadas para un juego de equipo), así como un sistema de puntuación simple (en el que los jugadores siempre recibían un número fijo de puntos de clasificación para la victoria y se los llevaban por la derrota).



El sistema Elo mostró los mejores resultados, en los que Ra es la calificación del jugador y Rb es la diferencia entre la calificación total del equipo contrario y la calificación total del equipo del jugador, con la excepción del propio jugador.

Las principales dificultades que encontramos después del lanzamiento:

• demasiada variación en el ranking entre jugadores;
  
• La velocidad poco predecible a la que los jugadores marcan (llegan a la liga).
  

El primer problema no pudo resolverse por completo debido al hecho de que hay muy pocos jugadores de habilidad, tienen que esperar mucho tiempo antes de que comience la batalla, y muy a menudo ven a los jugadores en sus equipos más débiles. Para mitigar el efecto, pusimos a disposición las batallas de clasificación solo en horario estelar (es decir, en un momento en que la cantidad máxima de personas jugaba en los servidores).

Resolvimos el segundo problema introduciendo un factor de desaceleración (es decir, cuanto más se aleja el jugador de la calificación promedio, más difícil es para él subir o bajar).

También intentamos de varias maneras mejorar la calidad del sistema de calificación. En las primeras versiones, para cambiar la calificación, solo utilizamos información sobre la victoria / derrota. Pero tenemos un juego de equipo, y no siempre las buenas acciones de un jugador específico conducen a la victoria de todo el equipo. Es decir, incluso si el jugador jugó bien y el equipo perdió, este jugador recibió el mismo signo negativo que todos los demás jugadores. Para evitar esto, comenzamos a tratar de tener en cuenta las acciones individuales del jugador en la batalla.

Para estos propósitos, tratamos de usar el aprendizaje automático: recopilamos varios factores e intentamos entrenar el modelo para predecir la victoria / derrota del equipo de acuerdo con las acciones del jugador en la batalla, luego usar este modelo para determinar el coeficiente de bonificación de calificación (es decir, si el equipo perdió, pero el comportamiento del jugador fue similar sobre el comportamiento de los jugadores ganadores, otorgue a dichos jugadores una bonificación adicional).


El jugador del equipo ganador que jugó bien recibió una calificación de +40. Y lo que es malo solo +10

Pudimos construir un buen modelo que mostró resultados mucho mejores que el actual, pero hubo una dificultad (que a menudo estropea todo en problemas de aprendizaje automático). El modelo era bueno, pero a veces tenía errores claramente visibles para las personas. Periódicamente hubo situaciones en las que un jugador que, desde el punto de vista de una persona mostró buenos resultados, recibió una bonificación baja desde el punto de vista del modelo, y viceversa.

Como resultado, abandonamos el modelo ML y tomamos una fórmula manual más simple. Esta fórmula solo tiene en cuenta la experiencia de combate sin tener en cuenta las bonificaciones por victoria, x2 y otras. Da un resultado muy decente, aunque es ligeramente más bajo que el del modelo ML.

Conclusión

• Un equilibrador basado en un método de simulación de recocido nos permitió pasar de una descripción de la solución (cómo armar el equipo) a una descripción de los requisitos (qué condiciones no deben ser violadas);
  
• En las batallas de clasificación de equipos, el sistema Elo modificado se mostró bien, teniendo en cuenta las acciones individuales del jugador en la batalla;
  
• No siempre vale la pena usar métodos complejos de aprendizaje automático (especialmente cuando la interpretación y la comprensión del resultado por parte de una persona es importante).
  

Continuamos desarrollando y mejorando el equilibrador. Casi derrotamos la impresión negativa del desequilibrio de clase. Los principales problemas a los que nuestros jugadores prestan atención son el desequilibrio en la habilidad, la turbulencia y los jugadores afk. Este es un desafío serio, seguimos trabajando en un equilibrador en estas áreas.

Si tiene alguna pregunta / sugerencia sobre un equilibrador en WoT Blitz, anule la suscripción en los comentarios (o en nuestro foro ).