General Game Player (GGP) [1] is a paradigm in Artificial Intelligence focused on developing algorithms and techniques to play more than one game successfully, possibly with limited prior knowledge of the game in hand. By contrast, for several games, such as chess, computers are programmed to play them using specially designed algorithm, which cannot be easily transferred from one game to another one.
In this context, the Game Description Language (GDL) [2,3] has been developed to represent games in GGP. This logic-based language allows to describe them from a game-theoretic perspective, specifying initial states, winning positions, and available moves. The main aim of this project is to extend GDL with operators for individual and joint strategies in the spirit of Alternating-time temporal logic (ATL) and Strategy Logic (SL), thus allowing for the expression of game-theoretical notions and solution concepts.
Your contribution
GDL supports compact representation by using a conceptualization of game states as databases and by relying on logic to define the notions of legal move, state update, etc. You will explore extensions of GDL by adding the strategic operator <<A>> from ATL so as to express notions such as "there exists a collective strategy for the coalition A to achieve...", thus enriching the power of GDL.
More precisely, the proposed project is structured as follows:
1. Preliminary study of the state of art on GGP and GDL.
2. Definition of an extension of GDL over ATL.
3. Investigation of the expressiveness of GDL+ATL over GDL.
4. Analysis of the benefit of GDL+ATL w.r.t. GDL in some specific games. In particular, show how a general game player improves its play technique by using GDL+ATL instead of GDL.
5. Possibly implementation of this new framework into an existing model checking tool for ATL.
[1] M. Genesereth, M. Thielscher; General Game Playing. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers 2014
[2] M. Thielscher; A General Game Description Language for Incomplete Information Games. AAAI 2010
[3] M. Genesereth, N. Love, B. Pell; General game playing: Overview of the AAAI competition. AI Magazine 2005
Keywords: Formal Methods, General Game Playing, Game Description Language, Logics for Strategies.
Arrangements and candidate's profile
Institution: Laboratoire IBISC, Université d'Evry, Evry
Duration: 6 months
Salary : ~600€/month
Requirements: 1st year master, or 4th/5th year in Engineering School. An interest in formal methods is essential.
Contact: francesco.belardinelli@univ-evry.fr, vadim.malvone@univ-evry.fr