Les chercheurs conçoivent plusieurs stratégies pour qu’un agent d’intelligence artificielle (IA) puisse résoudre un puzzle stochastique comme le Démineur.
Pendant des décennies, les efforts de résolution de jeux se sont limités à la résolution de jeux à deux joueurs (c’est-à-dire des jeux de plateau comme les dames, des jeux de type échecs, etc.), dont l’issue peut être prédite correctement et efficacement en appliquant une technique de recherche d’intelligence artificielle (IA) et en collectant une quantité massive de statistiques de jeu. Cependant, une telle méthode et une telle technique ne peuvent pas être appliquées directement au domaine de la résolution de puzzles, étant donné que les puzzles se jouent généralement seuls (à un seul joueur) et présentent des caractéristiques uniques (comme des informations stochastiques ou cachées). Une question s’est donc posée : comment la technique d’IA peut-elle conserver ses performances pour la résolution de jeux à deux joueurs, mais en l’appliquant à un puzzle à agent unique ?
Pendant des années, les puzzles et les jeux ont été considérés comme interchangeables ou comme une partie de l’autre. En réalité, ce n’est pas toujours le cas. Dans le monde réel, le terme “jeu” désigne une chose à laquelle nous sommes confrontés tous les jours : faire face à l’inconnu. Par exemple, l’incertitude de prendre la bonne décision (par exemple, se marier) ou la mauvaise (par exemple, quitter un emploi) ou de ne pas en prendre du tout (par exemple, regretter les “et si”). En revanche, le terme “puzzle” désigne quelque chose dont on connaissait l’existence, voire quelque chose de caché qui n’a pas encore été découvert. Un cas connu, par exemple, serait la découverte d’un matériau “merveilleux” tel que graphène et ses nombreux potentiels qui doivent encore être commercialisés et largement utilisés. Mais encore une fois, comment et quelle est la frontière entre “puzzle” et “jeu” dans un contexte de résolution de puzzle ?
Au Japan Advanced Institute of Science and Technology (JAIST), Japon, le professeur Hiroyuki Iida et ses collègues ont tenté de répondre à ces deux questions dans leur dernière étude publiée dans le journal Knowledge-based Systems. L’étude de recherche se concentre sur deux contributions importantes : (1) la définition de la solvabilité d’un puzzle dans un contexte de jeu à agent unique via Minesweeper et (2) proposer un nouvel agent d’intelligence artificielle (IA) utilisant la composition unifiée de quatre stratégies, appelé solveur PAFG. En tirant parti des informations connues et des informations inconnues des Minesweeper le solveur proposé a obtenu de meilleures performances dans la résolution du puzzle, comparables à celles des études de pointe.
La figure montre des stratégies d’IA qui utilisent des stratégies basées sur la connaissance pour traiter des informations inconnues et qui adoptent des stratégies basées sur les données pour utiliser les informations connues du puzzle Minesweeper. Les résultats obtenus établissent la condition limite de la solvabilité d’un puzzle stochastique à un joueur, qui est canonique pour de nombreux problèmes du monde réel. Crédit : Hiroyuki Iida du JAIST
Les chercheurs ont adopté un agent d’IA composé de deux stratégies basées sur la connaissance et de deux stratégies basées sur les données afin d’utiliser au mieux les informations connues et inconnues de la décision actuelle pour estimer au mieux la décision suivante à prendre. Par conséquent, la frontière entre le paradigme de la résolution d’énigmes et celui du jeu peut être établie pour l’énigme stochastique à agent unique, comme le puzzle Minesweeper.
Une telle condition joue un rôle particulièrement important dans les problèmes du monde réel où la frontière entre le connu et l’inconnu est généralement floue et très difficile à identifier. Comme le fait remarquer le professeur Iida : “Avec la capacité des agents d’IA à améliorer les performances de résolution des énigmes, la limite de la solvabilité devient apparente. Cette situation a permis de définir clairement les conditions du “puzzle” et du “jeu”, que l’on retrouve généralement dans de nombreuses situations de la vie réelle, comme la détermination d’un investissement à fort enjeu, l’évaluation du niveau de risque d’une décision importante, etc. En substance, nous vivons tous dans notre Minesweeper monde, essayant de deviner notre chemin vers l’avant tout en évitant la “bombe” dans notre vie.
De nombreuses incertitudes existaient avec l’avancement à un rythme effréné de la technologie existante et le nouveau paradigme de l’informatique disponible (c’est-à-dire l’IdO, les services basés sur le cloud, l’informatique périphérique, l’informatique neuromorphique, etc.) Cette condition pourrait être vraie pour les personnes (c’est-à-dire l’affordance technologique), la communauté (c’est-à-dire l’acceptation de la technologie), la société (c’est-à-dire la culture et la norme), et même aux niveaux nationaux (c’est-à-dire les changements de politiques et de règles). L’activité humaine quotidienne implique de nombreuses conditions de “jeu” et de “casse-tête”. Cependant, en cartographiant le paradigme de la solvabilité à l’échelle, les conditions limites entre le connu et l’inconnupeut être établi, en minimisant le risque de l’inconnu et en maximisant le bénéfice du connu”, explique Mme Chang Liu, l’auteur principal de l’étude. “Un tel exploit est réalisé en faisant culminer les techniques axées sur la connaissance, la technologie de l’IA et l’incertitude mesurable (comme le taux de gain, le taux de réussite, le taux de progression, etc.) tout en gardant le puzzle amusant et stimulant.”
Référence : “Un solveur de puzzle stochastique à agent unique : A case study with Minesweeper” par Chang Liu, Shunqi Huang, Gao Naying, Mohd Nor Akmal Khalid et Hiroyuki Iida, 28 mars 2022, Systèmes basés sur la connaissance.
DOI: 10.1016/j.knosys.2022.108630
À propos du Japan Advanced Institute of Science and Technology, Japon
Fondé en 1990 dans la préfecture d’Ishikawa, le Japan Advanced Institute of Science and Technology (JAIST) a été la première école supérieure nationale indépendante du Japon. Après 30 ans de progrès constants, le JAIST est devenu l’une des meilleures universités du Japon. Le JAIST compte de nombreux campus satellites et s’efforce de former des dirigeants compétents grâce à un système d’éducation de pointe où la diversité est essentielle ; environ 40 % de ses anciens étudiants sont des étudiants internationaux. L’université a un style unique d’enseignement supérieur, basé sur un programme d’études soigneusement conçu et axé sur le travail, afin de garantir que ses étudiants disposent d’une base solide pour mener des recherches de pointe. Le JAIST travaille également en étroite collaboration avec les communautés locales et étrangères en encourageant la recherche collaborative industrie-université.
A propos de Mme Chang Liu de l’Institut japonais des sciences et technologies avancées, Japon.
Mme Chang Liu est étudiante en doctorat à l’École des sciences et technologies avancées (JAIST), à Nomi, au Japon. Ses recherches se concentrent sur la recherche d’informations d’appel sur l’évolution des jeux de réflexion en fonction de la mécanique du jeu et de l’expérience du joueur. Elle est supervisée par le professeur Hiroyuki Iida dans le laboratoire de technologie du divertissement. Elle travaille sur l’analyse des facteurs significatifs dans l’évolution des jeux de puzzle anciens vers les jeux modernes, et sur l’analyse des informations pendant le processus de résolution des puzzles et des jeux, afin de trouver une ligne entre les puzzles et les jeux.
A propos du professeur Hiroyuki Iida de l’Institut japonais des sciences et technologies avancées, Japon.
Hiroyuki Iida a obtenu son doctorat en 1994 sur les théories heuristiques de la recherche par arbre de jeu à l’Université d’agriculture et de technologie de Tokyo, au Japon. Depuis 2005, il est professeur au JAIST, où il est également administrateur et vice-président des affaires éducatives et étudiantes. Il est à la tête du laboratoire Iida et a publié plus de 300 articles, présentations et livres. Ses recherches portent sur l’intelligence artificielle, l’informatique des jeux, la théorie des jeux, la modélisation mathématique, les algorithmes de recherche, la théorie du raffinement des jeux, la recherche par arbre de jeux et la science du divertissement.
Informations sur le financement
Cette étude a été financée par une subvention de la Société japonaise pour la promotion de la science dans le cadre du Grant-in-Aid for Challenging Exploratory Research (numéro de subvention 19K22893).
