Sciences / Culture

«Magic: The Gathering» est le jeu le plus dur au monde

Temps de lecture : 2 min

Ce jeu de cartes de fantasy a le plus haut quotient de complexité informatique connu.

Des scientifiques ont pour la première fois mesuré la complexité informatique de ce jeu inventé en 1993. | Wayne Low via Unsplash
Des scientifiques ont pour la première fois mesuré la complexité informatique de ce jeu inventé en 1993. | Wayne Low via Unsplash

Longtemps considéré comme le jeu le plus compliqué au monde, le go vient d'être détrôné par un outsider étonnant: Magic: The Gathering.

Ce jeu de cartes, dans lequel des mages jettent des sorts et invoquent des créatures pour vaincre leurs adversaires, comporte plus de 20.000 cartes et compte d'innombrables règles, évolutives au fil de la partie et bien plus complexes que dans d'autres jeux de société, wargames ou jeux de rôle.

Alex Churchill, chercheur indépendant et concepteur de jeux de société à Cambridge en Angleterre, Stella Biderman, mathématicienne à l'université de Géorgie aux États-Unis et Austin Herrick, analyste de données et codeur à l'université de Pennsylvanie, ont pour la première fois mesuré la complexité informatique de ce jeu inventé en 1993.

Bien plus difficile que les échecs

La complexité informatique d'un jeu dépend de nombreux facteurs, comme la prévisibilité du résultat de la partie ou le nombre de coups à jouer.

Pour une partie d'échecs, l'ordinateur doit calculer s'il existe une stratégie gagnante pour le camp des blancs. Le processus consiste à tester toutes les séquences possibles de coups, afin de déterminer s'il peut remporter une victoire.

Pour Magic, les scientifiques ont commencé par traduire les pouvoirs et les propriétés de chaque carte en un ensemble de données pouvant être codées. L'équipe a ensuite joué une partie à deux, analysée par l'ordinateur. Le verdict est sans appel: Magic a le plus grand quotient de complexité informatique connu.

L'ordinateur, pensé pour calculer les pièges, les stratégies à adopter et les probabilités de victoire, a été incapable de déterminer qui remporterait la partie. «C'est la première fois que le résultat d'un test montre qu'il existe un jeu réel [un jeu auquel nous jouons réellement, en opposition aux jeux hypothétiques qu'imaginent parfois les scientifiques] pour lequel il est impossible de déterminer la stratégie qui va gagner. Ce n'est pas calculable», assure Alex Churchill, pour qui le nombre pharaonique de cartes et l'évolution permanente des règles pourraient expliquer la complexité du jeu.

Contrairement à Magic, la plupart des jeux de société ont des limites définies, comme la taille d'un plateau de jeu, ou une durée fixe de partie, ce qui affaiblit considérablement leur degré de difficulté. Leur complexité est alors jugée «triviale», terme qui en mathématiques désigne un problème dont la solution apparaît si évidente que son étude n'a pas d'intérêt.

Selon les scientifiques, seuls quelques jeux sont connus pour avoir une complexité non-triviale, à l'image du Jenga ou de Tetris, dont le retour il y a quelques semaines en version en ligne fait un véritable carton.

Newsletters

Des scientifiques ont créé un steak à partir de cellules humaines

Des scientifiques ont créé un steak à partir de cellules humaines

Ils veulent développer leur projet et que chaque personne puisse créer sa viande à partir de ses propres cellules issues des joues.

Les greffes d'organes de porc pourraient guérir bien des maladies humaines

Les greffes d'organes de porc pourraient guérir bien des maladies humaines

Si les essais cliniques démontraient l'efficacité de la xénogreffe de rein, des dizaines de milliers de vies seraient sauvées chaque année dans le monde.

Quelques techniques pour stocker des informations dans son esprit ou sur son ordi

Quelques techniques pour stocker des informations dans son esprit ou sur son ordi

Les processus de mémorisation par association et par répétition, parmi lesquels figure l'écriture, sont drôlement efficaces. Un logiciel d'indexation peut aussi être d'une grande aide.

Newsletters