Juego posicional

Un juego posicional ^[1]^[2] es una especie de juego combinatorio para dos jugadores. Se describe por:

$X$ – un conjunto finito de elementos. Muchas veces se le llama tablero y a sus elementos se les llama posiciones . $X$
${\mathcal {F}}$ – una familia de subconjuntos de . Estos subconjuntos suelen denominarse conjuntos ganadores . $X$
Un criterio para ganar el juego.

Durante el juego, los jugadores reclaman alternativamente posiciones no reclamadas anteriormente, hasta que uno de los jugadores gana. Si se toman todas las posiciones sin que ningún jugador gane, el juego se considera empate. $X$

El ejemplo clásico de juego posicional es el tres en raya . En él, contiene las 9 casillas del tablero de juego, contiene las 8 líneas que determinan una victoria (3 horizontales, 3 verticales y 2 diagonales), y el criterio de victoria es: gana el primer jugador que tenga un conjunto ganador completo. Otros ejemplos de juegos posicionales son Hex y el juego de cambio de Shannon . $X$ ${\mathcal {F}}$

Para cada juego posicional hay exactamente tres opciones: o el primer jugador tiene una estrategia ganadora , o el segundo jugador tiene una estrategia ganadora, o ambos jugadores tienen estrategias para forzar un empate. ^[2]^{: 7} La principal cuestión de interés en el estudio de estos juegos es cuál de estas tres opciones se cumple en un juego en particular.

Un juego posicional es finito, determinista y tiene información perfecta ; por lo tanto, en teoría es posible crear el árbol de juego completo y determinar cuál de estas tres opciones se cumple. En la práctica, sin embargo, el árbol de juego puede ser enorme. Por tanto, los juegos posicionales suelen analizarse mediante técnicas combinatorias más sofisticadas.

Terminología alternativa

A menudo, la entrada a un juego posicional se considera un hipergráfico . En este caso:

Los elementos de se llaman vértices (o puntos ) y se denotan por V ; $X$
Los elementos de se llaman aristas (o hiperbordes ) y se denotan por E o H. ${\mathcal {F}}$

Variantes

Hay muchas variantes de juegos posicionales, que se diferencian en sus reglas y criterios de ganancia.

Diferentes criterios de ganancia

Juego posicional fuerte (también llamado juego Maker-Maker): Gana el primer jugador que reclame todos los elementos de un conjunto ganador. Si el juego termina con todos los elementos del tablero reclamados, pero ningún jugador ha reclamado todos los elementos de un conjunto ganador, se considera empate. Un ejemplo es el clásico tres en raya .
Juego Maker-Breaker: Los dos jugadores se llaman Maker y Breaker. Maker gana al reclamar todos los elementos de un conjunto ganador. Si el juego termina con todos los elementos del tablero reclamados y Maker aún no ha ganado, entonces Breaker gana. Los sorteos no son posibles. Un ejemplo es el juego de cambio de Shannon .
Juego Evitador-Enforcer: Los jugadores se llaman Evitador y Ejecutor. El ejecutor gana si el evitador alguna vez reclama todos los elementos de un conjunto ganador. Si el juego termina con todos los elementos del tablero reclamados y Evitador no ha reclamado un conjunto ganador, entonces Evitador gana. Como en los juegos de creadores y destructores, no es posible empatar. Un ejemplo es Sim .
juego de discrepancia: Los jugadores se llaman Balancer y Unbalancer. El equilibrador gana si se asegura de que en todos los conjuntos ganadores cada jugador tenga aproximadamente la mitad de los vértices. De lo contrario, gana el Desequilibrador.

Diferentes reglas de juego

Juego camarero-cliente (también llamado juego Picker-Chooser): los jugadores se llaman Camarero y Cliente. En cada turno, el camarero elige dos posiciones y se las muestra al cliente, quien puede elegir una de ellas.
Juego posicional sesgado: Cada juego posicional tiene una variante sesgada , en la que el primer jugador puede tomar p elementos a la vez y el segundo jugador puede tomar q elementos a la vez (en la variante insesgada, p = q =1).

Juegos específicos

La siguiente tabla enumera algunos juegos posicionales específicos que fueron ampliamente estudiados en la literatura.

Ver también

Juego topológico , una generalización de un juego posicional a conjuntos infinitos
Juego Banach-Mazur , un juego que se juega en un espacio topológico eligiendo entre ciertos subconjuntos, con condiciones ganadoras que se asemejan a las de un juego creador-rompedor.

Referencias

^ Beck, József (2008). Juegos combinatorios: teoría del tres en raya . Cambridge: Prensa de la Universidad de Cambridge. ISBN 978-0-521-46100-9.
^ ab Hefetz, Dan; Krivelevich, Michael ; Stojaković, Miloš; Szabó, Tibor (2014). Juegos posicionales . Seminarios de Oberwolfach. vol. 44. Basilea: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.