Computational approach to games

Game theory is the formal study of the interactions between rational agents defined by the objectives they seek to achieve and by their strategic options. Strategies can potentially be interdependent (i.e. situations in which the issue for each participant depends not only on the decisions they make, but also on the decisions made by other participants). In this course, we deal more specifically with the computational approach to games, which is based on computer models of game situations (state and graph models, constraint models, etc.) and which aims to automate the search for strategies and analyze their performance (optimality). This course covers the theory and practice of finding optimal and satisfying solutions for multi-player combinatorial games, such as popular games such as Soduku,Sokoban, Othello, Checkers, etc. It includes the following points: he relevant representation of information, intelligent decision-making (i.e. satisfactory, quasi-optimal or optimal), modelling of action sequences, taking into account paiements and uncertainties and capitalizing on experience, aggregation of conflicting preferences, algorithms for routing combinatorial game spaces.

Teaching time performed:

• 15 hours of practical classes about solving puzzles modeled as Constraint Satisfaction Problems and the implementation of Minimax algorithm with alpha-beta pruning to play Connect Four and Pylos.
• 17 hours of project supervision on congestion games in partnership with IRT SystemX. The students have to model the urban congestion on the Plateau du Moulon and study the consequences of the Métro Line 18 for users. In practice, the students use the SUMO tool and write Python scripts to generate supply and demand proposals on a map of the plateau extracted via OpenStreetMap.

Part of the teaching team for all school years between 2019-2020 and 2022-2023.

Instructors: Pascale Le Gall

Student level: First year (~L3/BSc).