Recherche de son dans les jeux à information imparfaite

Résumé

La recherche a joué un rôle fondamental dans la recherche sur les jeux informatiques depuis le tout début. Et si la recherche en ligne a été couramment utilisée dans les jeux à information parfaite tels que les échecs et le go, les méthodes de recherche en ligne pour les jeux à information imparfaite n'ont été introduites que relativement récemment. Cet article aborde la question de savoir ce qu'est un bon algorithme en ligne dans un cadre d'information imparfaite de jeux à somme nulle à deux joueurs. Nous soutenons que les définitions de la stratégie fixe de l'exploitabilité et des équilibres de Nash sont mal adaptées à la mesure de la performance d'un algorithme en ligne dans le pire des cas. Nous formalisons donc l'ϵ-soundness, un concept qui relie la performance dans le pire des cas d'un algorithme en ligne à la performance d'un équilibre ϵ-Nash. Comme la solidité peut être difficile à calculer en général, nous introduisons un cadre de cohérence - une hiérarchie qui relie le comportement d'un algorithme en ligne à un équilibre de Nash. Ces multiples niveaux de cohérence décrivent dans quel sens un algorithme en ligne joue "comme un équilibre de Nash fixe". Ces notions illustrent en outre la différence entre les contextes d'information parfaite et imparfaite, car les mêmes garanties de cohérence ont des performances en ligne différentes dans les jeux d'information parfaite et imparfaite. Les définitions de la solidité et de la hiérarchie de cohérence fournissent enfin des outils appropriés pour analyser les algorithmes en ligne dans les jeux d'information imparfaite répétés. Nous examinons donc certains des algorithmes en ligne précédents sous un jour nouveau, ce qui nous permet de mieux comprendre leurs garanties de performance dans le pire des cas.