Kombinatorická teorie her

Kombinatorická teorie her, známá také jako CGT, je obor aplikované matematiky a teoretické informatiky, který se zabývá kombinatorickými hrami a liší se od "tradiční" nebo "ekonomické" teorie her. CGT vznikla v souvislosti s teorií nestranných her, zejména hry pro dva hráče Nim, s důrazem na "řešení" určitých typů kombinatorických her.

Aby hra byla kombinatorickou hrou, musí splňovat několik podmínek. Jsou to:

Ve hře musí být alespoň dva hráči.
Hra musí být postupná (tj. hráči se střídají v tazích).
Hra musí mít dokonalou informovanost (tj. žádné skryté informace jako v pokeru).
Hra musí být deterministická (tj. bez náhody). Štěstí není součástí hry.
Hra musí mít definovaný počet možných tahů.
Hra musí nakonec skončit.
Hra musí skončit, když se jeden z hráčů již nemůže pohybovat.

Teorie kombinatorických her se do značné míry omezuje na studium podmnožiny kombinatorických her, které jsou pro dva hráče, jsou konečné a mají vítěze a poraženého (tj. nekončí remízou).

Tyto kombinatorické hry lze znázornit pomocí stromů, jejichž každý vrchol představuje hru, která je výsledkem určitého tahu ze hry, jež se nachází přímo pod ním na stromě. Těmto hrám lze přiřadit herní hodnoty. Nalezení těchto herních hodnot je pro teoretiky CG velmi zajímavé, stejně jako teoretický koncept sčítání her. Součet dvou her je hra, ve které každý hráč na svém tahu musí provést tah pouze v jedné z obou her a druhou ponechat tak, jak byla.

Elwyn Berlekamp, John Conway a Richard Guy jsou zakladateli této teorie. Pracovali společně v 60. letech 20. století. Jejich publikovaná práce se jmenovala Vítězné způsoby pro vaše matematické hry.

Definice

V teorii jsou dva hráči, kteří se nazývají levá a pravá strana. Hra je něco, co umožňuje levici a pravici provádět tahy do jiných her. Například v šachové hře je obvyklé výchozí rozestavení. Lze však také uvažovat o šachové partii po prvním tahu jako o jiné hře s jiným nastavením. Každá pozice se tedy také nazývá hra.

Hry mají zápis {L|R}. L {\displaystyle L} $L$ jsou hry, do kterých se může levý hráč přesunout. R {\displaystyle R} $R$ jsou hry, do kterých se může přesunout pravý hráč. Pokud znáte šachovou notaci, pak je obvyklým šachovým uspořádání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 \}$

Tečky "..." znamenají, že existuje mnoho tahů, takže nejsou zobrazeny všechny.

Šachy jsou velmi složité. Je lepší myslet na jednodušší hry. Například Nim je mnohem jednodušší na přemýšlení. Nim se hraje takto:

Je zde nula nebo více hromádek žetonů.
V jednom tahu si hráč může vzít z jedné hromádky tolik žetonů, kolik chce.
Hráč, který nemůže provést tah, prohrává.

Nejjednodušší hra Nim začíná bez počítadel! V takovém případě se žádný z hráčů nemůže hýbat. To je znázorněno jako {|}. Obě strany jsou prázdné, protože žádný z hráčů se nemůže pohnout. Hráč, který je na řadě jako první, se nemůže pohnout, a proto prohraje. V CGT se často píše {|} jako symbol 0 (nula).

Další nejjednodušší hra má pouze jednu hromádku s jedním počítadlem. Pokud jde levý hráč jako první, musí si vzít počítadlo a pravý hráč nemá žádný tah ({|} nebo 0). Pokud místo toho táhne jako první pravá strana, levá strana už nebude mít žádné tahy. Levá i pravá strana tedy mohou provést tah na 0. Ten se zobrazí jako {{|}|{|}}, neboli {0|0}. Vyhrává hráč, který provede tah jako první. Hry rovnající se {0|0} jsou velmi důležité. Zapisují se symbolem * (hvězdička).

Otázky a odpovědi

Otázka: Co je to teorie kombinatorických her?

Odpověď: Kombinatorická teorie her (CGT) je odvětví aplikované matematiky a teoretické informatiky, které studuje kombinatorické hry a liší se od "tradiční" nebo "ekonomické" teorie her.

Otázka: Jaké podmínky musí hra splňovat, aby byla považována za kombinatorickou hru?

Odpověď: Aby hra mohla být považována za kombinatorickou hru, musí mít alespoň dva hráče, musí být sekvenční (tj. hráči se střídají v tazích), musí mít dokonalou informaci (tj. žádná informace není skryta), musí být deterministická (tj. bez náhody), součástí hry nemůže být štěstí, musí existovat definovaný počet možných tahů, hra musí nakonec skončit a hra musí skončit, když jeden z hráčů již nemůže táhnout.

Otázka: Na jaký typ her se kombinatorická teorie her zaměřuje?

Odpověď: Teorie kombinatorických her se zaměřuje převážně na konečné hry pro dva hráče, které mají vítěze a poražené (tj. nekončí remízou).

Otázka: Jak jsou tyto typy her reprezentovány?

A: Tyto typy her lze znázornit pomocí stromů, kde každý vrchol představuje výsledek hry z určitého tahu přímo pod ním na stromě.

Otázka: Jaké jsou cíle teoretiků CG?

A: Mezi cíle teoretiků CG patří nalezení hodnot pro tyto typy her a také pochopení konceptu "sčítání her", který spočívá v tom, že každý hráč provede pouze jeden tah ve dvou různých hrách, přičemž druhý tah se během jeho tahu nezmění.

Otázka: Kdo založil CGT?

A: Elwyn Berlekamp, John Conway a Richard Guy se zasloužili o založení CGT ve svém publikovaném díle s názvem Winning Ways for Your Mathematical Plays v 60. letech 20. století.