Juego posicional

Un juego posicional^[1]^[2] es una especie de juego combinatorio para dos jugadores. Está descrito por:

$X$ – un conjunto finito de elementos. A menudo $X$ se llama tablero y sus elementos se denominan posiciones.
${\mathcal {F}}$ – una familia de subconjuntos de $X$ . Estos subconjuntos generalmente se denominan conjuntos ganadores.
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 todas las posiciones en $X$ se toman mientras ningún jugador gana, el juego se considera un empate.

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

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 hacer cumplir un empate.^[2] La principal cuestión de interés en el estudio de estos juegos es cuál de estas tres opciones se mantiene en cualquier 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 completo del juego y determinar cuál de estas tres opciones es válida. En la práctica, sin embargo, el árbol del juego puede ser enorme. Por lo tanto, los juegos posicionales generalmente se analizan mediante técnicas combinatorias más sofisticadas.

Terminología alternativa

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

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

Variantes

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

Diferentes criterios ganadores

Juego posicional fuerte (también llamado juego Creador-Creador): el primer jugador en reclamar todos los elementos de un set ganador gana. Si el juego termina con todos los elementos del tablero reclamados, pero ningún jugador ha reclamado todos los elementos de un conjunto ganador, es un empate. Un ejemplo es el clásico tic-tac-toe.
Juego Creador-Destructor: los dos jugadores se llaman Creador y Destructor. Creador gana al reclamar todos los elementos de un conjunto ganador. Si el juego termina con todos los elementos del tablero reclamados y Creador aún no ha ganado, entonces Destructor gana. Los empates no son posibles. Un ejemplo es el juego de cambio de Shannon.
Juego de Evitador-Ejecutor: los jugadores se llaman Evitador y Ejecutor. Ejecutor gana si Evitador alguna vez reclama todos los elementos de un set ganador. Si el juego termina con todos los elementos del tablero reclamados, y Evitador no ha reclamado un set ganador, Evitador gana. Como en los juegos Creador-Destructor, no es posible empatar. Un ejemplo es Sim.
Juego de discrepancia: los jugadores se llaman Balanceador y Desbalanceador. Balanceador gana si asegura que en todos los conjuntos ganadores, cada jugador tiene aproximadamente la mitad de los vértices. De lo contrario, Desbalanceador gana.

Diferentes reglas de juego

Juego Camarero-Cliente (también llamado juego Elector-Elección): 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.


Nombre	Posiciones	Conjuntos ganadores
Tic-tac-toe multidimensional	Todos los cuadrados en una caja multidimensional	Todas las líneas rectas
Juego de cambio de Shannon	Todos los bordes de un grafo	Todos los caminos de s a t
Sim	Todos los bordes entre 6 vértices	Todos los triángulos [conjuntos perdedores]
Juego de camarilla (también conocido como juego de Ramsey)	Todos los bordes de un grafo completo de tamaño n	Todas las camarillas de tamaño k
Juego de conexión	Todos los bordes de un grafo completo	Todos los spanning trees
Juego de hamiltoncidad	Todos los bordes de un grafo completo	Todos los caminos hamiltonianos
Juego de no planaridad	Todos los bordes de un grafo completo	Todos los subgrafos no planos
Juego de progresión aritmética	Los números {1, ..., n}	Todas las progresiones aritméticas de tamaño k

Véase también

Referencias

↑ Beck, József (2008). Combinatorial Games: Tic-Tac-Toe Theory. Cambridge: Cambridge University Press. ISBN 978-0-521-46100-9.
↑ ^a ^b Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor. Birkhäuser Verlag GmbH, ed. Positional Games. Oberwolfach Seminars. Basel. ISBN 978-3-0348-0824-8.

Datos: Q7233199

[beck08-1] Beck, József (2008). Combinatorial Games: Tic-Tac-Toe Theory. Cambridge: Cambridge University Press. ISBN 978-0-521-46100-9.

[pg14-2] Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor. Birkhäuser Verlag GmbH, ed. Positional Games. Oberwolfach Seminars. Basel. ISBN 978-3-0348-0824-8.

[1]

[2]