Scoring Nim

Este artículo propone una nueva variante del juego de Nim con puntuación que generaliza las reglas normales y misère, analizando sus aspectos teóricos, estrategias óptimas y funciones de pago.

Lo esencial

¡Hola! Imagina que el famoso juego de Nim (ese de las pilas de piedras donde ganas si tomas la última) es como un partido de fútbol tradicional. En el fútbol normal, solo importa quién mete el gol final. Pero en este nuevo juego, llamado "Nim de Puntuación" (Scoring Nim), los autores proponen una regla loca y fascinante: no solo importa quién gana, sino cuántos puntos consigues en el camino.

Aquí te explico la idea central de este paper usando analogías de la vida cotidiana:

1. La Regla del Juego: "Cada piedra vale un dólar, pero la última vale un bono"

Imagina que tienes varias pilas de monedas. Tú y tu oponente se turnan para quitar monedas.

• La regla básica: Por cada moneda que tomas, ganas 1 punto.
• La regla especial: Si tomas la última moneda de todas, ganas un bono extra de $N$ puntos.

Aquí es donde se pone interesante. El valor de $N$ (el bono) es como el "clima" del juego y puede cambiar:

• Si $N$ es un número gigante (como infinito): El juego se vuelve el Nim clásico. Todos corren desesperados por tomar la última moneda porque el premio es tan grande que no importa cuántas monedas normales hayas recogido antes. Es como si el último gol valiera un millón de dólares.
• Si $N$ es un número negativo gigante: ¡Cuidado! Tomar la última moneda te castiga. Ahora, el objetivo es dejarle la última moneda a tu rival. Es como el "Nim al revés" (misère).
• Si $N$ es cero o un número pequeño: Aquí está la magia. Como el bono no es tan importante, los jugadores empiezan a actuar como acaparadores. Quieren quitar la mayor cantidad de monedas posible, sin importar quién se quede con la última. Es como una carrera por comerse la mayor cantidad de pizza antes de que se acabe.

2. El Dilema del Estratega: ¿Cazar el premio o llenar el bolsillo?

Los autores descubrieron que la mejor estrategia depende totalmente de cuánto vale ese bono ($N$).

Imagina que eres un cazador de tesoros:

• Cuando el tesoro (N) es enorme: No te importa cargar con una mochila vacía si eso te garantiza llegar al tesoro primero. Tu estrategia es puramente matemática (la "estrategia ganadora de Nim") para asegurar que tú tomes la última piedra.
• Cuando el tesoro es pequeño: Te vuelves un "gordo glotón". Tu estrategia es "greedy" (codiciosa): tomas tantas piedras como puedas para llenar tu mochila, aunque eso signifique que tu rival tome la última.
• Cuando el tesoro es "intermedio" (el caso más complejo): Aquí es donde el juego se vuelve un ajedrez psicológico. A veces, la mejor jugada no es ni cazar el tesoro ni llenar la mochila al máximo. A veces, tienes que hacer un movimiento extraño que deje a tu oponente en una posición incómoda, donde no puede ni ganar el tesoro ni llenar su mochila.

3. El Mapa de las Estrategias (La función de pago)

Los autores crearon un "mapa" matemático (una función) que te dice exactamente cuánto ganarás (o perderás) dependiendo de cuántas piedras haya y cuánto valga el bono $N$.

• El gráfico es como una montaña rusa: Si dibujas la puntuación en función del valor del bono, la línea no es recta. Tiene muchos picos y valles.
• Los "puntos de quiebre": A medida que aumentas el número de piedras, la línea se vuelve más accidentada, con muchos cambios de dirección. Esto significa que un pequeño cambio en el valor del bono (por ejemplo, que valga 3.5 en lugar de 3.4) puede cambiar completamente la mejor jugada. Es como si el clima cambiara tan rápido que tu estrategia de viaje tendría que reinventarse en cada kilómetro.

4. ¿Por qué es importante esto?

Este paper no es solo sobre un juego de piedras. Es una ventana a cómo tomamos decisiones cuando los incentivos cambian.

• En la vida real, a veces trabajamos por un salario fijo (como el Nim normal).
• A veces trabajamos por comisiones (como el Nim de puntuación).
• A veces, un pequeño cambio en la comisión (el valor de $N$) hace que dejemos de ser competitivos y empecemos a ser simplemente "acaparadores" de recursos, o viceversa.

En resumen

Los autores (Hiromi Oginuma y Masato Shinoda) nos dicen que el juego de Nim, que parecía resuelto y aburrido, en realidad es un camaleón. Cambia de personalidad dependiendo de cuánto valga el premio final.

• Nim Normal: Es una carrera de velocidad.
• Nim de Puntuación: Es una carrera de resistencia y estrategia, donde a veces debes correr rápido, a veces debes caminar despacio y a veces debes esconderte, todo dependiendo de lo que valga el premio al final.

Es un estudio hermoso sobre cómo la matemática puede predecir el comportamiento humano cuando las reglas del juego se vuelven un poco más complejas y "sucias". ¡Y lo mejor es que, aunque las fórmulas son complicadas, la idea es tan simple como jugar a "quién se lleva más monedas"!

Resumen técnico

A continuación presento un resumen técnico detallado del artículo "Scoring Nim" de Hiromi Oginuma y Masato Shinoda, estructurado según los puntos solicitados.

1. Planteamiento del Problema

El juego de Nim es un juego combinatorio clásico de información perfecta, sin azar y de suma cero, donde dos jugadores alternan turnos retirando piedras de pilas. Tradicionalmente, el juego se rige por dos reglas de finalización:

• Juego Normal: Gana quien toma la última piedra.
• Juego Misère: Pierde quien toma la última piedra.

El problema central abordado en este trabajo es la generalización de estas reglas mediante un sistema de puntuación. Los autores proponen una nueva variante llamada Scoring Nim, donde el objetivo no es solo ganar o perder, sino maximizar la diferencia de puntos acumulados.

Reglas de Scoring Nim:

• Se juega con $n$ pilas de piedras.
• Cada piedra tomada otorga 1 punto.
• El jugador que toma la última piedra recibe un bono adicional de $N$ puntos, donde $N$ es un número real fijo antes de comenzar el juego (puede ser positivo, negativo o no entero).
• El ganador es quien tiene la mayor puntuación total.
• Casos límite:
  • Si $N \to \infty$, el juego se comporta como el Nim Normal.
  • Si $N \to -\infty$, el juego se comporta como el Nim Misère.
  • Si $N = 0$, es un juego simple de acumulación de piedras (estrategia codiciosa).

El desafío teórico radica en determinar la estrategia óptima y la función de pago (diferencia de puntaje) para cualquier posición inicial y cualquier valor de $N$, especialmente en los valores intermedios donde la estrategia no es ni puramente la de ganar la partida (Nim) ni puramente la de tomar la mayor cantidad de piedras.

2. Metodología

Los autores emplean un enfoque basado en la teoría de juegos combinatorios y el análisis recursivo:

• Función de Pago ($f_N(p)$): Se define como la diferencia entre la puntuación del primer jugador y la del segundo jugador, asumiendo que ambos juegan óptimamente para maximizar esta diferencia. Dado que la suma de puntos es constante ($|p| + N$), maximizar la diferencia es equivalente a maximizar el propio puntaje.
• Fórmula de Recurrencia: Se establece una relación recursiva basada en el método minimax:
  $$f_N(p) = \max_{p \to p'} \{ |p| - |p'| - f_N(p') \}$$
  Donde $|p| - |p'|$ es el número de piedras tomadas en el movimiento actual. La función base es $f_N(0) = -N$ (el oponente acaba de tomar la última piedra y obtuvo el bono).
• Análisis de Casos:
  • Dos pilas: Se resuelve explícitamente mediante inducción y análisis de casos.
  • Tres o más pilas: Se utilizan propiedades de simetría y sumas disyuntivas para simplificar posiciones (ej. eliminar pares de pilas de tamaño 1).
  • Límites de $N$: Se analiza el comportamiento cuando $|N|$ es muy grande, demostrando que converge a las estrategias de Nim Normal o Misère.
  • Valores Intermedios: Se estudia la estructura de la función de pago para $N$ intermedios, identificando puntos de ruptura (donde cambia la pendiente de la función).

3. Contribuciones Clave

1. Generalización Unificada: Se introduce un marco unificado que engloba el Nim Normal, el Nim Misère y juegos de puntuación pura como casos especiales de un solo parámetro $N$.
2. Propiedades de la Función de Pago: Se demuestra que $f_N(p)$ es una función continua y lineal por partes de $N$, con pendientes de $+1$ o $-1$. Esto implica que el valor para cualquier $N$ real puede interpolarse linealmente a partir de los valores enteros.
3. Estrategias Intermedias: Se identifica que para valores intermedios de $N$, la estrategia óptima no es ni la de "ganar la partida" (Nim) ni la de "tomar todo" (codiciosa), sino una estrategia híbrida que fuerza al oponente a posiciones desfavorables específicas.
4. Complejidad de Puntos de Ruptura: Se demuestra que el número de puntos donde la estrategia óptima cambia (puntos de ruptura en la función de pago) puede crecer arbitrariamente con el número de piedras, revelando una complejidad estructural inesperada.

4. Resultados Principales

A. Caso de Dos Pilas

Para una posición $(x, y)$ con $x, y \ge 2$, se obtiene una fórmula explícita:
$$f_N(x, y) = x - y + |1 - |1 + N||$$
Esto indica que la estrategia óptima depende críticamente de si $N$ está en rangos específicos (ej. si $-2 \le N \le 0$, se sigue la estrategia codiciosa; de lo contrario, se busca igualar las pilas o tomar todo).

B. Propiedades Generales

• Simetría y Pares de 1: La presencia de dos pilas de tamaño 1 no afecta el resultado de la función de pago: $f_N(p_1, \dots, p_n, 1, 1) = f_N(p_1, \dots, p_n)$.
• Comportamiento Asintótico:
  • Si $N$ es positivo y suficientemente grande ($N \ge |p| - 2$), el juego se rige por los conjuntos de posiciones $P^+$ (Nim Normal).
  • Si $N$ es negativo y suficientemente grande ($N \le -|p|$), se rige por $P^-$ (Nim Misère).
  • Se definen constantes $c_+(p)$ y $c_-(p)$ que representan la diferencia de piedras tomadas bajo estas restricciones.

C. Caso de Tres Pilas y la Función $F_k(N)$

El resultado más significativo se centra en posiciones de la forma $(2k+1, 2k, 1)$. Los autores definen una función auxiliar $F_k(N)$ que describe el pago óptimo:
$$F_k(N) = 2 - \min_{j \in J_k} |N - j|$$
Donde $J_k$ es un conjunto de enteros pares en el rango $[-(2k-2), 2k-2]$.

• Teorema 11: Establece fórmulas exactas para $f_N(2k+1, 2k, 1)$ y para posiciones con pilas más grandes $(x, 2k, 1)$ y $(x, 2k+1, 1)$.
• Puntos de Ruptura: La función $f_N(2k+1, 2k, 1)$ tiene exactamente **$4k - 3$puntos de ruptura**. Esto significa que a medida que aumenta el número de piedras, la cantidad de valores críticos de$N$ donde la estrategia óptima cambia crece linealmente, haciendo el análisis de estrategias intermedias extremadamente complejo.

D. Estrategia Óptima Intermedia

Para valores intermedios de $N$, el jugador óptimo no busca simplemente ganar o tomar la mayor cantidad de piedras, sino mover a una posición $(|j|, 2k, 1)$ donde $j$ es el entero par más cercano a $N$ dentro de un rango específico. Esto fuerza al oponente a una posición donde su ventaja es mínima.

5. Significado e Impacto

• Teoría de Juegos: El artículo proporciona un ejemplo concreto y analizable de juegos de puntuación imparciales (impartial scoring games), un área menos explorada que los juegos de victoria/derrota tradicionales.
• Complejidad Estratégica: Demuestra que incluso en juegos simples como Nim, la introducción de un parámetro de puntuación continuo genera una estructura de estrategias rica y fractal, con múltiples transiciones de fase en la estrategia óptima.
• Aplicaciones: Ofrece un modelo para entender cómo los incentivos (bonos) modifican el comportamiento estratégico en sistemas competitivos discretos. La capacidad de predecir cómo cambia la estrategia óptima al variar un parámetro de recompensa ($N$) es valiosa para el diseño de mecanismos y algoritmos.
• Herramientas Analíticas: Las fórmulas recursivas y las propiedades de interpolación lineal desarrolladas pueden servir como base para el análisis de otras variantes de juegos combinatorios con puntuación.

En resumen, "Scoring Nim" no solo resuelve un problema de juego específico, sino que revela una profunda estructura matemática subyacente en la interacción entre la lógica de victoria/derrota y la optimización de recursos (puntos).