Un juego posicional [1] [2] es una especie de juego combinatorio para dos jugadores. Está descrito por:
- - un conjunto finito de elementos. A menudose llama tablero y sus elementos se denominan posiciones .
- - una familia de subconjuntos de. 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 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 eso, contiene los 9 cuadrados del tablero de juego, 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 tiene 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] : 7 La principal cuestión de interés en el estudio de estos juegos es cuál de estas tres opciones se cumple 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 de juego completo 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 hipergráfico . En este caso:
- Los elementos de se llaman vértices (o puntos ), y se denotan por V;
- Los elementos de 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 Maker-Maker)
- 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 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, Breaker gana. Los sorteos no son posibles. Un ejemplo es el juego de cambio de Shannon .
- Juego de Avoider-Enforcer
- los jugadores se llaman Avoider y Enforcer. Enforcer gana si Avoider alguna vez reclama todos los elementos de un set ganador. Si el juego termina con todos los elementos del tablero reclamados y Avoider no ha reclamado un set ganador, Avoider gana. Como en los juegos maker-breaker, no es posible empatar. Un ejemplo es Sim .
- Juego de discrepancia
- los jugadores se llaman Balancer y Unbalancer. Balancer gana si se asegura de que en todos los conjuntos ganadores, cada jugador tenga aproximadamente la mitad de los vértices. De lo contrario, Unbalancer gana.
Diferentes reglas de juego
- Juego Waiter-Client (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.
Nombre | Posiciones | Conjuntos ganadores |
---|---|---|
Tic-tac-toe multidimensional | Todos los cuadrados en una caja multidimensional | Todas las lineas rectas |
Juego de cambio de Shannon | Todos los bordes de un gráfico | Todos los caminos de s a t |
Sim | Todas las aristas 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 gráfico completo de tamaño n | Todas las camarillas de tamaño k |
Juego de conectividad | Todos los bordes de un gráfico completo | Todos los árboles que se extienden |
Juego de hamiltonicity | Todos los bordes de un gráfico completo | Todos los caminos hamiltonianos |
Juego de no planaridad | Todos los bordes de un gráfico completo | Todos los subgráficos no planos |
Juego de progresión aritmética | Los números {1, ..., n} | Todas las progresiones aritméticas de tamaño k |
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 maker-breaker
Referencias
- ^ Beck, József (2008). Juegos combinatorios: teoría del tic-tac-toe . Cambridge: Cambridge University Press. ISBN 978-0-521-46100-9.
- ^ a b Hefetz, Dan; Krivelevich, Michael ; Stojaković, Miloš; Szabó, Tibor (2014). Juegos posicionales . Seminarios de Oberwolfach. 44 . Basilea: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.