Juego Poset

En la teoría de juegos combinatorios , los juegos de conjuntos parcialmente ordenados son juegos matemáticos de estrategia que generalizan muchos juegos conocidos como Nim y Chomp . ^{[ 1 ]} En estos juegos, dos jugadores comienzan con un conjunto parcialmente ordenado y, por turnos, eligen un punto del conjunto, eliminándolo junto con todos los puntos que sean mayores. El jugador que se queda sin ningún punto para elegir pierde.

Dado un conjunto parcialmente ordenado ( P ,  <), sea

${\displaystyle P_{x}=P-\{a\mid a\geq x\}}$

denotemos el conjunto parcialmente ordenado formado al eliminar x de P.

Un juego de conjuntos parcialmente ordenados en P , jugado entre dos jugadores llamados convencionalmente Alice y Bob , es el siguiente:

• Alice elige un punto x ∈ P ; reemplazando así P con P _x , y luego pasa el turno a Bob, quien juega en P _x , y pasa el turno a Alice.  
• Un jugador pierde si es su turno y no hay puntos para elegir.

Si P es un conjunto finito totalmente ordenado , entonces el juego en P es exactamente el mismo que el juego de Nim con un montón de tamaño | P |. Pues, en ambos juegos, es posible elegir un movimiento que conduzca a un juego del mismo tipo cuyo tamaño sea cualquier número menor que | P |. De la misma manera, un juego de poset con una unión disjunta de órdenes totales es equivalente a un juego de Nim con múltiples montones de tamaños iguales a las cadenas en el poset.

Un caso especial de Hackenbush , en el que todos los bordes son verdes (pueden ser cortados por cualquiera de los jugadores) y cada configuración tiene la forma de un bosque , puede expresarse de manera similar, como un juego de poset sobre un poset en el que, para cada elemento x , hay como máximo un elemento y para el cual x cubre a y . Si x cubre a y , entonces y es el padre de x en el bosque sobre el que se juega.

Chomp puede expresarse de manera similar, como un juego de poset sobre el producto de órdenes totales del cual se ha eliminado el ínfimo .

Los juegos de conjuntos parcialmente ordenados son juegos imparciales , lo que significa que cada movimiento disponible para Alice también estaría disponible para Bob si a Alice se le permitiera pasar , y viceversa. Por lo tanto, según el teorema de Sprague-Grundy , cada posición en un juego de conjuntos parcialmente ordenados tiene un valor de Grundy, un número que describe una posición equivalente en el juego de Nim. El valor de Grundy de un conjunto parcialmente ordenado se puede calcular como el menor número natural que no es el valor de Grundy de ningún P _x , x ∈ P . Es decir, ^{[ 2 ]}  

${\displaystyle G(P)=\min {\bigl (}\mathbb {N} \setminus \{G(P_{x})\mid x\in P\}{\bigr )}.}$

Este número puede utilizarse para describir la estrategia óptima en un juego de conjuntos parcialmente ordenados. En concreto, el valor de Grundy es distinto de cero cuando el jugador cuyo turno es tiene una estrategia ganadora, y cero cuando el jugador actual no puede ganar contra la estrategia óptima de su oponente. Una estrategia ganadora en el juego consiste en moverse a una posición cuyo valor de Grundy sea cero, siempre que esto sea posible.

Un argumento de robo de estrategia muestra que el valor de Grundy es distinto de cero para todo poset que tenga un supremo . Sea x el supremo de un conjunto parcialmente ordenado P. Si P _x tiene un valor de Grundy igual a cero, entonces P mismo tiene un valor distinto de cero, según la fórmula anterior; en este caso, x es una jugada ganadora en P. Si, por otro lado, P _x tiene un valor de Grundy distinto de cero, entonces debe existir una jugada ganadora y en P _x , tal que el valor de Grundy de ( P _x ) _y sea cero. Pero por la suposición de que x es un supremo, x  > y y ( P _x ) _y = P _y , por lo que la jugada ganadora y también está disponible en P y, de nuevo, P debe tener un valor de Grundy distinto de cero. ^{[ 1 ]}   

Por razones más triviales, un conjunto parcialmente ordenado con un ínfimo también tiene un valor de Grundy distinto de cero: moverse al ínfimo siempre es una jugada ganadora.

Decidir el ganador de un juego de poset finito arbitrario es PSPACE-completo . ^{[ 3 ]} Esto significa que, a menos que P=PSPACE, calcular el valor de Grundy de un juego de poset arbitrario es computacionalmente difícil.