Un juego posicional fuerte (también llamado juego Maker-Maker ) es un tipo de juego posicional . [1] : 9–12 Como la mayoría de los juegos posicionales, se describe por su conjunto de posiciones ( ) y su familia de conjuntos ganadores ( - una familia de subconjuntos de ). Lo juegan dos jugadores, llamados Primero y Segundo, que toman alternativamente posiciones no tomadas previamente.
En un juego posicional fuerte, el ganador es el primer jugador que posee todos los elementos de un conjunto ganador. Si se ocupan todas las posiciones y ningún jugador gana, entonces se produce un empate. El tres en raya clásico es un ejemplo de un juego posicional fuerte.
En un juego posicional fuerte, el Segundo no puede tener una estrategia ganadora. Esto se puede demostrar con un argumento de robo de estrategia : si el Segundo tenía una estrategia ganadora, entonces el Primero podría haberla robado y ganar también, pero esto es imposible ya que solo hay un ganador. [1] : 9 Por lo tanto, para cada juego posicional fuerte solo hay dos opciones: o el Primero tiene una estrategia ganadora, o el Segundo tiene una estrategia de empate.
Un corolario interesante es que, si un determinado juego no tiene posiciones de empate, entonces First siempre tiene una estrategia ganadora.
Todo juego posicional fuerte tiene una variante llamada juego Maker-Breaker . En esa variante, solo el primer jugador ("Maker") puede ganar si mantiene un set ganador. El segundo jugador ("Breaker") puede ganar solo si evita que Maker mantenga un set ganador.
En el caso de las partidas fijas y , la variante de posición fuerte es estrictamente más difícil para el primer jugador, ya que en ella, necesita tanto "atacar" (intentar obtener un set ganador) como "defender" (evitar que el segundo jugador obtenga uno), mientras que en la variante de creación-destrucción, el primer jugador puede centrarse únicamente en "atacar". Por lo tanto, cada estrategia ganadora de First en una partida de posición fuerte es también una estrategia ganadora de Maker en la partida de creación-destrucción correspondiente . Lo contrario no es cierto. Por ejemplo, en la variante de creación-destrucción de Tic-Tac-Toe, Maker tiene una estrategia ganadora, pero en su variante de posición fuerte (clásica), Second tiene una estrategia de empate. [2]
De manera similar, la variante de posición fuerte es estrictamente más fácil para el segundo jugador: cada estrategia ganadora de Breaker en un juego de maker-breaker es también una estrategia de empate de Second en el juego de posición fuerte correspondiente , pero lo opuesto no es cierto.
Supongamos que First tiene una estrategia ganadora. Ahora, añadimos un nuevo conjunto a . Contrariamente a la intuición, es posible que este nuevo conjunto destruya la estrategia ganadora y haga que el juego sea un empate. Intuitivamente, la razón es que First podría tener que realizar algunos movimientos para evitar que Second posea este conjunto adicional. [3]
La paradoja del conjunto extra no aparece en los juegos Maker-Breaker.
El juego de camarillas es un ejemplo de un juego posicional fuerte. Está parametrizado por dos números enteros, n y N. En él:
Según el teorema de Ramsey , existe un número R(n,n) tal que, para cada N > R(n,n), en cada dos coloraciones del grafo completo en {1,...,N}, uno de los colores debe contener una camarilla de tamaño n.
Por lo tanto, por el corolario anterior, cuando N > R(n,n), First siempre tiene una estrategia ganadora. [1] : 10
Consideremos el juego de tres en raya jugado en un cubo de dimensión d con longitud n . Según el teorema de Hales-Jewett , cuando d es suficientemente grande (como función de n ), cada coloración de las celdas del cubo contiene una línea geométrica monocromática.
Por lo tanto, por el corolario anterior, First siempre tiene una estrategia ganadora.
Además de estos resultados existenciales, hay pocos resultados constructivos relacionados con los juegos de posición fuerte. Por ejemplo, si bien se sabe que el primer jugador tiene una estrategia ganadora en un juego de camarilla suficientemente grande, actualmente no se conoce ninguna estrategia ganadora específica. [1] : 11–12
