Nim

Nim
NimGame.svg
Nim: exempel på hur tändstickorna kan läggas upp.
KategoriBrädspel

Nim är ett klassiskt sällskapsspel för två deltagare och samtidigt ett välkänt exempel på ett matematiskt spel inom kombinatorisk spelteori.

I spelet används exempelvis tändstickor, mynt eller små stenar som läggs i ett valfritt antal högar (eller rader) med valfritt antal föremål i varje hög. Spelarna turas om att ta bort ett eller flera föremål från en av högarna; ofta är det även tillåtet att ta bort en hel hög. I den vanligaste varianten vinner den som tar det sista föremålet, men spelet kan också spelas omvänt (misère), där den som tar det sista föremålet förlorar.

Nim är grundläggande för den så kallade Sprague–Grundy-satsen, som i normalspelsfallet säger att varje impartial-spel (”opartiskt” spel där båda spelarna har samma möjliga drag i varje läge) kan beskrivas som ekvivalent med en Nim-position.

Spelupplägg

En standardform av Nim spelas med flera högar. På varje drag måste spelaren ta bort minst ett föremål och får ta bort hur många som helst, så länge alla tas från samma hög. Den spelare som tar det sista föremålet vinner i normal spelvariant, medan spelaren som tar det sista föremålet förlorar i misère-varianten.

Vinnande strategi

För Nim finns en känd vinnande strategi. Charles L. Bouton publicerade 1901 en fullständig teori för normalvarianten av spelet. Den praktiska metoden bygger på att skriva varje högstorlek i binär form och beräkna den bitvisa summan utan överföringar, vanligen kallad XOR (”exklusivt eller”). Detta värde kallas ofta nim-summan.

I normalvarianten gäller att en spelare som efter sitt drag alltid lämnar en position med nim-summa 0 (om motståndaren inte gör misstag) har en vinnande strategi; om utgångsläget redan har nim-summa 0 har den spelare som står på tur en förlorande position vid perfekt spel.

I misère-varianten av Nim sammanfaller strategin med normalvarianten fram till dess att endast en enda hög har storlek större än 1; då behöver strategin justeras (i praktiken handlar det om att lämna ett udda antal ettor åt motståndaren i slutskedet).

Historia

Varianter av Nim har spelats sedan lång tid tillbaka och spelet har i litteraturen ofta beskrivits som mycket gammalt; ursprunget är osäkert och har ibland kopplats till Kina, där liknande lekar med att plocka stenar har förekommit.

Den första fullständiga matematiska teorin för spelet i modern form publicerades av Charles L. Bouton 1901. Nim blev senare ett standardexempel i populärvetenskapliga framställningar av matematiska spel, bland annat genom Martin Gardners spalt om matematiska lekar.

Matematisk teori

Nim är ett centralt exempel i kombinatorisk spelteori. I normalspelsfallet kan Nim-lägen beskrivas med så kallade nimtal (nimbers), och Nim utgör ett grundfall i Sprague–Grundy-teorin: summan av oberoende delspel kan analyseras genom att kombinera respektive nimtal med XOR.

Nim i dator- och kulturhistoria

Nim har spelats av (och implementerats på) maskiner och datorer tidigt i datorspelshistorien. På världsutställningen i New York visade Westinghouse den elektromekaniska Nim-maskinen Nimatron.

Ferranti byggde senare Nim-datorn Nimrod som visades vid Festival of Britain 1951, där spelets tillstånd visualiserades med lampor. 1952 rapporterades även om en Nim-maskin utvecklad av ingenjörer vid W. L. Maxson Corporation, som regelbundet kunde besegra mänskliga spelare.

Nim förekommer också i kultur, bland annat som symboliskt återkommande spel i filmen I fjol i Marienbad (1961).

Referenser

  1. ↑ Agostini, Franco; De Carlo, Nicola Alberto (1987). IQ-boken. Stockholm: Norstedt. sid. 146–148. ISBN 91-1-864262-4
  2. 1 2 Anker Helms Jorgensen (2009). ”Context and driving forces in the development of the early computer game Nimbi”. IEEE Annals of the History of Computing 31 (3): sid. 44–53. doi:10.1109/MAHC.2009.41.
  3. 1 2 Wennerberg, Bengt (1993). Stora spelboken. Stockholm: Prisma. sid. 67. ISBN 91-518-2537-6
  4. 1 2 3 4 5 Charles L. Bouton (1901–1902). ”Nim, a game with a complete mathematical theory”. Annals of Mathematics 3 (14): sid. 35–39. doi:10.2307/1967631.
  5. 1 2 3 Gardner, Martin (1960). Rolig matematik. Samling 1. Stockholm: Natur och kultur. sid. 146–155
  6. ↑ I. M. Yaglom (2001). Kvant Selecta: Combinatorics, I, Volume 1. American Mathematical Society. sid. 1–8. ISBN 9780821821718
  7. ↑ Rudolf Flesch (1951). The Art of Clear Thinking. New York: Harper and Brothers Publishers. sid. 3. https://archive.org/details/artofclearthinki0000rudo_y7u8
  8. ↑ Betsy Kellem (1 mars 2022). ”The Nimatron”. JSTOR Daily. https://daily.jstor.org/the-nimatron/. Läst 25 januari 2026.
  9. ↑ Tristan Donovan (2010). Replay: The History of Video Games. Yellow Ant. sid. 1–9. https://archive.org/details/replayhistoryofv0000dono
  10. ↑ Alexander Smith (2019). They Create Worlds. CRC Press. sid. 31–33
  11. ↑ ”The Talk of the Town – It”. The New Yorker. 2 augusti 1952.
  12. ↑ Bruce Morrissette (1968). ”Games and game structures in Robbe-Grillet”. Yale French Studies (41): sid. 159–167. doi:10.2307/2929672. https://archive.org/details/sim_yale-french-studies_1968_41/page/159.