Spelet Maker-Breaker

Ett Maker-Breaker-spel är ett slags positionsspel . Liksom de flesta positionsspel beskrivs det av dess uppsättning positioner/poäng/element ( $X$ ) och dess familj av vinnande set ( ${\mathcal {F}}$ - en familj av delmängder av $X$ ). Det spelas av två spelare, kallade Maker och Breaker, som växelvis tar tidigare otagna element.

I ett Maker-Breaker-spel vinner Maker om han lyckas hålla alla delar av ett vinnande set, medan Breaker vinner om han lyckas förhindra detta, dvs att ha minst ett element i varje vinnande set. Dragningar är inte möjliga. I varje Maker-Breaker-spel har antingen Maker eller Breaker en vinnande strategi. Den huvudsakliga forskningsfrågan om dessa spel är vilket av dessa två alternativ som gäller.

Exempel

Ett klassiskt Maker-Breaker-spel är Hex . Där är de vinnande seten alla vägar från vänster sida av brädet till höger sida. Maker vinner genom att äga en ansluten väg; Breaker vinner genom att äga en ansluten bana från topp till botten, eftersom den blockerar alla anslutna banor från vänster till höger.

Tic-tac-toe kan spelas som ett Maker-Breaker-spel: i den varianten är målet för Maker att välja 3 rutor i rad, och målet med Breaker är bara att hindra Maker från att göra det. I den varianten har Maker en vinnande strategi. Detta i motsats till den klassiska varianten (som är ett starkt positionsspel ) där den andra spelaren har en ritstrategi (se Starkt positionsspel#Jämförelse med Maker-Breaker-spelet ).

Oordnat CNF- spel på en positiv CNF (alla positiva bokstaver) kan betraktas som ett Maker-Breaker-spel där Maker vill förfalska CNF och Breaker vill tillfredsställa det.

En del forskning har gjorts om att spela Maker-Breaker-spel när spelets bräda är kantuppsättningen $E$ på någon graf $G$ (vanligtvis taget som en komplett graf ), och familjen för att vinna -mängder är ${\mathcal {F}}=\{E'\subset E\vert G[E']{\hbox{ har egenskapen }}{\mathcal {P}}\ }$ , där ${\mathcal {P}}$ är någon grafegenskap (vanligtvis uppfattad som monotont ökande [klargör?]) såsom anslutning. Shannon-bytespelet är till exempel ett Maker-Breaker-spel där de vinnande seten är vägarna mellan två distingerade hörn.

Breaker-Maker-dualitet

I ett Maker-Breaker-spel spelar Maker vanligtvis först. Men det är också möjligt att låta Breaker spela först. Att spela först är alltid fördelaktigt: varje vinnande strategi för Maker som spelar tvåa på $(X,{\mathcal {F}})$ ger en vinnande strategi för Maker som spelar först på $(X,{\mathcal {F}}).$ Detsamma gäller för Breaker.

Dessutom, för varje spel $(X,{\mathcal {F}})$ kan vi definiera dess tvärgående spel $(X,{\mathcal {F^{ *}}})$ , där de vinnande seten är de minimala seten som rör varje vinnande set i det ursprungliga spelet. Till exempel, om de vinnande seten i originalspelet är { {1,2,3},{4,5,6} } så är de i det dubbla spelet { {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6} }. Sedan är de vinnande strategierna för Breaker som spelar först på $(X,{\mathcal {F}})$ exakt de vinnande strategierna för Maker som spelar först på $(X,{\mathcal {F^{*}}})$ .

Beräkningskomplexitet

Maker-Breaker-spelet är PSPACE-komplett även om storleken på varje set är begränsad till 6. Det första resultatet var från 1978 där storleken på varje set var begränsad till 11, där spelet nämndes som G {\displaystyle $}$ ( POS CNF 11).

Strategier

Flera typer av strategier används vanligtvis för att lösa Maker-Breaker-spel.

Parningsstrategier

I vissa spel är det möjligt att partitionera elementen i X (eller en delmängd av dem) i en uppsättning parvis-disjunkta par. Under vissa förhållanden kan en spelare vinna genom att använda följande giriga strategi: "när din motståndare väljer ett element av par i , välj det andra elementet av par i ".

De "vissa villkoren" är olika för Maker och Breaker; se parningsstrategi .

Strategier från starka positionsspel

Varje vinnande strategi för First i ett starkt positionsspel är också en vinnande strategi för Maker i maker-breaker-varianten (se Strong positional game#Comparison to Maker-Breaker-spel) . Speciellt om det i den starka positionsvarianten inte kan bli oavgjort, så har Maker en vinnande strategi i den maker-breaker-varianten. Motsatsen är inte nödvändigtvis sant: en vinnande strategi för Maker i maker-breaker-varianten är inte nödvändigtvis en vinnande strategi för First i den starka varianten, eftersom i den starka varianten kan Second vinna genom att ta ett vinnande set före First .

Däremot är varje vinnande strategi för Breaker i ett maker-breaker-spel också en dragningsstrategi för Second i den starka positionsvarianten.

Potentialbaserade strategier

Anta att vi kan hitta en funktion som tilldelar, till varje vinnande set, en potential baserat på antalet element som redan tagits från den av Maker/Breaker. Den potentiella funktionen bör uppfylla följande egenskaper:

Potentialen för ett vinnande set är mellan 0 och 1;
När Breaker tar ett element, sjunker potentialen för alla uppsättningar som innehåller det till 0 och förblir 0;
När Maker tar ett element ökar potentialen för alla (icke brutna) uppsättningar som innehåller det;
Potentialen för en uppsättning som ägs av Maker är 1.

Sedan vinner Maker om den potentiella summan är mer än 0, och Breaker vinner om den potentiella summan är mindre än 1. Därför:

Om den initiala summan är mer än 0, och Maker kan spela så att den potentiella summan ökar svagt, så är detta en vinnande strategi för Maker;
Om den initiala summan är mindre än 1, och Breaker kan spela så att den potentiella summan minskar svagt, är detta en vinnande strategi för Breaker.

Ett vinnande villkor för Breaker

Paul Erdős och John Selfridge presenterade ett allmänt villkor som garanterar Breaker en vinnande strategi. De använde en potentialbaserad strategi. De definierade potentialen för alla (icke brutna) vinstuppsättningar $E$ med $|E|$ obesatta hörn som $2^{-|E|}$ . Så potentialen för en uppsättning som upptas av Maker är verkligen $2^{-0}=1$ . Närhelst Maker tar ett element, ökar potentialen för varje uppsättning som innehåller det till ${\displaystyle 2^{-(|E|-1)}} ,$ dvs. ökar med $2^{-|E|}$ ; närhelst Breaker tar ett element, sjunker potentialen för varje uppsättning som innehåller det till 0, dvs. minskar med $2^{-|E|}$ . Till varje element tilldelar vi ett värde som är lika med den totala potentialökningen om Maker tar det, dvs. $w(v):=\sum _{v\in E}2^{-|E|}$ . Den vinnande strategin för Breaker är att välja ett element med det högsta värdet . Detta garanterar att potentialen alltid minskar svagt från den första vändningen av Breaker och framåt. Därför, om potentialen vid den första Breaker-turen är mindre än 1, vinner Breaker. I Makers första tur kan han som mest dubbla potentialen (genom att ta ett element som finns i alla vinnande set). Därför är det tillräckligt att potentialen vid spelstarten är mindre än 1/2. För att sammanfatta säger Erdős-Selfridge-satsen att:

Om ${\displaystyle \sum _{E\in {\mathcal {F}}}2^{-|E|}<1/2} , då är$ F { $displaystyle {\mathcal {F}}}$ Breakers vinst .

Satsen ger ett mycket lättkontrollerat villkor, och när detta villkor är uppfyllt ger det också en effektiv algoritm för att beräkna Breakers optimala strategi.

Den potentiella funktionen har en probabilistisk tolkning. Potentialen för ett vinnande set är sannolikheten att, om spelet spelas slumpmässigt från och med nu, kommer Maker att äga det setet. Den potentiella summan är alltså det förväntade antalet vinnande set som ägs av Maker om spelet spelas slumpmässigt. Närhelst den potentiella summan är mindre än 1, måste det finnas ett sätt att spela spelet så att antalet set som ägs av Maker är 0. Genom att se till att potentialsumman förblir under 1, avrandomiserar Breaker i huvudsak detta sannolikhetspåstående tills i slutet av spelet blir det en säkerhet.

Observera att om Breaker spelar först ändras villkoret till $\sum _{E\in {\mathcal {F}}}2^{-|E|}<1$ .

I synnerhet, om de vinnande uppsättningarna är av storlek k (dvs. spelets hypergraf är k -uniform), så innebär Erdős-Selfridge-satsen att Breaker vinner när som helst ${\displaystyle |{\mathcal {F}}|<2^{k-1}} ,$ dvs antalet vinnande set är mindre än $2^{k- 1}$ .

Siffran $2^{k-1}$ är snäv: det finns $k$ -enhetliga hypergrafer där antalet vinnande set är exakt $2^{k -1}$ och där Maker har en vinnande strategi. Betrakta till exempel ett perfekt binärt träd med höjden $k-1$ . Den har $2^{k-1}$ blad. Definiera V som mängden trädnoder, och H som familjen av alla $2^{k-1}$ banor från roten till ett löv. Maker börjar med att plocka roten. Sedan, om Breaker väljer ett element i det vänstra underträdet, väljer Maker roten till det högra underträdet och vice versa. Genom att fortsätta på det här sättet kan Maker alltid välja en hel väg, dvs ett vinnande set.

Osammanhängande och nästan osammanhängande hypergrafer

Om alla vinnande set är parvis osammanhängande och deras storlek är minst 2, kan Breaker vinna med en parningsstrategi.

Antag nu att de vinnande uppsättningarna är nästan osammanhängande, dvs. två vinnande uppsättningar har högst ett element gemensamt. Om alla vinnande set är av storleken $k$ och antalet vinnande set är mindre än ${\displaystyle 4^{kc{\sqrt {k}}}} ($ för någon fast konstant c), då har Breaker en vinnande strategi. Så den här situationen är lättare för Breaker än det allmänna fallet, men svårare än fallet med osammanhängande vinnande set.

Ett vinnande villkor för Maker

Definiera graden av en uppsättning element som antalet olika vinnande set som innehåller denna uppsättning. Definiera pargraden för en uppsättningsfamilj, betecknad $d_{2}$ , som den maximala graden av ett elementpar (maximalt över alla par). Om alla vinnande set är av storleken $k$ och antalet vinnande set är mer än $2^{k-3}\cdot d_{2}\cdot |X|$ , då har Maker en vinnande strategi.

Strategin använder samma potentiella funktion som används av Erdos och Selfridge: potentialen för ett vinnande set $E$ med $|E|$ oupptagna element (och inget element upptaget av Breaker) är $2^{-|E|}$ . Värdet på ett element är den totala potential-minskningen om Breaker tar det elementet, vilket är samma som den totala potential-ökningen om Maker tar det. Makers strategi är helt enkelt att ta det mest värdefulla elementet.

Närhelst Maker tar ett element, ökar potentialen för varje vinnande set som innehåller det med $2^{-|E|}$ ; närhelst Breaker tar ett element, minskar potentialen för varje uppsättning som innehåller det och som inte innehåller Makers element med $2^{-|E|}$ . Därför, om vi bara tar hänsyn till de vinnande seten som berördes en gång, ökar den potentiella summan svagt. Potentialsumman kan endast minska på grund av uppsättningar som innehåller både Makers element och Breakers element. Dessa uppsättningar får $2^{-|E|}$ men förlorar sedan $2^{-(|E|-1)}$ , så allt som allt tappar de $2^{-|E|}$ . Eftersom sådana uppsättningar har minst två element, förlorar varje sådan uppsättning högst 1/4. Enligt antagandet om begränsade pargrader är antalet sådana uppsättningar som mest d ₂ . Efter varje omgång sjunker alltså potentialsumman med högst d ₂ /4. Antalet omgångar är |X|/2, så den slutliga potentialen är mindre än den initiala potentialen med högst $d_{2}\cdot |X|/8$ . Den initiala potentialen är $|{\mathcal {F}}|\cdot 2^{-k}$ .

Om ${\displaystyle |{\mathcal {F}}|\cdot 2^{-k}>d_{2}\cdot |X|/8} , slutpotentialen är mer än 0, så det finns minst$ en vinnande set med potential 1. Detta set ägs av Maker.

Kromatiska siffror och vinnande strategier

Det kromatiska antalet F $\displaystyle {\mathcal {F}}}$ är det minsta antalet färger som behövs för att färga elementen i X så att ingen enkel uppsättning i ${\mathcal {F}}$ är monokromatisk. Om det kromatiska talet för ${\mathcal {F}}$ är 3, så har Maker en vinnande strategi.

Översiktstabell

Följande tabell sammanfattar några villkor som garanterar att en av spelarna har en vinnande strategi. Villkoret i kolumnen "täthet" indikerar när specifika hypergrafer är kända på vilka strategin slutar fungera.

Under alla förhållanden är k storleken på vinnande set (dvs spelets hypergraf är k -uniform).


Skick	Vinnare	Åtdragning	Kommentarer
$\|{\mathcal {F}}\|<2^{k-1}$	Brytare	$\|{\mathcal {F}}\|\geq 2^{k-1}$	Potentiell strategi
Osammanhängande vinnande set, storlek minst 2	Brytare		Parningsstrategi
Nästan osammanhängande uppsättningar, $\|{\mathcal {F}}\|<4^{kc{\sqrt {k}}}$	Brytare
Par-grad d ₂ , $\|{\mathcal {F}}\|>2^{k-3}\cdot d_{2}\cdot \|X\|$	Tillverkare		Potentiell strategi

Breaker-Breaker spel

Det är möjligt att spela ett spel där båda spelarna vill uppnå målet Breaker (dvs ha minst ett element i varje vinnande set). Då är spelet inte nödvändigtvis nollsumma - det är möjligt att båda spelarna vinner. Faktum är att närhelst Breaker har en vinnande strategi i Maker-Breaker-spelet, är det möjligt att två Breakers båda vinner i Breaker-Breaker-spelet.

En tillämpning av denna strategi är en effektiv algoritm för att färglägga en hypergraf. Anta att vi vill färga hörnen på en k -uniform hypergraf i två färger så att båda färgerna representeras i varje hyperkant. Erdos bevisade redan 1963, med den probabilistiska metoden , att en sådan färgning existerar närhelst antalet hyperkanter är mindre än $2^{k-1}$ (se egenskap B ). Beviset var dock inte konstruktivt. Med Breakers konstruktiva vinnarstrategi kan vi färglägga hypergrafen ${\mathcal {F}}$ genom att låta två Breakers spela mot varandra med sina vinnande strategier. Båda spelarna kommer att vinna - så varje spelare kommer att ha minst en vertex i varje hyperedge.

Delvis tillverkning

Antag att Maker inte behöver ockupera ett helt vinnande set för att vinna - han behöver bara äga en del av ett sådant set. När kan Breaker vinna i det här fallet?

Konstant deltillverkning

m element i en uppsättning (där Breaker inte äger något element). Om storleken på varje vinnande set är minst m, och antalet set är mindre än $2^{m-1}$ , så har Breaker fortfarande en vinnande strategi. Strategin använder en potentialfunktion: potentialen för en "bruten" uppsättning är 0, och potentialen för en icke bruten uppsättning E är ${\displaystyle 2^{-r(E)}} ,$ där r(E) är antalet element som Maker måste ta för att vinna det. Så den initiala potentialen för varje vinnande set är $2^{-m}$ , och potentialen för en uppsättning som upptas av Maker är 1. Härifrån är beviset detsamma som Erdos-Selfridge-satsen.

Bråktillverkning

Antag att Maker, för att vinna, bara behöver äga en bråkdel ${\displaystyle 1/2<t\leq 1$ av elementen i ett vinnande set, där . Så Breaker måste äga en bråkdel större än (1- t ) av poängen i varje set. Definiera konstanten: ${\displaystyle c_{t}:=(2t)^ {t}\cdot (2-2t)^{1-t}=2\cdot t^{t}\cdot (1-t)^{1-t}} (i standardvarianten$ , $t=1,c_{t}\to 2$ ).

Om ${\displaystyle \sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<1} , då har$ Breaker en vinnande strategi när han spelar först .
Om ${\displaystyle \sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<{1 \over 2-2t}} , sedan$ Breaker har en vinnande strategi när du spelar tvåa .

I synnerhet, om alla set är av storlek k och deras antal är mindre än ${c_{t}}^{k}$ , så har Breaker (spelar först) en vinnande strategi.

Strategin använder en potentiell funktion. Potentialen för ett vinnande set definieras som ${\displaystyle (2t)^{-r}(2-2t)^{-s}} ,$ där r är antalet element Maker behöver ta för att ockupera uppsättningen, och s är antalet element som Breaker behöver ta för att bryta den. Om Maker upptar en uppsättning, kommer dess potential någon gång att vara minst 1. Därför vinner Breaker om han lyckas hålla potentialsumman under 1. Breakers strategi är att ta elementet med det högsta värdet, definierat som summan av potentialen för vinnande set som innehåller det elementet.

Närhelst Maker tar ett element multipliceras potentialen för varje uppsättning som innehåller det med 2 t , så den ökar med (2 t -1) gånger den nuvarande potentialen. Närhelst Breaker tar ett element, multipliceras potentialen för varje uppsättning som innehåller det med (2-2 t ), så den ökar med (1-2 t ) gånger den nuvarande potentialen. Närhelst Breaker och Maker båda rör vid samma uppsättning multipliceras dess potential med 2 t (2-2 t ), så den ökar med -(2 t -1) ² gånger den nuvarande potentialen. Eftersom Breakers element har ett högsta värde, minskar alltid potentialsumman. Därför, om den initiala potentiella summan är mindre än 1, vinner Breaker.

Oändliga brädor

Definitionen av Maker-Breaker-spelet har en subtilitet när det finns oändligt många hörn ( $|V|=\infty$ ) och oändligt många vinnande set ( $|H| =\infty$ ). I det här fallet säger vi att Breaker har en vinnande strategi om Breaker för alla j > 0 kan hindra Maker från att helt ockupera ett vinnande set vid tur j .

Se även