Jugar juegos de aventura de texto es puro placer, pero el placer consume bastante cerebro. Pero hoy tenemos todas estas capacidades de procesador inactivo.
¿Qué pasa si hacemos que la computadora pase por el juego por nuestra cuenta, y solo tenemos que recostarnos en la silla y mirar? Ni siquiera necesitamos todas estas redes neuronales novedosas, una fuerza bruta bastante simple.
Solo dejamos caer un montón de texto semi aleatorio en la entrada del juego de texto y vemos qué sucede. En el mundo de la seguridad de la información, esto se llama fuzzing.
El objetivo será la Z-Machine, un intérprete de máquina virtual desarrollado por Joel Berez y Mark Blanck en 1979, el corazón de los juegos de Infocom. Este es un objetivo ideal para aventuras fuzzing, ya que está bien documentado y tiene muchas herramientas y bibliotecas de soporte.
Zork se lanzó en el Atari 800XL (Sebastian Grunwald, CC 3.0)Mini Zork
El juego que vamos a
difuminar :
MINI-ZORK-1: The Great Underground Empire . Esta es una versión demo de Infokomovsky Zorka primero, diseñada para arrancar desde un cassette, no desde un disquete. De hecho, fue un anuncio publicado en el suplemento de la década de 1990 para la revista Commodore's UK para usuarios.
Para aquellos que no han jugado Zork, esto es lo que ves después de cargar el juego:
MINI-ZORK I: The Great Underground Empire Copyright (c) 1988 Infocom, Inc. All rights reserved. ZORK is a registered trademark of Infocom, Inc. Release 34 / Serial number 871124 West of House You are standing in an open field west of a white house, with a boarded front door. You could circle the house to the north or south. There is a small mailbox here. >
Sugerencia> invita al usuario a ingresar comandos como OPEN MAILBOX o GO NORTH para avanzar en el juego. El objetivo es "encontrar los tesoros del Gran Imperio Subterráneo y recogerlos en su caja de botín" en el camino resolviendo acertijos y hundiendo enemigos.
Juguemos a buscar verbos (y sustantivos)
El manual de usuario completo con Zork proporciona ejemplos de posibles comandos como ABRIR LA PUERTA DE MADERA y WARLOCK, TOMAR EL DESPLAZAMIENTO DEL HECHIZO Y SIGUIRME. Sin embargo, los usuarios tenían que adivinar independientemente cómo resolver un acertijo particular.
Los verbos como GET y DROP (GET / DROP) son bastante obvios, al igual que los ocho puntos cardinales estándar y arriba / abajo (UP / DOWN), y al mismo tiempo dentro y fuera (IN / OUT). Pero los usuarios también tuvieron que usar ATTACK, POOL y PRAY, así como pronunciar palabras mágicas que no estaban en el manual. La situación cuando el juego no daba suficientes pistas a los jugadores, se burlaban de ellos como "cazar verbos".
Para generar comandos, fuzzer necesitará una lista de palabras aceptadas por el juego, su vocabulario. La máquina Z selecciona esta lista como un diccionario de juego (se encuentra en un lugar estándar en el archivo de cada juego).
(¡Esto es una especie de estafa, sí! Pero realmente no hay otra manera de explicarle a la computadora qué palabras usar, ya que algunos verbos no se mencionan en ninguna parte del texto).
La forma más fácil de generar comandos es tomar aleatoriamente una o más palabras, en nuestro caso, una o dos. No sabemos qué palabras son verbos y qué sustantivos, por lo que generamos muchos comandos extraños como "VER OOPS" y "CONDUCTOR A CONTINUACIÓN".
Obviamente, esto es bastante ineficiente, porque tenemos que clasificar las combinaciones N * N (donde N es el tamaño del vocabulario) para encontrar el comando como "KILL TROLL".
Sin embargo, podemos hacer trampa un poco. Escanearemos todas las palabras en la salida de texto del juego y elegiremos las que se encuentran en nuestro diccionario. Y elija una palabra de esta lista (en lugar de un diccionario completo). Por ejemplo, si vemos NORTE, OESTE, CASA y CAJA DE CORREO en el texto, es más probable que usemos estas palabras.
Buscar marcadores de historia
Solo dando comandos al azar, obtenemos muchas tonterías que el analizador jurará:
>about painti [ !] >leathe guideb [ "leathe" , .]
(Las palabras de vocabulario no tienen más de seis caracteres de longitud en la máquina Z, por lo que generamos palabras como "cuero").
Sin embargo, tal pisada en el acto tomará una eternidad. ¿Cómo podemos determinar qué caminos son más prometedores que otros? Buscaremos marcadores para promocionar la historia.
La máquina Z tiene una instrucción PRINT que imprime texto en la consola. A menudo, estos son fragmentos de descripciones, como "West of the House" y "botella destrozada". Registraremos cada uno de ellos como un marcador.
Cada vez que vemos un nuevo marcador, guardamos el pasaje actual, una lista de los equipos que realizamos en el juego actual.
Asociamos esta lista con el marcador actual, por lo que podemos (con suerte) obtener el mismo texto en la salida después de reproducir los mismos comandos.
Cada lanzamiento del juego selecciona un marcador de objetivo específico y, por lo tanto, el pasaje asociado con él. El algoritmo de búsqueda selecciona nuevos marcadores con más frecuencia que los antiguos.
No repetiremos los equipos textualmente en cada juego, pero agregaremos algunos equipos al azar y mezclaremos el orden. Cuando vemos un nuevo marcador, aumentaremos el parámetro de "éxito", cuyo crecimiento mostrará que es posible cambiar la lista de comandos con menos frecuencia. Cuando este parámetro crece lo suficiente, marcamos este marcador como "estable", ya que tenemos un pasaje predecible que conduce a él.
Buscando un camino corto
Las formas en que pasamos por el juego a menudo son ineficaces. Aquí está la lista de comandos que se utilizaron para generar el marcador "¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡!!!)))") Esta es la lista de comandos que se usaron para generar el marcador "¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡!!!)))) - Aquí está la lista de los comandos que se usaron para generar el marcador" ¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡!!!)))):
curse, art, body gate, incant count, the, the egg, repent, from the, the consum, what, leathe, trap- see, breath here, what intnum, about here, leathe guideb, about, about here, pot, here, see, here about, about, self, here about, mangle, see, rug, the, reply, elvish, say, stilet beetle, say toss, pray, gate about, what bolt, guideb, wooden, say knock, say sit, trail and, here, pray leathe, intnum, one, pray one, jump
Todo lo que realmente necesitamos hacer es ingresar el último comando: JUMP (o DIVE). Pero el algoritmo de búsqueda no sabe cuál de los comandos anteriores son necesarios para mostrar "¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡
Necesitamos reducir el pasaje, para que sean lo más cortos posible. Cuando vemos un marcador, reemplazamos el pasaje asociado con una lista más corta de comandos, si es posible. Esto nos lleva al marcador de objetivo más rápido, dándonos más movimientos para experimentar después de alcanzar la meta.
Muchos marcadores, como "Wheeeeeeeeee !!!!!", no son interesantes, ya que podemos lograrlos en un turno al comienzo del juego. Al reducir su lista de comandos, eventualmente podremos confirmar que este es el caso, y así eliminarlos de la lista de posibles marcadores de destino.
Mas que palabras
Como tenemos acceso directo al estado interno de la máquina Z, podemos usar algo más que la salida de texto para controlar nuestra búsqueda. Por ejemplo, podemos arreglar cuando un objeto se ha movido de una habitación a otra, o cuando otras propiedades y banderas han cambiado en el objeto. Llámelo marcadores VM (marcadores de máquina virtual) y fíjelos en paralelo con marcadores de texto:
@mv_30_15 (#30) #15 @f_176_10_1 "" (10) ""(#176)
Necesitamos esto porque la salida de texto no nos cuenta toda la historia. Por ejemplo, al levantar una espada o lámpara, llegaremos al mismo marcador "Tomado". Y el marcador VM le dirá al algoritmo de búsqueda cuando se alcanza un nuevo estado de la máquina virtual, por ejemplo, cuando un jugador se mueve a una nueva habitación, o un objeto ha sido recogido o arrojado.
Romper una máquina virtual
Investigar el estado del juego es un proceso bastante lento. Una de las primeras tareas en el juego es matar al troll, lo que no te permite ir más allá. Sin embargo, antes de eso, el jugador necesita encontrar una espada en la casa un poco más arriba.
Para acelerar el proceso de búsqueda, descifraremos la máquina Z y llevaremos el estado del juego a lo que vimos anteriormente. Por ejemplo, accidentalmente movimos una espada a la mano de un jugador, lo que hizo posible ejecutar con éxito el comando "STAB" (puñalada). ("TROLL DE ATAQUE" no funcionará a menos que agreguemos "CON LA ESPADA", pero "PUNTA" (apuñalar) ya implica la presencia de un objeto afilado y, por lo tanto, funciona).
Romperemos solo marcadores estables, por lo que si podemos repetir el juego de manera confiable y las manos del jugador resultan ser una espada, permitiremos hackear este estado: "la espada está en las manos del jugador". Luego podemos combinar los equipos utilizados para levantar la espada con los equipos utilizados para bajar a la mazmorra, descubriendo en el camino que debemos atacar al troll.
El ejemplo del troll es especialmente jesuita, porque, por regla general, se requieren varios golpes para terminarlo, y cada ataque da un resultado aleatorio. Dado que nuestro algoritmo prefiere pases más cortos, es preferible cumplir con un pronóstico optimista sobre nuestras habilidades de combate.
Después de 530,000 recorridos y 10,600,000 equipos (200 equipos por juego), finalmente descubrimos cómo atacar al troll:
north, east, open window, into, west, light, lift trap, small hi, get, west, light, tug large, lift trap, down, north, stab
Todavía hay algunos comandos innecesarios, y todavía no entendemos que tenemos que golpearlo varias veces, pero podemos manejarlo.
Hobby fatal
El algoritmo de búsqueda no conoce la diferencia entre recolectar objetos, lanzar objetos y mover a un jugador de una habitación a otra. La única forma en que define el progreso es viendo progresar los marcadores de la historia.
Esto rápidamente desarrolla en el algoritmo de búsqueda un gusto por ... ¡Asesinato! Para matar a un jugador, en particular, porque es muy fácil y simple: ingrese "ATTACK":
>attack [ ] , ! **** **** , , . , . c-. , .
En Mini Zorka, la primera muerte no es el final del juego, el jugador se teletransporta a otro lugar y tus cosas están dispersas. Para un algoritmo de búsqueda, la muerte es simplemente un objeto que se mueve de una habitación a otra, creando marcadores para mover la historia en el camino. Este pasatiempo lleva a la exposición de otros errores divertidos en el juego, como la capacidad del jugador de arrojar sus manos al río.
El juego tiene una puntuación de 0 a 350 puntos, basado en resolver acertijos y recoger tesoros. Cuando un jugador muere, se reduce en 10 puntos. Podemos usar la cuenta como una heurística, pero esto puede reducir excesivamente el comportamiento arriesgado: el amor por deambular por lugares oscuros o por luchar contra trolls.
El algoritmo de búsqueda también está muy interesado en lo que el jugador no ve, como los NPC que se mueven de una habitación a otra. Por ejemplo, el marcador @ mv_112_37 indica el movimiento de un ladrón a una habitación específica. El algoritmo de búsqueda logra reproducir este marcador ejecutando repetidamente comandos Z o WAIT, esencialmente esperando que el ladrón llegue a la habitación objetivo.
También le gusta recoger y tirar objetos en diferentes lugares, porque cada movimiento del objeto es un nuevo marcador. Quien sabe ¡Quizás tirar esta hoja en un sendero del bosque conducirá a la victoria en el juego! (Narrador: no, no lo hará)
Fuzzing identifica invariablemente errores en el programa, y este juego no es diferente, aunque persiste. Él descubrió cómo generar la palabra "Clrthatrqdc" al comienzo del juego:
>tie up [ ] With a Clrthatrqdc!?!
Esto parece ser una variable no inicializada que indica datos no textuales. La codificación del texto comprimido en la máquina Z es principalmente alfabética, porque no se ve tanta basura aleatoria como cuando intenta imprimir un archivo binario como ASCII. (Actualmente, esta palabra
solo está dos veces en Google (
ya cuatro veces, aprox. Transl. )).
Tutorial
Para ganar el juego, tendremos que arrastrar nuestros productos saqueados de vuelta a la caja de botín y meter cada objeto en él. Nuestro algoritmo de búsqueda simple tardará mucho tiempo en tropezar con este comportamiento, especialmente dada su tendencia a desperdiciar energía y tiempo al mover objetos de una habitación a otra.
Complicar un algoritmo de investigación aleatoria lleva tiempo, por lo que debemos ser selectivos al agregar nuevas funciones. También queremos evitar el conocimiento a priori en el juego; en otras palabras, solo queremos hacer un poco de trampa.
Si desea experimentar,
consulte el código fuente en GitHub , que utiliza
JSZM (el intérprete de Z-Machine Daniel Legenbauer). Muchos
juegos están disponibles (solo se admiten versiones de hasta 3).
El documento Graham Nelson
Z-Machine Standards , que ha estado tratando con la máquina Z durante un par de décadas, también está disponible.
¿Y necesito agregar soporte para Z-Machine en
8bitworkshop ? Avísame