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.
Sources : Slate.fr, MIT Technology Review
