Poziční hra - Positional game

A poziční hra^[1][2] je druh a kombinatorická hra pro dva hráče. Popisuje to:

• ${ displaystyle X}$ - a konečná množina prvků. Často ${ displaystyle X}$ se nazývá prkno a jeho prvky se nazývají pozic.
• ${ displaystyle { mathcal {F}}}$ - a rodina podmnožin z ${ displaystyle X}$. Tyto podskupiny se obvykle nazývají výherní sady.
• Kritérium pro vítězství ve hře.

Během hry si hráči střídavě nárokují dříve nevyzvednuté pozice, dokud jeden z hráčů nevyhraje. Pokud jsou všechny pozice v ${ displaystyle X}$ jsou odebírány, dokud nevyhraje žádný hráč, hra se považuje za remízu.

Klasickým příkladem poziční hry je Piškvorky. V tom ${ displaystyle X}$ obsahuje 9 čtverců herního plánu, ${ displaystyle { mathcal {F}}}$ obsahuje 8 řádků, které určují vítězství (3 vodorovné, 3 svislé a 2 úhlopříčné), a kritérium vítězství je: vyhrává první hráč, který drží celou výherní sadu. Další příklady pozičních her jsou Hex a Shannon přepínání hry.

Pro každou poziční hru existují přesně tři možnosti: buď má první hráč a vítězná strategie, nebo má druhý hráč vítěznou strategii, nebo oba hráči mají strategie k vynucení remízy.^[2]:7 Hlavní otázkou zájmu o studium těchto her je, která z těchto tří možností platí v konkrétní hře.

Poziční hra je konečná, deterministická a má perfektní informace; teoreticky je tedy možné vytvořit celý herní strom a určit, která z těchto tří možností platí. V praxi však může být hra obrovská. Proto jsou poziční hry obvykle analyzovány pomocí sofistikovanějších kombinatorických technik.

Alternativní terminologie

Často je vstup do poziční hry považován za hypergraf. V tomto případě:

• Prvky ${ displaystyle X}$jsou nazývány vrcholy (nebo bodů), a označeno V;
• Prvky ${ displaystyle { mathcal {F}}}$jsou nazývány hrany (nebo hyperedges) a označeno E nebo H.

Varianty

Existuje mnoho variant pozičních her, které se liší pravidly a kritérii výher.

Různá výherní kritéria

Silná poziční hra (také nazývaná hra Maker-Maker)

vyhrává první hráč, který získal všechny prvky vítězného setu. Pokud hra končí se všemi prvky hracího plánu, ale žádný hráč nezískal všechny prvky vítězného setu, jedná se o remízu. Příkladem je klasický Piškvorky.

Hra Maker-Breaker

dva hráči se jmenují Maker a Breaker. Tvůrce vyhrává získáním všech prvků vítězného setu. Pokud hra končí s nárokovanými všemi prvky hracího plánu a Maker ještě nevyhrál, vyhrává Breaker. Remízy nejsou možné. Příkladem je Shannon přepínání hry.

Hra Avoider-Enforcer

hráči se jmenují Avoider a Enforcer. Enforcer vyhraje, pokud si někdy hráč vyhraje všechny prvky vítězného setu. Pokud hra končí se všemi nárokovanými prvky desky a Avoider si neprohlásil vítězný set, vyhrává Avoider. Stejně jako ve hře Maker Breaker není losování možné. Příkladem je Sim.

Nesrovnalost hra

hráči se jmenují Balancer a Unbalancer. Balancer vyhrává, pokud zajistí, že ve všech výherních sadách má každý hráč zhruba polovinu vrcholů. Jinak vyhrává Unbalancer.

Různá pravidla hry

Hra číšník-klient (také nazývaná hra Picker-Chooser)

hráči se jmenují číšník a klient. V každém kole si číšník vybere dvě pozice a ukáže je klientovi, který si může vybrat jednu z nich.

Předpjatá poziční hra

každá poziční hra má a předpojatý varianta, ve které si může vzít první hráč str prvky najednou a druhý hráč může vzít q prvky najednou (v nezaujaté variantě str=q=1).

Specifické hry

Následující tabulka uvádí některé konkrétní poziční hry, které byly v literatuře široce studovány.

Viz také

• Topologická hra, zobecnění poziční hry na nekonečné množiny
• Hra Banach – Mazur, hra hraná na a topologický prostor výběrem z určitých podskupin, přičemž výherní podmínky se podobají podmínkám hry tvůrce hry

Reference