Scoring Nim

Dit artikel introduceert een nieuwe variant van het spel Nim met scoren die zowel de normale als de misère spelregels generaliseert en de theoretische aspecten, zoals optimale strategieën en uitbetalingsfuncties, analyseert.

De kern

Stel je voor dat je een klassiek bordspel speelt, zoals Nim. Normaal gesproken is het doel simpel: wie de laatste steen pakt, wint. Of, in een gekke variant, wie de laatste steen pakt, verliest. Het is een strijd van strategie, waarbij je probeert je tegenstander in een val te lokken.

Maar wat als we het spel een beetje gekker maken? Wat als we niet alleen kijken naar wie wint, maar ook naar hoeveel punten je verzamelt?

Dat is precies wat de auteurs van dit paper, Hiromi Oginuma en Masato Shinoda, hebben bedacht. Ze noemen hun nieuwe spel Scoring Nim (Score-Nim). Hier is een uitleg in gewone taal, met een paar creatieve vergelijkingen om het duidelijk te maken.

1. Het Nieuwe Spel: Een Mix van Alles

In Scoring Nim heb je weer stapels stenen. Je mag er elke beurt zoveel van nemen als je wilt uit één stapel. Maar nu zijn er twee regels voor punten:

1. Elke steen die je pakt, levert 1 punt op.
2. De speler die de allerlaatste steen pakt, krijgt een bonus.

Die bonus noemen we N. En hier wordt het interessant: N kan elk getal zijn, zelfs een negatief getal of een heel groot getal.

• Als N heel groot is (bijv. oneindig): Dan is de bonus zo groot dat het alleen nog maar uitmaakt wie de laatste steen pakt. Dit is precies het oude, klassieke Nim-spel (wie wint, wint).
• Als N negatief is (bijv. -100): Dan is het nemen van de laatste steen een ramp! Je krijgt een enorme straf. Dit is dan het "misère" spel (wie de laatste steen pakt, verliest).
• Als N 0 is: Dan is de bonus niets. Het enige doel is om zo veel mogelijk stenen te verzamelen. Je wordt dan een "graai" die gewoon alles wil hebben.

De Metafoor:
Stel je voor dat je en je vriend een taart delen.

• Bij grote N is de taart zo groot dat het alleen uitmaakt wie het laatste stukje krijgt.
• Bij negatieve N is het laatste stukje vergiftigd; je wilt je vriend dwingen om dat stukje te eten.
• Bij N=0 is het gewoon een kwestie van wie de meeste kruimels kan rapen.

2. Het Grote Dilemma: Winnen vs. Verzamelen

Het meest fascinerende aan dit spel is dat de beste strategie verandert afhankelijk van de grootte van de bonus (N).

Soms wil je de "Nim-winststrategie" gebruiken (de wiskundige manier om de laatste steen te pakken).
Soms wil je de "Gierige strategie" gebruiken (simpele: pak gewoon alles wat je kunt).
Maar voor de tussenwaarden van N (bijvoorbeeld als de bonus net iets te klein is om alleen om de laatste steen te vechten, maar te groot om te negeren), gebeurt er iets magisch.

De spelers moeten dan een heel ingewikkeld dansje doen. Ze moeten hun tegenstander in een positie duwen waar geen van de twee simpele strategieën werkt. Het is alsof je in een danszaal staat en de muziek (de bonus N) verandert. Soms moet je een snelle sprint maken, soms een langzame dans, en soms moet je je partner dwingen om een rare stap te zetten die voor jou voordelig is.

3. De Wiskundige "Krachtlijnen"

De auteurs hebben gekeken naar hoe dit spel zich gedraagt als je de bonus (N) verandert. Ze hebben een grafiek getekend die eruitziet als een zaagtand.

• De Zaagtand: Als je de bonus N langzaam verhoogt, zie je dat de beste strategie plotseling van richting verandert. Het is alsof je een knop omdraait en ineens een heel ander spel speelt.
• Hoe meer stenen, hoe complexer: Hoe groter de stapels stenen zijn, hoe meer "knikpunten" er in die grafiek zitten. Bij een klein spelletje heb je misschien 3 of 4 strategieën. Bij een groot spel kunnen er honderden verschillende strategieën zijn, afhankelijk van de exacte waarde van de bonus.

De Vergelijking:
Stel je voor dat je een auto bestuurt op een weg met honderden verkeerslichten.

• Als de bonus (N) heel hoog is, is het alsof alle lichten groen zijn: je rijdt rechtstreeks naar de finish (de laatste steen).
• Als de bonus laag is, is het alsof je gewoon door de stad rijdt om zoveel mogelijk winkels te bezoeken (stelen verzamelen).
• Maar in het midden? Dan moet je constant remmen, optrekken en van rijbaan wisselen, afhankelijk van of het licht net op rood of groen springt. De auteurs hebben precies berekend waar die lichten springen.

4. Waarom is dit belangrijk?

Dit paper is niet alleen leuk voor spelletjesliefhebbers. Het laat zien hoe complexe systemen reageren op kleine veranderingen.

• Het verbindt twee oude ideeën (winnen of verliezen) met een nieuw idee (punten verzamelen).
• Het laat zien dat "optimaal spelen" niet altijd hetzelfde is. Wat vandaag de beste zet is, kan morgen de slechtste zet zijn als je de regels (de bonus) een klein beetje aanpast.

Samenvatting

Scoring Nim is een slimme uitvinding die het oude Nim-spel een nieuwe dimensie geeft. Het is een spel waar je niet alleen moet nadenken over wie wint, maar ook over hoe je je punten maximaliseert. De auteurs hebben bewezen dat de beste strategie een ingewikkeld, maar voorspelbaar patroon volgt dat lijkt op een zaagtand, waarbij elke tand een andere manier van spelen vertegenwoordigt, afhankelijk van de waarde van de bonus.

Kortom: het is een spel waar je je hersenen moet gebruiken om te zien of je moet jagen naar de laatste steen, of dat je beter kunt doen alsof je gewoon een verzamelaar bent, en wanneer je die twee strategieën moet mixen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Scoring Nim" van Hiromi Oginuma en Masato Shinoda, geschreven in het Nederlands.

Titel: Scoring Nim: Een uitbreiding van het klassieke Nim-spel met scoremechanismen

1. Probleemstelling

Het klassieke Nim-spel is een bekend combinatorisch spel waarbij twee spelers om de beurt stenen uit verschillende stapels verwijderen. De uitkomst wordt traditioneel bepaald door de spelregels:

• Normale spelregels (Normal play): De speler die de laatste steen neemt, wint.
• Misère spelregels (Misère play): De speler die de laatste steen neemt, verliest.

In beide gevallen is het doel puur strategisch gericht op het winnen of verliezen van het spel, zonder rekening te houden met de aantal stenen dat wordt genomen. De auteurs stellen een nieuw variant voor, genaamd Scoring Nim, die beide klassieke versies generaliseert. In dit nieuwe spel wordt de uitkomst niet alleen bepaald door wie de laatste steen neemt, maar door een scorefunctie die de totale punten van beide spelers vergelijkt.

Het centrale probleem is het analyseren van de optimale strategieën en de uitkomst (payoff) van dit spel, waarbij een variabele bonus $N$ wordt toegekend voor het nemen van de laatste steen. De waarde van $N$ kan elk reëel getal zijn (inclusief negatieve waarden en oneindigheid), wat leidt tot een continu spectrum van spelvarianten.

2. Methodologie

De auteurs hanteren een wiskundige benadering binnen de theorie van combinatorische spellen, specifiek gericht op impartiele spelletjes (waarbij de beschikbare zetten niet afhangen van wie er aan de beurt is) met een scorefunctie.

• Spelregels:

  • Er zijn $n$ stapels stenen.
  • Spelers nemen om de beurt een positief aantal stenen uit één stapel.
  • Score: Elke speler verdient 1 punt per genomen steen.
  • Bonus: De speler die de laatste steen neemt, krijgt een extra bonus van $N$ punten.
  • Doel: De speler met het hoogste totale aantal punten wint. De analyse richt zich op het maximaliseren van het verschil in score: $Payoff = (\text{Score Speler 1}) - (\text{Score Speler 2})$.

• Recursieve Analyse:
  De kern van de analyse is de definitie van een payoff-functie $f_N(p)$, waarbij $p$ de spelpositie is. Deze functie wordt recursief gedefinieerd via de minimax-methode:
  $$f_N(p) = \max_{p \to p'} \{ |p| - |p'| - f_N(p') \}$$
  Hierbij is $|p| - |p'|$ het aantal stenen genomen in de zet, en $f_N(p')$ de waarde voor de tegenstander vanaf de nieuwe positie. De basisgeval is $f_N(0) = -N$ (de tegenstander heeft de laatste steen genomen en de bonus gekregen).

• Analysegebieden:

  1. Twee stapels: Afleiding van expliciete formules voor posities $(x, y)$.
  2. Drie stapels: Analyse van posities $(x, y, 1)$ en $(x, y, z)$, met name de afhankelijkheid van $N$.
  3. **Grenzen van $N:** Onderzoek naar het gedrag wanneer$N \to \infty$(normale Nim),$N \to -\infty$(misère Nim) en$N \approx 0$ (puur scoregericht).

3. Belangrijkste Bijdragen en Resultaten

A. Generalisatie van Bestaande Spellen
Scoring Nim fungeert als een brug tussen verschillende spelvarianten:

• Als $N = \infty$, gedraagt het spel zich als Normale Nim (focus op het nemen van de laatste steen).
• Als $N = -\infty$, gedraagt het spel zich als Misère Nim (focus op het vermijden van de laatste steen).
• Als $N = 0$, is het een puur "greedy" spel waarbij spelers proberen zoveel mogelijk stenen te nemen, ongeacht wie de laatste neemt.
• Voor eindige $N$ ontstaan er intermediaire strategieën die noch puur Nim-gebaseerd, noch puur greedy zijn.

B. Eigenschappen van de Payoff-functie

• Continuïteit en Helling: De functie $f_N(p)$ is continu in $N$. Voor niet-gehele waarden van $N$ is de helling van de grafiek altijd $1$of$-1$. Dit betekent dat de optimale strategie (wie de laatste steen neemt) alleen verandert bij specifieke "knelpunten" (breakpoints).
• Pariteit: Voor gehele $N$ heeft de payoff dezelfde pariteit als $|p| + N$.

C. Expliciete Formules voor Twee Stapels
Voor twee stapels $(x, y)$ met $x \ge y \ge 2$ hebben de auteurs een gesloten formule afgeleid:
$$f_N(x, y) = x - y + |1 - |1 + N||$$
Dit toont aan dat de optimale zet afhangt van de grootte van $N$:

• Bij grote positieve $N$: Spelers proberen de Nim-som gelijk te maken (Nim-strategie).
• Bij $N \approx 0$: Spelers nemen alle stenen uit de grootste stapel (greedy strategie).

D. Complexiteit bij Drie Stapels en Breakpoints
Voor drie stapels, specifiek posities van het type $(2k+1, 2k, 1)$, ontdekten de auteurs een complexe structuur:

• De payoff-functie $f_N(2k+1, 2k, 1)$ wordt beschreven door een functie $F_k(N)$ die gedefinieerd is op basis van een verzameling gehele getallen $J_k$.
• Aantal Breakpoints: Het aantal punten waar de helling van de grafiek verandert (breakpoints) is gelijk aan $4k - 3$. Dit betekent dat het aantal strategische overgangen lineair toeneemt met het aantal stenen, wat de complexiteit van het spel aanzienlijk verhoogt vergeleken met klassieke Nim.
• De optimale zet hangt af van hoe dicht $N$ ligt bij even getallen in een bepaald bereik. Spelers proberen de tegenstander in een positie te dwingen waar de payoff minimaal is.

E. Symmetrie
De auteurs tonen aan dat hoewel de payoff-functie voor sommige symmetrische posities (zoals $(x, x, z)$) symmetrisch is rond $N = -1$, de algemene functie niet noodzakelijk symmetrisch is rond $N=0$ of $N=-1$.

4. Significantie en Implicaties

• Theoretische Uitbreiding: Het artikel biedt een wiskundig onderbouwd raamwerk voor scoring games binnen de combinatorische speltheorie. Het toont aan dat het introduceren van een score (in plaats van alleen win/verlies) leidt tot een continuüm van strategieën in plaats van een binair resultaat.
• Strategische Nuance: Het onderzoek onthult dat de "beste" zet niet statisch is, maar dynamisch verandert afhankelijk van de bonuswaarde $N$. Dit introduceert een nieuwe laag van complexiteit waarbij spelers moeten balanceren tussen het maximaliseren van directe punten en het manipuleren van de bonus-uitkomst.
• Toepassingsmogelijkheden: Hoewel het een theoretisch spel is, biedt Scoring Nim inzicht in situaties waar beloningen niet alleen afhangen van de einduitslag, maar ook van de tussenliggende prestaties (bijvoorbeeld in economische modellen of algoritmen voor resource allocation).
• Onderzoekspad: De ontdekking van het grote aantal breakpoints suggereert dat het analyseren van scoring games met meer stapels of complexere bonusstructuren een rijk en uitdagend onderzoeksgebied blijft.

Conclusie
Oginuma en Shinoda hebben met "Scoring Nim" een krachtige generalisatie van het klassieke Nim-spel gepresenteerd. Door de bonus $N$ als variabele parameter te behandelen, hebben ze de overgang tussen winst/verlies-strategieën en score-maximalisatie-strategieën kwantitatief in kaart gebracht. Hun werk levert expliciete formules voor kleine aantallen stapels en onthult een fascinerende, complexe structuur van optimale strategieën voor grotere spelposities.