K nerozlišitelnosti kvocient - Indistinguishability quotient

v kombinatorická teorie her, a zejména v teorii nestranné hry v misère hrát, an k nerozeznání je komutativní monoid který zobecňuje a lokalizuje Sprague – Grundyho věta pro sadu pravidel konkrétní hry.

Ve zvláštním případě nepravidelného hraní nestranných her se tyto komutativní monoidy staly známými jako misere kvocienty.

Příklad: Varianta Misere Nim

Předpokládejme hru o Nim hraje se jako obvykle s hromadami předmětů, ale na začátku hry je každá hromada omezena na to, aby v ní byl jeden nebo dva objekty. V konvence normální hry, hráči se střídají, aby odstranili libovolný počet předmětů z hromady, a poslední hráč, který vezme předmět z hromady, je prohlášen za vítěze hry; při hře Misere je tento hráč poraženým ze hry.

Bez ohledu na to, zda je v platnosti běžná konvence nebo úmluva o hraní hry, výsledek takové pozice je nutně jednoho ze dvou typů:

N

Další hráč, který se pohne, má vynucené vítězství v nejlepší hře; nebo

P

Předchozí pohybující se hráč má vynucenou výhru.

Můžeme zapsat komutativní monoidní prezentaci pro klamný kvocient této 1- a 2-hromádové hry Nim tím, že nejprve přepracujeme její konvenční prudký -řešení založené na multiplikativní formě a jeho následné mírné úpravy pro misere hru.

Analýza normálního hraní

The Nimbers které se vyskytují při normální hře těchto pozic, jsou * 0, * 1, * 2 a * 3.

Nimber	Výsledek	Pozice s tím hbitostí
${displaystyle ast 0}$	P	Sudý počet hromád velikosti 1 a sudý počet hromád velikosti 2
${displaystyle ast 1}$	N	Zvláštní počet hromád velikosti 1 a sudý počet hromád velikosti 2
${displaystyle ast 2}$	N	Sudý počet hromád velikosti 1 a lichý počet hromád velikosti 2
${displaystyle ast 3}$	N	Zvláštní počet hromád velikosti 1 a lichý počet hromád velikosti 2

Tyto čtyři hodnoty nim se kombinují podle Kleinova čtyřčlenná skupina:

${displaystyle {egin {array} {c | ccc} + & ast 0 & ast 1 & ast 2 & ast 3 hline ast 0 & ast 0 & ast 1 & ast 2 & ast 3 ast 1 & ast 1 & ast 0 & ast 3 & ast 2 ast 2 & ast 2 & ast 3 & ast 0 & ast 1 ast 3 & ast 3 & ast 2 & ast 1 & ast 0end {pole} }}$

Kleinova čtyři skupina je také definována komutativem skupinová prezentace

${displaystyle mathrm {V} = jazyk a, bmid a ^ {2} = b ^ {2} = 1 úhel}$.

Prvky ${displaystyle mathrm {V} = {1, a, b, ab}}$ lze chápat jako korespondenci s hodnotami nim${displaystyle {ast 0, ast 1, ast 2, ast 3}}$ které se vyskytují při hraní této zjednodušené hry Nim; kombinují se přesně stejným způsobem.

Toto formální představení Kleinovy ​​čtyřskupiny zatím nepřidalo nic nového do konvenční analýzy 1- a 2-hromádového Nim pomocí nimbers a nim-addition. Místo toho jsme teorii pouze přepracovali do multiplikativní formy.

Analýza chybné hry

Výhodou multiplikativní formy je, že nám umožňuje zapsat podobné řešení pro misere kvocient Nim, který se hraje pouze s hromadami velikosti jedna a dvě.

Představujeme komutativní monoidní prezentace

${displaystyle mathrm {M} = jazyk a, bmid a ^ {2} = 1, b ^ {3} = náramek.}$

jehož šest prvků je ${displaystyle {1, a, b, ab, b ^ {2}, ab ^ {2}}.}$

Nesprávná hodnota kvocientu	Výsledek	Pozice v této třídě
1	N	Sudý počet hromád velikosti 1 a žádné hromady velikosti 2
A	P	Zvláštní počet hromád velikosti 1 a žádné hromady velikosti 2
b	N	Sudý počet hromád velikosti 1 a lichý počet hromád velikosti 2
ab	N	Zvláštní počet hromád velikosti 1 a lichý počet hromád velikosti 2
${displaystyle b ^ {2}}$	P	Sudý počet hromad 1 a sudý počet (větší než nula) hromad 2
${displaystyle ab ^ {2}}$	N	Zvláštní počet hromád velikosti 1 a sudý počet (větší než nula) hromád velikosti 2

Řešení správné hry misere Nim již plně popsal Bouton v roce 1902.^[1] V závěrečné větě tohoto článku Bouton píše, že v misere Nim „bezpečné kombinace jsou stejné jako dříve, kromě toho, že lichý počet hromádek, z nichž každá obsahuje jednu, je nyní bezpečný [tj. Je P-pozice], zatímco sudý počet z nich není bezpečný [tj. je N-pozice]. “ Výše uvedená formulace klamného kvocientu se snadno považuje za ekvivalentní v případě, že Nim hraje pouze s hromadami velikosti jedna a dvě.

Formální definice

Předpokládat ${displaystyle A}$ je sada nestranných kombinatorických her, která je definitivně generována s ohledem na disjunktivní částky a Zavřeno v obou následujících smyslech:

(1) Aditivní uzávěr: Pokud ${displaystyle G}$ a ${displaystyle H}$ jsou hry v ${displaystyle A}$, pak jejich disjunktivní součet ${displaystyle G + H}$ je také v ${displaystyle A}$.

(2) Dědičné uzavření: Pokud ${displaystyle G}$ je hra v ${displaystyle A}$ a ${displaystyle H}$ je možnost ${displaystyle G}$, pak ${displaystyle H}$ je také v ${displaystyle A}$.

Dále definujte na ${displaystyle A}$ the shoda nerozeznatelnosti ≈ který se týká dvou her ${displaystyle G}$ a ${displaystyle H}$ pokud pro každou volbu hry ${displaystyle X}$ v ${displaystyle A}$, dvě polohy ${displaystyle G + X}$ a ${displaystyle H + X}$ mít stejný výsledek (tj. buď vyhrají oba hráči prvního hráče v nejlepší hře ${displaystyle A}$, nebo alternativně jsou oba výhry druhého hráče).

Jeden snadno zkontroluje, že ≈ je skutečně shoda na množině všech disjunktivních pozic součtů ${displaystyle A}$, a že to platí bez ohledu na to, zda se hra hraje v normálním nebo špatném hraní. Souhrn všech tříd shody tvoří k nerozeznání.

Li ${displaystyle A}$ se hraje jako nestranná hra s normálním hraním (poslední výhra), pak třídy shody ${displaystyle A}$ jsou ve vzájemném souladu s hodnotami nim, které se vyskytují při hraní hry (samy o sobě jsou určeny Sprague – Grundyho věta ).

Ve hře Misere tvoří třídy shody a komutativní monoid Místo toho se stal známým jako klamný kvocient.

Algoritmy pro výpočet chybných podílů

Bylo vypočítáno mnoho složitějších a složitějších klamných podílů pro různé nestranné hry, zejména pro osmičkové hry Aaron N. Siegel navrhl univerzální algoritmus pro výpočet klamné kvocientové monoidní prezentace dané konečné sady misere nestranných herních pozic.^[2] v příloze C.

Viz také

• Sprague – Grundyho věta
• Rodová teorie

Reference

externí odkazy

• http://miseregames.org/