¡Hola!



Estamos en nuestro primer año de estudios universitarios en Matemáticas Aplicadas e Informática en el HSE de San Petersburgo. Mientras trabajaba en un proyecto de equipo semestral en C ++, decidimos escribir una versión para computadora del Intellector con un bot: un juego de ajedrez en un tablero hexagonal con figuras especiales.



En este artículo hablaremos sobre cómo fue el desarrollo del juego, cómo domar el tablero hexagonal, cómo dibujar en la línea de comandos y también cómo hicimos un bot que casi no podemos derrotar.







Hay 3 personas en nuestro equipo: Yura Khudyakov, Valera Golovin, Misha Savrasov. Para cada uno de nosotros, este es el primer proyecto de equipo, por lo que en el proceso de trabajo no solo escribimos sobre los profesionales, sino que también aprendimos a trabajar en equipo y a usar sistemas de control de versiones (en nuestro caso, git). Hay una serie de rarezas en el proyecto, en particular, bicicletas: hay buenas soluciones listas para usar que podrían usarse. Sin embargo, el objetivo de nuestro proyecto era ganar experiencia, por lo que inventamos e implementamos mucho nosotros mismos.

¿Qué es un intelector?

Primero, vale la pena explicar qué tipo de juego escribimos.



El juego "Intellector" ha aparecido recientemente y sigue ganando popularidad. El primer campeonato abierto se celebró en San Petersburgo este año .





El intelector se diferencia del ajedrez en la estructura del campo, las reglas y un conjunto de piezas. Sin embargo, muchos elementos son similares: por ejemplo, hay una figura de Progresor en el juego, que desempeña el papel de un Peón. Camina solo hacia adelante y puede convertirse en otra figura cuando llega a la fila extrema.



El rey aquí es una figura llamada Intelector. El objetivo del juego es cortar esta pieza, no dar jaque mate (aunque esto es casi lo mismo).



Las diferencias en la mecánica del juego surgen de las características específicas del campo. El campo Intelecto es simétrico, lo que lo distingue significativamente del ajedrez con su flanco de rey y su flanco de dama.



Para comprender este artículo, no se requiere el conocimiento de las reglas y la habilidad para jugar.

Arquitectura general

¿Qué queremos en nuestra aplicación?

Para que el juego funcione, debes implementar su componente principal: la lógica del juego. Incluye un modelo de tablero y reglas de movimiento. Además, por conveniencia, vale la pena mantener el historial de movimientos e implementar deshacer / rehacer.



El tablero debe mostrarse y permitir que el usuario juegue. Esto lo hace el componente gráfico del juego: la interfaz. Una interfaz fácil de usar debe tener menús y configuraciones.



Después de todo, necesitas un oponente para jugar. Decidimos hacer un bot para estos propósitos para que el jugador pueda competir con la computadora. En este caso, la complejidad del bot debería ser ajustable.

Plan de aplicación:

1. Lógica del juego
   • Modelo de placa hexagonal
     
     Almacenado como una matriz bidimensional de celdas hexagonales
   • Reglas para mover piezas
     
     Verificar la admisibilidad de un movimiento, obtener todos los movimientos disponibles para una pieza, para un jugador
   • Mover el historial
     
     Deshacer y rehacer un movimiento
2. Interfaz
   
   2 interfaces planificadas: ncurses y Qt. Solo ncurses se implementa en el proyecto, consulte la sección Interfaz para obtener más detalles.
   • Visualización de un campo Representación
     
     y actualización de un campo en la consola
   • Mueva el cursor con las teclas del teclado, juegue sin mouse
   • Visualización del historial de texto de movimientos
   • Visualización del menú principal
3. El bot
   • Bot aleatorio
   • Bot codicioso
   • Bot Alpha-beta
     
     Optimizado para iterar sobre todos los movimientos

Como se hace

Este diagrama describe una arquitectura de aplicación muy simplificada:





La sección de Juego es responsable de toda la lógica del juego y almacena el tablero.



Cuando se enciende el juego con la computadora, el juego interactúa con el bot desde el bot



Controller, toma datos sobre el juego del juego y los transfiere a la interfaz para mostrarlos a los jugadores. La Interfaz, a su vez, devuelve el resultado de la interacción del usuario al Juego a través del Controlador.



El enlace intermedio en forma de controlador es útil cuando hay varias interfaces (inicialmente planeamos hacer 2 interfaces: consola y gráfica). Todos se comunican con el juego de manera uniforme a través del controlador, en lugar de que cada uno lo haga de manera diferente.

Detalles técnicos

Modelo de juego

Tablero hexagonal

Considere la sección Juego del diagrama anterior. Tiene que almacenar el tablero y manejar toda la lógica del juego.



Para una mejor comprensión, puede leer el artículo del que tomamos esta idea.



Almacenaremos todo el tablero en una matriz bidimensional de celdas, cuyos elementos están indexados por pares de coordenadas, (w,h)como se muestra en la figura siguiente. Tal elección de coordenadas parece natural, pero es inconveniente para describir el movimiento de formas (observe, por ejemplo, cómo cambian las coordenadas al moverse a lo largo de la diagonal).





^{Coordenadas de celdas a lo largo del eje horizontal wy el eje verticalh}



Para la conveniencia de describir el movimiento de las figuras, usaremos coordenadas tridimensionales. Elijamos alguna celda como celda de referencia con coordenadas {0,0,0}(por conveniencia, coincidirá con la celda de la (0, 0)matriz).





^{Coordenadas tridimensionales de las celdas relativas a la celda central con coordenadas El{0,0,0}}



desplazamiento a lo largo de la diagonal "de derecha a izquierda, de abajo hacia arriba" se denota por la coordenada x, el desplazamiento de abajo hacia arriba por la coordenada yy el desplazamiento a lo largo de la diagonal "de izquierda a derecha, de abajo hacia arriba" por la coordenada z. Al moverse a una celda adyacente, la coordenada correspondiente cambiará en uno. Por lo tanto, cada celda recibe tres coordenadas, como en la imagen de arriba.



En este caso, las celdas se numeran de forma ambigua. Por ejemplo, si desde la celda central con coordenadas {0,0,0}nos movemos hacia la izquierda hacia abajo y luego hacia arriba, obtenemos las coordenadas de la celda {0,1,-1}. Pero la misma celda tiene coordenadas {1,0,0}si se llega a ella directamente desde la celda central, como puede ver en la figura anterior.





^{Otra opción para especificar las coordenadas de la celda {1,0,0}.}



Atravesar cualquier celda en un ciclo "izquierda-abajo" - "arriba" - "derecha abajo" nos lleva a la misma celda, pero agrega un vector a sus coordenadas {-1,1,-1}, cuya suma de coordenadas es igual a -1. Realizando mentalmente dicho recorrido en la misma o en la dirección opuesta varias veces, podemos cambiar las coordenadas de cualquier celda a equivalentes, que diferirán en un vector proporcional {-1,1,-1}. Para deshacernos de la ambigüedad, en cada clase de equivalencia, elegimos como representante un triple de coordenadas, cuya suma es igual a cero. Esta elección de coordenadas es única (¡demuéstralo!).



Describamos con más detalle el algoritmo para convertir de coordenadas bidimensionales a coordenadas tridimensionales y viceversa dentro de la clase Position.

Position(int w, int h) //    
        : x_{-w/2 — w % 2 - h}
        , y_{w % 2 + 2 * h}
        , z_{w / 2 — h} {
}

int posW() const { //       
    return -x_ + z_;
}

int posH() const { //       
    return (x_ + z_ — (x_ + z_)%2) / 2 + y_;
}

Tenga en cuenta que el constructor produce coordenadas (x,y,z)que suman cero. En este caso, la conversión de coordenadas (x,y,z)a (w,h)funciona correctamente para cualquier conjunto de coordenadas (la suma no tiene que ser igual a cero).



¿Cómo encontramos todas estas fórmulas? Por método científico de empuje: analizando el cambio en coordenadas tridimensionales cuando una de las coordenadas bidimensionales es desplazada por 1(constructor) y en la dirección opuesta (métodos).



Usando coordenadas tridimensionales, podemos verificar fácilmente que las celdas sean colineales. Por ejemplo, para verificar que dos celdas se encuentran en la misma diagonal z, necesita encontrar un vector que conecte estas celdas y verificar que su clase de equivalencia contiene un vector de la forma{0, 0, z}... Z puede ser cualquier cosa: este número indica la distancia entre celdas. Será muy sencillo implementar la comprobación de la corrección del movimiento y encontrar todas las celdas disponibles para el movimiento.



En una matriz bidimensional que representa el tablero, almacenaremos información sobre la posición de las figuras. En cada celda, si hay una pieza de ajedrez, almacenaremos su tipo y color.



En nuestra implementación en la clase de tablero, solo almacenamos los tipos de piezas en celdas. Necesitamos una clase que pueda encontrar todos los movimientos posibles para las piezas en este tablero y verificar la exactitud de los movimientos.

Se mueve por piezas

Hemos hecho una clase FigureMoveValidatorque tiene 6 descendientes para cada tipo de figura (era posible prescindir de descendientes si en cada método hacíamos un caso de cambio para el tipo de figura). El constructor de clases tiene 2 parámetros: posición y referencia de placa. También en la clase hay dos métodos allMovesy checkMove.



Consideremos el método allMoves. Para encontrar todos los movimientos, compongamos una matriz de vectores de posibles desplazamientos y la revisemos. Para piezas que se mueven un paso, debemos comprobar que no saltamos del tablero y no entramos en la celda donde está nuestra pieza. Para figuras que mueven varias celdas en línea recta, agregue un vector de movimiento mientras pasa la condición anterior.



AhoracheckMove... Recordamos que sabemos comprobar si las figuras están en la misma línea recta. Si comprobamos que no hay otras piezas en esta línea, obtenemos un método listo para usar para el Dominator (análogo de la torre). Si las piezas están en una línea recta, entonces podemos encontrar la distancia entre ellas y obtener métodos para el Progresor (peón), Defensor (camina como un rey), Inteligencia (el rey, solo no puede cortar) y Liberador (puede caminar a través de una celda a cualquier lado). Todavía hay un agresor (un análogo de un elefante), que se mueve a las celdas en diagonal en seis direcciones desde la actual (de celda {0, 0, 0}a {0, 1, 1}, a {0, 2, 2}, etc.: vea las celdas grises en la imagen de abajo). Para esta figura, puedes intentar poner a cero una de las coordenadas y comprobar que las 2 coordenadas restantes son iguales en valor absoluto (gracias a las coordenadas tridimensionales).





^{Posibles movimientos para el agresor}



Ahora tenemos que averiguar qué hacer con los movimientos. Creemos una clase Move que almacenará toda la información necesaria para el movimiento. Decidimos almacenar 2 posiciones y 4 piezas: la posición desde la que se mueve la pieza, la posición a la que vendrá e información sobre qué piezas estaban en cada una de estas celdas y cuáles permanecerán después de aplicar el movimiento. Esto facilitará la implementación del sistema de historial de movimientos y la reversión de movimientos.

Interfaz

Arquitectura

La aplicación está escrita en la biblioteca de la consola ncurses (aquí hay un tutorial para ello ) . Esta biblioteca le permite crear pseudo gráficos en la consola. Por ejemplo, Midnight Commander y Nano se basan en él .



La elección puede parecer muy extraña: hay muchas otras bibliotecas, más hermosas, convenientes y multiplataforma. Está relacionado con el hecho de que inicialmente planeamos hacer 2 interfaces: consola y gráfica. No logramos escribir 2 interfaces en el momento en que se entregó el proyecto y, en cambio, hicimos más funciones en la versión de consola. Aunque arquitectónicamente, la aplicación todavía está diseñada para diferentes interfaces.



Hay 2 entidades principales: pantalla y controlador... Las asignaciones muestran la imagen a los jugadores, y el controlador media entre las diferentes asignaciones y el modelo de juego interno.



La pantalla maneja toda la interacción del usuario: posición y movimiento del cursor, selección de formas, resaltado de los campos disponibles, finalización del juego y más. Las acciones que afectan a la placa se refieren al controlador y envían / ​​reciben la información necesaria hacia / desde el modelo.



La pantalla crea su propia versión del tablero, pero con los parámetros adicionales que necesita, como la posición del cursor y el color de las celdas. Estos parámetros no se pueden agregar al modelo principal porque diferentes asignaciones necesitan diferentes parámetros. Por ejemplo, en la interfaz de la consola es necesario almacenar la posición del cursor, pero no en la interfaz gráfica, ya que la selección y el movimiento de la figura se realiza con el mouse.



Esto es lo que sucede si un jugador quiere conocer los campos disponibles para el movimiento:

1. El jugador mueve el cursor al campo de la figura y presiona la barra espaciadora
2. El campo con la forma está marcado como seleccionado
3. La interfaz se refiere a un método selectCellen el controlador
4. El método se selectCellrefiere al método del allFigureMovesmodelo.
5. allFigureMovescrea FigureMoveValidatorque calcula todos los movimientos disponibles
6. allFigureMoves las transferencias encontradas regresan al controlador
7. El controlador los pasa a la interfaz
8. La interfaz vuelve a dibujar el campo, resaltando los campos disponibles

^{El cursor está en el medio del tablero: en un cuadrado azul claro. Antes de moverlo a esta posición, el usuario seleccionó una forma. Los movimientos disponibles se resaltan en verde y la celda seleccionada en sí es violeta.}

¿Cómo se dibuja el campo?

La interfaz de la consola se representa en una ventana rectangular con líneas de texto. Si pones símbolos en los lugares correctos y los coloreas, obtienes una imagen:





^{(Evil Pacman, dibujado con las letras "o")}



Una función move(int y, int x)en ncurses cambia la posición actual, y la función addch(chtype c)agrega un carácter y desplaza la posición actual 1 a la derecha ( x —> x+1).



Una imagen compleja se puede almacenar como una matriz bidimensional y mostrarse línea por línea: cuando la línea termina, mueva la posición actual al comienzo de la siguiente línea. El principio es muy similar al de una máquina de escribir.



En la computadora del usuario, el campo de nuestro juego se coloreará si el terminal admite colores y otros atributos de texto.



Ncurses permite al desarrollador cambiar los atributos del texto cuando se envía a la consola (color, negrita, parpadeo). Para hacer esto, escriba el código:

attron( *attributes* );
addch(c);
attroff( *attributes* );

Cada símbolo tiene su propio color y color de fondo. Las consolas modernas admiten un máximo de 256 colores, por lo que tienes que trabajar con un conjunto limitado : bastante triste en términos de diseño de color.



Las imágenes para la salida se pueden almacenar en código (como hicimos inicialmente), o se pueden almacenar en archivos separados y leerlos cuando se inicia el programa. Para ello, hemos creado nuestro propio formato de archivo *.btn.



Almacena una imagen de texto que el juego leerá y mostrará. Por ejemplo, una forma o la inscripción "El blanco gana" / "El negro gana", o un botón de menú. En este caso, es posible que a veces necesite transparencia para no sobrescribir lo que se dibujó anteriormente. Para hacer esto, puede agregar un hash en la primera línea #y después de la lista de símbolos "transparentes" que serán ignorados en la salida.



Por ejemplo, digamos que tenemos 3 rectángulos dibujados en la pantalla:





Agregue un rectángulo del siguiente archivo al centro:

#C
AAAAAAAAA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
AAAAAAAAA

Y obtenemos la siguiente imagen:





^{(resaltado en amarillo para mayor claridad)}



Este formato fue especialmente útil al desarrollar menús.

Menú

El juego también tiene un menú que contiene configuraciones y se dibuja antes de que comience el juego y después de que termine.



Los botones de menú se leen de archivos *.btn. Estos botones deben tener un texto grande y atractivo. No sabemos cómo dibujar maravillosamente usando caracteres ASCII, pero figlet , una utilidad para mostrar texto ASCII en diferentes fuentes, puede:





Los botones enmarcan las etiquetas leídas del archivo:





A continuación, se centran y se generan de forma secuencial:





En algunos menús, puede fallar y, por ejemplo, ajustar la complejidad y el color del bot:





La parte más interesante del diseño de un sistema de menús es combinar sus elementos en un solo sistema. Esto se hace mediante un elemento separado del sistema, al que llamamos multiplexor. El nombre está inspirado en multiplexores de terminales .



El multiplexor acepta la tecla presionada por el usuario y la envía a todos los menús mostrados actualmente. Cada menú decide por sí mismo qué hacer con la tecla: ignorar o procesar de alguna manera. El resultado de procesar el menú se devuelve al multiplexor, quien decide qué hacer a continuación: cerrar el menú, crear uno nuevo, cambiar la configuración, cerrar la aplicación ...



Este enfoque resultó ser conveniente para nuestras necesidades, aunque en general puede no ser suficiente: 2 menús diferentes pueden responder a la misma tecla, y el usuario debe poder elegir qué menú debe responder. La solución sería un atajo de teclado especial que le permite cambiar entre diferentes menús. Por ejemplo, como en tmux . Pero esto es excesivo y no era necesario.

El bot

Como se mencionó anteriormente, nuestro juego tiene un bot. Intentamos hacerlo interesante tanto para principiantes como para jugadores experimentados.



Antes de describir los bots, me gustaría hablar sobre algunos detalles de implementación. Asignamos algo de peso a cada forma. Cuanto más grande es, más valiosa es esta cifra. Determinamos qué tan buena es una posición en el tablero usando la fórmula (suma de pesos de piezas blancas) - (suma de pesos de piezas negras). Es beneficioso para el blanco maximizar esta expresión y para el negro minimizarlo.



Un cálculo completo de todo el árbol de movimientos es una tarea demasiado difícil, por lo que solo calculamos los primeros movimientos (mirando hacia el futuro, diré que resultó que se calcularon 6 movimientos hacia adelante). Consideramos todos los estados del tablero a una cierta profundidad como hojas del árbol transversal.



Hay tres tipos diferentes de bots en el juego:

• RandomBot — . .
• GreedyBot — «» , , .
• AlphaBetaBot — , - .

Cuando comenzamos a experimentar con optimizaciones, nos dimos cuenta de que no podíamos prescindir de las pruebas unitarias para el bot, así que creamos un hermano gemelo para AlphaBetaBot'a', a quien nombramos OptimizedAlphaBetaBot. Probamos todas las ideas para la optimización OptimizedAlphaBetaBoty las pruebas unitarias ayudaron a asegurarnos de que los dos hermanos gemelos encontraran el mismo movimiento útil. RandomBot nos ha servido bien al generar patrones aleatorios en el tablero. Para ello, bastaba con preguntar RandomBote ir varias decenas de veces por ambos lados.



En total OptimizedAlphaBetaBot , se implementaron 3 optimizaciones principales (aquí se presentan en orden descendente de utilidad):

• Usando retrocesos. Después de esta optimización, ya no fue necesario copiar el tablero muchas veces para hacer un movimiento.
• FigureKeeper, , . std::vector .
• std::unordered_map Zobrish hashing.

Además de las optimizaciones importantes, también hubo otras más pequeñas. Por ejemplo, si, antes de ordenar, calcula todos los valores de las posiciones en el tablero, teniendo en cuenta un determinado movimiento, entonces ya no necesita ordenar los objetos complejos Move, sino simplemente intlos de.



Inicialmente, se planeó implementar varios conjuntos de funciones de evaluación: por ejemplo, una figura amenazada por un enemigo se estima en la mitad del costo. Pero resultó que el bot juega bastante "limpio", perdiendo pocas piezas, por lo que una cantidad simple resultó ser más efectiva.



Sin embargo, la arquitectura del bot todavía admite la adición de nuevas funciones de evaluación. Para hacer esto, necesita definir solo tres cosas:

1. Función si necesita calcular el costo "desde cero" para una disposición determinada de figuras
2. Función Delta, que debería recalcular rápidamente el costo de un movimiento determinado.
3. El número de este conjunto de funciones para el constructor de la clase personalizada FunctionSet.

Puede activar la batalla de bots y ver el proceso.





^{Un juego de 2 bots de la misma dificultad (nivel 4 de 6 posibles). El cursor está en el centro del campo durante todo el juego.}

Conclusión

Hemos implementado un juego similar al ajedrez, pero con reglas diferentes y un tablero inusual. Nuestra implementación tiene espacio para expandirse. El propio Intellector también se está desarrollando y cambiando: recientemente hubo una actualización de las reglas, que aún no hemos admitido en nuestra aplicación. Por ejemplo, ahora no puede cruzar la línea central durante los primeros 2 giros.



Además, hay varias características que planeamos originalmente, pero que no tuvimos tiempo de implementar en el momento del proyecto. Por ejemplo, en esta aplicación me gustaría mucho ver un juego en red. Además, una buena interfaz multiplataforma, por ejemplo, en Qt, no estaría de más.



Quizás todo o parte de esto aparezca en un futuro próximo. Hasta entonces, gracias por leer!



Repositorio de Github