Motivación del teorema de Sprague-Grundy

Question

El teorema de Sprague-Grundy afirma que todo juego combinatorio imparcial bajo la convención de juego normal es equivalente a un (único) nimber.

¿Qué nos dice la relación de equivalencia así definida sobre un determinado juego? ¿Cuáles son algunos usos específicos del teorema (además de facilitar el cálculo de las posiciones N y P)?

Answer 1

Equivalencia

Dos juegos combinatorios (opcionalmente imparciales) de juego normal (más algunas suposiciones que estoy barriendo bajo la alfombra) $G$ y $H$ son equivalentes exactamente cuando $G+J$ tiene el mismo ganador que $H+J$ para todos los juegos (imparciales) $J$ donde el signo más representa el acto de combinando juegos; $A+B$ significa "hacer una nueva partida en la que en tu turno puedes hacer un movimiento en cualquiera de los dos sumandos ( $A$ o $B$ ) si tiene un movimiento allí".

Por lo tanto, la clase de equivalencia nos da la información suficiente para determinar quién gana cada combinación de ese juego con otro juego combinatorio de juego normal. Dando la vuelta a esto, la relación de equivalencia nos permite descartar cosas irrelevantes como la "redacción de las reglas" o las "diferencias en el juego imperfecto".

El otro hecho importante de esta relación de equivalencia es un teorema que afirma que "si sustituyes todas las posiciones a las que puedes moverte por otras equivalentes, el nuevo juego es equivalente al original". Esto es importante para asegurarse de que se pueden ignorar las diferencias entre juegos equivalentes en todos los contextos.

Sprague-Grundy

Sprague-Grundy nos dice que en el caso imparcial, las únicas clases de equivalencia son las clases de equivalencia de montones individuales de nim, llamados nimbers. Esto nos dice que a efectos de ver quién gana las combinaciones, hay un grupo relativamente ordenado de clases de equivalencia. Si quieres saber cómo jugar a algún juego imparcial en combinaciones, todo lo que necesitas saber es que nimber equivale a (y los nimbers de las cosas con las que se combina). Este es un resultado sorprendente en el sentido de que podría haber toneladas de juegos diferentes, pero a los efectos de las combinaciones, todo es como un solo montón de Nim (y todos $\mathcal{P}$ posiciones son equivalentes).

Por lo que sé, los usos específicos del teorema son esencialmente los que has dicho, haciendo los cálculos de $\mathcal{N}$ y $\mathcal{P}$ posiciones más fáciles. Esto sólo es realmente útil con los juegos que se dividen en combinaciones de otros más pequeños, como juegos octales .