Subtraktionsspel

I kombinatorisk spelteori är ett subtraktionsspel ett abstrakt strategispel vars tillstånd kan representeras av ett naturligt antal eller vektor av tal (till exempel antalet spelpoletter i högar av polletter, eller positionerna för pjäser ombord) och i vilka de tillåtna dragen minskar dessa siffror. Ofta tillåter dragen i spelet att vilket tal som helst kan reduceras genom att subtrahera ett värde från en specificerad subtraktionsuppsättning , och olika subtraktionsspel varierar i sina subtraktionsuppsättningar. Dessa spel varierar också i om den sista spelaren som flyttar vinner (den normala spelkonventionen ) eller förlorar ( misère ). En annan vinnande konvention som också har använts är att en spelare som flyttar till en position med alla nummer noll vinner, men att vilken annan position som helst utan drag är oavgjort.

Exempel

Exempel på anmärkningsvärda subtraktionsspel inkluderar följande:

Nim är ett spel vars tillstånd består av flera högar av tokens, såsom mynt eller tändstickor, och ett giltigt drag tar bort valfritt antal tokens från en enda hög. Nim har en välkänd optimal strategi där målet vid varje drag är att nå en uppsättning högar vars nim-summa är noll, och denna strategi är central för Sprague-Grundys sats om optimalt spel i opartiska spel . Men när du bara spelar med en enda hög med tokens, är optimalt spel trivialt (bara ta bort alla polletter i ett enda drag).
Subtrahera en kvadrat är en variant av nim där endast kvadratantal av tokens kan tas bort i ett enda drag. Det resulterande spelet har en icke-trivial strategi även för en enda hög med tokens; Furstenberg –Sárközy-satsen antyder att dess vinnande positioner har densitet noll bland heltalen.
Fibonacci nim är en annan variant av nim där de tillåtna dragen beror på de tidigare dragen till samma hög med tokens. Vid det första draget till en hög är det förbjudet att ta hela högen, och vid efterföljande drag måste summan som subtraheras vara högst två gånger den tidigare summan som togs bort från samma hög.
Wythoffs spel spelas genom att placera en schackdrottning på ett stort schackbräde och, vid varje steg, flytta den (på normalt sätt för en schackdrottning) mot brädets nedre sida, vänstra sida eller nedre vänstra hörnet. Detta spel kan beskrivas på samma sätt med två högar med polletter, från vilka varje drag kan ta bort valfritt antal polletter från en eller båda högarna, vilket tar bort samma mängd från varje hög när båda högarna reduceras. Den har en optimal strategi som involverar Beatty-sekvenser och det gyllene snittet .

Teori

Subtraktionsspel är i allmänhet opartiska spel , vilket innebär att uppsättningen av drag som är tillgängliga i en given position inte beror på spelaren vars tur det är att flytta. För ett sådant spel kan tillstånden delas upp i ${\mathcal {P}}$ -positioner (positioner där den tidigare spelaren, som just flyttade, vinner) och ${\mathcal { N}}$ -positioner (positioner där nästa spelare att flytta vinner), och en optimal spelstrategi består av att flytta till en ${\mathcal {P}}$ -position närhelst detta är möjligt. Till exempel, med den normala spelkonventionen och en enda hög med tokens, är varje nummer i subtraktionsuppsättningen en ${\mathcal {N}}$ -position, eftersom en spelare kan vinna från ett sådant nummer genom att flytta till noll.

För normalspelade subtraktionsspel där det finns flera siffror, där varje drag endast reducerar ett av dessa nummer, och där de minskningar som är möjliga från ett givet nummer endast beror på det numret och inte på resten av spelets tillstånd , kan Sprague-Grundy-satsen användas för att beräkna ett "nim-värde" för varje tal, ett tal som representerar en ekvivalent position i spelet nim, så att värdet på det övergripande speltillståndet är nim-summan av dess nim- värden. På så sätt kan den optimala strategin för det övergripande spelet reduceras till beräkningen av nim-värden för en förenklad uppsättning spelpositioner, de där det bara finns ett enda nummer. Nim-värdena är noll för ${\mathcal {P}}$ -positioner, och icke-noll för ${\mathcal {N}}$ -positioner; enligt ett teorem av Tom Ferguson , är entalspositionerna med nim-värde ett exakt de tal som erhålls genom att addera det minsta värdet i subtraktionsmängden till en ${\mathcal {P}}$ -position. Fergusons resultat leder till en optimal strategi i multi-pile misère subtraktionsspel, med endast en liten förändring från den normala spelstrategin.

För ett subtraktionsspel med en enda hög med tokens och en fast (men möjligen oändlig) subtraktionsuppsättning, om subtraktionsuppsättningen har godtyckligt stora gap mellan sina medlemmar, då uppsättningen P {\ ${\mathcal {P}}}$ - positionerna i spelet är nödvändigtvis oändliga. För varje subtraktionsspel med en ändlig subtraktionsmängd är nim-värdena avgränsade och både partitionen i ${\mathcal {P}}$ -positioner och ${\mathcal {N}}$ -positioner och sekvensen av nim-värden är så småningom periodiska. Perioden kan vara betydligt större än maxvärdet $x$ i subtraktionsmängden, men är som mest $2^{x}$ . Det finns emellertid oändliga subtraktionsmängder som producerar gränsade nim-värden men en aperiodisk sekvens av dessa värden.

Komplexitet

För subtraktionsspel med en fast (men möjligen oändlig) subtraktionsmängd, som att subtrahera en kvadrat, kan partitionen i P-positioner och N-positioner för talen upp till ett givet värde n {\displaystyle n} $i$ tid $O(n\log ^{2}n)$ . Nim-värdena för alla tal upp till $n$ kan beräknas i tiden $O(\min(ns,nm\log ^{ 2}n))$ där $s$ anger storleken på subtraktionsmängden (upp till $n$ ) och $m$ anger det största nim-värdet som förekommer i denna beräkning.

För generaliseringar av subtraktionsspel, spelade på vektorer av naturliga tal med en subtraktionsmängd vars vektorer kan ha såväl positiva som negativa koefficienter, är det ett oavgörligt problem att avgöra om två sådana spel har samma P-positioner och N-positioner.

Se även

Grundys spel och oktala spel , generaliseringar av subtraktionsspel där ett drag kan dela en hög med tokens i två

Anteckningar

Althöfer, Ingo ; Bültermann, Jörg (1995), "Superlinjära periodlängder i vissa subtraktionsspel", Theoretical Computer Science , 148 (1): 111–119, doi : 10.1016/0304-3975(95)00019-S , MR 1347670
Berlekamp, Elwyn R. ; Conway, John H. ; Guy, Richard K. (2001), Winning Ways for your Mathematical Plays , vol. 1 (andra upplagan), AK Peters
Bouton, Charles L. (1901–1902), "Nim, ett spel med en komplett matematisk teori", Annals of Mathematics , Second Series, 3 (1/4): 35–39, doi : 10.2307/1967631 , JSTOR 1967631
Coxeter, HSM (1953), "Det gyllene snittet, phyllotaxis och Wythoffs spel", Scripta Mathematica , 19 : 135–143, MR 0057548
Eppstein, David (2018), "Snabbare utvärdering av subtraktionsspel", i Ito, Hiro; Leonardi, Stefano; Pagli, Linda ; Prencipe, Giuseppe (red.), Proc. 9th International Conference on Fun with Algorithms (FUN 2018) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 100, Dagstuhl, Tyskland: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, s. 20:1–20:12, doi : 10.4230/lipics.fun.2018.20
Ferguson, TS (1974), "On sums of graph games with last player losing", International Journal of Game Theory , 3 : 159–167, doi : 10.1007/BF01763255 , MR 0384169
Golomb, Solomon W. (1966), "A matematisk undersökning av spel av "take-away" ", Journal of Combinatorial Theory , 1 : 443–458, doi : 10.1016/S0021-9800(66)80016-9 , MR 150209
Larsson, Urban; Fox, Nathan (2015), "An aperiodic subtraction game of nim-dimension two" (PDF) , Journal of Integer Sequences , 18 (7), Artikel 15.7.4, arXiv : 1503.05751 , MR 3370791
Larsson, Urban; Rubinstein-Salzedo , Simon (2016), "Grundy values of Fibonacci nim", International Journal of Game Theory , 45 (3): 617–625, arXiv : 1410.0332 , doi : 10.1007/s00182-015-34y 34y 34y 34 .
Larsson, Urban; Wästlund, Johan (2013), "From heaps of matches to the limits of computability" , Electronic Journal of Combinatorics , 20 (3): P41:1–P41:12, arXiv : 1202.0664 , MR 3118949
Whinihan, Michael J. (1963), "Fibonacci nim" (PDF) , Fibonacci Quarterly , 1 (4): 9–13
Wythoff, WA (1907), "A modification of the game of nim" , Nieuw Archief voor Wiskunde , 7 (2): 199–202