Jouer à des jeux d'aventure texte est un pur plaisir, mais le plaisir est assez consommateur de cerveau. Mais aujourd'hui, nous avons toutes ces capacités de processeur inactives.
Que se passe-t-il si nous faisons passer l'ordinateur par le jeu par nous-mêmes et que nous devons simplement nous pencher en arrière sur la chaise et regarder? Nous n'avons même pas besoin de tous ces réseaux de neurones de nouvelle génération, plutôt d'une simple force brute.
Nous déposons juste un tas de texte semi-aléatoire à l'entrée du jeu de texte et voyons ce qui se passe. Dans le monde de la sécurité de l'information, on parle de fuzzing.
L'objectif sera la Z-Machine, un interprète de machine virtuelle développé par Joel Berez et Mark Blanck en 1979, au cœur des Jeux Infocom. C'est une cible idéale pour le fuzzing d'aventure, car il est bien documenté et dispose de nombreux outils et bibliothèques de support.
Lancement de Zork sur l'Atari 800XL (Sebastian Grunwald, CC 3.0)Mini Zork
Le jeu que nous allons
jouer -
MINI-ZORK-1: The Great Underground Empire . Il s'agit d'une version de démonstration du premier Zorka d'Infokomovsky, conçue pour démarrer à partir d'une cassette et non à partir d'une disquette. Il s’agissait essentiellement d’une publicité publiée dans le supplément des années 1990 au magazine britannique des utilisateurs de Commodore,
Zzap! 64 .
Pour ceux qui n'ont pas joué à Zork, voici ce que vous voyez après avoir chargé le jeu:
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. >
Astuce> invite l'utilisateur à entrer des commandes comme OPEN MAILBOX ou GO NORTH pour avancer dans le jeu. Le but est de «trouver les trésors du Grand Empire Souterrain et de les collecter dans votre boîte à butin» tout en résolvant des énigmes et en plongeant les ennemis.
Jouons à la chasse aux verbes (et aux noms)
Le guide de l'utilisateur complet avec Zork donne des exemples de commandes possibles, telles que OUVRIR LA PORTE EN BOIS et WARLOCK, PRENDRE LE SORTIE DÉFILER PUIS SUIVEZ-MOI. Cependant, les utilisateurs devaient deviner indépendamment comment résoudre une énigme particulière.
Les verbes tels que GET et DROP (GET / DROP) sont assez évidents, tout comme les huit points cardinaux standard et haut / bas (UP / DOWN), et en même temps in and out (IN / OUT). Mais les utilisateurs devaient également utiliser ATTACK, POOL et PRAY, ainsi que prononcer des mots magiques qui n'étaient pas dans le manuel. La situation où le jeu ne donnait pas suffisamment d'indices aux joueurs, ils appelaient moqueusement la «chasse aux verbes».
Pour générer des commandes, fuzzer aura besoin d'une liste de mots acceptés par le jeu, son vocabulaire. La Z-machine sélectionne cette liste comme dictionnaire de jeu (elle se trouve à un emplacement standard dans le fichier de chaque jeu).
(C'est une sorte d'arnaque, oui! Mais il n'y a vraiment pas d'autre moyen d'expliquer à l'ordinateur quels mots utiliser, car certains verbes ne sont mentionnés nulle part dans le texte.)
La façon la plus simple de générer des commandes est de prendre au hasard un ou plusieurs mots, dans notre cas, un ou deux. Nous ne savons pas quels mots sont des verbes et quels noms, donc nous générons beaucoup de commandes étranges comme "SEE OOPS" et "DRIVER BELOW".
Évidemment, cela est assez inefficace, car nous devons trier N * N combinaisons (où N est la taille du vocabulaire) pour trouver la commande même comme "KILL TROLL".
Cependant, nous pouvons tricher un peu. Nous scannerons tous les mots sur la sortie texte du jeu et choisirons ceux qui se trouvent dans notre dictionnaire. Et choisissez un mot dans cette liste (au lieu d'un dictionnaire complet). Par exemple, si nous voyons NORTH, WEST, HOUSE et MAILBOX dans le texte, nous sommes plus susceptibles d'utiliser ces mots.
Recherche de marqueurs d'histoire
En donnant simplement des commandes aléatoires, nous obtenons beaucoup de bêtises que l'analyseur jurera:
>about painti [ !] >leathe guideb [ "leathe" , .]
(Les mots de vocabulaire ne dépassent pas six caractères dans la Z-Machine, nous générons donc des mots comme «leathe».)
Cependant, un tel piétinement sur place prendra une éternité. Comment déterminer quelles voies sont plus prometteuses que d'autres? Nous chercherons des marqueurs pour promouvoir l'histoire.
La Z-Machine possède une instruction PRINT qui imprime du texte sur la console. Ce sont souvent des fragments de descriptions, comme «Ouest de la maison» et «bouteille brisée». Nous enregistrerons chacun d'eux comme marqueur.
Chaque fois que nous voyons un nouveau marqueur, nous enregistrons le passage actuel - une liste des équipes que nous avons exécutées dans le jeu en cours.
Nous associons cette liste au marqueur actuel, afin que nous puissions (espérons-le) obtenir le même texte dans la sortie après avoir relu les mêmes commandes.
Chaque lancement du jeu sélectionne un marqueur cible spécifique, et donc le passage qui lui est associé. L'algorithme de recherche sélectionne les nouveaux marqueurs plus souvent que les anciens.
Nous ne rejouerons pas les équipes textuellement dans chaque partie, mais nous ajouterons quelques équipes aléatoires et mélangerons l'ordre. Lorsque nous verrons un nouveau marqueur, nous augmenterons le paramètre «succès», dont la croissance montrera qu'il est possible de changer moins souvent la liste des commandes. Lorsque ce paramètre augmente suffisamment, nous marquons ce marqueur comme «stable», car nous avons un passage prévisible qui y mène.
Vous cherchez un court chemin
Les façons dont nous traversons le jeu sont souvent inefficaces. Voici la liste des commandes qui ont été utilisées pour générer le marqueur «Wheeeeeeeeee !!!!!»:
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
Tout ce que nous devons vraiment faire est d'entrer la dernière commande: JUMP (ou DIVE). Mais l'algorithme de recherche ne sait pas laquelle des commandes précédentes est nécessaire pour afficher "Wheeeeeeeeee !!!!!"
Nous devons réduire le passage - pour les rendre aussi courts que possible. Lorsque nous voyons un marqueur, nous remplaçons le passage associé par une liste de commandes plus courte, si possible. Cela nous amène plus rapidement au marqueur cible, nous donnant plus de mouvements à expérimenter après avoir atteint l'objectif.
De nombreux marqueurs, tels que "Wheeeeeeeeee !!!!!", ne sont pas intéressants, car nous pouvons les réaliser en un tour au tout début du jeu. En réduisant leur liste de commandes, nous pourrons éventuellement confirmer que c'est le cas, et ainsi les supprimer de la liste des marqueurs cibles potentiels.
Plus que des mots
Puisque nous avons un accès direct à l'état interne de la machine Z, nous pouvons utiliser autre chose que la sortie de texte pour contrôler notre recherche. Par exemple, nous pouvons corriger lorsqu'un objet s'est déplacé d'une pièce à l'autre, ou lorsque d'autres propriétés et indicateurs ont changé sur l'objet. Appelez-le marqueurs VM (marqueurs de machine virtuelle) et corrigez-les en parallèle avec les marqueurs de texte:
@mv_30_15 (#30) #15 @f_176_10_1 "" (10) ""(#176)
Nous en avons besoin parce que la sortie de texte ne nous raconte pas toute l'histoire. Par exemple, en ramassant une épée ou une lampe, nous atteindrons le même marqueur «Pris». Et le marqueur VM indiquera à l'algorithme de recherche quand un nouvel état de la machine virtuelle est atteint, par exemple, lorsqu'un joueur se déplace dans une nouvelle salle, ou qu'un objet a été ramassé ou jeté.
Briser une machine virtuelle
L'enquête sur l'état du jeu est un processus assez lent. L'une des premières tâches du jeu est de tuer le troll, ce qui ne vous permet pas d'aller plus loin. Cependant, avant cela, le joueur doit trouver une épée dans la maison un peu plus haut.
Afin d'accélérer le processus de recherche, nous allons casser la Z-machine et ramener l'état du jeu à ce que nous avons vu plus tôt. Par exemple, nous avons accidentellement déplacé une épée dans la main d’un joueur, ce qui a permis d’exécuter avec succès la commande «STAB» (stab). ("ATTACK TROLL" ne fonctionnera que si nous ajoutons "WITH SWORD", mais "STAB" (coup de couteau) implique déjà la présence d'un objet pointu et fonctionne donc.)
Nous ne casserons que des marqueurs stables, donc si nous pouvons répéter le jeu de manière fiable et que les mains du joueur se révèlent être une épée, nous autoriserons le piratage de cet état: "l'épée est entre les mains du joueur". Ensuite, nous pouvons combiner les équipes utilisées pour lever l'épée avec les équipes utilisées pour descendre le donjon, découvrant en cours de route que nous devons attaquer le troll.
L'exemple du troll est particulièrement jésuite, car, en règle générale, il faut plusieurs coups pour le terminer, et chaque attaque donne un résultat aléatoire. Étant donné que notre algorithme préfère les passes plus courtes, il est préférable d'adhérer à une prévision optimiste concernant nos capacités de combat.
Après 530 000 soluces et 10 600 000 équipes (200 équipes par match), nous avons enfin compris comment attaquer le troll:
north, east, open window, into, west, light, lift trap, small hi, get, west, light, tug large, lift trap, down, north, stab
Il y a encore quelques commandes inutiles, et nous ne comprenons toujours pas que nous devons le frapper plusieurs fois, mais nous pouvons le gérer.
Passe-temps fatal
L'algorithme de recherche ne connaît pas la différence entre collecter des objets, lancer des objets et déplacer un joueur d'une pièce à l'autre. La seule façon dont il définit le progrès est de voir les marqueurs de l'histoire progresser.
Cela développe rapidement dans l'algorithme de recherche un goût pour ... le meurtre! Pour tuer un joueur, en particulier, parce qu'il est si facile et simple: entrez "ATTACK":
>attack [ ] , ! **** **** , , . , . c-. , .
Dans Mini Zorka, la première mort n'est pas la fin du jeu, le joueur se téléporte vers un autre endroit et vos affaires sont dispersées. Pour un algorithme de recherche, la mort est simplement un objet se déplaçant d'une pièce à l'autre, créant des marqueurs pour déplacer l'histoire en cours de route. Ce passe-temps entraîne l'exposition d'autres bugs amusants dans le jeu, tels que la capacité du joueur à jeter ses mains dans la rivière.
Le jeu marque de 0 à 350 points, basé sur la résolution d'énigmes et la collecte de trésors. Lorsqu'un joueur meurt, il est réduit de 10 points. Nous pouvons utiliser le compte comme une heuristique, mais cela peut réduire excessivement les comportements à risque - l'amour d'errer dans des endroits sombres ou de combattre des trolls.
L'algorithme de recherche s'intéresse également vivement à ce que le joueur ne voit pas, comme les PNJ se déplaçant entre les pièces. Par exemple, le marqueur @ mv_112_37 indique le mouvement d'un voleur vers une pièce spécifique. L'algorithme de recherche parvient à reproduire ce marqueur en exécutant à plusieurs reprises des commandes Z ou WAIT, s'attendant essentiellement à ce que le voleur atteigne la pièce cible.
Il aime aussi ramasser et jeter des objets à différents endroits, car chaque mouvement de l'objet est un nouveau marqueur. Qui sait Peut-être que jeter cette feuille sur un chemin forestier mènera à la victoire dans le jeu! (Narrateur: non, ce ne sera pas le cas.)
Le fuzzing identifie invariablement les erreurs dans le programme, et ce jeu n'est pas différent, bien qu'il persiste. Il a compris comment générer le mot «Clrthatrqdc» au tout début du jeu:
>tie up [ ] With a Clrthatrqdc!?!
Cela semble être une variable non initialisée indiquant des données non textuelles. Le codage du texte compressé dans la machine Z est principalement alphabétique, car vous ne voyez pas autant de déchets aléatoires que lorsque vous essayez d'imprimer un fichier binaire en ASCII. (Actuellement, ce mot
n'est que deux fois sur Google (
déjà quatre fois, environ. Trad. ).)
Procédure pas à pas
Pour gagner le jeu, nous devrons ramener nos biens pillés dans la boîte à butin et y fourrer chaque objet. Notre algorithme de recherche simple mettra beaucoup de temps à tomber sur ce comportement, en particulier compte tenu de sa tendance à gaspiller de l'énergie et à déplacer des objets d'une pièce à l'autre.
La complication d'un algorithme de recherche aléatoire prend du temps, nous devons donc être sélectifs lors de l'ajout de nouvelles fonctionnalités. Nous voulons également éviter les connaissances a priori dans le jeu - en d'autres termes, nous voulons seulement tricher un peu.
Si vous voulez expérimenter,
consultez le code source sur GitHub , qui utilise
JSZM (l'interpréteur de Z-Machine Daniel Legenbauer). De nombreux
jeux sont disponibles (seules les versions jusqu'à 3 sont prises en charge.)
Le document Graham Nelson
Z-Machine Standards , qui traite de la machine Z depuis deux décennies, est également disponible.
Et dois-je ajouter le support Z-Machine sur
8bitworkshop ? Faites le moi savoir!