Kombinatorisk spilteori

Kombinatorisk spilteori, også kendt som CGT, er en gren af anvendt matematik og teoretisk datalogi, der studerer kombinatoriske spil, og adskiller sig fra "traditionel" eller "økonomisk" spilteori. CGT opstod i forbindelse med teorien om upartiske spil, især Nim-spillet for to spillere, med vægt på at "løse" visse typer af kombinatoriske spil.

Et spil skal opfylde flere betingelser for at være et kombinatorisk spil. Disse betingelser er:

  1. Spillet skal have mindst to spillere.
  2. Spillet skal være sekventielt (dvs. at spillerne skiftes til at spille på skift).
  3. Spillet skal have perfekt information (dvs. ingen information er skjult, som i poker.)
  4. Spillet skal være deterministisk (dvs. ikke tilfældigt). Held er ikke en del af spillet.
  5. Spillet skal have et bestemt antal mulige træk.
  6. Spillet skal slutte til sidst.
  7. Spillet skal slutte, når en af spillerne ikke længere kan bevæge sig.

Kombinatorisk spilteori er stort set begrænset til studiet af en delmængde af kombinatoriske spil med to spillere, som er begrænsede, og som har en vinder og en taber (dvs. ikke ender uafgjort).

Disse kombinatoriske spil kan repræsenteres ved træer, hvor hvert toppunkt er det spil, der er resultatet af et bestemt træk fra det spil, der ligger direkte under det på træet. Disse spil kan tildeles spilværdier. Det er af stor interesse for CG-teoretikere at finde disse spilværdier, ligesom det teoretiske begreb spiladdition er af stor interesse. Summen af to spil er det spil, hvor hver spiller på sin tur kun må flytte i det ene af de to spil og lade det andet spil forblive som det var.

Elwyn Berlekamp, John Conway og Richard Guy er grundlæggerne af teorien. De arbejdede sammen i 1960'erne. Deres offentliggjorte arbejde hed Winning Ways for Your Mathematical Plays.

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}{\displaystyle L} er de spil, som den venstre spiller kan flytte til. R {\displaystyle R}{\displaystyle 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 \}} {\displaystyle \{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:

  1. Der er nul eller flere bunker af tællere.
  2. På en tur kan en spiller tage så mange brikker fra en bunke, som han ønsker.
  3. 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.

AlegsaOnline.com - 2020 / 2023 - License CC3