Un programme pourrait-il déterminer si un autre programme joue aux échecs ?

Question

Je m'interroge sur le problème suivant. Je n'attends évidemment aucune solution pratique, mais j'apprécierais que les développeurs me fassent part de leurs réflexions à ce sujet :

Serait-il théoriquement possible d'avoir un programme qui ouvre d'autres programmes (pour les besoins de l'argumentation, disons qu'il ouvre des fichiers .exe), et détermine si oui ou non un exécutable particulier, lorsqu'il est exécuté (avec une entrée et un état machine fixes), joue une partie d'échecs (parmi toutes les autres tâches qu'il peut effectuer).

Par "jouer aux échecs", j'entends avoir une représentation quelconque d'un échiquier et de pièces, en appliquant les coups suivants pour les noirs et les blancs provenant d'un moteur d'échecs intégré.

Un tel "programme de détection des échecs" théorique peut contenir une machine virtuelle ou un émulateur de PC ou autre pour simuler réellement l'exécutable analysé si nécessaire. Nous pouvons supposer qu'il fonctionne sur un ordinateur arbitrairement rapide avec ditto ram.

---

(Edit) En ce qui concerne le problème de l'arrêt, je peux le résoudre comme ceci :

Chargez le programme dans une machine virtuelle, qui dispose de N bits (disque dur, espace mémoire et registres du CPU au total). Cette machine virtuelle peut prendre au maximum 2^N états différents.

Exécutez le programme dans la VM étape par étape. Après chaque étape, vérifiez s'il s'est arrêté. Si oui : problème résolu (résultat : oui, il s'arrête). Si non : prendre l'état actuel de la machine virtuelle, et voir si cet état existe dans une liste d'états que nous avons déjà rencontrés auparavant. Si oui : problème résolu (résultat : non, elle fonctionnera éternellement). Si non : ajouter cet état à la liste et continuer.

Comme il y a au plus 2^N états différents qui peuvent se produire, cet algorithme déterminera si le programme s'arrête ou non avec certitude en un temps fini.

---

(Edit2) Il semble y avoir une certaine ambiguïté sur l'(in)finitude de l'exécutable scanné ou de la machine (virtuelle) sur laquelle il tourne. Disons que les exécutables à analyser peuvent faire au maximum 1 Go (ce qui devrait être suffisant puisque la plupart des programmes d'échecs sont considérablement plus petits) et qu'ils sont censés fonctionner sur un PC (ou une VM) avec 10 Go de RAM.

Notre programme théorique de détection des échecs peut utiliser une quantité arbitraire de mémoire vive.

Answer 1

Non, il n'existe pas d'algorithme capable de détecter si un exécutable joue aux échecs.

La preuve de ceci repose sur le fait que le problème suivant (appelé le problème de l'arrêt ) ne peut être résolu par aucun algorithme :

Étant donné un programme informatique, ce programme finit-il par se terminer ?

Nous pouvons montrer que s'il existait un programme informatique capable de déterminer si un autre programme joue ou non à une partie d'échecs, nous pourrions résoudre le problème de l'arrêt. Pour ce faire, nous écririons un programme informatique qui ferait ce qui suit :

1. Prendre en entrée un autre programme informatique P.
2. Exécuter le programme P.
3. Si le programme P se termine, jouez une partie d'échecs.

Ce programme a le comportement intéressant suivant : il joue une partie d'échecs si et seulement si le programme P se termine. En d'autres termes, si nous pouvions détecter si ce programme peut jouer aux échecs, nous détecterions si le programme P se termine ou non. Cependant, nous savons que cela est impossible à faire, donc il ne doit pas y avoir de programme qui détecte si un programme informatique joue aux échecs.

Cette approche générale est appelée réduction du problème de l'arrêt et peut être utilisé pour montrer qu'un grand nombre de problèmes différents sont probablement insolubles.

J'espère que cela vous aidera, et désolé pour la réponse négative !

Answer 2

En ce qui concerne votre question éditée : oui, si nous limitons la taille de la mémoire afin de n'avoir qu'un nombre fini de programmes possibles, nous pourrions théoriquement énumérer tous les programmes possibles et les diviser manuellement en "jouant aux échecs" et "ne jouant pas aux échecs" selon n'importe quel ensemble de critères.

Dans ce cas, nous n'aurions plus de machine de Turing, et le problème de l'arrêt ne s'appliquerait pas. A la place, nous aurions une machine à états finis (et oui, cela signifie que dans le monde réel, tous les ordinateurs sont en fait des approximations à états finis d'une machine de Turing).

Cependant, vous avez ajouté cette limitation parce que vous vouliez être "pratique, et non théorique", alors voici un autre aspect pratique pour vous : pour énumérer tous les programmes 256-bit (avec un milliard de PC, chacun d'entre eux énumérant un milliard de programmes par seconde) prendrait beaucoup plus de temps que l'âge de l'univers pour se réaliser. Vous pouvez donc à peine imaginer le temps qu'il faudrait pour énumérer tous les programmes de moins de 1 Go (~1 000 000 000 bits).

Pour cette raison, il est en fait plus pratique de modéliser les ordinateurs réels comme des machines de Turing que comme des machines à états finis ; et sous ce modèle, comme @templatetypedef l'a prouvé, c'est impossible.

Answer 3

Non. C'est équivalent au problème du halting.

Answer 4

Qu'est-ce que cela signifie qu'un programme joue aux échecs ? Je ne crois pas qu'il existe une définition mathématique précise du problème qui ne pourrait pas être manipulée et qui ne serait pas trivialement équivalente à un problème impossible à traiter.

Par exemple, si vous demandez "Existe-t-il un codage des coups sous lequel ce programme joue aux échecs ?", un interprète Python nu joue aux échecs - sous le codage qui stipule que vous devez saisir :

• un programme Python pour jouer aux échecs plus le premier coup de l'adversaire si vous voulez qu'il joue les noirs
• un programme Python de jeu d'échecs si vous voulez qu'il joue les blancs.

Si vous réparez l'encodage, alors le problème devient ennuyeux. Les parties d'échecs sont finies (par la règle des 50 coups), donc la seule question difficile est "est-ce que ce programme s'accroche entre les coups sur l'un des jeux d'échecs finis". S'il ne se bloque pas et respecte toujours l'encodage (et effectue des déplacements valides, tout ceci est trivial à vérifier) alors il joue aux échecs. Bien sûr, il est impossible de vérifier s'il se bloque. L'énumération de toutes les parties d'échecs est traitable mais bien sûr aussi totalement impossible compte tenu des considérations pratiques.