Décomposition des jeux pour le General Game Playing

Abstract

Dans cet article nous présentons une approche pour la décomposition des jeux généraux décrits en Game Description Language (GDL). Dans le domaine du General Game Playing (GGP), les joueurs peuvent significativement diminuer le coût de l’exploration d’un jeu si ils disposent d’une version décomposée de celui-ci. Les travaux existants sur la décomposition des jeux s’appuient sur la structure syntaxique des règles, sur des habitudes d’écriture du GDL ou sur le coûteux calcul de la forme normale disjonctive des règles. Nous proposons une méthode plus générale pour décomposer les jeux solitaires ou multi-joueurs, fondée sur la collecte d’informations durant des simulations (playouts). Notre méthode est capable de traiter les différents types de jeux composés et de prendre en charge certains cas difficiles comme les jeux à actions composées et les jeux en série. Nous avons testé notre approche sur un panel de 597 jeux GGP. Pour 70% des jeux, la décomposition nécessite moins d’une minute en faisant 5k playouts. Nous montrons de 87% d’entre eux peuvent être correctement décomposés après seulement 1k playouts.

Publication
12èmes Journées de l’Intelligence Artificielle Fondamentale, JIAF 2018, Amiens, France, 13-15 June, 2018