Combinatiespel theorie

Combinatoriële speltheorie, ook wel bekend als CGT is een tak van toegepaste wiskunde en theoretische computerwetenschappen die combinatorische spelletjes bestudeert, en verschilt van de "traditionele" of "economische" speltheorie. CGT is ontstaan in relatie tot de theorie van onpartijdige spellen, het tweespelerspel van Nim in het bijzonder, met de nadruk op het "oplossen" van bepaalde soorten combinatorische spellen.

Een spel moet aan verschillende voorwaarden voldoen om een combinatorisch spel te zijn. Deze zijn:

Het spel moet minstens twee spelers hebben.
Het spel moet opeenvolgend zijn (d.w.z. dat de spelers elkaar afwisselen).
Het spel moet perfecte informatie hebben (d.w.z. dat er geen informatie verborgen is, zoals bij Poker).
Het spel moet deterministisch (d.w.z. niet-kans) zijn. Geluk is geen onderdeel van het spel.
De partij moet een bepaald aantal mogelijke zetten hebben.
Het spel moet uiteindelijk eindigen.
Het spel moet eindigen als een speler niet meer kan bewegen.

Combinatorial Game Theory is grotendeels beperkt tot de studie van een subset van combinatorische spellen die twee spelers zijn, eindig, en een winnaar en verliezer hebben (d.w.z. niet eindigen in remises).

Deze combinatorische spellen kunnen worden weergegeven door bomen, waarvan elk hoekpunt het spel is dat het resultaat is van een bepaalde beweging van het spel direct onder de boom. Aan deze spellen kunnen spelwaarden worden toegekend. Het vinden van deze spelwaarden is van groot belang voor CG-theoretici, net als het theoretische concept van speltoevoeging. De som van twee spellen is het spel waarin elke speler die aan de beurt is slechts in één van de twee spellen moet bewegen, waarbij het andere spel blijft zoals het was.

Elwyn Berlekamp, John Conway en Richard Guy zijn de grondleggers van de theorie. Ze werkten samen in de jaren zestig. Hun gepubliceerde werk heette Winning Ways for Your Mathematical Plays.

Definities

In de theorie zijn er twee spelers die links en rechts heten. Een spel is iets dat het mogelijk maakt om links en rechts te bewegen naar andere spellen. In het schaakspel is er bijvoorbeeld een gebruikelijke beginopstelling. Men zou echter ook kunnen denken aan een schaakpartij na de eerste zet als een andere partij, met een andere opzet. Elke stelling wordt dus ook wel een partij genoemd.

Spelletjes hebben de notatie {L|R}. L{\playstyle L} $L$ zijn de spellen waar de linker speler naartoe kan bewegen. R is het spel waar $R$ de rechter speler naartoe kan gaan. Als je de schaaknotatie kent, dan is de gebruikelijke schaakopzet de partij...

{ 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 , ... } Een voorbeeld van de manier waarop je het kunt afspelen. $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

De stippen "..." betekenen dat er veel bewegingen zijn, dus niet alle worden getoond.

Schaken is zeer complex. Het is beter om te denken aan gemakkelijkere spellen. Nim, bijvoorbeeld, is veel eenvoudiger om over na te denken. Nim wordt zo gespeeld:

Er zijn nul of meer stapels tellers.
In een beurt mag een speler zoveel counters van een stapel nemen als hij wil.
De speler die geen zet kan doen, verliest.

Het makkelijkste spel van Nim begint met geen enkele balie! In zo'n geval kan geen van beide spelers bewegen. Dat wordt getoond als {\an5}. Beide kanten zijn leeg, omdat geen van beide spelers kan bewegen. De eerste speler die gaat kan niet bewegen, en zal dus verliezen. In CGT schrijven mensen vaak {\an5} als symbool 0 (nul).

Het op een na makkelijkste spel heeft maar één stapel, met slechts één teller. Als de linker speler als eerste gaat, moet die speler de teller nemen, waarbij hij rechts laat staan zonder zetten ({||, of 0). Als in plaats daarvan eerst de rechtse zetten worden gedaan, zijn er geen zetten meer voor links. Dus zowel links als rechts kan een zet doen naar 0. Dat wordt getoond als {\an5}, of {\an5}. De eerste speler die een zet doet, zal winnen. Spellen gelijk aan {0|0} zijn erg belangrijk. Ze zijn geschreven met het symbool, * (ster).

Vragen en antwoorden

V: Wat is combinatorische speltheorie?

A: Combinatorische Speltheorie (CGT) is een tak van toegepaste wiskunde en theoretische computerwetenschap die combinatorische spellen bestudeert, en verschilt van de "traditionele" of "economische" speltheorie.

V: Aan welke voorwaarden moet een spel voldoen om als combinatorisch spel te worden beschouwd?

A: Om als combinatorisch spel te worden beschouwd, moet een spel ten minste twee spelers hebben, sequentieel zijn (d.w.z. de spelers wisselen elkaar af), perfecte informatie hebben (d.w.z. er is geen informatie verborgen), deterministisch zijn (d.w.z. geen toeval), geluk mag geen deel uitmaken van het spel, er moet een bepaald aantal mogelijke zetten zijn, het spel moet uiteindelijk eindigen, en het spel moet eindigen wanneer één speler geen zet meer kan doen.

V: Op wat voor soort spellen richt de combinatorische speltheorie zich?

A: Combinatorische Speltheorie richt zich voornamelijk op eindige spellen voor twee spelers die winnaars en verliezers hebben (en dus niet eindigen in remises).

V: Hoe worden dit soort spellen voorgesteld?

A: Dit soort spellen kan worden voorgesteld door bomen, waarbij elk hoekpunt het resultaat is van een bepaalde zet van de zet direct eronder in de boom.

V: Wat zijn enkele doelstellingen voor CG-theoretici?

A: Enkele doelen voor theoretici van CG zijn het vinden van waarden voor dit soort spellen en het begrijpen van het concept "speltoevoeging", waarbij elke speler slechts één zet doet in twee verschillende spellen en de andere tijdens zijn beurt onveranderd laat.

V: Wie heeft CGT opgericht?

A: Elwyn Berlekamp, John Conway en Richard Guy worden genoemd als oprichters van CGT in hun gepubliceerde werk genaamd Winning Ways for Your Mathematical Plays in de jaren 1960.