Gra Maker-Breaker

Maker -Breaker jest rodzajem gry pozycyjnej . Podobnie jak większość gier pozycyjnych, jest opisana przez zbiór pozycji / punktów / elementów ( $)$ i rodzinę zestawów wygrywających ( - rodzina podzbiorów $}}$ z ${\ displaystyle X}$ ). Grają w nią dwaj gracze, zwani Maker i Breaker, którzy na przemian biorą niewzięte wcześniej elementy.

W grze Maker-Breaker Maker wygrywa, jeśli uda mu się utrzymać wszystkie elementy wygrywającego zestawu, podczas gdy Breaker wygrywa, jeśli uda mu się temu zapobiec, tj. utrzymać co najmniej jeden element w każdym wygrywającym zestawie. Remisy nie są możliwe. W każdej grze Maker-Breaker Maker lub Breaker ma zwycięską strategię. Głównym pytaniem badawczym dotyczącym tych gier jest to, która z tych dwóch opcji jest prawdziwa.

Przykłady

Klasyczną grą Maker-Breaker jest Hex . Tam wygrywające zestawy to wszystkie ścieżki od lewej strony planszy do prawej. Maker wygrywa dzięki posiadaniu połączonej ścieżki; Breaker wygrywa, posiadając połączoną ścieżkę od góry do dołu, ponieważ blokuje wszystkie połączone ścieżki od lewej do prawej.

Kółko i krzyżyk można rozegrać jako grę Maker-Breaker: w tym wariancie celem Maker jest wybranie 3 kwadratów z rzędu, a celem Breaker jest po prostu uniemożliwienie Makerowi tego. W tym wariancie Maker ma zwycięską strategię. Kontrastuje to z klasycznym wariantem (który jest grą z silną pozycją ), w której drugi gracz ma strategię dobierania (patrz gra z silną pozycją # Porównanie z grą Maker-Breaker ).

Nieuporządkowaną grę CNF na pozytywnym CNF (wszystkie dodatnie literały) można uznać za grę Maker-Breaker, w której Maker chce sfałszować CNF, a Breaker chce ją zaspokoić.

$) i$ Maker-Breaker, gdy plansza do gry jest zbiorem $krawędzi$ pewnego wykresu (zwykle traktowanego jako pełny wykres wygranych. -zbiorów to ${\ Displaystyle {\ mathcal {F}} = \ {E '\ podzbiór E \ vert G [E'] {\ hbox {ma właściwość}} {\ mathcal {P}} \ }}$ , gdzie jest pewną właściwością wykresu (zwykle przyjmowaną jako rosnąca monotonnie [wyjaśnij?]), taką jak $.$ Na przykład gra przełączania Shannona to gra Maker-Breaker, w której zwycięskie zestawy to ścieżki między dwoma wyróżnionymi wierzchołkami.

Dwoistość Breaker-Maker

W grze Maker-Breaker zwykle Maker gra jako pierwszy. Ale możliwe jest również, aby Breaker zagrał pierwszy. Gra jako pierwsza jest zawsze korzystna: każda zwycięska strategia dla Makera grającego jako drugi na ${\ Displaystyle (X, {\ mathcal {F}})}$ daje zwycięską strategię dla Makera grającego jako pierwszy na ${\ Displaystyle (X, {\ mathcal {F}}).}$ To samo dotyczy Breakera.

$*}}})}$ dla każdej gry możemy zdefiniować jej grę przekrojową $)$ ${\ Displaystyle (X, {\ mathcal {$ , w którym wygrywające sety to minimalne sety dotykające każdego wygrywającego seta w oryginalnej grze. Na przykład, jeśli w oryginalnej grze zwycięskie zestawy to {{1,2,3},{4,5,6} }, to w grze podwójnej są to {{1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6} }. Następnie zwycięskie strategie dla Breakera grającego jako pierwszy na ${\ Displaystyle (X, {\ mathcal {F}})}$ to dokładnie zwycięskie strategie dla Makera grającego jako pierwszy na ${\ Displaystyle (X, {\ mathcal {F ^ {* }}})}$ .

Złożoność obliczeniowa

Gra Maker-Breaker jest kompletna w PSPACE, nawet jeśli rozmiar każdego zestawu jest ograniczony do 6. Pierwszy wynik pochodzi z 1978 r., Kiedy rozmiar każdego zestawu został ograniczony do 11, gdzie gra została wymieniona jako sol {\ displaystyle $}$ ( POS CNF 11).

Strategie

Do rozwiązywania gier Maker-Breaker powszechnie stosuje się kilka rodzajów strategii.

Strategie parowania

W niektórych grach możliwe jest podzielenie elementów X (lub ich podzbioru) na zestaw par rozłącznych parami. Pod pewnymi warunkami gracz może wygrać, stosując następującą zachłanną strategię: „kiedy twój przeciwnik wybierze element pary i , wybierz drugi element pary i ”.

„Pewne warunki” są różne dla Maker i Breaker; patrz strategia parowania .

Strategie z silnych gier pozycyjnych

Każda zwycięska strategia dla Pierwszego w silnej grze pozycyjnej jest również zwycięską strategią dla Stwórcy w wariancie Maker-Breaker (patrz Silna gra pozycyjna# Porównanie z grą Maker-Breaker ). W szczególności, jeśli w wariancie z silną pozycją nie może być remisu, to w wariancie make-breaker Maker ma strategię wygrywającą. Niekoniecznie jest odwrotnie: zwycięska strategia dla Stwórcy w wariancie twórca-łamacz niekoniecznie jest strategią wygrywającą dla Pierwszego w wariancie silnym, ponieważ w wariancie silnym Drugi może wygrać, zdobywając zwycięski zestaw przed Pierwszym .

W przeciwieństwie do tego, każda zwycięska strategia dla Breakera w grze make-breaker jest również strategią dobierania dla Seconda w wariancie z silną pozycją.

Strategie oparte na potencjale

Załóżmy, że możemy znaleźć funkcję, która przypisuje każdemu zwycięskiemu zestawowi potencjał oparty na liczbie elementów już z niego pobranych przez Maker/Breaker. Potencjalna funkcja powinna spełniać następujące właściwości:

Potencjał zwycięskiego zestawu wynosi od 0 do 1;
Kiedy Breaker bierze element, potencjał wszystkich zestawów, które go zawierają, spada do 0 i pozostaje 0;
Kiedy Stwórca bierze element, zwiększa się potencjał wszystkich (nie zepsutych) zestawów, które go zawierają;
Potencjał zbioru należącego do Makera wynosi 1.

Następnie Maker wygrywa, jeśli suma potencjałów jest większa niż 0, a Breaker wygrywa, jeśli suma potencjałów jest mniejsza niż 1. Stąd:

Jeśli suma początkowa jest większa niż 0, a Maker może grać tak, że suma potencjalna słabo rośnie, to jest to zwycięska strategia dla Makera;
Jeśli początkowa suma jest mniejsza niż 1, a Breaker może grać tak, że suma potencjalna nieznacznie spada, to jest to zwycięska strategia dla Breakera.

Zwycięski warunek dla Breakera

Paul Erdős i John Selfridge przedstawili ogólny warunek, który gwarantuje Breakerowi zwycięską strategię. Zastosowali strategię opartą na potencjale. $pomocą$ (nieprzerwanego) zwycięskiego seta za ${\ Displaystyle | E |}$ niezajęte wierzchołki jako ${\ Displaystyle 2 ^ {- | E |}}$ . Tak więc potencjał zestawu zajmowanego przez Stwórcę jest rzeczywiście ${\ Displaystyle 2 ^ {- 0} = 1}$ . Ilekroć Maker bierze element, potencjał każdego zawierającego go zestawu wzrasta do ${\ Displaystyle 2 ^ {- (| E | -1)}}$ , tj. wzrasta o ${\ Displaystyle 2 ^ {- | E |}}$ ; ilekroć Breaker bierze element, potencjał każdego zestawu zawierającego go spada do 0, tj. zmniejsza się o ${\ Displaystyle 2 ^ {- | E |}}$ . Każdemu elementowi przypisujemy wartość co jest równe całkowitemu wzrostowi potencjału w przypadku, gdy Stwórca go przyjmie, tj. ${\ Displaystyle w (v): = \ suma _ {v \ w E} 2 ^ {- | E |}}$ . Zwycięską strategią Breakera jest wybranie elementu o najwyższej wartości . Gwarantuje to, że od pierwszej tury Breakera potencjał zawsze nieznacznie spada. Dlatego, jeśli potencjał w pierwszej turze Breaker jest mniejszy niż 1, Breaker wygrywa. W pierwszej turze Stwórcy może co najwyżej podwoić potencjał (biorąc element ze wszystkich zwycięskich zestawów). Dlatego wystarczy, że na początku gry potencjał jest mniejszy niż 1/2. Podsumowując, twierdzenie Erdősa-Selfridge'a mówi, że:

Jeżeli ${\ Displaystyle \ suma _ {E \ in {\ mathcal {F}}} 2 ^ {- | E | <1/2}$ , to jest ${\ Displaystyle {\ mathcal {F}}}$ Wygrana Breakera .

Twierdzenie daje bardzo łatwy do sprawdzenia warunek, a gdy ten warunek jest spełniony, daje również wydajny algorytm obliczania optymalnej strategii Breakera.

Potencjalna funkcja ma interpretację probabilistyczną. Potencjał zwycięskiego zestawu to prawdopodobieństwo, że jeśli od teraz gra będzie rozgrywana losowo, to Maker będzie właścicielem tego zestawu. Suma potencjalna jest zatem oczekiwaną liczbą zwycięskich zestawów posiadanych przez Makera, jeśli gra jest rozgrywana losowo. Ilekroć suma potencjalna jest mniejsza niż 1, musi istnieć sposób na rozegranie gry w taki sposób, aby liczba zestawów posiadanych przez Makera wynosiła 0. Zapewniając, że suma potencjalna pozostaje poniżej 1, Breaker zasadniczo delosuje to probabilistyczne twierdzenie aż do końca gry staje się to pewne.

Zauważ, że jeśli Breaker zagra jako pierwszy, warunek zmieni się na ${\ Displaystyle \ suma _ {E \ w {\ mathcal {F}}} 2 ^ {- | E | <1}$ .

W szczególności, jeśli wszystkie zestawy wygrywające mają rozmiar k (tj. hipergraf gry jest k -jednolity), to z twierdzenia Erdősa-Selfridge'a wynika, że Breaker wygrywa zawsze, gdy ${\ Displaystyle | {\ mathcal {F}} | <2 ^ {k-1}}$ , tj. liczba zwycięskich setów jest mniejsza niż ${\ Displaystyle 2 ^ {k- 1}}$ .

Liczba $, w$ : istnieją $k$ których liczba zwycięskich setów jest dokładnie $2 ^ {k} -1}}$ i gdzie Maker ma zwycięską strategię. Rozważmy na przykład idealne drzewo binarne o wysokości ${\ displaystyle k-1}$ . ma ${\ Displaystyle 2 ^ {k-1}}$ liście. Zdefiniuj V jako zbiór węzłów drzewa, a H jako rodzinę wszystkich $do$ liścia Maker zaczyna od wybrania katalogu głównego. Następnie, jeśli Breaker wybierze element w lewym poddrzewie, Maker wybierze korzeń prawego poddrzewa i odwrotnie. Kontynuując w ten sposób, Maker zawsze może wybrać pełną ścieżkę, tj. wygrywającego seta.

Hipergrafy rozłączne i prawie rozłączne

Jeśli wszystkie zwycięskie zestawy są parami rozłączne, a ich rozmiar wynosi co najmniej 2, to Breaker może wygrać, stosując strategię parowania.

Załóżmy teraz, że zbiory wygrywające są prawie rozłączne, tj. dowolne dwa zbiory wygrywające mają co najwyżej jeden element wspólny. Jeśli wszystkie wygrywające sety mają rozmiar $4$ a liczba wygrywających setów jest mniejsza niż $\ Displaystyle 4 ^ {kc {\ sqrt {k}}}}$ (dla pewnej stałej stałej c), wtedy Breaker ma zwycięską strategię. Tak więc ta sytuacja jest łatwiejsza dla Breakera niż ogólny przypadek, ale trudniejsza niż przypadek rozłącznych wygrywających zestawów.

Zwycięski warunek dla Stwórcy

Zdefiniuj stopień zestawu elementów jako liczbę różnych wygrywających zestawów, które zawierają ten zestaw. Zdefiniuj stopień pary rodziny zestawów, oznaczony $jako$ maksymalny stopień pary elementów (maksymalny we wszystkich parach $wygrywające$ sety mają rozmiar a liczba wygrywających setów jest większa niż ${\ Displaystyle 2 ^ {k-3} \ cdot d_ {2} \ cdot | X |}$ , to Maker ma zwycięską strategię.

$Selfridge$ : potencjał zwycięskiego z ${\ displaystyle | E |}$ niezajęte elementy (i żaden element zajęty przez Breaker) to ${\ Displaystyle 2 ^ {- | E |}}$ . Wartość elementu to całkowity spadek potencjału, jeśli Breaker bierze ten element, który jest taki sam jak całkowity wzrost potencjału, jeśli bierze go Maker. Strategia Makera polega po prostu na wybraniu elementu o najwyższej wartości.

Ilekroć Stwórca bierze element, potencjał każdego wygrywającego zestawu, który go zawiera, wzrasta o ${\ Displaystyle 2 ^ {- | E |}}$ ; ilekroć Breaker bierze element, potencjał każdego zestawu, który go zawiera i nie zawiera elementu Maker, zmniejsza się o ${\ Displaystyle 2 ^ {- | E |}}$ . Dlatego, jeśli weźmiemy pod uwagę tylko zwycięskie zestawy, które zostały dotknięte raz, potencjalna suma słabo rośnie. Suma potencjałów może się zmniejszać tylko dzięki zestawom, które zawierają zarówno element Stwórcy, jak i element Rozbijacza. Te zestawy zyskują ${\ Displaystyle 2 ^ {- | E |}}$ , ale potem przegrywają ${\ Displaystyle 2 ^ {- (| E | -1)}}$ , więc w sumie tracą ${\ Displaystyle 2 ^ {- | E |}}$ . Ponieważ takie zestawy mają co najmniej dwa elementy, każdy taki zestaw traci najwyżej 1/4. Przy założeniu ograniczonego stopnia par liczba takich zbiorów wynosi co najwyżej d ₂ . Stąd po każdej rundzie suma potencjalna spada co najwyżej o d ₂ /4. Liczba rund wynosi |X|/2, więc potencjał końcowy jest mniejszy od potencjału początkowego co najwyżej o ${\ Displaystyle d_ {2} \ cdot | X |/8}$ . Początkowy potencjał to ${\ Displaystyle | {\ mathcal {F}} | \ cdot 2 ^ {- k}}$ .

Jeśli ${\ Displaystyle | {\ mathcal {F}} | \ cdot 2 ^ {-k}> d_ {2} \ cdot | X |/8} , ostateczny potencjał jest większy niż 0, więc jest co najmniej$ jeden wygrywający set z potencjałem 1. Ten zestaw jest własnością Maker.

Liczby chromatyczne i zwycięskie strategie

Liczba chromatyczna to najmniejsza liczba kolorów potrzebnych do $pokolorowania$ elementów X tak, że żaden pojedynczy zestaw $jest$ monochromatyczny . Jeśli liczba chromatyczna $ma$ zwycięską strategię.

Tabela podsumowań

Poniższa tabela podsumowuje niektóre warunki, które gwarantują, że jeden z graczy ma zwycięską strategię. Warunek w kolumnie „tightness” wskazuje, kiedy znane są określone hipergrafy, na których strategia przestaje działać.

We wszystkich warunkach k jest wielkością wygrywających setów (tj. hipergraf gry jest k -jednolity).


Stan	Zwycięzca	Szczelność	Uwagi
${\ Displaystyle \| {\ mathcal {F}} \| <2 ^ {k-1}}$	Przerywacz	${\ Displaystyle \| {\ mathcal {F}} \| \ geq 2 ^ {k-1}}$	Potencjalna strategia
Rozłączne zestawy wygrywające, rozmiar co najmniej 2	Przerywacz		Strategia parowania
Zbiory prawie rozłączne, ${\ Displaystyle \| {\ mathcal {F}} \| <4 ^ {kc {\ sqrt {k}}}}$	Przerywacz
Stopień pary d ₂ , ${\ Displaystyle \| {\ mathcal {F}} \|> 2 ^ {k-3} \ cdot d_ {2} \ cdot \| X \|}$	Producent		Potencjalna strategia

Gra Breaker-Breaker

Możliwe jest rozegranie gry, w której obaj gracze chcą osiągnąć cel Breaker (tj. mieć co najmniej jeden element w każdym zwycięskim zestawie). Wtedy gra niekoniecznie jest o sumie zerowej – możliwe, że obaj gracze wygrają. W rzeczywistości, ilekroć Breaker ma zwycięską strategię w grze Maker-Breaker, możliwe jest, że dwóch Breakers wygra w grze Breaker-Breaker.

Zastosowaniem tej strategii jest wydajny algorytm kolorowania hipergrafu . Załóżmy, że chcemy pokolorować wierzchołki k -jednolitego hipergrafu dwoma kolorami, tak aby w każdym hipergrafie reprezentowane były oba kolory. Erdos udowodnił już w 1963 roku, stosując metodę probabilistyczną , że takie zabarwienie istnieje zawsze, gdy liczba hiperkrawędzi jest mniejsza $.$ B ) ). Jednak dowód nie był konstruktywny. Korzystając z konstruktywnej strategii wygrywania Breakera, możemy pokolorować hipergraf, $pozwalając$ dwóm Breakerom grać jeden przeciwko drugiemu za pomocą ich zwycięskich strategii Obaj gracze wygrają - więc każdy gracz będzie miał co najmniej jeden wierzchołek w każdej hiperkrawędzi.

Wykonanie częściowe

Załóżmy, że aby wygrać, Stwórca nie musi zajmować całego wygrywającego zestawu - wystarczy, że posiada część takiego zestawu. Kiedy Breaker może wygrać w tym przypadku?

Ciągłe częściowe wytwarzanie

m elementów w jednym zestawie (gdzie Breaker nie posiada żadnego elementu). Jeśli wielkość każdego wygrywającego seta wynosi co najmniej m, a liczba setów jest mniejsza niż ${\ Displaystyle 2 ^ {m-1}}$ , to Breaker nadal ma zwycięską strategię. Strategia wykorzystuje funkcję potencjału: potencjał „zepsutego” zestawu wynosi 0, a potencjał zestawu niezepsutego mi wynosi ${\ Displaystyle 2 ^ {- r (E)}}$ , gdzie r(E) to liczba elementów, które Maker musi wziąć, aby go wygrać. Tak więc początkowy potencjał każdego zwycięskiego zestawu wynosi $.$ potencjał zbioru zajmowanego przez Stwórcę wynosi 1. Stąd dowód jest taki sam jak twierdzenie Erdosa-

Tworzenie ułamków

Załóżmy, że aby wygrać, Maker musi posiadać tylko ułamek t elementów w jednym zwycięskim zestawie, gdzie ${\ displaystyle 1/2 <t \ równoważnik 1}$ . Tak więc Breaker musi posiadać ułamek większy niż (1- t ) punktów w każdym zestawie. Zdefiniuj stałą: ${\ Displaystyle c_ {t}: = (2 t) ^ {t} \ cdot (2-2 t) ^ {1-t} = 2 \ cdot t ^ {t} \ cdot (1-t) ^ {1-t}}$ (w standardowym wariancie ${\ Displaystyle t = 1, c_ {t} \ do 2}$ ).

Jeśli $jako$ Breaker ma zwycięską strategię grając pierwszy .
Jeśli $_$ _ ma zwycięską strategię , gdy gra jako drugi .

$a$ szczególności, jeśli wszystkie zestawy mają rozmiar , ich liczba jest mniejsza niż to Breaker (grający pierwszy) ma strategię wygrywającą.

Strategia wykorzystuje funkcję potencjału. Potencjał zwycięskiego seta definiuje się jako ${\ Displaystyle (2t) ^ {-r} (2-2t) ^ {-s}}$ , gdzie r jest liczbę elementów, które Maker musi zabrać, aby zająć zestaw, oraz s to liczba elementów, które Breaker musi wziąć, aby go złamać. Jeśli Maker zajmuje zbiór, to jego potencjał w pewnym momencie będzie wynosił co najmniej 1. Dlatego Breaker wygrywa, jeśli uda mu się utrzymać sumę potencjałów poniżej 1. Strategią Breakera jest wzięcie elementu o najwyższej wartości, zdefiniowanej jako suma potencjałów zestawów wygrywających zawierających ten element.

Za każdym razem, gdy Stwórca bierze element, potencjał każdego zestawu, który go zawiera, jest mnożony przez 2 t , więc zwiększa się (2 t -1) razy obecny potencjał. Za każdym razem, gdy Breaker bierze element, potencjał każdego zestawu, który go zawiera, jest mnożony przez (2-2 t ), więc zwiększa się (1-2 t ) razy w stosunku do obecnego potencjału. Ilekroć Breaker i Maker stykają się z tym samym zestawem, jego potencjał jest mnożony przez 2 t (2-2 t ), więc zwiększa się o -(2 t -1) ² razy aktualny potencjał. Ponieważ element Breakera ma najwyższą wartość, suma potencjałów zawsze maleje. Dlatego, jeśli początkowa suma potencjałów jest mniejsza niż 1, wygrywa Breaker.

Nieskończone tablice

Definicja gry Maker-Breaker jest subtelna, gdy istnieje nieskończenie wiele wierzchołków ( $|$ $Displaystyle | H | =\infty }$ zwycięskich zestawów ( ). W tym przypadku mówimy, że Breaker ma zwycięską strategię, jeśli dla wszystkich j > 0, Breaker może uniemożliwić Makerowi całkowite zajęcie zwycięskiego zestawu po kolei j .

Zobacz też