Un juego Maker-Breaker es una especie 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 sets ganadores (- una familia de subconjuntos de). Es jugado por dos jugadores, llamados Maker y Breaker, que alternativamente toman elementos no tomados previamente.
En un juego Maker-Breaker, Maker gana si logra mantener todos los elementos de un set ganador, mientras que Breaker gana si logra evitarlo, es decir, si mantiene al menos un elemento en cada set ganador. Los sorteos no son posibles. En cada juego de Maker-Breaker, Maker o Breaker tiene una estrategia ganadora. La principal pregunta de investigación sobre estos juegos es cuál de estas dos opciones es válida.
Ejemplos de
Un juego clásico de Maker-Breaker es Hex . Allí, los conjuntos ganadores son todos caminos desde el lado izquierdo del tablero hacia el lado derecho. Maker gana al poseer una ruta conectada; Breaker gana al poseer una ruta conectada de arriba a abajo, ya que bloquea todas las rutas conectadas de izquierda a derecha.
Tic-tac-toe se puede jugar como un juego de Maker-Breaker: en esa variante, el objetivo de Maker es elegir 3 cuadrados seguidos, y el objetivo de Breaker es simplemente evitar que Maker lo haga. En esa variante, Maker 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 dibujo (ver Comparación del juego posicional fuerte # 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 bastantes investigaciones sobre los juegos Maker-Breaker cuando el tablero del juego es el borde-set de alguna gráfica (generalmente tomado como el gráfico completo ), y la familia de conjuntos ganadores es, dónde es alguna propiedad del gráfico (generalmente se considera que aumenta monótonamente) como la conectividad. [3] Por ejemplo, el juego de cambio de Shannon es un juego Maker-Breaker en el que los conjuntos ganadores son los caminos entre dos vértices distinguidos.
Dualidad Breaker-Maker
En un juego de Maker-Breaker, generalmente Maker juega primero. Pero también es posible dejar que Breaker juegue primero. Jugar primero es siempre una ventaja: cualquier estrategia ganadora para que Maker juegue segundo enproduce una estrategia ganadora para que Maker juegue primero en . Lo mismo ocurre con Breaker. [1] : 15
Además, para cada juego podemos definir su juego transversal , en el que los sets ganadores son los sets mínimos que tocan cada set 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}}. Luego, las estrategias ganadoras para que Breaker juegue primero enson exactamente las estrategias ganadoras para que Maker juegue primero en . [4] : 2
Complejidad computacional
El juego Maker-Breaker es completo para PSPACE 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 se mencionó como(POS CNF 11).
Estrategias
Se utilizan comúnmente varios tipos de estrategias para resolver juegos de 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 por pares. Bajo ciertas condiciones, un jugador puede ganar usando la siguiente estrategia codiciosa: "siempre que su oponente elija un elemento del par i , elija el otro elemento del par i ".
Las "determinadas condiciones" son diferentes para Maker y Breaker; ver estrategia de emparejamiento .
Estrategias de juegos posicionales fuertes
Cada estrategia ganadora de First en un juego posicional fuerte es también una estrategia ganadora para Maker en la variante maker-breaker (ver Comparación de juego posicional fuerte con el juego Maker-Breaker ). En particular, si en la variante de posición fuerte no puede haber empate, entonces en la variante maker-breaker Maker tiene una estrategia ganadora. Lo contrario no es necesariamente cierto: una estrategia ganadora para Maker en la variante maker-breaker no es necesariamente una estrategia ganadora para First en la variante fuerte, ya que en la variante fuerte, Second puede ganar al reclamar un set ganador antes que First. .
En contraste, cada estrategia ganadora para Breaker en un juego de maker-breaker es también una estrategia de dibujo para Segundo 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 Maker / Breaker ya le quitó. La función potencial debe 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, aumenta el potencial de todos los conjuntos (no rotos) que lo contienen;
- El potencial de un conjunto propiedad de Maker es 1.
Entonces, Maker gana si si la suma potencial es mayor que 0, y Breaker gana si si la suma potencial es menor que 1. Por lo tanto:
- Si la suma inicial es más de 0, y Maker puede jugar de 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 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 set ganador (no roto) con vértices desocupados como . Entonces, 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, le asignamos un valor que es igual al aumento de potencial total 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 comienzo del juego, el potencial sea menor que 1/2. Para resumir, el teorema de Erdos-Selfridge dice que:
Si , luego es la victoria de Breaker .
El teorema da una condición muy fácil de verificar, 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 set ganador es la probabilidad de que, si el juego se juega al azar de ahora en adelante, Maker sea dueño de ese set. La suma potencial es, por lo tanto, el número esperado de conjuntos ganadores propiedad de Maker si el juego se juega al azar. Siempre que la suma de potencial sea menor que 1, debe haber una manera de jugar el juego de tal manera que el número de conjuntos propiedad de Maker sea 0. Al asegurarse de que la suma de potencial permanezca 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 .
En particular, si los conjuntos ganadores son todos de tamaño k (es decir, el hipergrama del juego es k- uniforme), entonces el teorema de Erdos-Selfridge implica que Breaker gana siempre que, es decir, el número de sets ganadores es menor que . [7]
El número es apretado: hay -Hipergrafías uniformes donde el número de sets ganadores es exactamente y donde Maker tiene una estrategia ganadora. Por ejemplo, considere un árbol binario perfecto de altura. Tienesale de. Defina V como el conjunto de nodos del árbol y H como la familia de todoscaminos de la raíz a la 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.
Hipergrafos disjuntos y casi disjuntos
Si todos los sets ganadores están separados por pares y su tamaño es de al menos 2, entonces Breaker puede ganar usando una estrategia de emparejamiento.
Supongamos ahora que los conjuntos ganadores son casi inconexos, es decir, dos conjuntos ganadores cualesquiera tienen como máximo un elemento en común. Si todos los sets ganadores son de tamaño, y el número de sets ganadores es menor que (para alguna constante fija c), entonces Breaker tiene una estrategia ganadora. [8] Así que esta situación es más fácil para Breaker que el caso general, pero más difícil que el caso de sets ganadores separados.
Una condición ganadora para Maker
Defina el grado de un conjunto de elementos como el número de diferentes conjuntos ganadores que contienen este conjunto. Definir el grado de par de una familia de conjuntos, denotado, como el grado máximo de un par de elementos (máximo sobre todos los pares). Si todos los sets ganadores son de tamaño, y el número de sets ganadores es más de , entonces Maker tiene una estrategia ganadora. [9] : Teorema 1
La estrategia utiliza la misma función potencial utilizada por Erdos y Selfridge: el potencial de un set ganador con elementos desocupados (y ningún elemento ocupado por Breaker) es . El valor de un elemento es la disminución de potencial total si Breaker toma ese elemento, que es lo mismo que el aumento de potencial total si Maker lo toma. La estrategia de Maker es simplemente tomar el elemento de mayor valor.
Siempre que Maker toma un elemento, el potencial de cada set 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 Maker disminuye en. Por lo tanto, si consideramos solo los conjuntos ganadores que se tocaron una vez, la suma potencial aumenta débilmente. La suma de potencial puede disminuir solo debido a conjuntos que contienen tanto el elemento Maker como el elemento Breaker. Estos conjuntos gananpero luego perder , así que todos en todo lo que pierden . Dado que tales conjuntos tienen al menos dos elementos, cada uno de ellos pierde como máximo 1/4. Según el supuesto de grado de par limitado, el número de estos conjuntos es como máximo d 2 . Por lo tanto, después de cada ronda el potencial de suma cae por como máximo d 2 /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.
Si , el potencial final es más de 0, por lo que hay al menos un set ganador con potencial 1. Este set es propiedad de Maker.
Números cromáticos y estrategias ganadoras
El número cromático dees el menor número de colores necesarios para colorear los elementos de X de manera que ningún conjunto en es monocromático. Si el número cromático dees 3, entonces Maker tiene una estrategia ganadora. [10]
Tabla de resumen
La siguiente tabla resume algunas condiciones que garantizan que uno de los jugadores tenga una estrategia ganadora. La condición en la columna "rigidez" indica cuándo se conocen hipergráficos 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 hipergrama del juego es k -uniforme).
Condición | Ganador | Opresión | Comentarios |
---|---|---|---|
Rompedor [7] | Estrategia potencial | ||
Conjuntos ganadores separados, tamaño al menos 2 | Interruptor automático | Estrategia de emparejamiento | |
Conjuntos casi disjuntos, | Rompedor [8] | ||
Par-grado d 2 , | Creador [9] | Estrategia potencial |
Juego Breaker-Breaker
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 set ganador). Entonces, el juego no es necesariamente de suma cero; es posible que ambos jugadores ganen. De hecho, siempre que Breaker tiene una estrategia ganadora en el juego Maker-Breaker, es posible que dos Breakers ganen ambos en el juego Breaker-Breaker.
Una aplicación de esta estrategia es un algoritmo eficiente para colorear un hipergráfico. Supongamos que queremos colorear los vértices de un hipergrama k -uniforme en dos colores, de modo que en cada hiperfilo, ambos colores estén representados. Erdos ya demostró en 1963, utilizando el método probabilístico , que tal coloración existe siempre que el número de hiperexpresiones es inferior a(ver Propiedad B ). Sin embargo, la prueba no fue constructiva. Usando la estrategia ganadora constructiva de Breaker, podemos colorear el hipergráficodejando 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 hipermercado. [1] : 17-20
Fabricación parcial
Supongamos que, para ganar, Maker no necesita ocupar un conjunto ganador completo, solo necesita poseer una parte de dicho conjunto. ¿Cuándo puede ganar Breaker 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 set ganador es al menos m, y el número de sets 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 E no roto es, donde r (E) es la cantidad de elementos que Maker debe tomar para ganarlo. Entonces, el potencial inicial de cada set ganador es, y el potencial de un conjunto ocupado por Maker es 1. A partir de aquí, la demostración es la misma que la del teorema de Erdos-Selfridge. [9] : Lema 1
Fabricación fraccionada
Suponga que, para ganar, Maker necesita poseer solo una fracción t de los elementos en un conjunto ganador, donde. Por lo tanto, Breaker debe poseer una fracción mayor que (1 t ) de los puntos en cada conjunto. Defina la constante:(en la variante estándar, ).
- Si , entonces Breaker tiene una estrategia ganadora cuando juega primero . [9] : Lema 3
- Si , entonces Breaker tiene una estrategia ganadora cuando juega segundo . [11]
En particular, si todos los conjuntos son de tamaño k y su número es menor que, entonces Breaker (jugando primero) tiene una estrategia ganadora.
La estrategia utiliza una función potencial. El potencial de un set 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 potencial 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.
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) 2 veces el potencial actual. Dado que el elemento de Breaker tiene un valor más alto, la suma de potencial siempre disminuye. Por lo tanto, si la suma potencial inicial es menor que 1, Breaker gana.
Tableros infinitos
La definición de juego Maker-Breaker tiene una sutileza cuando hay infinitos vértices () e infinitos sets ganadores (). En este caso decimos que Breaker tiene una estrategia ganadora si, para todo j > 0, Breaker puede evitar que Maker ocupe completamente un set ganador en el turno j .
Ver también
Referencias
- ^ a b c Hefetz, Dan; Krivelevich, Michael ; Stojaković, Miloš; Szabó, Tibor (2014). Juegos posicionales . Seminarios de Oberwolfach. 44 . Basilea: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.
- ^ Rahman, Md Lutfar Watson, Thomas (2018). Complejidad de los juegos CNF desordenados . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. OCLC 1081450453 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Chvatal; Erdos (1978). "Juegos posicionales sesgados". Annals of Discrete Mathematics . 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). "En los juegos posicionales Chooser-Picker" . Matemáticas discretas . 309 (16): 5141–5146. doi : 10.1016 / j.disc.2009.03.051 . ISSN 0012-365X .
- ^ Rahman, Md Lutfar; Watson, Thomas (2021). Bläser, Markus; Monmege, Benjamin (eds.). "El juego 6-Uniform Maker-Breaker es completo para PSPACE" . 38º Simposio Internacional sobre Aspectos Teóricos de la Informática (STACS 2021) . Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Alemania: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 187 : 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 de dos personas". Revista de Ciencias de la Computación y Sistemas . 16 (2): 185–225. doi : 10.1016 / 0022-0000 (78) 90045-4 . ISSN 0022-0000 .
- ^ a b c Erdős, P .; Selfridge, JL (1973). "En un juego combinatorio" (PDF) . Revista de teoría combinatoria . Serie A. 14 (3): 298-301. doi : 10.1016 / 0097-3165 (73) 90005-8 . Señor 0327313 .
- ^ a b Beck, József (1981). "Sobre juegos posicionales". Revista de Teoría Combinatoria, serie A . 30 (2): 117-133. doi : 10.1016 / 0097-3165 (81) 90001-7 . ISSN 0097-3165 .
- ^ a b c d Beck, József (1981). "Juegos tipo van der waerden y ramsey". Combinatorica . 1 (2): 103-116. doi : 10.1007 / bf02579267 . ISSN 0209-9683 . S2CID 36276515 .
- ^ Hales, Alfred W .; Jewett, Robert I. (1963). "Regularidad y juegos posicionales" . Trans. Amer. Matemáticas. Soc. 106 (2): 222–229. doi : 10.1090 / S0002-9947-1963-0143712-1 . Señor 0143712 .
- ^ Xiaoyun, Lu (29 de noviembre de 1991). "Un juego de correspondencias". Matemáticas discretas . 94 (3): 199–207. doi : 10.1016 / 0012-365X (91) 90025-W . ISSN 0012-365X .