¿Es NP-difícil jugar borradores internacionales correctamente?

26

¿El siguiente problema es NP-hard?

Dada una configuración de tablero para borradores internacionales , encuentre un solo movimiento legal.n×norte

El problema correspondiente para damas estadounidenses (también conocido como borradores en inglés) se puede resolver trivialmente en tiempo polinómico. Hay tres diferencias principales entre estos dos juegos.n×norte

La primera y más significativa diferencia es la regla del "rey volador". En las damas, un rey puede saltar sobre la pieza de un oponente adyacente en un cuadrado vacío a dos pasos de distancia en cualquier dirección diagonal. En los sorteos internacionales, un rey puede saltar sobre la pieza de un oponente a una distancia arbitraria al moverse una distancia arbitraria a lo largo de una diagonal.

Como en las fichas, la misma pieza se puede usar para capturar una serie de piezas en un solo turno. Sin embargo, a diferencia de las fichas, las piezas capturadas en los borradores internacionales no se eliminan hasta que termina la secuencia completa. La pieza de captura puede saltar o aterrizar en el mismo cuadrado vacío varias veces, pero no puede saltar sobre la pieza de un oponente más de una vez.

Finalmente, tanto las damas como los borradores internacionales tienen una regla de captura forzada: si puedes capturar la pieza de un oponente, debes hacerlo. Sin embargo, las reglas no están de acuerdo cuando hay varias opciones para múltiples. En las fichas, puede elegir cualquier secuencia máxima de capturas; en otras palabras, puede elegir cualquier secuencia de captura que termine cuando la pieza de captura no pueda capturar más. En los borradores internacionales, debe elegir la secuencia más larga de capturas. Por lo tanto, mi problema es equivalente a lo siguiente:

Dada una configuración de tablero para borradores internacionales , encuentre un movimiento que capture el número máximo de piezas opuestas.n×n

Sería suficiente demostrar que el siguiente problema es NP-completo. (Obviamente está en NP).

Dada una configuración de tablero para borradores internacionales que involucran solo reyes , ¿puede (y por lo tanto debe) un jugador capturar todas las piezas de su oponente en un solo turno?n×n

El problema de las fichas correspondientes se puede responder en tiempo polinómico; Este es un entretenido ejercicio de tarea. El problema se parece más al análisis de Demaine, Demaine y Eppstein de los finales de Phutball ; Al final de su trabajo aparece una solución para el entretenido ejercicio de tarea. También aparece una solución en el artículo de FOCS 1978 de Frankel et al. eso prueba que jugar damas de manera óptima es difícil para PSPACE; vea también la prueba de 1984 de Robson de que las damas son en realidad EXPTIME-complete.

Jeffε
fuente
error tipográfico? "obviamente está en P", ¿tal vez quieres decir "en NP"? Además, ¿DÓNDE obtienes estas preguntas?
Suresh Venkat
Sí, arreglado. También reformuló el problema; no está claro que el número de movimientos legales desde una posición dada sea solo polinomial.
Jeffε
Este surge de escribir una solución para el "entretenido ejercicio de tarea".
Jeffε
Supongo que la pregunta adicional no formulada aquí es, ¿cuál es la complejidad del juego en sí (determinar si un jugador puede ganar)? ¿Es EXPTIME-complete, como lo son las damas? Probablemente, pero la prueba para las damas es bastante complicada.
Bob Hearn

Respuestas:

24

OK, aquí está la reducción. Resulta que no necesitas planaridad después de todo. Además, para "encontrar un movimiento legal", tomo la pregunta de decisión como "¿es legal el movimiento X?".

Primero, trabajemos con un juego donde las piezas se mueven ortogonalmente en lugar de diagonalmente. Este juego es equivalente (solo mira el tablero de borrador girado 45 grados) excepto por las propiedades de borde, que no usaremos. Utilizamos dos gadgets: fusionar / dividir y crossover. Ver http://www.hearn.to/draughts.pdf . Asumimos que hay un solo rey blanco en el tablero para moverse. (Ninguna otra pieza podrá capturar un número significativo de piezas). Se moverá a través de los corredores indicados, capturando piezas negras en el camino.

Primero, fusionar: si el rey entra en cualquiera de los N caminos A (mediante la captura de una pieza negra, no se muestra), puede salir en B. Del mismo modo, si invertimos el dispositivo y entra en B, capturando la pieza mostrada, puede salir por cualquier camino A (nuevamente, capturando una pieza negra externa). Este es un gadget de un solo uso (porque la pieza negra de salida se puede capturar solo una vez).

Segundo, cruzado. Si el rey entra por A (C), puede salir por B (D). No puede detenerse en el medio y cambiar las rutas, porque ese sería un segmento de movimiento sin captura.

Ahora, dado un gráfico dirigido, construya la configuración de juego correspondiente de la siguiente manera. Para cada vértice, construya una fusión que se alimente en una división. Dirija las salidas divididas a las entradas de fusión de los dispositivos de vértice (fusión + división) correspondientes a los vértices a los que se conectan los bordes de salida, utilizando cruces según sea necesario. Comience el rey en una entrada adicional a cualquier vértice (con una pieza negra para capturar para permitirle ingresar al vértice).

Finalmente, ecualice todas las "longitudes de borde" agregando piezas negras adicionales a lo largo de las rutas de salida / entrada según sea necesario. Si hay vértices V y k piezas negras a lo largo de cada borde, entonces el rey puede capturar 2V + kV + 1 piezas si y solo si hay un circuito hamiltoniano de la gráfica correspondiente. Si el rey tiene un movimiento alternativo disponible, capturar una cadena simple de piezas de 2V + kV, luego determinar si ese movimiento alternativo es legal es NP-completo.

Bob Hearn
fuente
2
Buena reducción!
Jeffε
¿Pero puedes responder la segunda pregunta? ¿Ganar en un movimiento es NP-duro?
Jeffε
Tal vez ... creo que los dispositivos podrían modificarse para que después de completar un circuito hamiltoniano, el rey pudiera capturar todas las piezas negras en los "cables". Las piezas internas fusionadas / divididas aún tendrían que capturarse durante el circuito hamiltoniano, por lo que aún sería NP-hard. La idea sería abrir espacios en los corredores adyacentes a las piezas negras, que permitirían cruzar los pasillos, pero no salir del interior.
Bob Hearn
Supongo que también tomaría un poco de maquinaria de navegación adicional fuera de los corredores, pero debería ser factible.
Bob Hearn
5

Aquí hay una posible alternativa a la reducción de Bob, esta vez del ciclo hamiltoniano (no dirigido). No estoy 100% seguro de que los detalles sean correctos (ya he encontrado y solucionado varios problemas), pero estoy seguro de que se puede combinar con una prueba correcta. Como señala Bob, esta reducción tiene un error grave; el rey blanco puede desviarse fácilmente de su camino canónico a través del tablero. Este error se puede solucionar agregando el dispositivo cruzado de Bob en las ubicaciones apropiadas (creo) , pero luego no es significativamente diferente de su reducción.

solnortemetrosol-1

Ahora reducimos este dibujo a O(norte2)×O(norte2)O(norte2+metro)kkhnorteh

gadget de esquina

gadget horizontal de 4 divisores

artilugio de acumulación

Ahora reemplace cada vértice de grado con un tesoro, conectado a un divisor horizontal ky un vertical kkkk(yo,j)yojXy

un borde

hnorte2+4 4nortesol

Jeffε
fuente
Muy agradable. Pero sí veo un par de problemas, uno de los cuales también tiene mi reducción. Primero, cuando el rey sale de una esquina, puede detenerse en cualquier lugar, lo que potencialmente le permite entrar en otra esquina de manera inapropiada. Segundo, no hay nada que obligue al rey a regresar al vértice inicial; podría terminar en cualquier vértice. El mío tiene el mismo problema, pero se soluciona fácilmente para cualquier reducción, al agregar una pieza adicional adecuada para capturar dentro del vértice de inicio.
Bob Hearn
El segundo problema es fácil de solucionar: mueve la ubicación de inicio del rey más adentro de la horda.
Jeffε
Pero el primer problema es más serio. Supongo que necesitamos tus gadgets cruzados después de todo. Drat!
Jeffε
Creo que quitar la pieza negra de salida del gadget de esquina y agregar una pieza negra en cada brazo del divisor de entrada para cada vértice, también podría ser el truco.
Bob Hearn, el
3

Ahora, ¿por qué no me planteaste este problema cuando estaba trabajando en mi tesis?

OK, tengo una reducción del Ciclo Hamiltoniano Planar Dirigido.

Bob Hearn
fuente
1
¡Digas! (¿Puedes describir brevemente la reducción?)
Ryan Williams
Lo siento, Bob. No pensé en eso entonces. Sí, por favor describa (o enlace a) la reducción.
Jeffε
Esto no es realmente una respuesta.
Dave Clarke
1
No ... pensé que estaba agregando un comentario en ese momento. Ahora, no veo cómo agregar un comentario a la publicación principal.
Bob Hearn
Necesita 100 reputación para agregar un comentario. Es un feechur.
Jeffε