Tipo de juego combinatorio para dos jugadores
Un juego posicional [1] [2] es un tipo de juego combinatorio para dos jugadores. Se describe de la siguiente manera:
- – un conjunto finito de elementos. A menudo se le llama tablero y sus elementos se denominan posiciones .
- – una familia de subconjuntos de . Estos subconjuntos suelen denominarse conjuntos ganadores .
- Un criterio para ganar el juego.
Durante el juego, los jugadores van ocupando posiciones que no habían ocupado hasta que uno de ellos gana. Si todas las posiciones están ocupadas y ningún jugador gana, el juego se considera un empate.
El ejemplo clásico de un juego posicional es el tres en raya . En él, se forman las 9 casillas del tablero de juego, se encuentran las 8 líneas que determinan la victoria (3 horizontales, 3 verticales y 2 diagonales) y el criterio de victoria es: gana el primer jugador que consiga un conjunto ganador completo. Otros ejemplos de juegos posicionales son el 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 lograr un empate. [2] : 7 La principal pregunta 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. Sin embargo, en la práctica, el árbol de juego puede ser enorme. Por lo 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 hipergrafo . En este caso:
- Los elementos de se llaman vértices (o puntos ), y se denotan por V ;
- Los elementos de se llaman aristas (o hiperaristas ) y se denotan por E o H.
Variantes
Existen muchas variantes de juegos posicionales, que se diferencian en sus reglas y criterios de victoria.
Diferentes criterios de adjudicación
- Juego posicional fuerte (también llamado juego Maker-Maker)
- El primer jugador que consiga todos los elementos de un conjunto 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 tres en raya .
- Juego de hacer y deshacer
- 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. No es posible que haya empates. Un ejemplo es el juego de cambio de Shannon .
- Juego del que evita y del que hace cumplir
- Los jugadores se llaman Avoider y Enforcer. Enforcer gana si Avoider alguna vez reclama todos los elementos de un conjunto ganador. Si el juego termina con todos los elementos del tablero reclamados, y Avoider no ha reclamado un conjunto ganador, entonces Avoider gana. Al igual que en los juegos de creación-destrucción, no es posible un empate. Un ejemplo es Sim .
- Juego de discrepancias
- Los jugadores se denominan Balancer y Unbalancer. Balancer gana si consigue que en todos los conjuntos ganadores, cada jugador tenga aproximadamente la mitad de los vértices. De lo contrario, gana Unbalancer.
Diferentes reglas de juego
- Juego del camarero y el cliente (también llamado juego del selector)
- 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 no sesgada, p = q = 1).
Juegos específicos
La siguiente tabla enumera algunos juegos posicionales específicos que fueron ampliamente estudiados en la literatura.
Véase también
Referencias