Un juego Avoider-Enforcer [1] : 43–60 (también llamado juego Avoider-Forcer [2] o juego Antimaker-Antibreaker [3] : sección 5 ) es una especie de juego posicional . Como la mayoría de los juegos posicionales, se describe mediante un conjunto de posiciones / puntos / elementos () y una familia de subconjuntos (), que se denominan aquí los conjuntos perdedores . Es jugado por dos jugadores, llamados Avoider y Enforcer, que se turnan para elegir elementos hasta que se tomen todos los elementos. El evitador gana si se las arregla para evitar llevarse un set perdedor; Enforcer gana si logra que Avoider se lleve un set perdedor.
Un ejemplo clásico de este tipo de juegos es Sim . Allí, las posiciones son todos los bordes del gráfico completo en 6 vértices. Los jugadores se turnan para sombrear una línea de su color y pierden cuando forman un triángulo completo de su propio color: los conjuntos perdedores son todos los triángulos.
Comparación con los juegos Maker-Breaker
La condición ganadora de un juego Avoider-Enforcer es exactamente lo opuesto a la condición ganadora del juego Maker-Breaker en el mismo. Por lo tanto, el juego Avoider-Enforcer es la variante del juego Misère del juego Maker-Breaker. Sin embargo, existen diferencias contraintuitivas entre estos tipos de juegos.
Por ejemplo, considere la versión sesgada de los juegos, en la que el primer jugador toma p elementos en cada turno y el segundo jugador toma q elementos en cada turno (en la versión estándar p = 1 yq = 1). Los juegos Maker-Breaker son monótonos con prejuicios : tomar más elementos siempre es una ventaja. Formalmente, si Maker gana el juego ( p : q ) Maker-Breaker, también gana el juego ( p +1: q ) y el juego (p: q-1). Los juegos Avoider-Enforcer no son monótonos: tomar más elementos no siempre es una desventaja . Por ejemplo, considere un juego de Evita-Ejecutor muy simple donde los conjuntos perdedores son {w, x} e {y, z}. Entonces, Avoider gana el juego (1: 1), Enforcer gana el juego (1: 2) y Avoider gana el juego (2: 2).
Hay una variante monótona de las ( p : q ) reglas del juego Evitante-Ejecutor, en la que el Evitante tiene que elegir al menos p elementos en cada turno y Enforcer tiene que elegir al menos q elementos en cada turno; esta variante es sesgada-monótona. [1] : 45–46
Evitación parcial
De manera similar a los juegos Maker-Breaker , los juegos Avoider-Enforcer también tienen generalizaciones fraccionarias.
Suponga que el Evitante necesita evitar tomar al menos una fracción t de los elementos en cualquier conjunto ganador (es decir, tomar como máximo 1 t de los elementos en cualquier conjunto), y Enforcer necesita evitar esto, es decir, Enforcer necesita tomar menos que una fracción t de los elementos en algún conjunto ganador. Defina la constante:(en la variante estándar, ).
- Si , y el número total de elementos es par , Avoider tiene una estrategia ganadora cuando juega primero . [3] : thm A5
Ver también
Juego posicional sesgado # Una condición ganadora para Evita
Referencias
- ^ a b 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.
- ^ Bednarska-Bzdęga, Małgorzata (12 de enero de 2014). "Juegos de Avoider-Forcer en Hypergraphs con rango pequeño" . La Revista Electrónica de Combinatoria . 21 (1): 1–2. ISSN 1077-8926 .
- ^ a b Lu, Xiaoyun (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 .