[bull-ia] Stage de Master en Méthodes Formelles au Laboratoire

An interniship on Formal Methods for General Game Playing is available
at the Laboratoire IBISC, Université d’Evry.

————————————————————————————————————————————————————————————————————————————————

Background

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 <> 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

———————————————————————
Desinscription: envoyez un message a: bull-ia-unsubscribe@gdria.fr
Pour obtenir de l’aide, ecrivez a: bull-ia-help@gdria.fr