Introduktion till kombinatorisk spelteori: regler, spelvärden och Nim

Introduktion till kombinatorisk spelteori: lär dig regler, spelvärden och Nim — grundläggande begrepp, strategier och analys för tvåspelars kombinatoriska spel.

Författare: Leandro Alegsa

25-03-2026 19:16

Kombinatorisk spelteori, även kallad CGT, är en gren av tillämpad matematik och teoretisk datavetenskap som studerar kombinatoriska spel och deras matematiska struktur. Den skiljer sig från "traditionell" eller "ekonomisk" spelteori genom fokus på exakta lösningar och algoritmer för tvåspelarsituationer utan slump eller dold information. CGT växte fram ur studiet av opartiska (impartial) spel, särskilt Nim-spelet för två spelare, och intresserar sig framför allt för att "lösa" spel — det vill säga att bestämma vilka positioner är vinnande och vilka dragen som leder till vinst.

Ett spel måste uppfylla flera villkor för att räknas som ett kombinatoriskt spel. Dessa är:

Spelet måste ha minst två spelare.
Spelet måste vara sekventiellt (dvs. spelarna turas om att spela).
Spelet måste ha perfekt information (dvs. ingen information är dold, som i poker).
Spelet måste vara deterministiskt (dvs. inte slumpmässigt). Tur är inte en del av spelet.
Spelet måste ha ett definierat antal möjliga drag.
Spelet måste till slut avslutas.
Spelet måste avslutas när en spelare inte längre kan röra sig.

Dessa villkor innebär att CGT i praktiken ofta studerar ändliga tvåspelsspel där det finns en tydlig vinnare och förlorare (normalt enligt "normal play"-regeln: den som inte kan göra ett drag förlorar). Det finns också varianter, t.ex. "misère"-regeln, där sista draget ger förlust — sådana varianter förändrar ofta analysen och kräver särskild behandling.

Spelträd, N- och P-positioner

Kombinatoriska spel representeras vanligtvis med spelträd: varje nod är en spelposition och varje kant är ett tillåtet drag till en ny position. Terminala noder är positioner utan vidare drag. Ett grundläggande koncept är indelningen i N-positioner (Next player win — nästa spelare har en vinstplan) och P-positioner (Previous player win — föregående spelare kan tvinga en vinst om båda spelar optimalt). Dessa klasser bestäms rekursivt: terminala positioner där nästa spelare inte kan röra sig är P-positioner (efter normal play), och en position är N om det finns åtminstone ett drag till en P-position; annars är den P.

Spelvärden och addition av spel

Utöver att avgöra vinst/förlust kan positioner tilldelas strikt definierade spelvärden. För opartiska spel leder analysen ofta till så kallade nimbers (eller Grundy-tal) som fungerar som element i ett algebraiskt system där summan av spel definieras som ett spel där på sin tur får spelaren välja att spela i exakt ett av delspelen. Detta kallas disjunktiv summa (spelsumman) och är centralt för strategin i sammansatta spel.

Opartiska spel och Sprague–Grundy-teoremet

I opartiska spel är samma dragmöjligheter tillgängliga för båda spelarna i varje position. Sprague–Grundy-teoremet säger att varje ändligt opartiskt spel är ekvivalent mot en enda Nim-hög av viss storlek — eller mer precist, mot en nimber (ett Grundy-tal) som är det minsta icke-negativa heltal (mex, "minimum excluded value") som inte förekommer bland Grundy-talen för positionernas följare. När man bildar summan av flera opartiska spel får man ett positionens Grundy-värde som är bitvis XOR (nim-summa) av delspelenas Grundy-tal.

Praktisk konsekvens: för en Nim-position bestående av flera högar, beräknas vägen till vinst med bitvis XOR av högarna. Om nim-summan är 0 är positionen en P-position; annars kan nästa spelare göra ett drag som ger nim-summa 0 och därmed vinna med korrekt spel.

Exempel: tre högar med storlekar 3, 4 och 5. Nim-summan är 3 ^ 4 ^ 5 = 2 (där ^ betecknar bitvis XOR). Eftersom resultatet inte är 0 är det en N-position — nästa spelare har ett vinnande drag som förändrar en hög så att nim-summan blir 0.

Observera att misère-versioner av opartiska spel (där sista draget förlorar) kräver särskild hantering och följer inte alltid samma enkla regel som normal play.

Partizanska spel, surreal numbers och spelklassificering

För partizanska spel — där spelarna har olika dragmöjligheter i vissa positioner — introducerade John Conway begreppet "game" och kopplade spel till de s.k. surrealistiska talen (surreal numbers). I denna teori kan spelvärden vara reella, infinitesimala eller "heta" (icke-numeriska) och det finns en rik algebraisk struktur: spel kan adderas, tas negativa av och reduceras till kanoniska former. Begrepp som 0, positiva/negativa spel och "fuzzy" spel (där första spelaren vinner oavsett vem det är) används för att analysera komplicerade positioner.

Strategier och beräkning

I praktiken bygger analys och spelsätt i CGT ofta på:

Att konstruera spelträdet och bestämma N- och P-positioner rekursivt.
Att beräkna Grundy-tal med mex-funktionen för opartiska spel.
Att utnyttja spelsumman: i en sammansatt position strävar man efter att göra spelvärdet (eller nim-summan) 0.
Att förenkla partizanska spel till kanoniska former eller jämföra dem med kända spelvärden (t.ex. surreal numbers).

För många intressanta spel blir träd och beräkningar snabbt stora, och man använder datorhjälp, simuleringar och teoretiska reduktioner för att nå slutsatser. CGT har också samband med algoritmer, komplexitetsteori och konstruktion av effektiva vinnande strategier.

Historik och vidare läsning

Elwyn Berlekamp, John Conway och Richard Guy var nyckelfigurer i utvecklingen av modern kombinatorisk spelteori. De samarbetade under 1960-talet och deras arbete kulminerade i den klassiska boken Winning Ways for Your Mathematical Plays, som systematiserar många av teorins metoder och exempel. Deras forskning har öppnat för vidare utveckling inom både opartiska och partizanska spel, inklusive formaliseringar som Sprague–Grundy-teoremet och Conways teori om spel och surreal numbers (publicerade verk).

Sammanfattningsvis erbjuder kombinatorisk spelteori ett kraftfullt ramverk för att analysera turordningsbaserade, deterministiska spel med perfekt information. Genom begrepp som spelträd, N/P-positioner, Grundy-tal och spelsumma kan man både förstå varför vissa positioner är vinnande och konstruera effektiva strategier för att vinna dem.

Definitioner

I teorin finns det två spelare som kallas vänster och höger. Ett spel är något som gör det möjligt för vänster och höger att göra drag till andra spel. I schackspelet finns till exempel en vanlig startuppställning. Man kan dock också tänka sig ett schackspel efter det första draget som ett annat spel, med en annan uppställning. Så varje ställning kallas också för ett parti.

Spel har beteckningen {L|R}. L {\displaystyle L} $L$ är de spel som den vänstra spelaren kan flytta till. R {\displaystyle R} $R$ är de spel som den högra spelaren kan flytta till. Om du kan schacknotering är den vanliga schackuppställningen spelet

{ a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\displaystyle \{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}} $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

Punkterna "..." betyder att det finns många drag, så alla visas inte.

Schack är mycket komplext. Det är bättre att tänka på enklare spel. Nim, till exempel, är mycket enklare att tänka på. Nim spelas så här:

Det finns noll eller fler högar med räknare.
Under en tur får en spelare ta så många brickor från en hög som han eller hon vill.
Den spelare som inte kan göra ett drag förlorar.

Det enklaste spelet Nim startar utan några räknare alls! I ett sådant fall kan ingen av spelarna röra sig. Det visas som {|}. Båda sidorna är tomma, eftersom ingen av spelarna kan röra sig. Den första spelaren kan inte röra sig och förlorar därför. I CGT skriver man ofta {|} som symbolen 0 (noll).

Det näst enklaste spelet har bara en hög med bara en räknare. Om den vänstra spelaren går först måste den spelaren ta brickan, vilket innebär att höger inte får några drag ({|}, eller 0). Om istället höger flyttar först finns det inga fler drag för vänster. Så både vänster och höger kan göra ett drag till 0. Det visas som {{|}|{|}}}, eller {0|0}. Den spelare som flyttar först vinner. Spel som är lika med {0|0} är mycket viktiga. De skrivs med symbolen, * (stjärna).

Frågor och svar

F: Vad är kombinatorisk spelteori?

S: Kombinatorisk spelteori (CGT) är en gren av tillämpad matematik och teoretisk datavetenskap som studerar kombinatoriska spel och skiljer sig från "traditionell" eller "ekonomisk" spelteori.

F: Vilka villkor måste ett spel uppfylla för att betraktas som ett kombinatoriskt spel?

S: För att ett spel ska betraktas som ett kombinatoriskt spel måste det ha minst två spelare, det måste vara sekventiellt (dvs. spelarna turas om), det måste ha perfekt information (dvs. ingen information är dold), det måste vara deterministiskt (dvs. ingen slump), tur kan inte vara en del av spelet, det måste finnas ett definierat antal möjliga drag, spelet måste så småningom ta slut, och spelet måste ta slut när en av spelarna inte längre kan flytta.

F: Vilken typ av spel fokuserar Combinatorial Game Theory på?

S: Combinatorial Game Theory fokuserar till stor del på ändliga spel med två spelare som har vinnare och förlorare (dvs. som inte slutar oavgjort).

F: Hur representeras dessa typer av spel?

S: Dessa typer av spel kan representeras av träd där varje hörn representerar det spel som blir resultatet av ett visst drag från det drag som ligger direkt under det i trädet.

F: Vilka är några mål för CG-teoretiker?

S: Några av målen för CG-teoretiker är att hitta värden för dessa typer av spel samt att förstå begreppet "game addition" som innebär att varje spelare bara gör ett drag i två olika spel och lämnar det andra oförändrat under sin tur.

F: Vem grundade CGT?

S: Elwyn Berlekamp, John Conway och Richard Guy anses ha grundat CGT i deras publicerade verk Winning Ways for Your Mathematical Plays på 1960-talet.

Sök