Complejidad del hex con orden de turno aleatorio.

He estado pensando en una variante de hex , donde en lugar de que los dos jugadores hagan movimientos alternativamente, cada turno que un jugador escogido al azar hace un movimiento. ¿Qué tan difícil es determinar las posibilidades de que gane cada jugador? Este problema está obviamente en PSPACE, pero no puede ser NP-hard, mucho menos PSPACE-complete. Las dificultades provienen de cómo la aleatoriedad hace imposible que un jugador se vea obligado a elegir entre opciones; si ese jugador tiene suerte, obtiene suficientes movimientos, tome ambas opciones, y si el jugador tiene mala suerte, el oponente obtiene suficientes movimientos para bloquear ambas opciones. Por otro lado, no puedo pensar en ningún algoritmo de tiempo polinómico para esto.

cc.complexity-theory board-games Itai Bar-Natan
fuente

Sea S una cadena binaria de n bits que representa qué jugador está tomando el turno. En el peor de los casos, recuperas el juego hexagonal estándar si la secuencia aleatoria es 010101 ... o 101010 .... Entonces, tu problema es al menos tan difícil como el hexágono estándar.

Mohammad Al-Turkistany

Hay dos posibles interpretaciones de este juego. (1) Justo antes de cada turno, los jugadores lanzan una moneda para determinar quién sigue. (2) Al comienzo del juego, los jugadores lanzan una moneda

veces (en un tablero de tamaño

) y usan esta secuencia para sus turnos. Turkistany parece estar asumiendo el modelo (2); la pregunta original es ambigua, pero por algunas de sus palabras, supongo que Itai pregunta sobre (1), que podría ser más fácil que el hexadecimal estándar.

n^{2}

$n^2$

n

$n$

Peter Shor

De hecho, me refiero a la primera interpretación, que la moneda se lanza justo antes del movimiento. Además, noté otra ambigüedad en mi pregunta: la precisión con la que quiero saber la probabilidad. Si bien la impresión que dejé al preguntar el problema es que quiero saber la probabilidad con precisión completa, pero solo quiero saber la probabilidad con precisión logarítmica. Al igual que la diferencia entre PP y BPP, la última parece más útil y natural.

Itai Bar-Natan

@Itai: Otra pregunta. ¿Por qué afirmas que esto está obviamente en PSPACE? Me parece que es un juego arbitrado, lo que significaría que el límite superior teórico de la complejidad natural es EXPTIME. Ver Feige y Kilian, "Making Short Games".

Peter Shor

@tukistany ¡Inútil NO implica trivial!

Jeffε

Respuestas:

Es posible que desee ver el documento "Random-Turn Hex and Other Selection Games", de Yuval Peres, Oded Schramm, Scott Sheffield y David Wilson. De la introducción:

"El hexágono de turno aleatorio es el mismo que el hexágono ordinario, excepto que en lugar de alternar turnos, los jugadores lanzan una moneda antes de cada turno para decidir quién coloca la siguiente piedra. Aunque el hexágono ordinario es famoso por ser difícil de analizar, la estrategia óptima para Aleatorio -Turn Hex resulta ser muy simple ".

De hecho, su intuición era correcta: esto será en BPP (o tal vez P).

Peter Shor
fuente

Estoy sorprendido de que la gente haya trabajado en esto :) ¡Buena referencia!

Suresh Venkat

Es una buena prueba también. Creo que escuché a Scott Sheffield mencionarlo en una de sus charlas (pero luego lo olvidé por completo hasta que apareció en Google).

Peter Shor

Además, el sitio web de David Wilson en realidad tiene una aplicación que te permite jugar Hex de turnos aleatorios (en contra de su estrategia publicada, creo): dbwilson.com/#software

Andy Drucker

En su última visita a Israel, inspirado en el artículo del PSSW, Oded Schramm y yo jugamos varias rondas de ajedrez al azar para darnos cuenta de que no es un juego particularmente interesante.

Gil Kalai

Resulta que hay una conexión notable (debido a David Richman) entre los juegos de turnos aleatorios y los juegos de licitación , donde los jugadores ofertan para el próximo movimiento; ver arxiv.org/pdf/0812.3677.pdf y users.math.yale.edu/~sp547/pdf/Discrete-bidding-games.pdf Esta conexión permite un juego esencialmente óptimo de pujas Hex, utilizando el trabajo de Peres et al. Me gusta porque los juegos de pujas son, al menos ostensiblemente, sin suerte, y creo que apostar por Hex sería más satisfactorio de jugar que Hex de turno aleatorio. (Sin embargo, ofertar en cada turno puede ser una tarea enloquecedoramente exigente).

Andy Drucker