21/05/2007

3 Problèmes EXPTIME

Les problèmes EXPTIME et EXPTIME-complets existent et malgré leur complexité, on cherche à les résoudre en utilisant en particulier les sciences cognitives. Nous nous proposons de faire une brève introduction à quelques exemples connus de tels problèmes.

3.1       EXPTIME dans les jeux

Voici un tableau regroupant des jeux connus ayant au moins une complexité EXPTIME ou qui sont EXPTIME-complets.

3.2       Le jeu de Go

Le Go est un jeu à deux joueurs plaçant alternativement  des pierres blanches et noires sur un plateau de 19x19. L’objectif est de contrôler le plus grand territoire en l’encerclant ou en capturant des pierres adverses. Les joueurs sont classés dans une échelle allant de 9dans à 30kyu en passant par 1kyu.

Bien que le concept soit vraiment simple en apparence, les meilleurs ordinateurs se situent aux alentours de 8kyu, alors que dans les échecs ils rivalisent contre les meilleurs ! Les raisons qui font du jeu de Go un problème EXPTIME-complet sont principalement :
·         La grande dimension du plateau et le nombre de coups possibles (en moyenne 150 à 250).
·         La difficulté augmente au fur et à mesure, contrairement aux échecs où les pièces disparaissent.
·         La stratégie consiste parfois à céder des points pour en prendre plus ultérieurement. Il est souvent intéressant d’enfermer l’ennemi même si on ne prend aucun point contrairement à l’adversaire. Le mur construit peut servir lors d’une prise de territoire au centre par exemple.
·         La règle du ko, qui consiste au fait que le plateau ne peut pas se retrouver dans la même configuration deux tours de suite.
·         Les formes prises par les groupes de pierre sont importantes. Cela relève de la détection de forme et donc d’IA. Cette importance s’explique en particulier pour des raisons telles que l’ « influence » dans le Go.

3.3       Le jeu d’échecs

Le jeu d’échecs est un jeu bien connu de tous. Il s’agit d’un problème EXPTIME-complet. La conception d’un ordinateur de jeu a passionné durant de nombreuses années les chercheurs. Aujourd’hui, l’ordinateur est aussi fort que les meilleurs au monde. Néanmoins, l’augmentation de leur force se justifie plus par l’augmentation de la puissance de calcul que par l’intelligence.

3.4       Les circuits succincts

Un exemple de problème plus théorique est la représentation par circuits succincts. Les circuits succincts sont des machines simples utilisées pour décrire des graphes, comme les matrices d’adjacence, mais avec un espace exponentiellement plus petit. Ils acceptent deux sommets en entrée et trouvent s‘il existe ou non un arc entre eux. On peut alors représenter un graphe avec un ensemble de circuits succincts. Si la résolution d'un problème sur un graphe dans une représentation naturelle, comme une matrice d'adjacence, est P-complète, alors la résolution du même problème dans une représentation sous forme de circuits succincts est EXPTIME-complète