En la teoría de juegos combinatorios , los juegos de poset son juegos matemáticos de estrategia , que generalizan muchos juegos conocidos como Nim y Chomp . [1] En tales juegos, dos jugadores comienzan con un poset (un conjunto parcialmente ordenado ) y se turnan para elegir un punto en el poset, eliminándolo y 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
denota el conjunto parcial formado al eliminar x de P.
Un juego poset en P , jugado entre dos jugadores llamados convencionalmente Alice y Bob , es el siguiente:
Si P es un conjunto finito totalmente ordenado , entonces el juego en P es exactamente el mismo que el juego en un juego de Nim con un montón de tamaño | P |. Porque, 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 conjuntos parciales con una unión disjunta de órdenes totales es equivalente a un juego de Nim con múltiples montones con tamaños iguales a las cadenas en el conjunto parcial.
Un caso especial de Hackenbush , en el que todos los bordes son verdes (pueden ser cortados por cualquier jugador) y cada configuración toma la forma de un bosque , puede expresarse de manera similar, como un juego de conjuntos parciales en un conjunto parcial en el que, para cada elemento x , hay como máximo un elemento y para el que x cubre a y . Si x cubre a y , entonces y es el padre de x en el bosque en el que se juega el juego.
Chomp puede expresarse de manera similar, como un juego poset sobre el producto de los órdenes totales de los cuales se ha eliminado el ínfimo .
Los juegos poset 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, por el teorema de Sprague-Grundy , cada posición en un juego poset tiene un valor Grundy, un número que describe una posición equivalente en el juego de Nim. El valor Grundy de un juego poset se puede calcular como el menor número natural que no es el valor Grundy de ningún P x , x ∈ P . Es decir, [2]
Este número se puede utilizar para describir el juego óptimo en un juego de conjuntos parciales. En particular, el valor de Grundy es distinto de cero cuando el jugador al que le toca el turno tiene una estrategia ganadora, y cero cuando el jugador actual no puede ganar contra el juego óptimo 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 cada conjunto parcial que tiene un supremo . Sea x el supremo de un conjunto parcialmente ordenado P. Si P x tiene un valor de Grundy cero, entonces P en sí mismo tiene un valor distinto de cero, por la fórmula anterior; en este caso, x es un movimiento ganador en P. Si, por otro lado, P x tiene un valor de Grundy distinto de cero, entonces debe haber un movimiento ganador y en P x , tal que el valor de Grundy de ( P x ) y sea cero. Pero por el supuesto de que x es un supremo, x > y y ( P x ) y = P y , por lo que el movimiento ganador y también está disponible en P y nuevamente P debe tener un valor de Grundy distinto de cero. [1]
Por razones más triviales, un poset con un ínfimo también tiene un valor de Grundy distinto de cero: moverse al ínfimo es siempre un movimiento ganador.
Decidir el ganador de un juego poset finito arbitrario es PSPACE-completo . [3] Esto significa que, a menos que P=PSPACE, calcular el valor de Grundy de un juego poset arbitrario es computacionalmente difícil.
