Juego posicional
# Juego posicional

Un juego posicional 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. 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 |
