Calcular el valor SG para juegos sencillos.
El teorema de Sprague-Grundy es una pieza fundamental de la teoría de juegos combinatorios, y asegura que todo juego imparcial bajo la convención de juego normal es equivalente a una pila de Nim de un tamaño específico. A este tamaño lo llamamos el valor de Sprague-Grundy (o simplemente valor SG, número de Grundy o nim-valor) del estado del juego. Para "juegos pequeños" —juegos imparciales finitos sin posibilidad de empate— calculamos estos valores de forma recursiva. El valor SG de un estado terminal (donde ya no puedes hacer movimientos) lo definimos como 0. Para cualquier otro estado, el valor SG es el entero no negativo más pequeño (0, 1, 2, ...) que no está entre los valores SG de los estados a los que puedes llegar en un solo movimiento. A esta operación la conocemos como el Mínimo Excluido, o mex.
Esta técnica es vital porque te permite descomponer juegos complejos en componentes más simples. Muchas veces, un problema de competencia presenta un juego que en realidad es la suma de varios subjuegos más pequeños e independientes. En lugar de analizar el árbol de juego gigante del juego combinado, calculas el valor SG de cada subjuego pequeño por separado. El valor SG del juego combinado es simplemente la suma XOR (suma Nim) de los valores SG de sus componentes. Esto transforma un problema difícil de estrategia en un simple cálculo de valores enteros.
Intuitivamente, el valor SG representa el "grado de libertad