Kombinatorická teória hier

Kombinatorická teória hier, známa aj ako CGT, je odvetvie aplikovanej matematiky a teoretickej informatiky, ktoré skúma kombinatorické hry a odlišuje sa od "tradičnej" alebo "ekonomickej" teórie hier. CGT vznikla v súvislosti s teóriou nestranných hier, najmä hry Nim pre dvoch hráčov, s dôrazom na "riešenie" určitých typov kombinatorických hier.

Aby hra bola kombinatorickou hrou, musí spĺňať niekoľko podmienok. Sú to:

V hre musia byť aspoň dvaja hráči.
Hra musí byť postupná (t. j. hráči sa striedajú v ťahoch).
Hra musí mať dokonalé informácie (t. j. žiadne informácie nie sú skryté, ako v pokri.)
Hra musí byť deterministická (t. j. bez náhody). Šťastie nie je súčasťou hry.
Hra musí mať definovaný počet možných ťahov.
Hra sa nakoniec musí skončiť.
Hra musí skončiť, keď sa jeden z hráčov už nemôže pohybovať.

Teória kombinatorických hier sa zväčša obmedzuje na štúdium podmnožiny kombinatorických hier, ktoré sú pre dvoch hráčov, sú konečné a majú víťaza a porazeného (t. j. nekončia remízou).

Tieto kombinatorické hry možno reprezentovať stromami, ktorých každý vrchol je hra vyplývajúca z určitého ťahu z hry, ktorá sa nachádza priamo pod ním na strome. Týmto hrám možno priradiť herné hodnoty. Hľadanie týchto herných hodnôt je pre teoretikov CG veľmi zaujímavé, rovnako ako teoretický koncept sčítania hier. Súčet dvoch hier je hra, v ktorej každý hráč vo svojom ťahu musí vykonať ťah len v jednej z týchto dvoch hier a druhú ponechať tak, ako bola.

Elwyn Berlekamp, John Conway a Richard Guy sú zakladateľmi tejto teórie. Spolupracovali na nej v 60. rokoch 20. storočia. Ich publikovaná práca sa volala Víťazné spôsoby pre vaše matematické hry.

Definície

V teórii sú dvaja hráči nazývaní ľavá a pravá strana. Hra je niečo, čo umožňuje ľavici a pravici vykonávať ťahy do iných hier. Napríklad v šachovej hre existuje zvyčajné východiskové rozostavenie. O šachovej hre by sa však dalo uvažovať aj po prvom ťahu ako o inej hre s iným nastavením. Každá pozícia sa teda tiež nazýva hra.

Hry majú zápis {L|R}. L {\displaystyle L} $L$ sú hry, do ktorých sa môže ľavý hráč presunúť. R {\displaystyle R} $R$ sú hry, do ktorých sa môže presunúť pravý hráč. Ak poznáte šachovú notáciu, potom je obvyklým šachovým usporiadaním hra

{ 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 \}$

Bodky "..." znamenajú, že je veľa ťahov, preto nie sú zobrazené všetky.

Šach je veľmi zložitý. Je lepšie myslieť na jednoduchšie hry. Napríklad Nim je oveľa jednoduchší. Nim sa hrá takto:

Existuje nula alebo viac hromádok počítadiel.
V jednom ťahu si hráč môže vziať z jednej hromádky toľko žetónov, koľko chce.
Hráč, ktorý nemôže vykonať ťah, prehráva.

Najjednoduchšia hra Nim začína bez počítadiel! V takom prípade sa ani jeden z hráčov nemôže pohnúť. To je znázornené ako {|}. Obe strany sú prázdne, pretože ani jeden z hráčov sa nemôže pohnúť. Prvý hráč, ktorý sa pohne, sa nemôže pohnúť, a preto prehrá. V CGT sa často píše {|} ako symbol 0 (nula).

Ďalšia najjednoduchšia hra má len jednu hromádku s jedným počítadlom. Ak ide ľavý hráč ako prvý, musí si vziať počítadlo, pričom pravý hráč nemá žiadny ťah ({|} alebo 0). Ak namiesto toho pravý ťahá ako prvý, ľavý už nebude mať žiadne ťahy. Ľavý aj pravý hráč teda môžu urobiť ťah na 0. Ten sa zobrazí ako {{|}|{|}}, alebo {0|0}. Hráč, ktorý sa pohne ako prvý, vyhrá. Hry rovné {0|0} sú veľmi dôležité. Sú zapísané symbolom * (hviezdička).

Otázky a odpovede

Otázka: Čo je kombinatorická teória hier?

Odpoveď: Teória kombinatorických hier (CGT) je odvetvie aplikovanej matematiky a teoretickej informatiky, ktoré skúma kombinatorické hry a líši sa od "tradičnej" alebo "ekonomickej" teórie hier.

Otázka: Aké podmienky musí hra spĺňať, aby sa považovala za kombinatorickú hru?

Odpoveď: Aby sa hra považovala za kombinatorickú hru, musí mať aspoň dvoch hráčov, musí byť sekvenčná (t. j. hráči sa striedajú v ťahoch), musí mať dokonalé informácie (t. j. žiadne informácie nie sú skryté), musí byť deterministická (t. j. bez náhody), šťastie nemôže byť súčasťou hry, musí existovať definovaný počet možných ťahov, hra musí nakoniec skončiť a hra musí skončiť, keď jeden z hráčov už nemôže ťahať.

Otázka: Na aký typ hier sa zameriava kombinatorická teória hier?

Odpoveď: Teória kombinatorických hier sa zameriava najmä na konečné hry pre dvoch hráčov, ktoré majú víťazov a porazených (t. j. nekončia remízou).

Otázka: Ako sú tieto typy hier reprezentované?

Odpoveď: Tieto typy hier sa dajú reprezentovať stromami, pričom každý vrchol predstavuje výslednú hru z určitého ťahu priamo pod ním na strome.

Otázka: Aké sú ciele teoretikov CG?

A: Medzi ciele teoretikov CG patrí nájdenie hodnôt pre tieto typy hier, ako aj pochopenie konceptu "sčítania hier", ktorý zahŕňa, že každý hráč urobí iba jeden ťah v dvoch rôznych hrách, pričom ostatné hry sa počas jeho ťahu nezmenia.

Otázka: Kto založil CGT?

Odpoveď: Elwyn Berlekamp, John Conway a Richard Guy sa zaslúžili o založenie CGT vo svojej publikovanej práci s názvom Winning Ways for Your Mathematical Plays v 60. rokoch 20. storočia.