"Aggressive moves in extensive (very long) games", Paolo Turrini, Séminaire de l'IRIT

le 10 mars 2015

12h30
ME303

Paolo Turrini, Marie Curie Fellow à Imperial College London, nous presentera ses travaux "Aggressive moves in extensive (very long) games"

Paolo Turrini est Marie Curie Fellow à Imperial College London. Il donnera ce séminaire entièrement en anglais.

Abstract:

For classical game theory chess is an uninteresting game.
It is a finite extensive game of perfect information that can
(therefore) be solved by backwards induction, and that's the end of it.

For artificial intelligence - as well as for human beings - chess is a very interesting game. This because, in practice, humans (and even supercomputers) are not able to correctly assess game positions and decide the best thing to do. In other words, they make mistakes. 

What I present in this talk is a model of interactive decision-making in chess-like scenarios, where participants are not able to foresee the consequences of their decisions all the way up to the terminal nodes and need to make a judgement call to evaluate intermediate game positions.

On top of that players can form beliefs about what the other players are able to foresee and how they evaluate it, and all higher order variants thereof (beliefs about beliefs of others, beliefs about beliefs about beliefs of others and so forth).

I will introduce and analyse a solution concept to solve these scenarios, which is a generalisation of classical backwards induction, and where players' local decisions are a best response to the (higher-order) beliefs they hold about the other players' foresight and evaluation criteria. In other words, they play rationally against their opponents' believed weaknesses.

I will also show that the potentially unbounded chain of complex beliefs sustaining this solution concept can be computed using a PTIME algorithm.

*This talk builds upon a line of research started with Davide Grossi and being developed further with Chanjuan Liu and Johan van Benthem

**There is no deep game-theoretic background required to understand what I will be saying. It does help though if you played chess, at least once in your life.
Mis à jour le 2 mars 2015