Dagaz: fuera de la niebla

Todo esto es la reina de la reina Mab.
Ella teje en los establos de una melena
Y el cabello derriba un enredo ...

William Shakespeare

Fue un lanzamiento largo, pero se hizo mucho. Ha aparecido un administrador de sesión , que le permite retroceder movimientos realizados por error. En algunos lugares, se agregó el diseño de sonido. Y, sin embargo, se me ocurrió una forma genial de impulsar varias opciones alternativas para la colocación inicial en un juego. Y lo más importante: finalmente llegué a los juegos con información incompleta.

Explicaré lo que está en juego. En los juegos de mesa habituales, como Ajedrez o Damas , los jugadores, en cualquier momento del juego, tienen información completa sobre la ubicación de las piezas (la suya y la del oponente), las reglas para moverlas, los objetivos del juego, etc. Tales juegos están bastante bien estudiados y entran en la categoría de " juegos con información completa ". Ahora, imagine que parte de esta información puede estar oculta para el jugador.


La niebla de la guerra es una gran ilustración del tema. De acuerdo con las reglas del " Ajedrez a ciegas ", los jugadores no pueden ver todas las piezas del enemigo, sino solo aquellas que se colocan en los campos, a las que se puede acceder con un movimiento de cualquiera de sus piezas. Hice dos adiciones a esta regla:

1. Por supuesto, el jugador siempre ve sus piezas, pero por la forma en que se muestran, en forma normal o translúcida, puede juzgar si el oponente las ve.
2. Solo con fines decorativos, coloqué "nubes" en áreas que actualmente son invisibles.

Habiendo dominado el principio general, me dejé llevar e hice una gran cantidad de juegos con la "niebla de guerra". Además del ajedrez en sí , tengo opciones "oscuras" para Xiang , Changi , Shatrange , Sittuyin y muchos otros juegos. ¡Incluso hay un " Blind Guns "! Todos estos juegos tienen una cosa en común:


Sin embargo, en general, este no es un enfoque muy correcto. Quiero ver un bot que pueda hacer exactamente con los datos que tiene su adversario: man. ¿Por qué es esto importante? Todo es muy simple: por la forma en que juega el bot, a veces es muy fácil adivinar si tiene acceso a información oculta (píos) o no. Y, por supuesto, es mucho más interesante que una persona juegue con ese bot que no se asoma (jugar con otra persona es aún más interesante, pero esta es una historia diferente).

Y aquí vale la pena elegir un juego que sea ligeramente diferente del Ajedrez (ya que no estoy listo para desarrollar un bot "honesto" jugando ajedrez "a ciegas"). Hay muchos juegos de este tipo y no se puede decir que sean más simples que el Ajedrez o las Damas. Son simplemente diferentes y requieren un enfoque individual.


Para empezar, decidí pensar en BanQi : ajedrez chino ciego. Este es un juego muy original con información oculta, similar a la "Jungla". Es importante para mí que los desarrollos, en relación con la creación de un bot para este juego, se puedan usar en otros juegos, como Dou Shou Qi , Luzhan Qi , Stratego o incluso (posiblemente) Tafl .


Te contaré sobre las reglas. El juego se ejecuta en la mitad del tablero para el "Ajedrez chino" ( Xiang Qi ), mientras que el diseño original del tablero no juega ningún papel. Las piezas se colocan dentro de las celdas (como en las tradicionales), y no en las intersecciones de las líneas (como en el ajedrez chino). Al comienzo del juego, todas las piezas se mezclan a fondo y se colocan boca abajo en el tablero (dado que las piezas tradicionales de Syants son una especie de barriles, y su número coincide con el número de campos en la mitad del tablero, no hay dificultad).

A continuación, los jugadores alternan sus movimientos. Al realizar un movimiento, el jugador puede voltear cualquiera de las piezas cerradas, o mover una pieza abierta previamente de su color. Los colores de los jugadores están determinados por el primer movimiento. Si se abre la primera pieza negra, el jugador que la abrió jugará en negro. Todas las figuras en el juego van de la misma manera (con la excepción del "Cañón" en la versión taiwanesa, que discutiré más adelante), en una celda adyacente vertical u horizontalmente. La posibilidad de tomar está determinada por el orden de antigüedad de las cifras:

General> Asesor> Elefante> Vagón> Caballo> Cañón> Soldado

Las figuras más viejas golpean más jóvenes o iguales a ellos, con una excepción: un soldado golpea al general (una especie de " Piedra-Papel-Tijera "). Queda por decir algunas palabras sobre TaiQuan BanQi:

1. A diferencia de la versión china, en Taiwán BanQi, un general no puede vencer a un soldado.
2. El cañón se mueve de acuerdo con las reglas XiangQi , es decir, a cualquier número de campos ortogonales a baja velocidad (como un carro) o golpea a cualquier figura enemiga, con un salto a través del "carro", al realizar un movimiento de ataque.

También hay una versión de Hong Kong, pero prácticamente no es diferente de la china, excepto que el orden de antigüedad de las cifras ha cambiado. Decidí centrarme en la versión taiwanesa de las reglas, como la más interesante tácticamente.


En primer lugar, es importante comprender que es poco probable que pueda utilizar efectivamente algoritmos minimax aquí. Los movimientos que revelan piezas previamente ocultas también cambian radicalmente la estimación de posición. Al no tener información sobre piezas ocultas, es casi imposible ver una posición con muchos movimientos por delante. Pero cada nube tiene un lado positivo, ¡pero podemos usar heurísticas mucho más complejas (en términos de cálculo) para evaluar los movimientos en sí!

Ya tengo un bot que evalúa los movimientos por su heurística (necesario para un juego divertido). Este es un algoritmo muy simple. Todos los movimientos se ordenan en orden descendente por heurístico (los movimientos con un valor heurístico negativo generalmente se descartan), después de lo cual se escanean en orden. Si el siguiente movimiento lleva a una posición desde la cual no hay respuesta enemiga que conduzca a una victoria inmediata, el bot lo considera el mejor. Con este algoritmo, no puede molestarse con la estimación de la posición, pero debe sudar por la heurística .


Por supuesto, guardo en caché todos los datos intermedios en el estado del juego, para no leerlos varias veces. Además, aquí se usa un truco, que es muy útil para calcular áreas conectadas. I itero sobre la matriz del grupo , colocando elementos adicionales dentro del ciclo, según sea necesario. Todas las dificultades están asociadas con las armas. Para ellos, los objetivos de las cadenas no son las figuras mismas, sino los campos desde los cuales se puede atacar a estas últimas.


... dependiendo de la longitud y paridad de la cadena, así como teniendo en cuenta los costos de las figuras atacantes y atacadas. ¡Pero esto es solo la mitad de la batalla! Es necesario evaluar cada uno de los movimientos posibles usando las cadenas construidas. Presento una estructura intermedia más: desea agregar los datos disponibles. La evaluación del curso consiste en evaluaciones de los deseos, que satisface:


En cuanto a la función getWish en sí , la magia comienza aquí (y este es el lugar donde probablemente aré más de una vez). En primer lugar, comparto la evaluación de movimientos basada en información abierta y la introducción de nuevas piezas en el juego. Esto no es del todo correcto, pero hasta ahora no sé cómo conciliar opiniones tan diversas. Si en base a información abierta no se formaron deseos, el bot intenta abrir nuevas figuras (también hay algunos trucos aquí).

1. Si un cañón enemigo está abierto, rodeado de figuras cerradas, tiene sentido abrir una de las figuras al lado, ya que es probable que pueda atacar el arma, y ​​el arma no podrá vencerlo, en cualquier caso.
2. Si una figura que no sea un cañón está abierta, puede intentar abrir una figura ubicada a través del "carro", ya que existe la posibilidad de que resulte ser un cañón.
3. Si hay una cadena de ataque desde el lado del enemigo, se puede abrir una de las piezas, al lado de la cadena, para interceptar el ataque.
4. Si no puede proteger la figura, puede abrir la figura al lado, tratando de reducir la situación a un intercambio.

El jugador puede evaluar las probabilidades haciendo un seguimiento de las cifras que han abandonado el juego. En principio, el bot puede hacer lo mismo, pero hay una manera más fácil: mirar las cifras aún no abiertas a granel y evaluar la probabilidad de abrir la deseada en función de la información recopilada. Además, el éxito del movimiento seleccionado no está garantizado, pero si la probabilidad de un resultado favorable es baja, el movimiento no se seleccionará en absoluto.


Y para aquellos que todavía me están leyendo, puedo ofrecer otro divertido juego de rompecabezas con información oculta:


Lo jugué en mi infancia, en una calculadora programable llamada Fox Hunt. Ocho zorros se ocultan al azar en el campo, que se debe encontrar utilizando el "método de empuje". Cuando selecciona un área vacía, se muestra el número total de zorros en las ocho direcciones. Es imposible perder, pero puede competir por la cantidad mínima de clics. Y si juegas con auriculares, baja el sonido. Quizás lo exageré con efectos de sonido.