Una captura de pantalla de ese mismo juego flash todavía te da la bienvenida a toox.com/jeux/jeux-de-cartes/coinche
Exposición del problema y su relevancia
Quosh, Belote y Tarot son juegos nacionales franceses. De acuerdo con las reglas, esto es aproximadamente como jugar preferencia en un juego cerrado, y un par se juega por un par, por lo que por cuántos sobornos y en qué carta de triunfo su compañero propone anunciar el juego durante la negociación, puede entender aproximadamente qué tipo de cartas tiene. El juego es largo y la existencia de una IA capaz de llevar el juego al final de alguna manera es simplemente vital, porque uno de los jugadores puede simplemente dejar la mesa y decidir que está perdiendo irremediablemente, y el ganador naturalmente quiere llevarlo a la puntuación final en el marcador. En este caso, la IA terminará el juego para el jugador perdido. Pero dado que tenemos IA, ¿por qué no permitirnos comenzar el juego molestando al AI-shki en los espacios vacíos? Y entonces lanzamos estos grandes juegos a las masas y rápidamente descubrimos que básicamente hay dos opciones sobre cómo les gusta jugar a los franceses.Aproximadamente la mitad de todas las mesas esperan ser llenas de personas vivas hasta que la victoriosa, y la mitad baja y comienza el juego contra tres IA, como en la captura de pantalla anterior.
En principio, dado que el juego está cerrado, la gente está dispuesta a perdonar a los robots por pequeños errores de cálculo y dotes alternativos. Principalmente porque no se pueden ver las cartas del robot. "Debajo del jugador con simak", "debajo de la vistuza con el as" y reglas simples similares que sacudí de nuestro cliente francés nos permitieron hacer el lanzador mínimo aceptable. Fue nafigched en una semana justo en el ifs. Por otro lado, el juego se juega "dos por dos", los puntos se cuentan para una pareja y, naturalmente, el jugador no quiere que su estúpido compañero entre "del segundo rey", es decir, tener un rey en sus manos y alguna otra carta pequeña hace un movimiento para este palo, en lugar de dejar que el oponente juegue un as, dejarlo pasar con una carta pequeña y tomar el siguiente movimiento en este palo con su rey. (En realidad, en estos juegos, la segunda carta más antigua es 10,pero de ahora en adelante hablaré en términos rusos). Pero si el as por alguna razón dejó el juego y tienes una reina y algo más pequeño, entonces es casi como el segundo rey. Especialmente si reserva las cartas de triunfo. Y tú, por ejemplo, no estás jugando a Belote, donde se usan 32 cartas, sino al Tarot, en el que el juego se juega con una baraja de 78 cartas (la misma que algunos adivinan). Y allí, en algunos casos, ni siquiera la tercera reina, sino la cuarta jota, pueden aceptar el soborno. En general, todo esto da lugar a tal número de casos extremos que un tonto tonto en ifs se vuelve de alguna manera completamente inaceptablemente complejo. Y en este punto dije: “¡Bah! He leído muchopor ejemplo, no estás jugando a Belote, que usa 32 cartas, sino al Tarot, en el que el juego se juega con una baraja de 78 cartas (la misma que algunas personas usan para adivinar). Y allí, en algunos casos, ni siquiera la tercera reina, sino la cuarta jota, pueden aceptar el soborno. En general, todo esto da lugar a tal número de casos extremos que un tonto tonto en ifs se vuelve de alguna manera completamente inaceptablemente complejo. Y en este punto dije: “¡Bah! He leído muchopor ejemplo, no se juega a Belote, donde se usan 32 cartas, sino al Tarot, en el que el juego se juega con una baraja de 78 cartas (la misma que algunos adivinan). Y allí, en algunos casos, ni siquiera la tercera reina, sino la cuarta jota, pueden aceptar el soborno. En general, todo esto da lugar a tal número de casos extremos que un tonto tonto en ifs se vuelve de alguna manera completamente inaceptablemente complejo. Y en este punto dije: “¡Bah! He leído mucho¡Breve e impresionado! " Luego me escapé de la oficina por unos días, me senté con una computadora portátil en un café y unos días después engendré algo.
Ideas claves
¿En qué se basa el Prólogo declarativamente? Sobre hechos, por ejemplo:
('', '').
('', '').y en términos o reglas, por ejemplo, si A es la madre B, entonces A es una niña:
() :- (, ).Por supuesto, entiendo que en nuestro tiempo no todo es tan simple, y en general es incluso un poco indecente decir esto, pero en los días en que la gente creía en la lógica formal, no había nada reprensible en tales ejemplos. Digamos por tolerancia:
(A, B) :- (A, B).
(, ) :- (, ), (, ).Y luego me preguntas así:
?- (X, '')Y el Prólogo terriblemente lógico te responde:
X = ''
X = ''La idea era que el usuario no se calentara la cabeza en qué secuencia y en qué cantidad el sistema de prólogo aplicaría reglas a los hechos para llegar a una respuesta. Pero, por supuesto, no es tan simple. El prólogo está lleno de muletas, adiciones funcionales, cortadores de diferentes ramas del razonamiento y cosas por el estilo, y todavía corre regularmente hacia una recursividad infinita.
En el libro de ese Bratko tan inspirador, se dedicó un capítulo completo a cómo se realiza la máquina del prólogo en su interior. En resumen, recorre el árbol de todas las reglas en profundidad, tratando de aplicar cada una de las reglas a su vez al conjunto de todos los hechos y variables que conoce para obtener un nuevo estado, y si la regla no se puede aplicar, retrocede al paso anterior e intenta probar otra opción.
Además, si logra reunir algo útil, la máquina toma la lista de reglas y, en el siguiente paso, comienza a buscar reglas para aplicar desde el principio de la lista. Además, si una variable ocurre en las reglas, la máquina recuerda qué estados de estas variables, teniendo en cuenta las reglas ya aplicadas, pueden ser. A esto se le llama desarrollo. Si puede encontrar una instanciación de las variables que hace que la pregunta sea verdadera, imprime esa instanciación. Luego puede ir a buscar la siguiente concretización y así sucesivamente. En el ejemplo artificial anterior, el sistema encontró dos concretizaciones que satisfacen las condiciones.
Me gustaría formular de alguna manera las reglas del juego, pero por supuesto no literalmente. Teniendo cierta experiencia en la depuración de programas en Prolog, no tenía muchas ganas de afrontar esta depuración y estos gastos generales en mi producto.
Primero, todo esto debería funcionar no en un montón de hechos dispersos, sino en el árbol de estado del juego: un modelo y aplicar los resultados de su trabajo también al mismo árbol. En segundo lugar, quiero escribir las reglas para que un valor específico, una variable y una expresión aritmética puedan estar en la misma posición, y el sistema debe manejar esto apropiadamente sin hacer preguntas adicionales al programador y sin requerir sintaxis adicional. En tercer lugar, por supuesto, es de vital importancia abandonar la recursividad infinita, pero aún es necesario dejar cierta repetición en la aplicación de las reglas. En cuarto lugar, el sistema de reglas debe estar escrito en un formato legible por humanos muy conveniente, de modo que de un vistazo quede claro lo que el autor quería decir. Y finalmente, en quinto lugar,todo esto debe estar vinculado a alguna herramienta conveniente de registro y depuración, de modo que sea fácil seguir el razonamiento de este sistema y comprender por qué ciertas reglas no funcionan en contra de las expectativas.
Esto, por supuesto, no es un solucionador universal de lógica de predicados de primer orden, sino simplemente un conveniente sistema declarativo de reglas de juego. Lo que en un sentido práctico también es muy bueno. Para esto se me ocurrió el nombre de Logrus mucho más tarde en uno de los siguientes proyectos. Describiré la versión final de una vez, sin pasar por todas las etapas intermedias del desarrollo del motor.
La sintaxis resultante de la biblioteca Logrus
Habrá mucha sintaxis.
1) En tiempo de ejecución, el árbol de decisiones se almacena en forma de algunas clases, pero lo primero que le adjunté, tan pronto como funcionó, fue Importar y Exportar en JSON. Resultó que esto también es conveniente porque si su estructura de datos no ha cambiado mucho, puede actualizar las reglas desde el archivo sin volver a compilar. Escribir en forma de JSON resultó ser tan conveniente que en uno de los siguientes proyectos, cuando los programadores tenían prisa, a veces en lugar de escribir un comando normal, simplemente lo hacían
state.AplayJSON("...");y en él se insertó la acción requerida como una cadena JSON. Esto, por supuesto, no afectó muy bien el rendimiento, pero si no es regular y solo en respuesta a los clics de los usuarios, entonces no da miedo ... Todo lo demás lo ilustraré de inmediato con JSON. Reproduzco JSON aproximadamente de memoria, porque fue muchísimo tiempo. Estrictamente hablando, JSON no garantiza el orden de los nodos en el objeto, pero la mayoría de las bibliotecas aún lo respetan, y aquí y debajo se usa activamente el orden de los nodos.
2) La Regla se convirtió en la unidad estructural principal del motor. Una regla consta de una condición y una acción. Por lo general, las reglas venían en matrices y se aplicaban una por una cada vez:
[{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]3) Cada regla contiene una condición: esta es una plantilla de árbol, que posiblemente contenga variables. El sistema buscará si el árbol de estado coincide con la plantilla para cualquier valor de las variables. Y si encuentra tal concretización, desencadenará una acción. Por ejemplo:
{"condition":{
"player":{
"$X":{"gold" : "<20", "name":"$NAME"}
}},
"action":{}}Tal construcción significará que para desencadenar una acción en el árbol, debe haber un nodo "jugador" en el nivel superior en el que haya uno o más nodos secundarios, cada uno de los cuales tiene campos "dorados" con un valor menor que 20 y "nombre". Si se cumple tal condición, entonces se llamará a la acción y, como entrada, se pasará en la variable X - la clave del nodo, y en la variable NAME el nombre del jugador. Si hay varios nodos adecuados y, en consecuencia, hay varias instancias posibles, entonces la acción se llamará varias veces con cada una de las instancias encontradas en la entrada.
4) Inicialmente, todo era un poco menos flexible allí, pero luego Valyard, a quien muchos conocen por numerosas charlas en conferencias sobre Unity, nos jodió con un analizador que analiza las expresiones aritméticas en un árbol de decisión rápido y la flexibilidad finalmente floreció en un color violento.
5) Comienzan los nombres de las variables C $. Pueden aparecer como una clave, como $ X, y luego se seleccionarán varias instancias, ya que un valor de hoja, como $ NAME, se puede insertar en expresiones aritméticas: por ejemplo: {"gold": "<$ X * 10" } Y luego se puede usar para verificar las condiciones, solo aquellos jugadores que tengan más oro que su número ordinal multiplicado por 10 pasarán la verificación, y finalmente se pueden calcular directamente en alguna expresión, por ejemplo: {"oro": "$ X = 3 + $ this "} donde $ this es el valor del punto actual en el que se llamó al cálculo. Pasar este nodo especifica el valor de la variable $ X como 3 + la cantidad de oro que tiene el jugador. De las posibilidadesque me vino a la mente no se implementó, solo había uno: la variable no puede aparecer primero en el lado derecho de una expresión aritmética, esto será un error, cuando se use como argumento, ya debe estar concretizado de una de varias otras formas.
6) Una variable en una expresión puede aparecer tantas veces como desee, mientras que la primera mención de ella lo especifica, y las siguientes serán una verificación de igualdad. Por ejemplo, tal construcción tomará al primer jugador, lo revisará por dinero y luego buscará a otro jugador para quien el primero sería el objetivo. Si no lo encuentra, retrocederá al punto de concretización X elegirá el siguiente jugador, buscará dinero, y así sucesivamente hasta pasar por todas las opciones posibles X e Y. Al intercambiar las líneas, el programador cambiará el orden de las verificaciones, pero no el resultado final:
{ "player":{
"$X":{"gold":">20"},
"$Y":{"target":"$X"}
}}7) La acción también es una plantilla de árbol que puede contener variables y expresiones aritméticas, y el árbol de estado del juego se cambiará para que coincida. Por ejemplo, esta plantilla asignaría al jugador X a un oponente en forma de jugador Y, pero si por alguna razón el jugador Y no existiera, se crearía. Y el reproductor "superfluo" se eliminará por completo. En el momento de crear el juego a partir de la captura de pantalla, el signo de eliminación era nulo, pero luego lo reemplacé con una palabra reservada, en caso de que alguien necesite insertar un valor en blanco por clave. En general, el principio, creo, es claro, y el significado de las acciones realizadas con el juego es básicamente el mismo.
{
"condition":{
"player":{
"$X":{"gold":">20"},
"$Y":{"target":"$X"}}},
"action":{
"$X":{"target":"$Y"},
"superfluous":"@remove"}
}
8) Una acción tampoco puede ser una plantilla de árbol, sino un conjunto de reglas. Cada uno de ellos se comprobará no desde cero, sino con la instanciación inicial con la que se llamó a la acción. Es decir, puede haber un grupo completo de reglas y todas usarán la variable X.
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":[
{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]
}9) La regla secundaria se puede aplicar no desde la raíz del árbol de estado, sino desde algún punto alcanzado durante la aplicación de la acción. En este caso, todas las condiciones y todas las acciones utilizarán este punto como raíz. Se parece a esto:
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":{
"$X":{"@rules":[
{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]}
}10) La repetición de la regla podría configurarse como un nodo más, esto logró, en caso necesario, una recursividad de profundidad limitada. Pero en la práctica, esa decisión no suele ser necesaria. También se puede usar para repetir un montón de reglas según sea necesario colocándolo en una acción:
{
"condition":{},
"action":{},
"repeat":5
}11) El árbol de reglas se puede cargar desde varios archivos JSON, su estructura de árbol simplemente se superpone entre sí. Era conveniente romper las reglas en bloques significativos separados. Probablemente algún Incluir también sería útil, ahora no recuerdo cómo se organizó con nosotros.
12) ¡Registro! Cualquier regla podría tener un "@log": nodo verdadero, lo que llevó al hecho de que esta regla comenzó a cagarse con gran detalle en el registro que describe el proceso de solución. Qué concretizaciones intentamos, qué ramas del razonamiento se suprimen y por qué. El registro era jerárquico, es decir, la regla anidada podría ser "@log": falso y no se registrará todo lo que ocurra en él y a continuación. Idealmente, me gustaría que este nodo pudiera dejarse en cualquier lugar del árbol de condiciones para ver solo lo que está sucediendo en un nivel de la plantilla, pero no parece que haya completado tal extensión. Quizás la depuración funcionó bien sin él, por lo que se pospuso hasta "algún día".
13) Escribir. El juguete era tan viejo que algunos de los programadores de hoy ni siquiera habían nacido. Estaba escrito en ActionScript2, que tenía escritura dinámica y herencia a través de prototipos disponibles en tiempo de ejecución. De los lenguajes modernos que se escuchan, solo Python funciona de esta manera. Sin embargo, vincularse a esta idea no es particularmente difícil. Lo haría usando el símbolo de tecla ':' como este: "$ X: int" pero puede ser complicado si la primera aparición de la variable no tuviera ninguno del tipo especificado. Y además, puede haber confusión con el operador ternario.
Como dicen, era suave sobre el papel, pero el uso práctico requería varias muletas diferentes. Estos son los que recuerdo:
14) Un mismo nodo puede ser verificado no por uno, sino por varias condiciones. Por ejemplo, tal condición verificaba primero que había más de 20 monedas y luego especificaba la variable en la que se representaba esta cantidad de dinero. El símbolo de servicio '@' si no está al principio de la línea significaba reingreso en el nodo, el identificador de reingreso yendo más allá no fue útil de ninguna manera. Quizás se usó un símbolo de servicio y algún otro, pero nada, en mi opinión, le impide usar este:
{
"player":{
"$X":{"gold":"<20", "gold@cnt":"$COUNT"}
}
}15) Se necesitaron operaciones aritméticas que se podían realizar sin usar ningún nodo en absoluto. Según la tradición del prólogo, fueron designados '_' y puede haber muchos de ellos:
{
"_":"$SUM=$A+$B",
"_@check":"@SUM <20"
}16) Dado que hay un pase de verificación hacia arriba del árbol, también tomó un descenso hacia abajo, hecho a través de la palabra clave "@parent". Esto, por supuesto, no contribuyó a mejorar la legibilidad, pero era imposible prescindir de él. Aquí, por supuesto, se sugiere directamente algún análogo de la función de ruta, que redirigiría al lugar especificado en el árbol, pero no recuerdo si logré implementarlo al final o no:
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":{
"$X":{"rules":[
{
"condition":{
"@parent":{"@parent":{"…":"…"}}
}
]},
}
}17) La acción ahora tiene la capacidad de extraer directamente algún método de clase. Esta es una patada en la garganta de la legibilidad, y preferiría algún análogo de #include, pero tal como está, no puedes descartar las palabras de la canción. Me pregunto si puedo prescindir de esto en la práctica si reanimo la biblioteca ahora en C #.
18) La regla ahora tiene una configuración adicional para repetir la acción no para todas las concreciones encontradas, sino solo para la primera. No recuerdo ahora cómo se llamaba, pero por alguna razón esta muleta fue útil para algunas reglas.
Resultados de uso
Tan pronto como la biblioteca comenzó a usarse activamente, todos los AI-shki se transfirieron rápidamente a ella, y esto hizo posible tener el doble de inteligencia artificial inteligente y gastar tres veces menos recursos de programación. El hecho de que los datos intermedios de la escala de IA se almacenaran directamente en el árbol ayudó mucho. En particular, las reglas mismas escribieron información sobre las cartas de cada palo que habían salido del juego en el árbol de estado del juego.
Ya en el próximo proyecto, comprobando las reglas del juego y posibilitando movimientos desde cada puesto movido al mismo motor. Y en general, no solo para la creación rápida de prototipos, sino también para juegos en los que simplemente hay muchas reglas, esto sería algo muy útil. Al final, los JSON descargables con lógica pueden reemplazar la mitad de lo que hacen los programadores con el código y también ganar en flexibilidad.
Por supuesto, en términos de velocidad de ejecución, todo esto fue notablemente inferior al lío de ifs, especialmente en la implementación en AS2 con sus prototipos y objetos dinámicos, pero no tanto como para que no pudiera implementarse en producción.
El siguiente paso fue transferir la verificación de reglas y determinar la acción de la IA a la computadora cliente. Para que los jugadores se controlen entre sí. E incluso se me ocurrió un algoritmo de este tipo para hacer esto a pesar de que no conocemos los valores de las cartas enemigas, pero esa fue una historia completamente diferente.
Pasaron muchos años, cambié de trabajo una docena de veces, y cada vez que actualizaba mi currículum, iba a toox.com y me sorprendía encontrar mi trabajo todavía en servicio. Incluso me detuve para jugar otro juego. Y una vez en Belot me encontré accidentalmente con un juego de cartas que daban el máximo número posible de puntos. La probabilidad de obtener tal conjunto es de uno entre tres millones.
Algún día reuniré mi voluntad en un puñado y haré un remake moderno de Logrus para C # y Unity3d, por ejemplo, para el estratega hexagonal con el que sueño. Pero no será hoy, hoy me iré a la cama. Se ha cumplido con éxito el deber de difundir ideas que valgan la pena difundir.
En conclusión, un par de anécdotas
Estábamos ubicados en Novosibirsk Academgorodok. Alquilamos una oficina en el instituto. Y el cliente es francés, completamente ajeno a las costumbres locales. Y así, al tercer o cuarto mes de trabajo conjunto, viene a visitarnos, a conocernos. Me registré el fin de semana en el hotel local "Zolotaya Dolina" y el lunes, le dice al gerente, nos vemos en un taxi a las diez de la mañana, iremos con los programadores a conocernos. Y coge a Vovchik y llega a las 10. En general, van hasta el instituto, tocan la puerta, y del otro lado viene la abuela del vigilante y los mira completamente sin entender desde detrás de la puerta cerrada. En una fecha tan temprana, no había científicos ni programadores alquilando oficinas en el edificio. Literalmente la despertaron.
Y aquí hay otro caso. Nuestro Sebastián Pereira llama al gerente y le dice que milagrosamente lograron irrumpir en la TV y pronto nos mostraremos en la TV con nuestro sitio web. Después de unas 8 horas. Entonces, ¿qué haces allí para que funcione de manera más confiable ... En el reloj del 2 de enero ... No importa la hora ... Y entonces Vovchik toma un taxi, comienza a recoger programadores en dormitorios y apartamentos, completamente en un estado de obscenidad, y los lleva a la oficina. Ese día vi a nuestro administrador de sistemas por primera vez en mi vida. Hasta este punto, hizo todo exclusivamente de forma remota. Y así torcimos a todos los que pudieron. En particular, rompí todo este sistema volviendo a poner un montón de si en su lugar, y aquí estamos, mirando el gráfico de asistencia y de repente vemos cómo comienza a subir. En algún lugar de la marca x15, el servidor se bloqueó. Pero el administrador dijo que todo está bien, cayó suavemente,ahora se levantará. El servidor se bloqueó tres veces más ese día.