Positionsspel

Ett positionsspel är ett slags kombinatoriskt spel för två spelare. Det beskrivs av:

$X$ – en ändlig uppsättning element. Ofta kallas ${\displaystyle X} för$ brädet och dess element kallas positioner .
${\mathcal {F}}$ – en familj av delmängder av $X$ . Dessa delmängder kallas vanligtvis för vinnande uppsättningar .
Ett kriterium för att vinna spelet.

Under spelet tar spelare omväxlande anspråk på tidigare outtagna positioner, tills en av spelarna vinner. Om alla positioner i $X$ tas medan ingen spelare vinner, anses spelet vara oavgjort.

Det klassiska exemplet på ett positionsspel är Tic-tac-toe . I den $X$ spelplanens 9 rutor, ${\mathcal {F}}$ innehåller de 8 linjerna som bestämmer en seger (3 horisontella, 3 vertikala och 2 diagonala), och vinstkriteriet är: den första spelaren som har ett helt vinnande set vinner. Andra exempel på positionsspel är Hex och Shannon-bytespelet .

För varje positionsspel finns det exakt tre alternativ: antingen har den första spelaren en vinnande strategi , eller så har den andra spelaren en vinnande strategi, eller så har båda spelarna strategier för att genomföra oavgjort. Huvudfrågan av intresse i studien av dessa spel är vilket av dessa tre alternativ som gäller i ett visst spel.

Ett positionsspel är ändligt, deterministiskt och har perfekt information ; Därför är det i teorin möjligt att skapa hela spelträdet och avgöra vilket av dessa tre alternativ som gäller. I praktiken kan dock spelträdet vara enormt. Därför analyseras positionsspel vanligtvis via mer sofistikerade kombinatoriska tekniker.

Alternativ terminologi

Ofta anses input till ett positionsspel som en hypergraf . I detta fall:

Elementen i $X$ kallas hörn (eller punkter ), och betecknas med V;
Elementen i ${\mathcal {F}}$ kallas kanter (eller hyperkanter ), och betecknas med E eller H.

Varianter

Det finns många varianter av positionsspel som skiljer sig åt i deras regler och deras vinstkriterier.

Olika vinstkriterier

Starkt positionsspel (även kallat Maker-Maker-spel): vinner den första spelaren som gör anspråk på alla delar av ett vinnande set. Om spelet slutar med alla delar av brädet, men ingen spelare har gjort anspråk på alla delar av ett vinnande set, är det oavgjort. Ett exempel är klassiska Tic-tac-toe .
Maker-Breaker-spel: de två spelarna kallas Maker och Breaker. Maker vinner genom att göra anspråk på alla delar av ett vinnande set. Om spelet slutar med alla delar av brädet anspråk på, och Maker ännu inte har vunnit, vinner Breaker. Dragningar är inte möjliga. Ett exempel är Shannon som byter spel .
Avoider-Enforcer-spelet: spelarna kallas Avoider och Enforcer. Enforcer vinner om Avoider någonsin gör anspråk på alla delar av ett vinnande set. Om spelet slutar med alla delar av brädet anspråkade, och Avoider inte har gjort anspråk på ett vinnande set, vinner Avoider. Liksom i maker-breaker-spel är oavgjort inte möjligt. Ett exempel är Sim .
Diskrepansspel: spelarna kallas Balancer och Unbalancer. Balancer vinner om han ser till att varje spelare har ungefär hälften av hörnen i alla vinnande set. Annars vinner Unbalancer.

Olika spelregler

Waiter-Client-spel (även kallat Picker-Chooser-spel): spelarna kallas för Waiter och Client. I varje tur väljer Waiter två positioner och visar dem för kunden, som kan välja en av dem.
Partiskt positionsspel: varje positionsspel har en partisk variant, där den första spelaren kan ta p element åt gången och den andra spelaren kan ta q element åt gången (i den opartiska varianten, p = q =1).

Specifika spel

Följande tabell listar några specifika positionsspel som studerades mycket i litteraturen.


namn	Positioner	Vinnande set
Flerdimensionell tic-tac-toe	Alla rutor i en flerdimensionell låda	Alla raka linjer
Shannon byter spel	Alla kanter på en graf	Alla vägar från s till t
Sim	Alla kanter mellan 6 hörn.	Alla trianglar [förlorande set].
Klickspel (alias Ramsey-spel )	Alla kanter på en komplett graf med storlek n	Alla klick i storlek k
Anslutningsspel	Alla kanter av en komplett graf	Alla spänner över träd
Hamiltonicity-spel	Alla kanter av en komplett graf	Alla Hamiltonska stigar
Icke-planaritetsspel	Alla kanter av en komplett graf	Alla icke-planära subgrafer
Aritmetisk progressionsspel	Siffrorna {1,...,n}	Alla aritmetiska progressioner av storlek k

Se även

Topologiskt spel , en generalisering av ett positionsspel till oändliga uppsättningar
Banach–Mazur-spel , ett spel som spelas på ett topologiskt utrymme genom att välja bland vissa delmängder, med vinstvillkor som liknar de för ett maker-breaker-spel