Hra Avoider-Enforcer - Avoider-Enforcer game - Wikipedia

An Hra Avoider-Enforcer^[1]^:43–60 (také zvaný Hra Avoider-Forcer^[2] nebo Hra Antimaker-Antibreaker^[3]^{:bod 5.}) je druh poziční hra. Jako většina pozičních her je popsán souborem pozice / body / prvky ( ${ displaystyle X}$ ) a a rodina podmnožin ( ${ displaystyle { mathcal {F}}}$ ), které se zde nazývají prohrávající sady. Hrají ho dva hráči zvaní Avoider a Enforcer, kteří střídavě vybírají prvky, dokud nebudou všechny prvky vybrány. Vyhýbající hráč vyhraje, pokud se mu podaří vyhnout se ztrátovému setu; Enforcer vyhraje, pokud se mu podaří donutit Avoidera vzít si poražený set.

Deska pro hru Sim, hra Avoider-Enforcer

Klasickým příkladem takové hry je Sim. Tam jsou pozice všechny hrany celého grafu na 6 vrcholech. Hráči se střídají, aby stínili čáru ve své barvě, a prohrávají, když vytvoří plný trojúhelník své vlastní barvy: prohrávající sady jsou všechny trojúhelníky.

Srovnání s hrami Maker-Breaker

Vítězná podmínka hry Avoider-Enforcer je přesně opakem vítězné podmínky hry Hra Maker-Breaker na stejné ${ displaystyle { mathcal {F}}}$ . Hra Avoider-Enforcer je tedy Misere hra varianta hry Maker-Breaker. Mezi těmito typy her však existují protiintuitivní rozdíly.

Zvažte například předpojatý verze her, ve kterých hraje první hráč str prvky v každém tahu a druhý hráč bere q prvky v každé zatáčce (ve standardní verzi str= 1 a q= 1). Hry Maker-Breaker jsou předpětí monotónní: přijetí více prvků je vždy výhodou. Formálně, pokud Maker vyhraje (str:q) Hra Maker-Breaker, poté také vyhrává (str+1:q) a hra (p: q-1). Hry Avoider-Enforcer nejsou zkreslené: monotónnost více prvků není vždy disvýhoda. Zvažte například velmi jednoduchou hru Avoider-Enforcer, kde jsou prohrávající sady {w, x} a {y, z}. Poté vyhraje Avoider hru (1: 1), Enforcer vyhraje hru (1: 2) a Avoider vyhraje hru (2: 2).

Tady je monotónní varianta (str:q) Pravidla hry Avoider-Enforcer, ve kterých musí Avoider vybírat alespoň str prvky v každém tahu a Enforcer musí vybrat alespoň q prvky každé kolo; tato varianta je bias-monotónní.^[1]^:45–46

Částečné vyhýbání se

Podobně jako Hry Maker-Breaker „Hry Avoider-Enforcer také mají částečné zobecnění.

Předpokládejme, že se vyhýbající musí vyhýbat přijímání alespoň zlomku t prvků v libovolné výherní sadě (tj. vezměte maximálně 1-t prvků v libovolné sadě) a Enforcer tomu musí zabránit, tj. Enforcer musí brát méně než zlomek t prvků v některé výherní sadě. Definujte konstantu: ${ displaystyle c_ {t}: = (2t) ^ {t} cdot (2-2t) ^ {1-t} = 2 cdot t ^ {t} cdot (1-t) ^ {1-t }}$ (ve standardní variantě ${ displaystyle t = 1, c_ {t} až 2}$ ).

Li ${ displaystyle sum _ {E v { mathcal {F}}} {c_ {t}} ^ {- | E |} <1}$ , a celkový počet prvků je sudý, pak má Avoider vítěznou strategii když hrát jako první.^[3]^{:thm A5}

Viz také

Předpojatá poziční hra # Vítězná podmínka pro Vyhýbající se

Reference

^ ^A ^b Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor (2014). Poziční hry. Semináře Oberwolfach. 44. Basilej: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.
^ Bednarska-Bzdęga, Małgorzata (01.01.2014). „Hry typu Avoider-Forcer na hypergrafech s malým hodnocením“. Electronic Journal of Combinatorics. 21 (1): 1–2. ISSN 1077-8926.
^ ^A ^b Lu, Xiaoyun (1991-11-29). "Odpovídající hra". Diskrétní matematika. 94 (3): 199–207. doi:10.1016 / 0012-365X (91) 90025-W. ISSN 0012-365X.

[pg14-1] A ^b Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor (2014). Poziční hry. Semináře Oberwolfach. 44. Basilej: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.

[2] Bednarska-Bzdęga, Małgorzata (01.01.2014). „Hry typu Avoider-Forcer na hypergrafech s malým hodnocením“. Electronic Journal of Combinatorics. 21 (1): 1–2. ISSN 1077-8926.

[Lu_1991-3] A ^b Lu, Xiaoyun (1991-11-29). "Odpovídající hra". Diskrétní matematika. 94 (3): 199–207. doi:10.1016 / 0012-365X (91) 90025-W. ISSN 0012-365X.

[1]

[2]

[3]