Gra Unikacz-Egzekutor

Unikacz -Egzekutor” (zwana także grą „Unikacz-Forcer” lub gra „Antimaker-Antibreaker ”) jest rodzajem gry pozycyjnej . Podobnie jak większość gier pozycyjnych, jest ona opisana przez zbiór pozycji/punktów/elementów ( ) i rodzinę podzbiorów ( ), które nazywane $displaystyle$ tutaj $X}$ przegrane sety . Rozgrywana jest przez dwóch graczy, zwanych Unikającym i Egzekutorem, którzy na zmianę wybierają elementy, aż wszystkie elementy zostaną zabrane. Unikający wygrywa, jeśli uda mu się uniknąć przegranego seta; Enforcer wygrywa, jeśli uda mu się zmusić Unikającego do wzięcia przegranego seta.

Plansza do gry Sim , gry Unikacz-Egzekutor

Klasycznym przykładem takiej gry jest Sim . Tam pozycjami są wszystkie krawędzie pełnego grafu na 6 wierzchołkach. Gracze na zmianę zacieniają linię swoim kolorem i przegrywają, gdy utworzą pełny trójkąt w swoim kolorze: przegranymi setami są wszystkie trójkąty.

Porównanie do gier Maker-Breaker

Zwycięski warunek gry w Unikanie-Egzekutor jest dokładnie odwrotny do warunku zwycięstwa w grze Maker-Breaker na tym samym ${\ displaystyle {\ mathcal {F}}}$ . Tak więc gra „Unikacz-Egzekutor” jest gry Misère gry „Maker-Breaker”. Istnieją jednak sprzeczne z intuicją różnice między tymi typami gier.

Rozważmy na przykład stronniczą wersję gry, w której pierwszy gracz bierze p elementów w każdej turze, a drugi gracz bierze q elementów w każdej turze (w wersji standardowej p = 1 i q = 1). Gry Maker-Breaker są monotoniczne : wzięcie większej liczby elementów jest zawsze zaletą. Formalnie, jeśli Maker wygrywa grę ( p : q ) Maker-Breaker, to wygrywa również grę ( p +1: q ) i grę (p: q-1). Gry z unikaniem i egzekucją nie są monotoniczne: wzięcie większej liczby elementów nie zawsze jest wadą . Rozważmy na przykład bardzo prostą grę Unikanie-Egzekutor, w której przegrywające sety to {w,x} i {y,z}. Następnie Unikacz wygrywa grę (1:1), Egzekutor wygrywa grę (1:2), a Unikacz wygrywa grę (2:2).

Istnieje monotonny wariant reguł gry ( p : q ) Unikający-Egzekutor, w którym Unikający musi wybierać co najmniej p elementów w każdej turze, a Egzekutor musi wybierać co najmniej q elementów w każdej turze; ten wariant jest bias-monotoniczny.

Częściowe unikanie

Podobnie jak w grach Maker-Breaker , gry z unikaniem i egzekucją również mają ułamkowe uogólnienia.

Załóżmy, że Unikający musi uniknąć zabrania co najmniej ułamka t elementów w dowolnym wygrywającym zestawie (tj. wziąć najwyżej 1- t elementów w dowolnym zestawie), a Enforcer musi temu zapobiec, tj. Enforcer musi wziąć mniej niż ułamek t elementów w jakimś wygrywającym zestawie. Zdefiniuj stałą: ${\ Displaystyle c_ {t}: = (2 t) ^ {t}\cdot (2-2t)^{1-t}=2\cdot t^{t}\cdot (1-t)^{1-t}} (w wariancie$ standardowym ${\ displaystyle t = 1, c_ {t} \ do 2}$ ).

• Jeśli ${\ Displaystyle \ sum _ {E \ in {\ mathcal {F}}} {c_ {t}} ^ {- | E | <1} , a całkowita liczba elementów jest parzysta,$ to Unikacz ma Zwycięska strategia , gdy grasz jako pierwszy .

Zobacz też

Stronnicza gra pozycyjna # Warunkiem zwycięstwa dla Unikającego