Juego poset

En teoría de juegos combinatorios, los juegos 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 son mayores. El jugador que se queda sin un punto para elegir, pierde.

Juego

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

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

denotar el poset formado mediante la eliminación de x de P.

Un juego poset en P, jugado entre dos jugadores convencionalmente llamados 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.

Ejemplos

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 poset 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 del poset.

Un caso especial de Hackenbush, en el que todos los bordes son verdes (puede ser cortado por cualquiera de los jugadores) y cada configuración toma la forma de un bosque, puede expresarse de manera similar, como un juego poset en un poset en el que, para cada elemento x, hay como máximo un elemento y para el que x cubre y. Si x cubre 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 del total de pedidos de los que se ha eliminado el infimum.

Valor de Grundy

Los juegos poset son juegos imparciales, lo que significa que todos los movimientos disponibles para Alice también estarían disponibles para Bob si se permitiera que Alice pasara, y viceversa. Por lo tanto, según el teorema de Sprague-Grundy, cada posición en un juego poset tiene un valor de Grundy, un número que describe una posición equivalente en el juego de Nim. El valor Grundy de un poset puede calcularse como el menor número natural que no es el valor Grundy de cualquier 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 usarse para describir la jugabilidad óptima en un juego poset. En particular, el valor de Grundy es distinto de cero cuando el jugador cuyo 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 pasar a una posición cuyo valor de Grundy sea cero, siempre que sea posible.

Robo de estrategia

Un argumento de robo de estrategia muestra que el valor de Grundy es distinto de cero para cada poset que tiene un supremum. Sea x el supremo de un conjunto P parcialmente ordenado. Si P_x tiene un valor de Grundy cero, entonces P tiene un valor distinto de cero, según 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, de modo que el valor de Grundy de (P_x)_y sea cero. Pero asumiendo 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.

Por razones más triviales, un poset con un mínimo también tiene un valor de Grundy distinto de cero: moverse al mínimo es siempre un movimiento ganador.

Complejidad

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.

Referencias

1. Soltys, Michael; Wilson, Craig (1 de abril de 2011). «On the Complexity of Computing Winning Strategies for Finite Poset Games». Theory of Computing Systems (en inglés) 48 (3): 680-692. ISSN 1433-0490. doi:10.1007/s00224-010-9254-y. Consultado el 15 de febrero de 2021. 
2. Byrnes, Steven (2003), «Poset game periodicity», Integers 3 (G3): 1-16, MR 2036487 ..
3. Grier, Daniel (2012), «Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-Complete», Automata, Languages, and Programming, Lecture Notes in Computer Science 7965, pp. 497-503, Bibcode:2012arXiv1209.1750G, ISBN 978-3-642-39205-4, arXiv:1209.1750, doi:10.1007/978-3-642-39206-1_42 ..

•   Datos: Q7233029