Vyřešená hra - Solved game

Vyřešit hra je hra , jejíž výsledek (výhra, prohra nebo remíza ) může být správně předpovědět z jakékoli pozice, za předpokladu, že oba hráči hrát perfektně. Tento koncept je obvykle aplikován na abstraktní strategické hry , a zejména na hry s úplnými informacemi a bez prvku náhody; řešení takové hry může využívat kombinatorickou teorii her a/nebo počítačovou pomoc.

Přehled

Hra pro dva hráče může být řešen na několika úrovních:

Ultra slabý
Dokažte, zda první hráč vyhraje, prohraje nebo remizuje z počáteční pozice, za předpokladu dokonalé hry na obou stranách. To může být nekonstruktivní důkaz (případně zahrnující argument o krádeži strategie ), který ve skutečnosti nemusí určovat žádné tahy dokonalé hry.
Slabý
Poskytněte algoritmus, který zajistí výhru pro jednoho hráče nebo remízu pro oba proti případným tahům soupeře od začátku hry. To znamená, že vytvořte alespoň jednu úplnou ideální hru (všechny tahy začínají až končí) s důkazem, že každý tah je optimální pro hráče, který ho dělá.
Silný
Poskytněte algoritmus, který dokáže vytvářet dokonalé pohyby z jakékoli polohy, i když již došlo k chybám na jedné nebo obou stranách.

Navzdory svému jménu mnozí teoretici her věří, že „ultra slabé“ důkazy jsou nejhlubší, nejzajímavější a nejcennější. "Ultra slabé" důkazy vyžadují, aby učenec uvažoval o abstraktních vlastnostech hry a ukázal, jak tyto vlastnosti vedou k určitým výsledkům, pokud je realizována dokonalá hra.

Naproti tomu „silné“ důkazy často postupují hrubou silou - pomocí počítače k ​​vyčerpávajícímu prohledávání herního stromu zjistí, co by se stalo, kdyby byla realizována dokonalá hra. Výsledný důkaz poskytuje optimální strategii pro každou možnou pozici na hrací ploše. Tyto důkazy však nejsou tak nápomocné při pochopení hlubších důvodů, proč jsou některé hry řešitelné jako remíza a jiné, zdánlivě velmi podobné hry, jsou řešitelné jako výhra.

Vzhledem k pravidlům jakékoli hry pro dvě osoby s konečným počtem pozic lze vždy triviálně sestrojit algoritmus minimaxu , který by vyčerpávajícím způsobem procházel stromem hry . Jelikož však u mnoha netriviálních her by takový algoritmus vyžadoval nerealizovatelný čas na vygenerování tahu v dané pozici, není hra považována za vyřešenou slabě nebo silně, pokud algoritmus nelze spustit pomocí stávajícího hardwaru v rozumný čas. Mnoho algoritmů spoléhá na obrovskou předem vygenerovanou databázi a ve skutečnosti nejsou ničím jiným.

Jako příklad silného řešení je hra tic-tac-toe řešitelná jako remíza pro oba hráče s perfektní hrou (výsledek dokonce ručně určitelný školáky). Hry jako nim také připouštějí důkladnou analýzu pomocí kombinatorické teorie her .

Zda je hra vyřešena, nemusí nutně znamenat to, zda zůstává pro lidi zajímavé hrát. I silně vyřešená hra může být stále zajímavá, pokud je její řešení příliš složité na to, aby se dalo zapamatovat; naopak slabě vyřešená hra může ztratit na přitažlivosti, pokud je vítězná strategie dostatečně jednoduchá na zapamatování (např. Maharajah a Sepoys ). Ultra slabé řešení (např. Chomp nebo Hex na dostatečně velké desce) obecně nemá vliv na hratelnost.

Perfektní hra

V teorii her , perfektní hra je chování nebo strategie hráče, který vede k nejlepším možným výsledkem pro tohoto hráče bez ohledu na reakci ze strany soupeře. Dokonalá hra pro hru je známá, když je hra vyřešena. Na základě pravidel hry lze vyhodnotit každou možnou konečnou pozici (výhru, prohru nebo remízu). By zpětném uvažování , lze rekurzivně vyhodnotit non-konečné pozici identické do pozice, která je jedním odklon a nejlepší ceněný pro hráče, jehož pohyb je. Přechod mezi pozicemi tedy nikdy nemůže vést k lepšímu hodnocení pohybujícího se hráče a dokonalý pohyb v pozici by byl přechodem mezi pozicemi, které jsou stejně hodnoceny. Například dokonalý hráč na vylosované pozici by vždy získal remízu nebo výhru, nikdy ne prohru. Pokud existuje více možností se stejným výsledkem, je dokonalá hra někdy považována za nejrychlejší metodu vedoucí k dobrému výsledku nebo za nejpomalejší metodu vedoucí ke špatnému výsledku.

Perfektní hru lze zobecnit na neperfektní informační hry jako strategii, která by zaručovala nejvyšší minimální očekávaný výsledek bez ohledu na strategii soupeře. Jako dokonalá strategie pro nůžky papírenského papíru by například bylo, kdybyste náhodně vybrali každou z možností se stejnou (1/3) pravděpodobností. Nevýhodou v tomto případě je, že tato strategie nikdy nebude využívat neoptimální strategie protivníka, takže očekávaný výsledek této strategie oproti jakékoli strategii bude vždy stejný jako minimální očekávaný výsledek.

Ačkoli optimální strategie hry nemusí být (zatím) známa, počítač pro hraní her může stále těžit z řešení hry z určitých pozic koncových her (ve formě tabulek s koncovými hrami ), což jí umožní hrát perfektně po několika bod ve hře. Počítačové šachové programy jsou dobře známé.

Vyřešené hry

Awari (hra rodiny Mancala )
Varianta Oware umožňující hru končit „Grand Slam“ byl silně řešen Henri Bal a John Romein na Vrije Universiteit v Amsterdamu , Nizozemsko (2002). Každý hráč může přinutit hru k remíze.
Tyčinky
Druhý hráč může vždy vynutit výhru.
Connect Four
Vyřešil nejprve James D. Allen 1. října 1988 a nezávisle Victor Allis 16. října 1988. První hráč si může vynutit výhru. Silně vyřešeno 8vrstvou databází Johna Trompa (4. února 1995). Slabé řešení pro všechny velikosti desek, kde šířka+výška je maximálně 15 (stejně jako 8 × 8 na konci roku 2015) (18. února 2006).
Anglické návrhy (dáma)
Tento 8 × 8 varianta návrhů byla slabě vyřešen 29. dubna 2007, týmem Jonathan Schaeffer . Ze standardní výchozí pozice mohou oba hráči zaručit remízu perfektní hrou. Checkers je největší hra, která byla dosud vyřešena, s vyhledávacím prostorem 5 × 10 20 . Počet zahrnutých výpočtů byl 10 14 , které byly provedeny po dobu 18 let. Proces zahrnoval 200 stolních počítačů na svém vrcholu až na zhruba 50.
Fanorona
Slabě to vyřešil Maarten Schadd. Tato hra je remíza.
Zdarma gomoku
Vyřešil Victor Allis (1993). První hráč si může vynutit výhru bez pravidel otevírání.
Duch
Vyřešil Alan Frank pomocí oficiálního slovníku hráčů Scrabble v roce 1987.
Hex
  • Argumentace Strategie pro krádež (jak použitý John Nash ), ukazuje, že všechny čtvercové velikosti deska nemůže být ztracena prvním hráčem. V kombinaci s důkazem nemožnosti remízy to ukazuje, že hra je ultra slabá vyřešená jako výhra prvního hráče.
  • Silně vyřešeno několika počítači pro velikosti desek až 6 × 6.
  • Jing Yang předvedl vítěznou strategii (slabé řešení) pro desky 7 × 7, 8 × 8 a 9 × 9.
  • Vítězná strategie pro Hex s výměnou je známá pro desku 7 × 7.
  • Silné řešení Hex na desce N × N je nepravděpodobné, protože se ukázalo, že problém je úplný pro PSPACE .
  • Hraje -li se Hex na desce N × ( N +1), pak hráč, který má kratší vzdálenost k připojení, může vždy vyhrát jednoduchou strategií párování, a to i s nevýhodou druhého hraní.
  • Slabé řešení je známé pro všechny otevírací pohyby na desce 8 × 8.
Hexapawn
Varianta 3 × 3 vyřešena jako výhra pro černé, vyřešeno také několik dalších větších variant.
Kalah
Většinu variant vyřešili Geoffrey Irving, Jeroen Donkers a Jos Uiterwijk (2000) kromě Kalah (6/6). Variantu (6/6) vyřešil Anders Carstensen (2011). Ve většině případů byla prokázána silná výhoda pro prvního hráče. Mark Rawlings z MD Gaithersburg kvantifikoval velikost vítězství prvního hráče ve variantě (6/6) (2015). Po vytvoření 39 GB databází koncových her, vyhledávání celkem 106 dní času CPU a více než 55 bilionů uzlů, bylo prokázáno, že s perfektní hrou první hráč vyhraje o 2. Všimněte si, že všechny tyto výsledky se týkají programu Empty-pit Capture varianty, a proto jsou pro standardní hru velmi omezeným zájmem. Analýza hry se standardními pravidly byla nyní zveřejněna pro Kalah (6,4), což je výhra 8 pro prvního hráče, a Kalah (6,5), což je výhra 10 pro prvního hráče. Analýza Kalah (6,6) se standardními pravidly probíhá, nicméně bylo prokázáno, že je to výhra alespoň 4 pro prvního hráče.
L hra
Snadno řešitelné. Každý hráč může přinutit hru k remíze.
Ztráta šachů
Slabě vyřešeno jako výhra pro bílé počínaje 1. e3.
Maharajah a Sepoys
Tato asymetrická hra je výhrou pro hráče sepoys se správnou hrou.
Nim
Silně vyřešeno.
Morris devíti mužů
Vyřešil Ralph Gasser (1993). Každý hráč může přinutit hru k remíze.
Pořádek a chaos
Objednávka (první hráč) vítězí.
Ohvalhu
Slabě vyřešeno lidmi, ale dokázáno počítači. (Dakon však není totožný s Ohvalhu, hrou, kterou ve skutečnosti pozoroval de Voogt)
Pangki
Silně vyřešen Jasonem Doucette (2001). Tato hra je remíza. Pokud zahodíte zrcadlené pozice, existují pouze dva jedinečné první tahy. Jeden vynutí remízu a druhý dá soupeři vynucenou výhru za 15.
Pentominoes
Slabě vyřešeno HK Orman. Je to výhra pro prvního hráče.
Poddavki („Ruská dáma rozdávající “)
Vyřešili Osipov a Morozev v roce 2011. Bílé vítězství.
Kvarto
Vyřešil Luc Goossens (1998). Dva dokonalí hráči budou vždy losovat.
Qubic
Slabě vyřešili Oren Patashnik (1980) a Victor Allis . Vyhrává první hráč.
Hra podobná Renju bez pravidel otevírání
Tvrdí, že je vyřešen Jánosem Wagnerem a Istvánem Virágem (2001). Výhra prvního hráče.
Sim
Slabě vyřešeno: výhra pro druhého hráče.
Teeko
Vyřešil Guy Steele (1998). V závislosti na variantě buď výhra prvního hráče, nebo remíza.
Morris tří mužů
Triviálně řešitelné. Každý hráč může přinutit hru k remíze.
Tři mušketýři
Silně vyřešen Johannesem Lairem v roce 2009 a slabě vyřešen Ali Elabridim v roce 2017. Je to výhra pro modré figury (muži kardinála Richelieua, neboli nepřítele).
Piškvorky
Triviálně silně řešitelný kvůli malému stromu zvěře. Pokud nedojde k žádným chybám, hra se losuje, přičemž v úvodním tahu není možná chyba.
Tygři a kozy
Slabě vyřešen Yew Jin Lim (2007). Tato hra je remíza.
Wythoffova hra
Silně vyřešeno.

Částečně vyřešené hry

Šachy
Hlavní článek: Řešení šachů
Plně řešitelné šachy zůstávají nepolapitelné a spekuluje se, že složitost hry může zabránit jejímu řešení. Prostřednictvím retrográdní počítačové analýzy , endgame tablebases (silné roztoky) Bylo zjištěno, že pro všechny tří- až sedmi kusů endgames počítal dva krále jako kusy.
Byly vyřešeny některé varianty šachů na menší desce se sníženým počtem figurek . Byly také vyřešeny některé další populární varianty; například slabé řešení Maharajah a Sepoys je snadno zapamatovatelná série tahů, která zaručuje vítězství hráči „sepoys“.
Jít
Deska 5 × 5 byla slabě vyřešena pro všechny otevírací tahy v roce 2002. Deska 7 × 7 byla slabě vyřešena v roce 2015. Lidé obvykle hrají na desce 19 × 19, což je o více než 145 řádů složitější než 7 × 7.
Mezinárodní návrhy
Byly vyřešeny všechny pozice koncových her se dvěma až sedmi kusy, stejně jako pozice s 4 × 4 a 5 × 3 kusy, kde každá strana měla jednoho krále nebo méně, pozice s pěti muži proti čtyřem mužům, pozice s pěti muži proti třem mužům a jednomu král, a pozice se čtyřmi muži a jedním králem proti čtyřem mužům. Pozice koncových her byly vyřešeny v roce 2007 Edem Gilbertem ze Spojených států. Počítačová analýza ukázala, že pokud oba hráči hráli perfektně, bylo velmi pravděpodobné, že skončí remízou.
m , n , k -hra
Je triviální ukázat, že druhý hráč nikdy nemůže vyhrát; viz argument o krádeži strategie . Téměř všechny případy byly vyřešeny slabě pro k ≤ 4. Některé výsledky jsou známy pro k = 5. Hry jsou kresleny pro k ≥ 8.
Reversi (Othello)
Slabé řešení na desce 4 × 4 a 6 × 6 jako vítězství druhého hráče v červenci 1993 Joel Feinstein. Na desce 8 × 8 (standardní) to není matematicky vyřešeno, ačkoli počítačová analýza ukazuje pravděpodobnou remízu. Neexistují žádné silně předpokládané odhady kromě zvýšených šancí pro začínajícího hráče (černé) na deskách 10 × 10 a větších.

Viz také

Reference

Další čtení

  • Allis, porazil mistra světa? Nejmodernější způsob hraní počítačových her. ve výzkumu nových přístupů k deskovým hrám.

externí odkazy