Existe-t-il un jeu simple avec une complexité asymétrique?

Considérez les jeux combinatoires à deux joueurs à informations complètes qui se terminent après un nombre polynomial de mouvements, et d'une manière alternée, les joueurs choisissent parmi un nombre fini de mouvements autorisés. La question habituelle est de savoir à quel point il est difficile de distinguer le vainqueur d'une position donnée. Un autre serait la difficulté de choisir un coup gagnant dans une position gagnante. (Ici, j'appelle un coup gagnant, si la position reste gagnante après l'avoir jouée.) Pour différencier, j'appellerai l'ancienne COMPLEXITÉ DE POSITION et la dernière COMPLEXITÉ DE DÉPLACEMENT.

Il est facile de voir que si la MOVE-COMPLEXITY est en $P$ ou , alors la POSITION-COMPLEXITY l'est aussi - nous pouvons calculer les mouvements optimaux et vérifier qui gagne à la fin. (Je n'ai pas vraiment réfléchi à ce qui se passe si la MOVE-COMPLEXITY est dans , probablement la POSITION-COMPLEXITY est dans quelque chose comme .) Cependant, il y a des exemples factices lorsque la MOVE-COMPLEXITY est triviale et la POSITION -COMPLEXITY est arbitrairement difficile - comme le jeu (pas très intéressant) de vérification de la sortie d'un algorithme, les joueurs faisant les prochaines étapes, ne pouvant effectuer qu'un seul mouvement. J'ai fait une petite digression, ma principale question est la suivante. $PSPACE$ $NP$ $P^{NP}$

Existe-t-il un jeu naturel, où la MOVE-COMPLEXITÉ des deux joueurs est différente?

Par exemple, le jeu où le premier joueur choisit les valeurs des variables d'un CNF (qui pourrait ne pas avoir de solution), tandis que le deuxième joueur essaie de résoudre un puzzle SOKO-BAN (qui pourrait ne pas avoir de solution), est un tel exemple.

cc.complexity-theory np board-games pspace domotorp
la source

J'aime vraiment cette question.

Tayfun Pay du

Je ne sais pas si le jeu QBF satisfait votre condition, un joueur est un joueur existentiel, un autre est un joueur universel. Eh bien, de nombreux jeux sont sous une forme similaire. Je pense que s'il n'y a pas de dépendance entre les joueurs, alors le jeu n'est pas un jeu à deux joueurs mais s'il y a une dépendance entre eux, alors (vaguement parlant) il y a des interprétations qui sont similaires au style QBF.

Saeed

C'est une remarque secondaire, mais la plupart des jeux naturels (dans le sens où ils se jouent dans le monde réel comme les échecs, allez, ...) ne se terminent pas après un nombre polynomial de coups, mais plutôt exponentiels (dans le pire des cas). Avez-vous une raison particulière d'ajouter cette contrainte, en plus d'obtenir une relation polynomiale entre MOVE-COMPLEXITY et POSITION-COMPLEXITY?

Denis

Peut-être qu'une famille d'exemples peut être créée en relaxant les conditions gagnantes de l'un des deux joueurs: par exemple un match d'échecs dans lequel les blancs gagnent avec un échec et les noirs gagnent avec un échec ou capturent la reine blanche. Un autre exemple peut être GG avec des nœuds de couleur rouge-bleu, et l'un des deux joueurs peut gagner non seulement de manière standard, mais aussi en collectant une certaine quantité de nœuds rouges. Je penserai davantage aux formalisations possibles d'exemples similaires.

Marzio De Biasi

Si le jeu n'a pas de nul (et un nombre raisonnablement limité de coups possibles par tour), le fait suivant implique-t-il que la réponse est "non"? Un coup est gagnant si et seulement si aucune des réponses de l'adversaire ne gagne.

usul

Réponses:

Un jeu assez naturel est peut-être le suivant:

Le joueur 1 est placé au milieu d'un labyrinthe et doit atteindre la sortie pour gagner.

Le joueur 2 est dans le même labyrinthe et doit collecter un ensemble de "composants" pour construire un contrôleur radio qui lui permet de fermer la sortie (et de gagner).

Décider du prochain mouvement à partir d'une position gagnante est facile pour le joueur 1: il suffit de suivre le chemin le plus court depuis sa position actuelle et la sortie; mais peut être très difficile pour le joueur 2.
En effet, si les composants (restants) du contrôleur radio sont sur les sommets d'un graphique en grille de $n$ $n$

Pour rendre le jeu plus "interactif", nous pouvons également ajouter des actions supplémentaires au joueur 2 qui ne peuvent que provoquer un ralentissement polynomial dans le calcul du prochain mouvement du joueur 1; par exemple lui permettant de bloquer un nombre fixe de couloirs du labyrinthe.

Marzio De Biasi
la source

$C$ , alors MOVE-COMPLEXITY l'est aussi, car il suffit de tester le nombre fini de mouvements disponibles. (J'ai supposé par "fini" que vous vouliez dire "constant", si c'est arbitraire, la complexité pourrait changer).

Ensuite, il suffit de regarder certains jeux naturels où la POSITION-COMPLEXITÉ est asymétrique. Nous aurons toujours besoin certaine asymétrie entre les joueurs pour créer de telles situations, mais j'espère que ce sera aussi naturel que possible.

$\cap$

$P_1$ $P_2$ $p(n)$ $i$ $P_i$

Denis
la source

Je dirais qu'il est peu probable que «fini» signifie «constant» ici.

Kyle

En fait, dans les jeux soi-disant Picker-Chooser ou Chooser-Picker, il est facile de construire des exemples pour lesquels la meilleure stratégie d'un joueur est une stratégie d'appariement simple, tandis que l'autre doit résoudre un 3-SAT sur n'importe quel CNF spécifié auparavant, c'est un problème NP-complet.

Disons qu'un jeu Picker-Chooser est un jeu asymétrique sur un hypergraphe H = (V, E): Picker sélectionne deux éléments non sélectionnés de V, puis Chooser prend l'un de ces éléments et renvoie l'autre à Picker. Sélecteur gagne ssi il obtient tous les éléments d'un A de E. Maintenant, étant donné une formule CNF F de 3-SAT, V est l'ensemble des littéraux et E réalise un gadget. Dans l'ensemble, Picker doit toujours proposer x_i et x_i nier à toutes les étapes (sinon il perd immédiatement), tandis que la sélection Sélecteur est une entrée arbitraire 0-1 pour tout x_i, et il gagne en satisfaisant F.

Voir les détails dans: A. Csernenszky, R. Martin et A. Pluhár, Sur la complexité des jeux de position sélecteur-sélecteur. Entiers 11 (2011).

ou sur: http://www.inf.u-szeged.hu/~pluhar/complexity_2011.pdf

Andras Pluhar
la source