AlegsaOnline.com

Kombinatorisk spilteori – definition, regler og nøglebegreber

Lær kombinatorisk spilteori: definition, regler og nøglebegreber. Fra Nim til spilværdier — forstå strategier, matematik og spiladdition trin for trin.

Forfatter: Leandro Alegsa

09-02-2026

Kombinatorisk spilteori, også kendt som CGT, er en gren af anvendt matematik og teoretisk datalogi, der studerer deterministiske, sekventielle spil med perfekt information. Den adskiller sig fra "traditionel" eller "økonomisk" spilteori ved sit fokus på at analysere konkrete bræt- eller puslespil og på at finde entydige matematiske "værdier" for stillinger og spil. CGT opstod især i forbindelse med teorien om upartiske spil, ikke mindst Nim-spillet for to spillere, og handler ofte om at "løse" spil — det vil sige at bestemme, hvilke stillinger er vindende for hvilken spiller, og hvordan man beregner kombinationer af spil.

Definition og krav

For at være et typisk kombinatorisk spil i CGT-sammenhæng skal spillet normalt opfylde en række grundlæggende betingelser. De vigtigste er:

Spillet har (som regel) to spillere.
Spillet er sekventielt: spillerne skiftes til at foretage et træk.
Spillet har perfekt information: ingen skjult information eller hemmelige hænder (modsat f.eks. poker).
Spillet er deterministisk: der indgår ikke tilfældige elementer. Held eller terningekast er ikke en del af spillets regler.
Der er et veldefineret antal mulige træk i enhver given stilling (ingen uendelige valgmuligheder i et enkelt træk).
Spillet ender efter et endeligt antal træk (ingen uendelige løkker i normal-play-udgave).
Under normal-play-reglen slutter spillet, når en spiller ikke længere kan foretage et lovligt træk—den spiller taber.

Bemærk, at der findes udvidelser og variationer (f.eks. loopy spil, spil med chance eller flere spillere), men størstedelen af klassisk CGT begrænser sig til finitte, to-personers, deterministiske spil uden skjult information.

Impartial vs. partizan spil

En central sondring i CGT er mellem upartiske (impartial) og partizan spil:

Upartiske spil: de to spillere har de samme trækmuligheder i en given stilling. Her gælder Sprague–Grundy-teoremet: enhver stilling kan tildeles et grundtal eller nimber (Grundy-tal), og summen af upartiske spil svarer til Nim-heap-summer. Det gør mange upartiske spil praktisk muligt at "løse".
Partizan spil: de to spillere (ofte kaldet Left og Right) har forskellige trækmuligheder. Disse spil analyseres med en mere omfattende teori, introduceret af bl.a. John Conway, hvor spil kan tildeles mere generelle "værdier" — inklusive tal, infinitesimals og det specielle symbol * (fuzzy-værdi).

Spil som træer og spiladdition

I CGT repræsenteres en stilling ofte som et spiltræ, hvor hver node svarer til en stilling, og hver kant er et træk til en efterfølgende stilling. Hvert spil kan formelt beskrives ved sine Left- og Right-muligheder: G = {GL | GR}.

Et af de vigtigste begreber er summen (disjunktiv sum) af to spil: summen G + H er det spil, hvor en spiller på sin tur må lave et træk i enten G eller H, men ikke i begge samtidig. At kunne beregne summen af spil og kende hver dels "værdi" er centralt for at afgøre, hvem der vinder i det kombinerede spil.

Spilværdier og klassifikation

I CGT tilskrives stillinger typiske typer af værdier:

Tal: reelle eller surrealistiske tal svarer til stillinger, hvor det er fordelagtigt for en bestemt spiller (positive tal for Left, negative for Right).
Fuzzy-værdier (fx *): stillinger som er fordelagtige for den spiller, der starter (førstespillerfordel) — de er hverken positive, negative eller nul.
Infinitesimals: meget små værdier, som kan påvirke resultatet når de kombineres med andre spil.

CGT arbejder også med begreber som outcome-klasser (f.eks. N- og P-stillinger for upartiske spil — Next-player win vs Previous-player win; og for partizan spil: Left-win, Right-win, Next-win eller Previous-win), samt værktøjer til at forenkle spiltræer ved at fjerne dominerede eller reversible træk og dermed finde en kanonisk form.

Vigtige resultater og teoremer

Sprague–Grundy-teoremet: enhver position i et finit upartisk normal-play spil er ækvivalent med en Nim-heap (et nimber), og summen af upartiske spil beregnes ved XOR af nimbers.
Conways teori: for partizan spil udviklede John Conway en omfattende teori, der forbinder spil med surrealistiske tal og giver et regelsæt for hvordan spilværdier kan kombineres og sammenlignes.
Complexitet: mange beslutningsproblemer i CGT er beregningsmæssigt svære; bestemme vinderen i et generelt bipartizan spil kan fx være PSPACE-komplet.

Eksempler på spil og anvendelser

Typiske spil studeret i CGT omfatter Nim, Hackenbush, Domineering, Kayles, Dawson's Kayles og mange puslespil. CGT giver både konkrete strategier (hvordan vinde i en given stilling) og et teoretisk sprog til at sammenligne spil og deres kombinationer.

Historie og centrale værker

Elwyn Berlekamp, John Conway og Richard Guy er blandt grundlæggerne af den moderne kombinatoriske spilteori. De begyndte at arbejde sammen i 1960'erne, og deres mest kendte arbejde blev udgivet under titlen Winning Ways for Your Mathematical Plays. John Conway skrev desuden On Numbers and Games, hvor han udviklede mange af de grundlæggende ideer om spilværdier og surrealistiske tal.

Afsluttende bemærkninger

Kombinatorisk spilteori kombinerer konkret spilanalyse med dyb matematisk struktur. For upartiske spil giver Sprague–Grundy-metoden en praktisk vej til løsning, mens partizan spil fører til et rigt sæt begreber (værdier, temperatur, kanoniske former), som gør det muligt at forstå, sammenligne og summere spil på en systematisk måde. Feltet har både teoretisk interesse og praktiske anvendelser i spilanalyse, algoritme-design og rekreativ matematik.

Definitioner

I teorien er der to spillere, der hedder venstre og højre. Et spil er noget, der gør det muligt for venstre og højre at foretage træk til andre spil. I skakspillet er der f.eks. en sædvanlig startopstilling. Man kan dog også tænke på et skakspil efter det første træk som et andet spil med en anden opstilling. Så hver stilling kaldes også et spil.

Spil har betegnelsen {L|R}. L {\displaystyle L} $L$ er de spil, som den venstre spiller kan flytte til. R {\displaystyle R} $R$ er de spil, som den højre spiller kan flytte til. Hvis du kender skaknotationen, er den sædvanlige skakopstilling spillet

{ 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 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\displaystyle \{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b6,b5,c6,c5,Nc6,\dots \}} $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

Punkterne "..." betyder, at der er mange træk, så de er ikke alle vist.

Skak er meget komplekst. Det er bedre at tænke på lettere spil. Nim er f.eks. meget nemmere at tænke på. Nim spilles på denne måde:

Der er nul eller flere bunker af tællere.
På en tur kan en spiller tage så mange brikker fra en bunke, som han ønsker.
Den spiller, der ikke kan foretage et træk, taber.

Det letteste spil Nim starter uden nogen tællere overhovedet! I et sådant tilfælde kan ingen af spillerne flytte sig. Det er vist som {|}. Begge sider er tomme, fordi ingen af spillerne kan flytte. Den første spiller kan ikke flytte sig, og vil derfor tabe. I CGT skriver man ofte {|} som symbolet 0 (nul).

Det næstletteste spil har kun én bunke med kun én tæller. Hvis den venstre spiller går først, skal denne spiller tage brikken, så højre spiller ikke har nogen træk ({|}, eller 0). Hvis i stedet højre spiller først, er der ikke flere træk for venstre. Så både venstre og højre kan foretage et træk til 0. Det er vist som {{|}|{|}}}, eller {0|0}. Den spiller, der først trækker, vinder. Spil svarende til {0|0} er meget vigtige. De er skrevet med symbolet, * (stjerne).

Spørgsmål og svar

Spørgsmål: Hvad er kombinatorisk spilteori?

A: Kombinatorisk spilteori (CGT) er en gren af anvendt matematik og teoretisk datalogi, der studerer kombinatoriske spil, og som adskiller sig fra "traditionel" eller "økonomisk" spilteori.

Spørgsmål: Hvilke betingelser skal et spil opfylde for at blive betragtet som et kombinatorisk spil?

A: For at et spil kan betragtes som et kombinatorisk spil, skal det have mindst to spillere, det skal være sekventielt (dvs. spillerne skiftes til at spille på skift), det skal have perfekt information (dvs. ingen information er skjult), det skal være deterministisk (dvs. ikke tilfældigt), held kan ikke være en del af spillet, der skal være et bestemt antal mulige træk, spillet skal ende på et tidspunkt, og spillet skal slutte, når en spiller ikke længere kan flytte.

Spørgsmål: Hvilken type spil fokuserer kombinatorisk spilteori på?

Svar: Kombinatorisk spilteori fokuserer i høj grad på endelige spil med to spillere, som har vindere og tabere (dvs. som ikke ender uafgjort).

Spørgsmål: Hvordan er disse typer spil repræsenteret?

A: Disse typer af spil kan repræsenteres ved træer, hvor hvert toppunkt repræsenterer det spil, der opstår ved et bestemt træk fra det træk, der ligger direkte under det på træet.

Spørgsmål: Hvad er nogle af målene for CG-teoretikere?

A: Nogle af målene for CG-teoretikere er bl.a. at finde værdier for disse typer spil og at forstå begrebet "spiladdition", som indebærer, at hver spiller kun foretager ét træk i to forskellige spil og lader det andet spil forblive uændret i deres tur.

Spørgsmål: Hvem grundlagde CGT?

A: Elwyn Berlekamp, John Conway og Richard Guy er krediteret for at have grundlagt CGT i deres offentliggjorte arbejde kaldet Winning Ways for Your Mathematical Plays i 1960'erne.