Posetová hra - Poset game - Wikipedia

v kombinatorická teorie her, poset hry jsou matematický strategické hry, zobecňující mnoho známých her, jako je Nim a Chomp.[1] V takových hrách začínají dva hráči s a poset (A částečně objednaná sada), a střídavě vyberte jeden bod v posetu, odstraňte jej a všechny body, které jsou větší. Hráč, který nemá na výběr, prohrává.

Hraní her

Vzhledem k částečně objednaná sada (P, <), nechat

označte poset vytvořený odstraněním X z P.

Posetová hra je zapnutá P, hrál mezi dvěma hráči konvenčně pojmenovanými Alice a Bob, je následující:

  • Alice si vybere bod X ∈ P; tedy nahrazovat P s PX, a pak předá turnu Bobovi, který hraje dál PXa předává odbočku Alici.
  • Hráč prohraje, pokud je na řadě, a nemá na výběr žádné body.

Příklady

Li P je konečný úplně objednaná sada, poté hrát hru P je přesně to samé jako hraní hry ve hře Nim s hromadou velikosti |P|. U obou her je možné zvolit tah, který povede ke hře stejného typu, jehož velikost je libovolné číslo menší než |P|. Stejným způsobem je posetová hra s disjunktním spojením celkových objednávek ekvivalentní hře Nim s více hromadami s velikostmi rovnými řetězcům v posetu.

Zvláštní případ Hackenbush, ve kterém jsou všechny hrany zelené (lze je oříznout kterýmkoli hráčem) a každá konfigurace má formu a les, lze vyjádřit podobně jako posetová hra na poset, ve které pro každý prvek X, existuje maximálně jeden prvek y pro který X kryty y. Li X kryty y, pak y je rodičem X v lese, ve kterém se hra hraje.

Chomp mohou být vyjádřeny podobně jako posetová hra na produkt z celkového počtu objednávek, z nichž infimum byla odstraněna.

Zelená hodnota

Poset hry jsou nestranné hry, což znamená, že každý pohyb, který má Alice k dispozici, by byl k dispozici také Bobovi, kdyby to Alice mohla složit a naopak. Proto by Sprague – Grundyho věta, každá pozice v posetové hře má hodnotu Grundy, číslo popisující ekvivalentní pozici ve hře Nim. Zelenou hodnotu posetu lze vypočítat jako nejmenší přirozené číslo, které není Grundovou hodnotou žádného PX, X ∈ P. To znamená[2]

Toto číslo může být použito k popisu optimálního hraní hry v posetové hře. Zejména hodnota Grundy je nenulová, když hráč, jehož řada je na řadě, má vítěznou strategii, a nula, když aktuální hráč nemůže vyhrát proti optimální hře od svého soupeře. Vítězná strategie ve hře spočívá v přesunu do polohy, jejíž Grundyova hodnota je nulová, kdykoli je to možné.

Krádež strategie

A argument o krádeži strategie ukazuje, že hodnota Grundy je nenulová pro každý poset, který má a supremum. Pro, pojďme X být supremem částečně objednané sady P. Li PX má tedy zelenou hodnotu nula P sám má nenulovou hodnotu podle výše uvedeného vzorce; v tomto případě, X je vítězný tah P. Pokud na druhou stranu PX má nenulovou hodnotu Grundy, pak musí existovat vítězný tah y v PX, takže Grundyova hodnota (PX)y je nula. Ale za předpokladu, že X je supremum, X > y a (PX)y = Py, takže vítězný tah y je k dispozici také v P a znovu P musí mít nenulovou zelenou hodnotu.[1]

Z triviálních důvodů má poset s infimem také nenulovou hodnotu Grundy: přesun do infimum je vždy vítězný tah.

Složitost

Rozhodování o vítězi libovolné hry s konečnými posety je PSPACE - kompletní.[3] To znamená, že pokud P = PSPACE, je výpočet Grundyho hodnoty libovolné posetové hry výpočetně obtížné.

Reference

  1. ^ A b Soltys, Michael; Wilson, Craig (2011), „O složitosti výpočtu vítězných strategií pro hry s konečným množstvím“, Teorie výpočetních systémů, 48 (3): 680–692, CiteSeerX  10.1.1.150.3656, doi:10.1007 / s00224-010-9254-r, PAN  2770813.
  2. ^ Byrnes, Steven (2003), „Periodicita hry Poset“ (PDF), Celá čísla, 3 (G3): 1–16, PAN  2036487.
  3. ^ Grier, Daniel (2012), „Rozhodování o vítězi svévolné konečné hry Poset je PSPACE-Complete“, Automaty, jazyky a programování, Přednášky v informatice, 7965, str. 497–503, arXiv:1209.1750, Bibcode:2012arXiv1209.1750G, doi:10.1007/978-3-642-39206-1_42, ISBN  978-3-642-39205-4.