Juego de Evitador-Forzador

Un juego Evitador-Forzador (también llamado juego Anticreador-Antirompedor) es una especie de juego posicional. Como la mayoría de los juegos posicionales, se describe mediante un conjunto de posiciones / puntos / elementos ($X$) y una familia de subconjuntos ($ℱ$), que se denominan aquí los conjuntos perdedores. Es jugado por dos jugadores, llamados Evitador y Forzador, que se turnan para elegir elementos hasta que se toman todos los elementos. El evitador gana si logra evitar llevarse un conjunto perdedor; Forzador gana si logra que Evitador se lleve un conjunto perdedor.

El tablero para el juego de Sim, un juego de Evitador-Forzador.

Un ejemplo clásico de tal juego 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 Creador-Rompedor

La condición ganadora de un juego Evitador-Forzador es exactamente lo opuesto a la condición ganadora del juego Creador-Rompedor en el mismo $ℱ$. Por lo tanto, el juego Evitador-Forzador es la variante del juego misère del juego Creador-Rompedor. Sin embargo, existen diferencias contraintuitivas entre estos tipos de juegos.

Por ejemplo, considérese 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 y q=1). Los juegos Creador-Rompedor son monótonos con prejuicios: tomar más elementos siempre es una ventaja. Formalmente, si Creador gana el juego (p:q) Creador-Rompedor, también gana el juego (p +1: q) y el juego (p:q-1). Los juegos de Evitador-Forzador no son monótonos: tomar más elementos no siempre es una desventaja. Por ejemplo, considérese un juego de Evitador-Forzador muy simple donde los conjuntos perdedores son {w, x} e {y, z}. Entonces, Evitador gana el juego (1:1), Forzador gana el juego (1:2) y Evitador gana el juego (2:2).

Existe una variante monótona de las (p:q) reglas del juego Evitador-Forzador, en la que el Evitador tiene que elegir al menos p elementos en cada turno y Forzador tiene que elegir al menos q elementos en cada turno; esta variante es sesgada-monótona.

Evasión parcial

De manera similar a los juegos Creador-Rompedor, los juegos Evitador-Forzador también tienen generalizaciones fraccionarias.

Suponga que el Evitador 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 Forzador necesita evitar esto, es decir, Forzador necesita tomar menos que una fracción t de los elementos en algún conjunto ganador. Defina la constante $c_t:=(2t{)}^t\cdot (2-2t{)}^{1-t}=2\cdot t^t\cdot (1-t{)}^{1-t}$(en la variante estándar, $t=1,c_t\to 2$).

• Si$\sum _{E\in ℱ}{c_t}^{-|E|}<1$, y el número total de elementos es par, Evitador tiene una estrategia ganadora cuando juega primero.