Kombinatorisk spelteori

Kombinatorisk spelteori, även kallad CGT, är en gren av tillämpad matematik och teoretisk datavetenskap som studerar kombinatoriska spel och skiljer sig från "traditionell" eller "ekonomisk" spelteori. CGT uppstod i samband med teorin om opartiska spel, särskilt Nim-spelet för två spelare, med tonvikt på att "lösa" vissa typer av kombinatoriska spel.

Ett spel måste uppfylla flera villkor för att vara 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.

Kombinatorisk spelteori är till stor del begränsad till studiet av en delmängd av kombinatoriska spel som har två spelare, är ändliga och har en vinnare och en förlorare (dvs. som inte slutar i oavgjorda matcher).

Dessa kombinatoriska spel kan representeras av träd, där varje hörn är det spel som blir resultatet av ett visst drag från det spel som ligger direkt under det i trädet. Dessa spel kan tilldelas spelvärden. Att hitta dessa spelvärden är av stort intresse för CG-teoretiker, liksom det teoretiska begreppet speladdition. Summan av två spel är det spel där varje spelare vid sin tur får flytta i endast ett av de två spelen och lämna det andra spelet oförändrat.

Elwyn Berlekamp, John Conway och Richard Guy är grundarna av teorin. De arbetade tillsammans på 1960-talet. Deras publicerade arbete hette Winning Ways for Your Mathematical Plays.

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.