Argument o kradení strategie

Technology

12 hours ago

Author

Argument o kradení strategie (anglicky strategy stealing) je matematická věta z oboru kombinatorické teorie her, která praví, že v každé silné poziční hře má začínající hráč neprohrávající strategii. Staví na jednoduché úvaze, sporu:

: Kdyby měl druhý hráč vyhrávající strategii, mohl by začínající hráč odehrát svůj tah na libovolné (náhodné místo) a dál hrát podle vyhrávající strategie druhého hráče. Počáteční tah mu v ní určitě bude překážet, protože určitě nezpůsobí jeho prohru (hra je silná poziční) a pokud mu strategie nařídí zahrát na místo, kde tento počáteční tah leží, prostě zahraje na libovolné jiné místo. +more Tímto postupem by tedy musel vyhrát, ale to by bylo ve sporu s tím, že začínal a že převzatá strategie druhého hráče je skutečně vyhrávající.

Další výsledky (např. Hales-Jewettova věta, nebo obecně věty Ramseyovské teorie) mohou takový argument zesílit tak, že označí hry, ve kterých má začínající hráč zaručenou existenci vyhrávající strategie. +more Věta dál postuluje existenci neprohrávající strategie, nenaznačuje však, jak se k ní dostat (je nekonstruktivní), což představuje další práci pro matematiky zkoumající jednotlivé hry.

Tento výrok se dá aplikovat kupříkladu na piškvorky, jak v prostorově omezené, tak i v neomezené variantě. Výrok se vztahuje jen na poziční hry, tj. +more dosti speciální třídu matematických her. Nevyslovuje se například o šachách.

Příklady aplikace argumentu

Piškvorky

Pro piškvorky na omezené i neomezené hrací ploše existuje neprohrávající strategie pro začínajícího hráče. Důkaz plyne zhruba následovně:

* Nechť (pro spor) existuje výherní strategie nezačínajícího hráče. Budeme chtít využít (ukradnout) tuto strategii pro hráče začínajícího. +more * První piškvorku nechť první hráč zahraje na libovolné pole. Tomuto tahu budeme říkat tah zahozený. * Každý další tah nechť začínající hraje podle hypotetické vyhrávající strategie druhého hráče pro hru bez zahozeného tahu, tedy pro hru, v ní původně nezačínající hráč začíná (původně až druhým tahem). Pokud mu strategie určí zahrát do zahozeného tahu (který jí byl předložen jako neobsazený), nechť hráč zahraje na libovolné neobsazené pole a tento tah si dále pamatuje jako zahozený (tj. pamatuje si hru, jako by úvodní zbytečný tah zahrál na toto nové místo a původní zahozený tah zahrál až ve chvíli, kdy byl diktován ukradenou strategií). * Byla-li strategie nezačínajícího hráče vítězná, musí být vítězná také tato pozměněná strategie. Nemůže však existovat vítězná strategie jak pro hráče začínajícího, tak pro nezačínajícího: to je kýžený spor.