Juego de hacer y deshacer

Un juego Maker-Breaker es un tipo de juego posicional . ^[1]^{: 13–24} Como la mayoría de los juegos posicionales, se describe por su conjunto de posiciones/puntos/elementos ( ) y su familia de conjuntos ganadores ( - una familia de subconjuntos de ). Lo juegan dos jugadores, llamados Maker y Breaker, que toman alternativamente elementos no tomados previamente. ${\estilo de visualización X}$ ${\mathcal {F}}$ ${\estilo de visualización X}$

En un juego Maker-Breaker, el creador gana si logra mantener todos los elementos de un conjunto ganador, mientras que el rompedor gana si logra evitarlo, es decir, mantener al menos un elemento en cada conjunto ganador. No es posible el empate. En cada juego Maker-Breaker, tanto el creador como el rompedor tienen una estrategia ganadora. La principal pregunta de investigación sobre estos juegos es cuál de estas dos opciones se cumple.

Ejemplos

Un juego clásico de Maker-Breaker es Hex . En este juego, los conjuntos ganadores son todos los caminos que van del lado izquierdo del tablero al lado derecho. Maker gana si posee un camino conectado; Breaker gana si posee un camino conectado de arriba a abajo, ya que bloquea todos los caminos conectados de izquierda a derecha.

El tres en raya se puede jugar como un juego de Maker-Breaker: en esa variante, el objetivo del Maker es elegir 3 cuadrados en una fila, y el objetivo del Breaker es simplemente evitar que Maker lo haga. En esa variante, Breaker tiene una estrategia ganadora. Esto contrasta con la variante clásica (que es un juego posicional fuerte ) donde el segundo jugador tiene una estrategia de robo (ver Juego posicional fuerte#Comparación con el juego Maker-Breaker ).

El juego CNF desordenado ^[2] en un CNF positivo (todos los literales positivos) puede considerarse como un juego Maker-Breaker donde Maker quiere falsificar el CNF y Breaker quiere satisfacerlo.

Se han realizado algunas investigaciones sobre la práctica de juegos Maker-Breaker cuando el tablero del juego es el conjunto de aristas de algún gráfico (normalmente tomado como un gráfico completo ), y la familia de conjuntos ganadores es , donde es alguna propiedad del gráfico (normalmente tomada como monótona creciente [¿aclarar?]) como la conectividad. ^[3] Por ejemplo, el juego de conmutación de Shannon es un juego Maker-Breaker en el que los conjuntos ganadores son los caminos entre dos vértices distinguidos. ${\estilo de visualización E}$ ${\estilo de visualización G}$ ${\mathcal {F}}=\{E'\subset E\vert G[E']{\hbox{ tiene la propiedad }}{\mathcal {P}}\}$ ${\mathcal {P}}$

Dualidad Breaker-Maker

En un juego Maker-Breaker, normalmente Maker juega primero. Pero también es posible dejar que Breaker juegue primero. Jugar primero siempre es ventajoso: cualquier estrategia ganadora para Maker jugando segundo en da como resultado una estrategia ganadora para Maker jugando primero en Lo mismo es cierto para Breaker. ^[1]^{: 15} $(X,{\mathcal {F}})$ $(X,{\mathcal {F}}).$

Además, para cada juego podemos definir su juego transversal , en el que los conjuntos ganadores son los conjuntos mínimos que tocan cada conjunto ganador en el juego original. Por ejemplo, si en el juego original los conjuntos ganadores son { {1,2,3},{4,5,6} } entonces en el juego dual son { {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6} }. Entonces, las estrategias ganadoras para Breaker jugando primero en son exactamente las estrategias ganadoras para Maker jugando primero en . ^[4]^{: 2} $(X,{\mathcal {F}})$ $(X,{\mathcal {F^{*}}})$ $(X,{\mathcal {F}})$ $(X,{\mathcal {F^{*}}})$

Además, existe una convención alternativa de Misère de un juego Creador-Destructor llamado juego Evitador-Ejecutor .

Complejidad computacional

El juego Maker-Breaker es PSPACE-completo incluso si el tamaño de cada conjunto está restringido a 6. ^[5] El primer resultado fue de 1978, donde el tamaño de cada conjunto se restringió a 11, ^[6] donde el juego fue mencionado como (POS CNF 11). ${\estilo de visualización G}$

Estrategias

Comúnmente se utilizan varios tipos de estrategias para resolver juegos Maker-Breaker.

Estrategias de emparejamiento

En algunos juegos, es posible dividir los elementos de X (o un subconjunto de ellos) en un conjunto de pares disjuntos. En determinadas condiciones, un jugador puede ganar utilizando la siguiente estrategia codiciosa: "siempre que tu oponente elija un elemento del par i , elige el otro elemento del par i ".

Las "condiciones ciertas" son diferentes para Maker y para Breaker; ver estrategia de emparejamiento .

Estrategias para juegos posicionales fuertes

Toda estrategia ganadora para el primero en un juego posicional fuerte es también una estrategia ganadora para el segundo en la variante de creador-rompedor (ver Juego posicional fuerte#Comparación con el juego de creador-rompedor ). En particular, si en la variante de fuerte posición no puede haber tablas, entonces en la variante de creador-rompedor el segundo tiene una estrategia ganadora. Lo opuesto no es necesariamente cierto: una estrategia ganadora para el segundo en la variante de creador-rompedor no es necesariamente una estrategia ganadora para el primero en la variante fuerte, ya que en la variante fuerte el segundo puede ganar al reclamar un set ganador antes que el primero.

Por el contrario, cada estrategia ganadora para Breaker en un juego de creación-destrucción, es también una estrategia de empate para Second en la variante de posición fuerte.

Estrategias basadas en el potencial

Supongamos que podemos encontrar una función que asigne, a cada conjunto ganador, un potencial basado en la cantidad de elementos que ya tomó de él el Creador/Destructor. La función potencial debería satisfacer las siguientes propiedades:

El potencial de un set ganador está entre 0 y 1;
Cuando Breaker toma un elemento, el potencial de todos los conjuntos que lo contienen cae a 0 y permanece en 0;
Cuando Maker toma un elemento, el potencial de todos los conjuntos (no rotos) que lo contienen aumenta;
El potencial de un conjunto propiedad de Maker es 1.

Entonces, Maker gana si la suma potencial es mayor que 0, y Breaker gana si la suma potencial es menor que 1. Por lo tanto:

Si la suma inicial es mayor que 0, y Maker puede jugar de tal manera que la suma potencial aumente débilmente, entonces esta es una estrategia ganadora para Maker;
Si la suma inicial es menor que 1 y Breaker puede jugar de tal manera que la suma potencial disminuya débilmente, entonces esta es una estrategia ganadora para Breaker.

Una condición ganadora para Breaker

Paul Erdős y John Selfridge presentaron una condición general que garantiza a Breaker una estrategia ganadora. ^[7] Utilizaron una estrategia basada en el potencial. Definieron el potencial de cualquier conjunto ganador (no roto) con vértices desocupados como . Por lo tanto, el potencial de un conjunto ocupado por Maker es de hecho . Siempre que Maker toma un elemento, el potencial de cada conjunto que lo contiene aumenta a , es decir, aumenta en ; siempre que Breaker toma un elemento, el potencial de cada conjunto que lo contiene cae a 0, es decir, disminuye en . A cada elemento, asignamos un valor que es igual al aumento total del potencial en caso de que Maker lo tome, es decir, . La estrategia ganadora de Breaker es elegir un elemento con un valor más alto . Esto garantiza que, desde el primer turno de Breaker en adelante, el potencial siempre disminuye débilmente. Por lo tanto, si el potencial en el primer turno de Breaker es menor que 1, Breaker gana. En el primer turno de Maker, puede, como máximo, duplicar el potencial (tomando un elemento contenido en todos los conjuntos ganadores). Por lo tanto, es suficiente que al inicio del juego el potencial sea menor que 1/2. En resumen, el teorema de Erdős-Selfridge dice que: ${\estilo de visualización E}$ ${\estilo de visualización |E|}$ $2^{-|E|}$ $2^{-0}=1$ $2^{-(|E|-1)}$ $2^{-|E|}$ $2^{-|E|}$ $w(v):=\sum _ {v\in E}2^{-|E|}$

Si , entonces la victoria de Breaker es $\suma _{E\in {\mathcal {F}}}2^{-|E|}<1/2$ ${\mathcal {F}}$ .

El teorema proporciona una condición muy fácil de comprobar y, cuando esta condición se satisface, también proporciona un algoritmo eficiente para calcular la estrategia óptima de Breaker.

La función potencial tiene una interpretación probabilística. El potencial de un conjunto ganador es la probabilidad de que, si el juego se juega aleatoriamente a partir de ahora, Maker posea ese conjunto. La suma potencial es, por tanto, el número esperado de conjuntos ganadores que posee Maker si el juego se juega aleatoriamente. Siempre que la suma potencial sea menor que 1, debe haber una forma de jugar el juego de manera que el número de conjuntos que posee Maker sea 0. Al garantizar que la suma potencial se mantenga por debajo de 1, Breaker esencialmente desaleatoriza esta afirmación probabilística hasta que, al final del juego, se convierte en una certeza.

Tenga en cuenta que si Breaker juega primero, la condición cambia a . $\suma _{E\in {\mathcal {F}}}2^{-|E|}<1$

En particular, si los conjuntos ganadores son todos de tamaño k (es decir, el hipergrafo del juego es k -uniforme), entonces el teorema de Erdős-Selfridge implica que Breaker gana siempre que , es decir, el número de conjuntos ganadores es menor que . ^[7] $|{\mathcal {F}}|<2^{k-1}$ $Estilo de visualización 2^{k-1}}$

El número es ajustado: hay hipergrafos -uniformes donde el número de conjuntos ganadores es exactamente , y donde Maker tiene una estrategia ganadora. Por ejemplo, considere un árbol binario perfecto de altura . Tiene hojas. Defina V como el conjunto de nodos del árbol y H como la familia de todos los caminos desde la raíz hasta una hoja. Maker comienza eligiendo la raíz. Luego, si Breaker elige un elemento en el subárbol izquierdo, Maker elige la raíz del subárbol derecho y viceversa. Al continuar de esta manera, Maker siempre puede elegir un camino completo, es decir, un conjunto ganador. $Estilo de visualización 2^{k-1}}$ ${\estilo de visualización k}$ $Estilo de visualización 2^{k-1}}$ ${\estilo de visualización k-1}$ $Estilo de visualización 2^{k-1}}$ $Estilo de visualización 2^{k-1}}$

Hipergrafos disjuntos y casi disjuntos

Si todos los conjuntos ganadores son disjuntos en pares y su tamaño es al menos 2, entonces Breaker puede ganar usando una estrategia de emparejamiento.

Supongamos ahora que los conjuntos ganadores son casi disjuntos, es decir, que dos conjuntos ganadores tienen como máximo un elemento en común. Si todos los conjuntos ganadores son de tamaño , y el número de conjuntos ganadores es menor que (para alguna constante fija c), entonces Breaker tiene una estrategia ganadora. ^[8] Por lo tanto, esta situación es más fácil para Breaker que el caso general, pero más difícil que el caso de conjuntos ganadores disjuntos. ${\estilo de visualización k}$ $4^{kc{\sqrt {k}}}$

Una condición ganadora para Maker

Defina el grado de un conjunto de elementos como el número de conjuntos ganadores diferentes que contienen este conjunto. Defina el grado de par de una familia de conjuntos, denotado como , como el grado máximo de un par de elementos (máximo sobre todos los pares). Si todos los conjuntos ganadores tienen un tamaño de , y el número de conjuntos ganadores es mayor que , entonces Maker tiene una estrategia ganadora. ^[9]^{: Teorema 1} $estilo de visualización d_{2}$ ${\estilo de visualización k}$ $2^{k-3}\cdot d_{2}\cdot |X|$

La estrategia utiliza la misma función potencial que utilizaron Erdos y Selfridge: el potencial de un conjunto ganador con elementos desocupados (y ningún elemento ocupado por Breaker) es . El valor de un elemento es la disminución potencial total si Breaker toma ese elemento, que es lo mismo que el aumento potencial total si Maker lo toma. La estrategia de Maker es simplemente tomar el elemento de mayor valor. ${\estilo de visualización E}$ ${\estilo de visualización |E|}$ $2^{-|E|}$

Siempre que Maker toma un elemento, el potencial de cada conjunto ganador que lo contiene aumenta en ; siempre que Breaker toma un elemento, el potencial de cada conjunto que lo contiene y no contiene el elemento de Maker disminuye en . Por lo tanto, si consideramos solo los conjuntos ganadores que fueron tocados una vez, la suma potencial aumenta débilmente. La suma potencial puede disminuir solo debido a conjuntos que contienen tanto el elemento de Maker como el elemento de Breaker. Estos conjuntos ganan pero luego pierden , por lo que en total pierden . Dado que tales conjuntos tienen al menos dos elementos, cada uno de esos conjuntos pierde como máximo 1/4. Por el supuesto de grado de par limitado, el número de tales conjuntos es como máximo d ₂ . Por lo tanto, después de cada ronda, la suma potencial cae como máximo en d ₂ /4. El número de rondas es |X|/2, por lo que el potencial final es menor que el potencial inicial en como máximo . El potencial inicial es . $2^{-|E|}$ $2^{-|E|}$ $2^{-|E|}$ $2^{-(|E|-1)}$ $2^{-|E|}$ $d_{2}\cdot |X|/8$ $|{\mathcal {F}}|\cdot 2^{-k}$

Si , el potencial final es mayor que 0, entonces hay al menos un conjunto ganador con potencial 1. Este conjunto es propiedad de Maker. $|{\mathcal {F}}|\cdot 2^{-k}>d_{2}\cdot |X|/8$

Números cromáticos y estrategias ganadoras

El número cromático de es el número más pequeño de colores necesarios para colorear los elementos de X de modo que ningún conjunto sea monocromático. Si el número cromático de es 3, entonces Maker tiene una estrategia ganadora. ^[10] ${\mathcal {F}}$ ${\mathcal {F}}$ ${\mathcal {F}}$

Tabla resumen

La siguiente tabla resume algunas condiciones que garantizan que uno de los jugadores tenga una estrategia ganadora. La condición en la columna "estrechez" indica cuándo se conocen hipergrafos específicos en los que la estrategia deja de funcionar.

En todas las condiciones, k es el tamaño de los conjuntos ganadores (es decir, el hipergrafo del juego es k -uniforme).

Juego de rompedor-rompedor

Es posible jugar un juego en el que ambos jugadores quieran alcanzar el objetivo de Breaker (es decir, tener al menos un elemento en cada conjunto ganador). En ese caso, el juego no es necesariamente de suma cero: es posible que ambos jugadores ganen. De hecho, siempre que Breaker tenga una estrategia ganadora en el juego Maker-Breaker, es posible que dos Breakers ganen en el juego Breaker-Breaker.

Una aplicación de esta estrategia es un algoritmo eficiente para colorear un hipergrafo. Supongamos que queremos colorear los vértices de un hipergrafo k -uniforme en dos colores de modo que en cada hiperarista estén representados ambos colores. Erdos demostró ya en 1963, utilizando el método probabilístico , que tal coloración existe siempre que el número de hiperaristas sea menor que , en otras palabras, un hipergrafo debe ser 2-uniforme para que exista tal coloración. (ver Propiedad B ). Sin embargo, la prueba no fue constructiva. Utilizando la estrategia ganadora constructiva de Breaker, podemos colorear el hipergrafo dejando que dos Breakers jueguen uno contra el otro con sus estrategias ganadoras. Ambos jugadores ganarán, por lo que cada jugador tendrá al menos un vértice en cada hiperarista. ^[1]^{: 17–20} $Estilo de visualización 2^{k-1}}$ ${\mathcal {F}}$

Fabricación parcial

Supongamos que, para ganar, el Creador no necesita ocupar todo un conjunto ganador, sino que sólo necesita poseer una parte de dicho conjunto. ¿Cuándo puede ganar el Rompedor en este caso?

Fabricación parcial constante

m elementos en un conjunto (donde Breaker no posee ningún elemento). Si el tamaño de cada conjunto ganador es al menos m, y el número de conjuntos es menor que , entonces Breaker todavía tiene una estrategia ganadora. La estrategia utiliza una función potencial: el potencial de un conjunto "roto" es 0, y el potencial de un conjunto no roto E es , donde r(E) es el número de elementos que Maker tiene que tomar para ganar. Por lo tanto, el potencial inicial de cada conjunto ganador es , y el potencial de un conjunto ocupado por Maker es 1. A partir de aquí, la prueba es la misma que el teorema de Erdos-Selfridge. ^[9]^{: Lema 1} $Estilo de visualización 2^{m-1}}$ $Estilo de visualización 2^{-r(E)}}$ $Estilo de visualización 2-m$

Fabricación de fracciones

Supongamos que, para ganar, Maker necesita poseer solo una fracción t de los elementos de un conjunto ganador, donde . Por lo tanto, Breaker necesita poseer una fracción mayor que (1- t ) de los puntos de cada conjunto. Defina la constante: (en la variante estándar, ). $1/2<t\leq 1$ $c_{t}:=(2t)^{t}\cdot (2-2t)^{1-t}=2\cdot t^{t}\cdot (1-t)^{1-t}$ $t=1,c_{t}\to 2$

Si , entonces Breaker tiene una estrategia ganadora $\suma _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<1$ cuando juega primero . ^[9]^{: Lema 3}
Si , entonces Breaker tiene una estrategia ganadora $\sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<{1 \sobre 2-2t}$ al jugar en segundo lugar . ^[11]

En particular, si todos los conjuntos son de tamaño k y su número es menor que , entonces Breaker (que juega primero) tiene una estrategia ganadora. $Estilo de visualización {c_{t}}^{k}}$

La estrategia utiliza una función potencial. El potencial de un conjunto ganador se define como , donde r es el número de elementos que Maker necesita tomar para ocupar el conjunto, y s es el número de elementos que Breaker necesita tomar para romperlo. Si Maker ocupa un conjunto, entonces su potencial en algún momento será al menos 1. Por lo tanto, Breaker gana si logra mantener la suma de potenciales por debajo de 1. La estrategia de Breaker es tomar el elemento con el valor más alto, definido como la suma de potenciales de conjuntos ganadores que contienen ese elemento. $(2t)^{-r}(2-2t)^{-s}$

Siempre que Maker toma un elemento, el potencial de cada conjunto que lo contiene se multiplica por 2 t , por lo que aumenta en (2 t -1) veces el potencial actual. Siempre que Breaker toma un elemento, el potencial de cada conjunto que lo contiene se multiplica por (2-2 t ), por lo que aumenta en (1-2 t ) veces el potencial actual. Siempre que Breaker y Maker tocan el mismo conjunto, su potencial se multiplica por 2 t (2-2 t ), por lo que aumenta en -(2 t -1) ² veces el potencial actual. Dado que el elemento de Breaker tiene un valor más alto, la suma de potenciales siempre disminuye. Por lo tanto, si la suma de potenciales inicial es menor que 1, Breaker gana.

Tableros infinitos

La definición del juego Maker-Breaker tiene una sutileza cuando hay infinitos vértices ( ) y infinitos conjuntos ganadores ( ). En este caso decimos que Breaker tiene una estrategia ganadora si, para todo j > 0, Breaker puede impedir que Maker ocupe por completo un conjunto ganador en el turno j . $|V|=\infty$ $|H|=\infty$

Véase también

Referencias

^ abc Hefetz, Dan; Krivelevich, Michael ; Stojaković, Miloš; Szabó, Tibor (2014). Juegos posicionales . Seminarios de Oberwolfach. vol. 44. Basilea: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.
^ Rahman, doctor Lutfar; Watson, Thomas (2018). Complejidad de los juegos CNF desordenados . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. doi : 10.4230/LIPIcs.ISAAC.2018.9 . OCLC 1081450453.
^ Chvatal, V.; Erdös, P. (1978). "Juegos posicionales sesgados". Anales de Matemáticas Discretas . 2 : 221–229. doi :10.1016/S0167-5060(08)70335-2. ISBN 9780720410433.
^ Csernenszky, András; Mándity, C. Ivett; Pluhár, András (2009). "Sobre los juegos posicionales entre selector y selector". Matemáticas Discretas . 309 (16): 5141–5146. doi : 10.1016/j.disc.2009.03.051 . ISSN 0012-365X.
^ Rahman, doctor Lutfar; Watson, Thomas (2021). Bläser, Markus; Monmege, Benjamín (eds.). "El juego 6-Uniform Maker-Breaker está completo en PSPACE". 38º Simposio Internacional sobre Aspectos Teóricos de la Informática (STACS 2021) . Procedimientos internacionales de informática de Leibniz (LIPIcs). 187 . Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 57:1–57:15. doi : 10.4230/LIPIcs.STACS.2021.57 . ISBN 978-3-95977-180-1.
^ Schaefer, Thomas J. (abril de 1978). "Sobre la complejidad de algunos juegos de información perfecta para dos personas". Journal of Computer and System Sciences . 16 (2): 185–225. doi :10.1016/0022-0000(78)90045-4. ISSN 0022-0000.
^ abc Erdős, P. ; Selfridge, JL (1973). "Sobre un juego combinatorio" (PDF) . Journal of Combinatorial Theory . Serie A. 14 (3): 298–301. doi : 10.1016/0097-3165(73)90005-8 . MR 0327313.
^ ab Beck, József (1981). "Sobre juegos posicionales". Journal of Combinatorial Theory . Serie A. 30 (2): 117–133. doi : 10.1016/0097-3165(81)90001-7 . ISSN 0097-3165.
^ abcd Beck, József (1981). "Juegos tipo Van der waerden y ramsey". Combinatoria . 1 (2): 103–116. doi :10.1007/bf02579267. ISSN 0209-9683. S2CID 36276515.
^ Hales, Alfred W.; Jewett, Robert I. (1963). "Regularidad y juegos posicionales". Transactions of the American Mathematical Society . 106 (2): 222–229. doi : 10.1090/S0002-9947-1963-0143712-1 . MR 0143712.
^ Xiaoyun, Lu (29 de noviembre de 1991). "Un juego de emparejamiento". Matemáticas discretas . 94 (3): 199–207. doi : 10.1016/0012-365X(91)90025-W . ISSN 0012-365X.