Modèles de calcul, TD numéro 8

Natacha Portier mardi 21 mars 2000

Question 1

Nous étudions le jeu de Go.

Définitions et règles du jeu

Le plateau est une grille de 19×19 points. Un point est soit inoccupé, soit occupé par une pierre noire, soit occupé par une pierre blanche. Chaque point a quatre voisins : ceux situés directement au-dessus, au-dessous, à droite et à gauche. Les points en diagonale ne sont pas voisins. Héloïse joue en posant ou non une pierre blanche et Brian en posant ou non une pierre noire sur la grille.

Grossièrement, le but du jeu est de former de grands groupes de pierres de sa couleur qui soient en sécurité et de capturer le plus possible de pierres de la couleur de l’adversaire.

Les définitions et règles suivantes sont symétriques pour les noirs et les blancs.

Un groupe noir est un ensemble maximal de pierres noires connexe sur la grille. Un groupe noir est encerclé si aucune pierre du groupe n’a de voisin inoccupé. Sitôt qu’un groupe noir devient encerclé, en général parcequ’une pierre blanche a été posée, il est capturé et enlevé du plateau.

Héloïse n’a pas le droit de poser une pierre blanche qui provoque l’encerclement d’un groupe blanc sans provoquer l’encerclement d’un groupe noir. Par contre si un groupe noir et un groupe blanc se retrouvent simultanément encerclés par le dépôt d’une pierre blanche, alors le groupe noir est capturé.

Nous altérons maintenant les véritables règles du jeu. La grille est constituée de n × n points. Une partie dure exactement n^{2} coups. Le gagnant est celui dont il reste le plus de pierres sur la grille. En cas d’égalité des nombres de pierres restantes, les blancs sont déclarés vainqueurs.

GO est l’ensemble des couples formés d’une configuration du plateau et d’un entier k < n^{2} tels que les joueurs se retrouvent dans cette configuration après k coups, c’est à Héloïse de jouer et elle a une stratégie gagnante.

Nous allons montrer que ce jeu est ESPACE-P-complet.

Question 1,1

Montrer que GO est ESPACE-P.

Nous montrons maintenant que GO est ESPACE-P-complet en réduisant GEO à GO.

Question 1,2

Montrer que pour GEO, il suffit de considérer les cas où le graphe est obtenu par réduction de QBF.

Question 1,3

Montrer qu’il suffit également de considérer les cas où tout sommet du graphe est soit de degré entrant un et de degré sortant au plus deux, soit de degré sortant un et de degré entrant au plus deux.

Question 1,4

Montrer qu’il suffit de considérer des graphes planaires.

Question 1,5

Donner les différents types de sommets qui finalement peuvent être présents dans le graphe.

Question 1,6

Le graphe est simulé à l’aide d’un plateau sur lequel se trouve un large rectangle blanc entouré de noir, à l’exception d’un fil blanc bordé de noir qui s’en échappe. Il reste p coups à jouer. Montrer qu’on peut prendre la taille de la zone blanche suffisamment grande de manière à ce que l’issue de la partie ne dépende que du fait que ce groupe soit ou non capturé. Montrer comment le graphe peut être simulé.

Question 2

Les machines considérées travaille sur un demi-ruban. Définissons le problème ACCEP T E − SUR − P LACE comme l’ensemble des couples (machine de Turing M, mot x) tels que M accepte l’entrée x sans quitter les |x| + 1 premiers symboles de son ruban. Montrer que ce problème est ESPACE-P-complet.

Question 3 Le problème DIV ERGE − SUR − P LACE est l’ensemble des machines de Turing M qui ont un calcul divergent qui utilise seulement les |M| premiers symboles du ruban (|M| est la taille de la description de la machine).Montrer que ce problème est ESPACE-P, puis qu’il est ESPACE-P-complet en utilisant une réduction du problème précédent.

Question 4,1

Un processus est un graphe orienté G = (S, A) dont les sommets sont appelés états et les arcs transitions. Un système de processus de communications est un ensemble de processus {G_{1} = (S_{1}, A_{1}), ..., G_{n} = (S_{n}, A_{n})} où les S_{i} sont disjoints, ainsi qu’un ensemble P = {{a_{1}, a′_{1}}, ..., {a_{m}, a′_{m}}} de paires de transitions, appelées paires communicantes. Pour tout i, il existe j et k différents tels que a_{i} ∈ A_{j} et a′_{i} ∈ A_{k}.

L’ensemble des états du système est S = S_{1} ×...×S_{n}. La relation de transition T entre deux états est définie par : (b_{1}, ..., b_{n})T (c_{1}, ..., c_{n}) si et seulement si ces uples sont égaux sauf en deux indices i et j différents tels que {(b_{i}, c_{i}), (b_{j}, c_{j})} soit un élément de P.

Un état est bloquant s’il ne peux plus évoluer.

Donner un exemple non trivial.

Le problème du BLOCAGE est l’ensemble des couples (système de processus de communications, état initial i) tels que i puisse évoluer vers un état bloquant.

Question 4,2

Montrer que ce problème est ESPACE-P.

Question 4,3

Montrer que ce problème est ESPACE-P-complet en utilisant une réduction de ACCEP T E − SUR − P LACE.