Une brève histoire de Pac-Man

Lors de l’organisation des journées de la recherche d’Orange en 2017, j’avais été à l’initiative de l’organisation d’une exposition « Pac-Man 1980-2017 » qui retraçait l’histoire de ce jeu mythique, de la ROM de 16K à la HTML5, la 3D et l’IA. Mais ce jeu touche aussi d’autres de mes passions, du design hardware au design thinking, de la biologie cellulaire à l’IA, du géocaching à Google Maps… Bref j’ai, avec ce billet, pris plaisir à explorer mon petit univers à travers le prisme de Pac-Man.

1980 Naissance d’un jeu video icônique

I don’t have any particular interest in computers. I’m interested in creating images that communicate with people.
Toru Iwatani

Pac-Man est né au Japon en 1980. Les 1er jeux video de type casse-brique commençaient à lasser et les shoot-them-up comme Space Invaders étaient dans toutes les salles d’arcade. Toru Iwatani, un autodidacte japonais de 25 ans qui travaillait pour la petite société Namco, décide de concevoir un jeu qui ne soit pas basé sur la violence, et attractif aussi bien pour les filles comme pour les garçons.

Grâce à une remarquable démarche de Design Thinking, Toru Iwatani a créé seul le jeu d’arcade qui sera le plus vendu au monde.

Une partie importante de l’attrait du jeu vient des « personnalités » différentes de chacun des fantômes.

Blinky, le fantôme rouge, attaque directement Pac Man. Il suit Pac-Man comme son ombre.
Pinky, le fantôme rose, se met en embuscade. Il vise l’endroit où va se trouver Pac-Man.
Inky, le fantôme bleu, est capricieux. A certains instants, il décide de s’éloigner de Pac-Man.
Clyde, le fantôme orange, feint l’indifférence. De temps en temps, il choisit une direction au hasard.

Les premiers jeux d’arcade, équipés du Z80

Pour programmer ce jeu, Toru Iwatani a dû réaliser des prouesses techniques. Le microprocesseur employé dans les consoles d’arcades était le Z80, qui n’effectuait que 0,4 Million d’instruction par seconde. L’écran 16 couleur avait une résolution de 224×288 et le programme complet devait peser moins de 16Koctets.

Par comparaison, le logiciel Pac-Man sur un téléphone Android dispose d’un processeur 600 000 fois plus puissant (260 GFLops), et un logiciel Pac-Man typique sous Android pèse 20 MégaOctets, soit 1250 fois plus que le Pac-Man Original.

1981 – Pac-Man sur la tout première console de jeu Atari2600

Le jeu est porté sur l’Atari2600, l’une des toutes premières consoles de jeu largement diffusée. Au prix de $199 (environ 750€ de nos jours) plus de 30 Millons de consoles ont été vendues. La version Atari2600 de Pac-Man était de piètre qualité et l’expérience des joueurs moins bonne que sur le jeu d’arcade. Avec 7 millions de cartouches vendues, Pac-Man a toutefois été le jeu le plus diffusé sur Atari2600

L’Atari2600 utilisait un microprocesseur devenu par la suite mythique : le 6502 de Motorola. Récemment, une équipe de chercheurs en neurobiologie a pris le 6502 comme modèle d’étude. Leur but est de déterminer comment les techniques utilisées aujourd’hui pour comprendre « de l’extérieur » le fonctionnement du cerveau fonctionnent si on les utilise pour comprendre le comportement du 6502 exécutant des jeux videos.

1984 – Pac-Man à la poursuite de Super Mario sur NES

Pac-Man est porté sur la NES (Nintendo Entertainment System). Tirée par le Titre Super Mario Bros, la NEs va se vendre à plus de 60 millions d’exemplaires dans le monde et Nintendo va dominer pendant une décennie le marché des consoles. Lancée en 1987 en France, la NES sera vendue à plus 1,8 million d’exemplaires entre 1987 et 1993, avec un pic 697 000 consoles vendues en 1991.

Un des problèmes qui avait affaibli l’expérience utilisateur de l’Atari2600 (et aussi les revenus d’Atari), avait été le rapide développement de jeux pirates de faible qualité, non autorisés par Atari. Pour éviter ce problème, le hardware de la NES embarquait pour la première fois un dispositif anti-pirate, nommé le « Lockout chip », qui rendait impossible l’utilisation de cassettes pirate. Evidemment, des hackeurs ont mis au point rapidement un dispositif anti dispositif anti-pirate !

1990 – Une version Noir et Blanc pour la Game Boy

Le jeu est porté sur la Game Boy, sortie en France en 1990. La Game Boy sera vendue à 1,4 million d’exemplaires la première année en France, un record à l’époque.

La première génération de Game Boy disposant seulement d’un écran noir et blanc, les différents fantômes ne sont plus identifiables facilement. Les fans de Pac-Man regrettent alros que le jeux soit en noir sur fond blanc en non en blanc sur fond noir, comme le Pac-Man Original. Avec l’avènement de la Game Boy Color, les fantômes redeviennent colorés. Mais ils sont malheureusement tous de la même couleur !

2008 – Pac-Man arrive sur iPhone

Namco porte Pac-Man sur l’iPhone (iPhone 2 G et 3G alors disponibles). Le jeu est strictement identique au jeu d’origine, mais Namco propose 3 façons de piloter le Pac-Man.

un joystick virtuel qui émule le joystick de la machine d’arcade
accéléromètres : le Pac-Man est contrôlé en penchant l’iPhone
le contrôle par le doigt de l’utilisateur qui désigne sur l’écran l’endroit où il souhaite envoyer son Pac-Man

Les joueurs se rendront compte très rapidement que la 3ème méthode est, de loin, la plus efficace. A l’époque du balbutiement des interfaces tactiles, ce retour des utilisateurs allait guider le design de nombreux autres jeux de parcours.

2011 – un Pac-Man géant débarque en HTML5 sur navigateur

Pour célébrer le 30e anniversaire du Pac-man original, des équipes australienne ont conçu avec Namco-Bandai the world’s biggest Pac-Man, un Pac-Man qui fait jouer plusieurs joueurs ensemble dans une série de labyrinthes créés par l’utilisateur, personnalisables et imbriqués.

D’un point de vue technique, le jeu se joue sur un navigateur, et a été développé grâce aux nouvelles fonctions HTML5 qui était en train à l’époque d’être intégré dans les principaux navigateurs Internet.

Au tout début des approches de crowd-sourcing à grande échelle, les initiateurs du projet se sont très vite rendus compte qu’il était nécessaire de mettre en place des modérateurs pour que les labyrinthes créés ne contenaient pas de contenus offensants!

Une semaine après son lancement, il comptait 13 500 labyrinthes conçus par les utilisateurs et près de 300 millions de points mangés. Le site est toujours actif, il contient aujourd’hui 600 000 grilles interconectées, les internautes ont collectivement dévoré 1,985,431,181,624,258,560 points (2 exa points, soit 2 10 ¹⁸ points). Un petit calcul rapide indique que, pour le terminer, il faudrait jouer 70 ans jour et nuit… sans se faire rattraper par un fantôme plus de 3 fois!

2020 – Une version 3D

Pac-Man World 2, un jeu dérivé de Pac-Man, sort sur la Xbox. Pour la première fois, le personnage de Pac-Man passe en 3D. Chacun des 4 fantômes devient un dangereux personnage 3D : Blinky prend la forme d’une grenouille, Clyde celle d’une machine, Pinky souffle un vent glacé et Inky menace Pac-Man avec de dangereuses scies circulaire

Pac-Man, une magnifique illustration des progrès de l’IA

2017 : IA à base de sysème multi-agent

En 2017, une équipe de Microsoft décide d’utiliser Ms. Pac-Man pour développer une Intelligence Artificielle capable de jouer à Ms. Pac-Man, une évolution du jeu d’Arcade original. Il a la particularité d’introduire un comportement totalement aléatoire des fantômes dans des niveaux remaniés, ce qui rend le jeu encore plus difficile et imprévisible, pour les joueurs … mais aussi pour une IA.

Les chercheurs de Microsoft utilisaient une approche « traditionnelle » de l’IA, sur la base d’une approche multi-agent. En utilisant une méthode d’apprentissage baptisée Hybrid Reward Architecture, ils ont mis en place à 150 agents différents, chacun adapté à une tâche particulière dans le cadre de ce jeu. Certains agents sont spécialisés dans l’évitement de fantômes, d’autres dans le choix des meilleurs chemins à emprunter pour optimiser la collecte de points… Ces agents coopèrent pour s’attaquer au jeu, coordonnés par un agent principal ayant pour rôle de récupérer les informations envoyées par chaque agent et de prendre la décision finale pour déplacer Ms. Pac-Man de manière optimale.

Le record humain sur borne d’Arcade a été réalisé le 6 avril 2006 par l’américain Abdner Ashman, avec 933 580 points. L’IA développée par les chercheurs a atteint le score maximal possible à ce jeu, soit 999 990 points. L’article de blog de Microsoft et la video ci-dessous vous donnent plus de détails sur les techniques mises en oeuvre.

Mais il faut surtout retenir que l’architecture de cette IA a été entièrement développée de manière spécifique pour Pac-Man et reflète de très nombreuses connaissances expertes des joueurs humains. On ne peut donc pas vraiment dire que l’IA a appris seule à jouer. Elle a juste optimisé parfaitement un système d’analyse du jeu qui reproduit les éléments d’une stratégie humaine.

2020 : IA à base de deep learning

40 ans après l’invention du jeu Pac-Man, les chercheurs de NVIDIA ont mis en place GameGAN, un réseau génératif (Generative Adversarial Network, ou réseau antagoniste génératif) composé de deux réseaux de neurones concurrents, un générateur (qui apprend à générer des situations de jeux favorables) et d’un discriminateur (qui apprend à vérifier que ces actions sont conformes aux règles du jeu).

Entrainé à partir de 50 000 parties de Pac-Man, GameGAN apprend, uniquement à partir des images video des parties, deux choses imultanément :

il recrée un moteur de jeu correspondant parfaitement aux règles implicitement présentes dans les videos de parties
il développe une stratégie optimale pour jouer à ce jeu

Le papier scientifique montre qu’une IA basée sur le deep learning peut par ce biais apprendre « comment fonctionne » un environnement complexe sans que les règles du jeu ne lui soit jamais explicitement communiquées. Il reste que, au final, les règles du jeu de Pac-Man sont relativement simples. Rien ne dit que cette approche peu attaquer un monde plus proche du nôtre où les « règles du jeu » sont à la fois multiples, beaucoup plus complexes, et évoluent en fonction du temps et des situations.

Pac-Man et l’intelligence biologique ?

En 2016 des biologistes norvégiens réalisent un Pac-Man d’1mm² destiné à des organismes vivants. Loin d’une « expérience gadget », ce travail visait à comprendre l’adaptation de micro-organismes à leur environnement.

Pac-Man est donc aussi devenu un labyrinthe microscopique au sein duquel des organismes unicellulaires devaient apprendre à échapper à leurs prédateurs pluricellulaires. Les chercheurs ont ainsi étudié deux organismes unicellulaires (les ciliés et les euglènes) qui devaient échapper à des rotifères, jouant le rôle des fantômes du jeu vidéo. Selon les résultats de l’étude, les rotifères ont parfaitement su s’adapter à leur nouvel habitat. Si lors des premiers jours leurs déplacements ont été lents et peu assurés, ils ont rapidement su augmenter leur vitesse pour traquer avec davantage d’efficacité leurs proies.

J’adore les images issues de leur expérimentation (voir la vidéo ci-dessous).