Un juego posicional es una especie de juego combinatorio para dos jugadores.
Está descrito por: 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 él, contiene los 9 cuadrados del tablero de juego, contiene las 8 líneas que determinan una victoria, 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.
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.
Hay muchas variantes de juegos posicionales, que difieren en sus reglas y en sus criterios de ganancia.
Juego posicional fuerte 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.
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 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.
Juego Camarero-Cliente 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.
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 Juego de camarilla 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 Todas las progresiones aritméticas de tamaño k 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.