Předpjatá poziční hra - Biased positional game

A zaujatá poziční hra^{[1][2]:27–42} je varianta a 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 obvykle nazývají výherní sady. Hrají ho dva hráči, kteří střídavě vybírají prvky, dokud nejsou všechny prvky vybrány. Zatímco ve standardní hře si každý hráč vybere jeden prvek za kolo, ve zkreslené hře si každý hráč vezme jiný počet prvků.

Formálněji, pro každé dvě kladná celá čísla str a q„Polohová hra (p: q) je hra, ve které si vybere první hráč str prvků za kolo a druhý hráč si vybere q prvků za kolo.

Hlavní otázkou zájmu ohledně zaujatých pozičních her je, jaké jsou práh zkreslení - jaké je zkreslení, ve kterém výherní síla přechází z jednoho hráče na druhého.

Příklad

Jako příklad zvažte trojúhelníková hra. V této hře jsou prvky všechny hrany a kompletní graf na n vrcholy a výherní sady jsou všechny trojúhelníky (= kliky na 3 vrcholech). Předpokládejme, že to budeme hrát jako Hra Maker-Breaker, tj. cílem Makera (prvního hráče) je vzít trojúhelník a cílem Breakeru (druhého trojúhelníku) je zabránit Makerovi vzít trojúhelník. Pomocí jednoduché analýzy případů lze dokázat, že Maker má vítěznou strategii kdykoli n je minimálně 6. Proto je zajímavé se zeptat, zda může být toto zvýhodnění ovlivněno tím, že necháme Breaker vybrat více než 1 prvek za kolo.

Je skutečně možné prokázat, že:^[1]

• Pro každého ${ displaystyle q leq 0,5 { sqrt {n}}}$, Maker vyhrává (1:q) trojúhelníková hra zapnuta n vrcholy.
• Pro každého ${ displaystyle q geq 2 { sqrt {n}}}$, Breaker vyhraje (1:q) trojúhelníková hra zapnuta n vrcholy.

Vítězná podmínka pro Breaker

Nestranně Hra Maker-Breaker dává Erdos-Selfridgeova věta vítězná podmínka pro Breaker. Tuto podmínku lze zobecnit na zaujaté hry následovně:^{[3] [2]:30–32}

• Li ${ displaystyle sum _ {E v { mathcal {F}}} (1 + q) ^ {- | E | / p} <1}$, pak má Breaker při prvním hraní vítěznou strategii ve hře (p: q).
• Li ${ displaystyle sum _ {E v { mathcal {F}}} (1 + q) ^ {- | E | / p} <{1 nad 1 + q}}$, pak má Breaker vítěznou strategii ve hře (p: q), i když hraje druhý.

Strategie využívá potenciální funkci, která zobecnila funkci Erdos-Selfridge. Potenciál (neporušeného) výherního setu E s |E| unaken elements is defined as ${ displaystyle (1 + q) ^ {- | E | / p}}$. Pokud Maker vyhraje hru, pak existuje sada E s |E| = 0, takže jeho potenciál je 1; proto k prokázání toho, že Breaker vyhrává, stačí prokázat, že konečný součet potenciálu je menší než 1. Ve skutečnosti je předpokládaný součet potenciálu v prvním tahu Breakera menší než 1; a pokud Breaker vždy vybere prvek, který maximalizuje pokles potenciálu, je možné ukázat, že součet potenciálu vždy slabě klesá.

Když má každý výherní set ${ displaystyle k}$ prvky, pro některé pevné k„Výherní podmínka Breakera se zjednodušuje na: ${ displaystyle | { mathcal {F}} | <(q + 1) ^ {k / p}}$ (při prvním přehrávání) nebo ${ displaystyle | { mathcal {F}} | <(q + 1) ^ {k / p-1}}$(při hraní na druhém místě). Tato podmínka je přísná: existují k-jednotné set-rodiny s ${ displaystyle | { mathcal {F}} | = (q + 1) ^ {k / p-1}}$sady, kde vyhrává Maker.^[4]

Vítězná podmínka pro Maker

V nezaujaté hře Maker-Breaker dává Beckova věta pro Makera vítězná podmínka. Využívá párový stupeň hypergrafu - označený ${ displaystyle d_ {2}}$. Tuto podmínku lze zobecnit na zaujaté hry následovně:^[3]

Li ${ displaystyle sum _ {E v { mathcal {F}}} {p + q nad p} ^ {- | E |}> {p ^ {2} q ^ {2} nad (p + q) ^ {3}} cdot d_ {2} cdot | X |}$, pak má Maker při první hře vítěznou strategii ve hře (p: q).

Vítězná podmínka pro Avoidera

V předpětí Hra Avoider-Enforcer, následující podmínky zaručují, že má aplikace Avoider vítěznou strategii:^[2]:47–49

• Li ${ displaystyle sum _ {E v { mathcal {F}}} (1 + 1 / p) ^ {p- | E |} <1}$, pak Avoider vyhrává hru (p: q), když hraje jako první, za přísné i monotónní sady pravidel. To je téměř těsné: existuje nekonečná rodina her (p: q), ve kterých je tento výraz o něco větší než 1 a vyhrává Enforcer.^[5] Zejména v nestranné hře se stav stává ${ displaystyle sum _ {E v { mathcal {F}}} 2 ^ {1- | E |} <1}$. Pokud je graf k- uniforma, stav se stává ${ displaystyle | { mathcal {F}} | <(1 + 1 / p) ^ {k-1}}$. Je pozoruhodné, že tento stav nezávisí q vůbec.
• Pokud má každá výherní sada nejvýše k prvků, a ${ displaystyle sum _ {E v { mathcal {F}}} vlevo (1+ {q over pk} vpravo) ^ {p- | E |} <1}$, pak Avoider vyhrává (p: q) hru, když hraje jako první.^[6]

Viz také

• Hra na výrobu krabic

Reference