Des chercheurs étudient un algorithme de jeu Atari vintage impénétrable
La légende raconte que l’alcool a été impliqué dans la création de la table déroutante qui fait le labyrinthe du jeu Atari.
Les algorithmes sont un sujet de conversation brûlant, car Facebook, euh, Meta, se trouve critiqué pour avoir utilisé des algorithmes qui favorisent la colère et les conflits dans le but d’augmenter l’engagement des clients avec le site Web.
Mais il est difficile d’explorer les algorithmes pour voir exactement comment ils fonctionnent, en particulier les algorithmes de médias sociaux très complexes. L’ampleur de ce défi est illustrée par l’article des chercheurs de l’Université de Calgary, John Aycock et Tara Copplestone, « L’art, la science et l’ingénierie de la programmation ».
Le joueur se déplace dans le labyrinthe à défilement vertical d’Entombed.
L’article examine un jeu de console Atari 2600 de 1982 appelé « Entombed ». Ce jeu à défilement vertical générait un labyrinthe en temps réel au fur et à mesure que le joueur progressait dans les catacombes, mais l’algorithme qui crée le labyrinthe résoluble à la volée en utilisant les ressources informatiques minimales d’Atari fait que les programmeurs modernes se grattent la tête.
Le manuel du jeu le présente ainsi : « Vous et votre équipe d’archéologues êtes tombés dans les ‘catacombes des zombies’. Plus vous survivez longtemps, plus vous devez vous déplacer rapidement.
Pour rappel, la console Atari 2600, comme les PC Apple II et Commodore 64, était alimentée par un processeur MOS Technologies 6507. Il fonctionnait à 1,19 MHz et disposait de 128 octets de RAM sur une puce MOS 6532 RAM, I/O et Timer (RIOT). Octets. Pas des gigaoctets, des mégaoctets ou même des kilo-octets. Les cartouches de jeu apportaient 4 kilo-octets de ROM contenant le jeu.
La dernière puce du 2600 était un adaptateur d’interface de télévision. Comme l’expliquent Aycock et Copplestone, « Un programmeur 2600 devait structurer son code pour rendre l’affichage sur un ligne par ligne base et répéter cela pour tous image vidéo unique.
Travailler dans ces contraintes exigeait que le jeu génère un nouveau labyrinthe à la volée à chaque fois car il n’y avait pas d’espace pour stocker une conception de labyrinthe existante. En effet, l’article explique que « les défis de la programmation sont notés par les 2 600 anciens programmeurs lors d’entretiens. John Harris a déclaré : « La façon dont la machine devait être programmée était si obscure et si difficile que vous deviez écrire un code extrêmement optimal. »
L’Atari 2600 a été produit de 1977 à 1992 en raison du grand nombre de jeux disponibles pour la console.
Tellement optimal, semble-t-il, que dans le cas de l’algorithme de génération de labyrinthe, personne ne peut comprendre comment fonctionne la table qui le crée aujourd’hui. Le programmeur Paul Allen Newell se souvient ainsi de sa création : « Duncan et moi sommes sortis boire une bière et avons fini par trouver ce « problème » de se demander si l’on pouvait générer un labyrinthe sans fin qui avait toujours une solution et que « Nous avons élaboré le algorithme et […] J’ai passé un week-end à coder quelque chose.
Le collègue de Newell, Steve Sidley, s’en souvient ainsi : « La routine de génération de labyrinthe de base avait été partiellement écrite par un stoner qui était parti. Je l’ai contacté pour essayer de comprendre ce que faisait l’algorithme de génération de labyrinthe. Il m’a dit que cela lui était venu alors qu’il était ivre et qu’il avait perdu la tête, il l’a codé en assemblage pendant la nuit avant de s’évanouir, mais maintenant, il ne pouvait plus se souvenir de la façon dont l’algorithme fonctionnait.
Ce n’est pas une surprise pour Sidley que les ingénieurs d’aujourd’hui ne sachent pas comment le labyrinthe du jeu est généré parce qu’il ne pouvait pas le comprendre à l’époque. « C’était un mystère pour moi aussi », a-t-il déclaré. «Je ne pouvais pas le déchiffrer. Je viens de l’utiliser pour générer le nouveau [maze] ligne en bas de l’écran.
