Complexité de l'hex avec ordre de tour aléatoire.

J'ai pensé à une variante d' hex , où au lieu que les deux joueurs effectuent des mouvements alternativement, chaque tour un joueur choisi au hasard fait un mouvement. Est-il difficile de déterminer les chances de chaque joueur de gagner? Ce problème est évidemment dans PSPACE, mais ne peut pas être NP-hard, et encore moins PSPACE-complete. Les difficultés viennent de la façon dont le caractère aléatoire rend impossible pour un joueur d'être forcé de faire un choix parmi les options; si ce joueur a de la chance, il obtient suffisamment de coups deux prennent les deux options, et si le joueur n'a pas de chance, l'adversaire obtient assez de coups pour bloquer les deux options. D'un autre côté, je ne peux penser à aucun algorithme polynomial pour cela.

cc.complexity-theory board-games Itai Bar-Natan
la source

Soit S une chaîne binaire de n bits qui représente le joueur qui prend le tour. Dans le pire des cas, vous récupérez le jeu hexadécimal standard si la séquence aléatoire est 010101 ... ou 101010 .... Donc, votre problème est au moins aussi difficile que l'hexagone standard.

Mohammad Al-Turkistany

Il y a deux interprétations possibles de ce jeu. (1) Juste avant chaque tour, les joueurs lancent une pièce pour déterminer qui va ensuite. (2) Au début du jeu, les joueurs lancent une pièce

fois (sur un plateau de taille

) et utilisent cette séquence pour leurs tours. La Turkistanie semble supposer un modèle (2); la question d'origine est ambiguë, mais d'après certains de ses mots, je suppose que Itai pose des questions sur (1), ce qui pourrait être plus facile qu'un hex standard.

n^{2}

$n^2$

n

$n$

Peter Shor

En effet, je veux dire la première interprétation, que la pièce est retournée juste avant le mouvement. De plus, j'ai remarqué une autre ambiguïté dans ma question: la précision avec laquelle je veux connaître la probabilité. Alors que l'impression que j'ai laissée en posant le problème est que je veux connaître la probabilité en précision complète, mais je veux seulement connaître la probabilité en précision logarithmique. Comme la différence entre PP et BPP, la dernière semble plus utile et naturelle.

Itai Bar-Natan

@Itai: Une autre question. Pourquoi prétendez-vous que c'est évidemment dans PSPACE? Il me semble que c'est un jeu arbitré, ce qui voudrait dire que la limite supérieure théorique de la complexité naturelle est EXPTIME. Voir Feige et Kilian, «Making Games Short».

Peter Shor

@tukistany Inutile n'implique PAS trivial!

Jeffε

Réponses:

Vous voudrez peut-être consulter l'article «Random-Turn Hex and Other Selection Games», de Yuval Peres, Oded Schramm, Scott Sheffield et David Wilson. Depuis l'introduction:

"Random-Turn Hex est le même que Hex ordinaire, sauf qu'au lieu d'alterner les tours, les joueurs lancent une pièce avant chaque tour pour décider qui va placer la pierre suivante. Bien que Hex ordinaire soit difficile à analyser, la stratégie optimale pour Random -Turn Hex s'avère très simple. "

Donc en effet, votre intuition avait raison: ce sera dans BPP (ou peut-être P).

Peter Shor
la source

Je suis juste étonné que les gens aient réellement travaillé dessus :) Belle référence!

Suresh Venkat

C'est aussi une très belle preuve. Je pense avoir entendu Scott Sheffield le mentionner dans l'une de ses discussions (mais ensuite je l'ai complètement oublié jusqu'à ce qu'il apparaisse sur Google).

Peter Shor du

En outre, le site Web de David Wilson a en fait une application qui vous permet de jouer à Hex à tour aléatoire (contre leur stratégie publiée, je crois): dbwilson.com/#software

Andy Drucker

Lors de sa dernière visite en Israël, inspiré par le journal de la PSSW, Oded Schramm et moi avons joué pas mal d'échecs au tour par tour pour réaliser que ce n'était pas un jeu particulièrement intéressant.

Gil Kalai

Il s'avère qu'il existe une connexion remarquable (due à David Richman) entre les jeux à tour aléatoire et les jeux d'enchères , où les joueurs enchérissent pour le prochain coup; voir arxiv.org/pdf/0812.3677.pdf et users.math.yale.edu/~sp547/pdf/Discrete-bidding-games.pdf Cette connexion permet un jeu essentiellement optimal des enchères Hex, en utilisant le travail de Peres et al. J'aime cela parce que les jeux d'enchères sont, au moins ostensiblement, sans chance, et je pense que les enchères Hex seraient plus satisfaisantes à jouer que Hex à tour aléatoire. (Enchérir à chaque tour peut être une tâche exaspérante, cependant.)

Andy Drucker