Oskiljbar kvot

I kombinatorisk spelteori , och särskilt i teorin om opartiska spel i misère- spel, är en omöjlighetskvotient en kommutativ monoid som generaliserar och lokaliserar Sprague-Grundy-satsen för ett specifikt spels regeluppsättning.

I det specifika fallet med opartiska spel med misere-play har sådana kommutativa monoider blivit kända som misere-kvoter .

Exempel: Misere Nim variant

Anta att spelet Nim spelas som vanligt med högar av föremål, men att i början av spelet är varje hög begränsad till att ha antingen ett eller två föremål i sig. I normalspelskonventionen turas spelare om att ta bort valfritt antal föremål från en hög, och den sista spelaren som tar ett föremål från en hög utses till vinnare av spelet; i Misere-spel är den spelaren spelets förlorare.

Oavsett om den normala eller eländiga spelkonventionen är i kraft, är resultatet av en sådan position nödvändigtvis av en av två typer:

N: Nästa spelare att flytta har en framtvingad vinst i bästa spel; eller

P: Den föregående spelaren att flytta har en tvingad vinst.

Vi kan skriva ner en kommutativ monoid presentation för eländekvoten i detta 1- och 2-högars Nim-spel genom att först gjuta om dess konventionella nimberbaserade lösning till en multiplikativ form, och sedan modifiera det något för eländigt spel.

Normalspelsanalys

De nimbers som förekommer i det normala spelet av sådana positioner är *0, *1, *2 och *3.

Nimber	Resultat	Positioner med den nimberen
$\ast 0$	P	Jämnt antal högar av storlek 1 och jämnt antal högar av storlek 2
$\ast 1$	N	Udda antal högar av storlek 1 och jämnt antal högar av storlek 2
$\ast 2$	N	Jämnt antal högar av storlek 1 och udda antal högar av storlek 2
$\ast 3$	N	Udda antal högar av storlek 1 och udda antal högar av storlek 2

Dessa fyra nim-värden kombineras enligt Klein fyra-gruppen :

\begin

Klein-fyragruppen definieras också av den kommutativa grupppresentationen

\mathrm {V} =\langle a,b\mid a^{2}=b^{2}=1\rangle

.

Elementen i $\mathrm {V} =\{1,a,b,ab\}$ kan ses som i en-till-korrespondens med nim värden $\{\ast 0,\ast 1,\ast 2,\ast 3\}$ som förekommer i detta förenklade Nim-spel; de kombinerar exakt på samma sätt.

Hittills har denna formella introduktion av Klein-fyragruppen inte tillfört något nytt till den konventionella analysen av 1- och 2-stapel Nim med hjälp av nimbers och nim-addition. Istället har vi bara gjort om teorin till en multiplikativ form.

Misere-play analys

Fördelen med den multiplikativa formen är att den tillåter oss att skriva ner en liknande lösning för eländekvoten av Nim som spelas med bara högar av storlek ett och två.

Vi introducerar den kommutativa monoidpresentationen

\mathrm {M} =\langle a,b\mid a^{2}=1,\ b^{3}=b\rangle .

vars sex element är $\{1,a,b,ab,b^{2},ab^{2}\}.$

Misere kvotvärde	Resultat	Positioner i den klassen
$1$	N	Jämnt antal högar av storlek 1 och inga högar av storlek 2
$a$	P	Udda antal högar av storlek 1 och inga högar av storlek 2
$b$	N	Jämnt antal högar av storlek 1 och udda antal högar av storlek 2
$ab$	N	Udda antal högar av storlek 1 och udda antal högar av storlek 2
$b^{2}$	P	Jämnt antal högar av storlek 1 och jämnt antal (större än noll) av högar av storlek 2
$ab^{2}$	N	Udda antal högar av storlek 1 och jämnt antal (större än noll) av högar av storlek 2

Lösningen på det korrekta spelet av misere Nim beskrevs redan fullt ut av Bouton 1902. I den sista meningen i den tidningen skriver Bouton att i misere Nim "är de säkra kombinationerna desamma som tidigare, förutom att ett udda antal högar , som var och en innehåller en, är nu säker [dvs. är en P-position], medan ett jämnt antal ettor inte är säkert [dvs. är en N-position]." Miserkvotens formulering ovan kan lätt ses vara likvärdig i fallet med Nim som bara spelas med högar av storlek ett och två.

Formell definition

Anta att $A$ är en uppsättning opartiska kombinatoriska spel som är ändligt genererade med avseende på disjunktiva summor och stängda i båda följande betydelser:

(1) Additiv stängning : Om $G$ och $H$ är spel i $A$ , så är deras disjunktiva summa $G+H$ också i ${\ displaystil A}$ .

(2) Ärftlig stängning : Om $G$ är ett spel i $A$ och $H$ är ett alternativ för $G$ , så är $H$ också i $A$ .

Definiera sedan på $A$ den omöjliga kongruensen ≈ som relaterar till två spel $G$ och $H$ om för varje val av ett spel $X$ i $A$ , de två positionerna $G+X$ och $H+X$ har samma resultat (dvs. är antingen båda första spelare vinner i bästa spel av $A$ , eller alternativt vinner båda andra spelare).

Man kontrollerar lätt att ≈ verkligen är en kongruens på mängden av alla disjunktiva positionssummor i ${\displaystyle A} ,$ och att detta är sant oavsett om spelet spelas i normalt eller eländigt spel. Helheten av alla kongruensklasser bildar oskiljbarhetskvoten .

Om $A$ spelas som ett normalt spel (sist spelade vinnande) opartiskt spel, är kongruensklasserna för $A$ i en-till-en-överensstämmelse med nim-värdena som förekommer i spelets spel (själv bestäms av Sprague-Grundy-satsen) .

I eländespel bildar kongruensklasserna istället en kommutativ monoid , och den har blivit känd som en eländekvot.

Algoritmer för att beräkna eländekvoter

Många mer komplicerade och intrikata eländekvoter har beräknats för olika opartiska spel, och särskilt för oktala spel . En allmän algoritm för att beräkna eländekvoten monoid presentation av en given en finit uppsättning eländiga opartiska spelpositioner har utarbetats av Aaron N. Siegel och beskrivs i dess Appendix C.

Se även

Plambeck, Thane E. (2005-07-19). "Tämja vildmarken i opartiska kombinatoriska spel" (PDF) . HELTAL: The Electronic Journal of Combinatorial Number Theory (PDF). 5 (G05) . Hämtad 2010-12-21 .

Siegel, Aaron N. Kombinatorisk spelteori . Vol. 146. American Mathematical Society 2013. ISBN 9780821851906 .

externa länkar

http://miseregames.org/