Un juego posicional fuerte (también llamado juego Maker-Maker ) es una especie 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 alternativamente ocupan posiciones no ocupadas anteriormente.
En un juego posicional fuerte, el ganador es el primer jugador que tenga todos los elementos de un conjunto ganador. Si se toman todas las posiciones y ningún jugador gana, entonces se trata de un empate. El clásico Tic-tac-toe es un ejemplo de un juego posicional fuerte.
En un juego posicional fuerte, Segunda no puede tener una estrategia ganadora. Esto se puede demostrar mediante un argumento de robo de estrategia : si Segundo tuviera una estrategia ganadora, entonces Primero podría haberla robado y ganar también, pero esto es imposible ya que sólo hay un ganador. [1] : 9 Por lo tanto, para cada juego posicional fuerte sólo 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 Primera siempre tiene una estrategia ganadora.
Todo juego posicional fuerte tiene una variante que es un juego Maker-Breaker . En esa variante, sólo el primer jugador ("Creador") puede ganar si tiene un conjunto ganador. El segundo jugador ("Breaker") sólo puede ganar impidiendo que Maker tenga un set ganador.
Para fijo y , la variante posicional fuerte es estrictamente más difícil para el primer jugador, ya que en ella necesita "atacar" (intentar conseguir un conjunto ganador) y "defender" (evitar que el segundo jugador consiga uno). , mientras que en la variante creador-rompedor, el primer jugador puede centrarse sólo en "atacar". Por lo tanto, cada estrategia ganadora de Primero en un juego posicional fuerte es también una estrategia ganadora de Creador en el correspondiente juego creador-rompedor . Lo contrario no es verdad. Por ejemplo, en la variante creador-rompedor de Tic-Tac-Toe, Maker tiene una estrategia ganadora, pero en su variante posicional fuerte (clásica), Second tiene una estrategia de empate. [2]
De manera similar, la variante posicional fuerte es estrictamente más fácil para el segundo jugador: cada estrategia ganadora de Breaker en un juego maker-breaker es también una estrategia de empate de Second en el correspondiente juego posicional fuerte , pero lo contrario no es cierto.
Supongamos que First tiene una estrategia ganadora. Ahora, agregamos 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 Primero podría tener que gastar algunos movimientos para evitar que Segundo posea este conjunto extra. [3]
La paradoja del set extra no aparece en los juegos Maker-Breaker.
El juego de camarilla es un ejemplo de juego posicional fuerte. Está parametrizado por dos números enteros, n y N. En él:
Según el teorema de Ramsey , existe algún 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, según el corolario anterior, cuando N > R(n,n), First siempre tiene una estrategia ganadora. [1] : 10
Considere el juego de tres en raya jugado en un cubo d -dimensional de longitud n . Según el teorema de Hales-Jewett , cuando d es lo suficientemente grande (en función de n ), cada 2 colores de las celdas del cubo contiene una línea geométrica monocromática.
Por lo tanto, según el corolario anterior, First siempre tiene una estrategia ganadora.
Además de estos resultados existenciales, hay pocos resultados constructivos relacionados con los juegos posicionales fuertes. Por ejemplo, si bien se sabe que el primer jugador tiene una estrategia ganadora en un juego de camarillas suficientemente grande, actualmente no se conoce ninguna estrategia ganadora específica. [1] : 11-12
