Hra vyřešena

Vyřešit hra je hra , jejíž výsledek (vítězství, prohry, nebo nula) může být správně předpovědět z jakékoli pozice, za předpokladu, že oba hráči hrají výborně.

Přehled

Hra pro dva  (v) může mít několik úrovní „rozlišovací schopností“

Velmi nízké Dokažte, zda první hráč vyhraje, prohraje nebo remizuje z výchozí pozice za předpokladu perfektní hry na obou stranách. Může to být důkaz nekonstruktivní (možná se strategií ukázkou letu  (ne) ), který nemusí skutečně určovat pohyby dokonalé hry. Nízký Poskytuje algoritmus, který zaručuje vítězství jednoho z hráčů nebo remízu proti všem možným pohybům soupeře od začátku hry. To znamená, že toto rozlišení produkuje alespoň úplnou ideální hru (všechny tahy od začátku do povrch) s důkazem, že každý úder je pro hráče optimální. To nutně neznamená, že počítačový program využívající toto rozlišení bude fungovat optimálně proti nedokonalému protivníkovi. Například program Chinook checkers nikdy nezmění pozici draw do pozice prohrávající (protože nízké rozlišení v checkers dokazuje, že jde o remízu), ale může se pohybovat z pozice vítěze do pozice prohry. Pozice draw protože 'Chinook ne' Neočekávejte, že protivník udělá střelu, která nevyhraje, ale mohla by prohrát, a tyto tahy plně neanalyzuje. Silný Poskytuje algoritmus, který umožňuje vytvářet ideální záběry z jakékoli pozice, i když již na jedné nebo druhé straně došlo k chybám.

Přes své jméno se mnoho teoretiků her domnívá, že „ultra-slabé“ důkazy jsou nejhlubší, nejzajímavější a nejužitečnější. „Ultra slabé“ důkazy vyžadují vědecké uvažování o abstraktních vlastnostech hry a ukazují, jak tyto vlastnosti vedou k určitým výsledkům, pokud je dosaženo dokonalé hry.

Naproti tomu „silné“ důkazy často vycházejí hrubou silou - pomocí počítače k ​​vyčerpávajícímu prozkoumání stromu hry, abychom pochopili, co by se stalo, kdyby byla vytvořena dokonalá hra. Důkazy vyplývající z tohoto výzkumu poskytují optimální strategii pro každou pozici na desce. Tento důkaz však není užitečný pro další pochopení toho, proč jsou některé hry vyřešitelné remízou, zatímco jiné zdánlivě velmi podobné hry lze vyřešit vítězstvím.

Vzhledem k pravidlům hry pro dva hráče s konečným počtem pozic lze vždy triviálně sestrojit algoritmus minimax, který by vyčerpávajícím způsobem procházel herním stromem. Protože však pro mnoho netriviálních her by takový algoritmus potřeboval příliš mnoho čas na generování pohybu v dané pozici, hra se nepovažuje za vyřešenou slabě nebo silně, pokud nelze algoritmus implementovat s existujícím hardwarem v rozumném časovém rámci. Mnoho algoritmů se spoléhá na velkou předgenerovanou databázi a vlastně nic víc.

Jako příklad solidního řešení je hra tic-tac-toe řešitelná jako remíza pro oba hráče s dokonalou hrou (výsledek, který lze dokonce ručně určit studenty). Hry jako Nimovy hry také umožňují přísnou analýzu pomocí kombinatorické teorie her .

Jen proto, že je hra vyřešena, nemusí nutně znamenat, že pro člověka není stále 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 zapamatování; Naopak slabě vyřešená hra může ztratit svou přitažlivost, pokud je úspěch strategie dostatečně snadno zapamatovatelný (např . Maharajah a Sepoys ). Ultra nízké rozlišení (např. Chomp nebo Hex na dostatečně velkém gramofonu) obvykle nemá vliv na hraní.

Navíc, i když hra není vyřešena, je možné, že algoritmus poskytuje dobrou aproximaci řešení: například článek v Science ze dneledna 2015oznámili, že jejich verze Poker Heads up  (ne) omezuje záruky, že robot Cepheus z Texasu drží pokerový život lidského hráče nestačí na statisticky významné zjištění, že jeho strategie není přesným řešením.

Perfektní hra

V herní teorii , ideální hra je chování nebo strategie hráče, který vede k nejlepším možným výsledkem pro hráče, bez ohledu na reakci soupeře. Na základě pravidel hry lze hodnotit každou konečnou pozici (například výhru, prohru nebo remízu). Při zpětném zřetězení lze rekurzivně vyhodnotit nefinální pozici jako identickou s tou, která se pohybuje od nejlepší hodnoty pro hráče, jehož je na řadě. Přechod mezi pozicemi tedy nikdy nemůže vyústit v lepší hodnocení hráče, který je na řadě, a dokonalý pohyb v pozici by byl přechodem mezi pozicemi, které jsou hodnoceny stejně. Například dokonalý hráč s nerozhodnou pozicí vždy skončí remízou nebo výhrou, nikdy ne prohrou. Pokud existuje několik možností nabízejících stejný výsledek, 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.

Hru lze zobecnit na dokonalé hry na  nedokonalé informace  (in) , protože strategie zaručující minimální výsledek je nejvyšší bez ohledu na strategii soupeře. Například dokonalou strategií pro nůžky Rock-Paper-Scissors by bylo náhodně vybrat každou z možností se stejnou pravděpodobností (1/3). Nevýhodou tohoto příkladu je, že tato strategie nikdy nevyužije neoptimální strategie oponenta, takže očekávané výsledky této strategie proti jakékoli strategii budou vždy stejné jako minimální očekávaný výsledek.

Ačkoli optimální strategie hry nelze (zatím) je známo, herní počítač může stále těžit z herní řešení od některých koncových poloh (pomocí finálových stolů ), který bude mít možnost hrát. Dokonale od určitého bodu ve hře. Šachy programy jsou dobře známé.

Vyřešené hry

Awalé (hra z rodiny Mancala ) Varianta Oware umožňující „grandslamovou“ koncovku byla silně vyřešena Henri Balem  (en) a Jean Romeinem na Free University of Amsterdam v Nizozemsku (2002). Každý hráč může hru přinutit k remíze. Je třeba poznamenat, že španělský mistr Oware Viktor Bautista i Roca oznámil na své staré domovské stránce manqala.org , že „Awari Oracle“ (zcela založené na výzkumu Bala a Romeina) mělo ve finále několik nedostatků a že je možné proto pochybujte, že řešení Bala a Romeina je platné. Obě stránky ( manqala.org a Oracle) však byly vyřazeny z internetu a zdá se, že není možný žádný nový výzkum. To odhaluje hlavní problém: Velká část výzkumu prováděného v oblasti řešení her není plně recenzována. Malé chyby v programování, které však mohou přinést velmi odlišné výsledky, obvykle zůstávají bez povšimnutí. Anglické dámy Tato varianta hry dáma 8 × 8 byla slabě vyřešena29.dubna 2007týmem Jonathana Schaeffera , známého pro Chinook , „mistra světa Ladies Man-Machine“. Ze standardní výchozí pozice mohou oba hráči zaručit remízu s perfektní hrou. Dáma je největší hra, která byla dosud vyřešena, s prostorem pro vyhledávání 5 × 10 20 . Počet výpočtů, které měly být provedeny, bylo 10 14 , které byly provedeny po dobu 18 let. Tento proces zahrnoval 200 desktopů na svém vrcholu, až kolem 50. Dobutsu shogi Silně vyřešen. Výsledkem hry je vítězství hráče, který nezačne. Fanorona Slabě vyřešen Maartenem Schaddem. Hra končí remízou. Zdarma gomoku Vyřešil Victor Allis  (en) (1993). První hráč si může vynutit výhru bez pravidel otevření. Duch  (en) Vyřešen Alanem Frankem v oficiálním slovníku Scrabble  (en) v roce 1987. Hex Hexapawn Varianta 3 × 3 je vyřešena jako vítězství černé, vyřešeno je i několik dalších větších variant. Hra s hůlkami Druhý hráč si stále může vynutit vítězství. Kalah Většinu variant vyřešili Geoffrey Irving, Jeroen Donkers a Jos Uiterwijk (2000), s výjimkou Kalah (6/6). Variantu (6/6) ř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 kvantifikoval velikost první výhry hráče ve variantě (6/6) (2015). Po vytvoření finální databáze o velikosti 39 gigabajtů a průzkumu 106denního času CPU a více než 55 bilionů uzlů bylo prokázáno, že s dokonalou hrou první hráč vyhrává o 2. Je třeba poznamenat, že všechny tyto výsledky odkazují k variantě „Empty-pit Capture“, a proto mají pro standardní hru velmi omezený zájem. Analýza hry se standardním pravidlem byla vytvořena pro Kalaha (6,4), což je výhra 8 pro začínajícího hráče, a Kalaha (6,5), což je výhra 10 pro prvního hráče. Analýza Kalah (6.6) se standardními pravidly stále probíhá, ale ukázalo se, že je výhrou alespoň 4 pro prvního hráče. L set Snadno řešitelné. Každý hráč může hru přinutit k remíze. Kdo prohraje, vyhrává Slabě vyřešen jako výhra pro White počínaje 1.e3. Maharajah a sepoys Tato asymetrická hra zaručuje vítězství hráče Sepoy , pokud hraje správně. Nim hry Silně vyřešen. Mill hra Vyřešil Ralph Gasser (1993). Každý hráč může hru přinutit k remíze. Congklak Slabě vyřešené lidmi, ale dokázané počítači. Dakon však není totéž jako Congklak, hra, kterou de Voogt skutečně sledoval. Pangki Silně vyřešen Jason Doucette (2001). Tato hra je remíza. Existují pouze dva první pohyby, pokud ignorujete symetrické polohy. Jeden vynucuje remízu a druhý dává soupeři vynucené vítězství v 15. Pentago Silně vyřešen. První hráč vyhrává. Pentominoes Slabě vyřešeno Hilarie K.Orman. Je to vítězství prvního hráče. Síla 4 Nejprve vyřešil James D. Allen (1 st říjen 1988,) a nezávisle Victor Allis  (en) (16. října 1988). První hráč si může vynutit vítězství. Silně vyřešen databází Johna Trompa (4. února 1995). Slabé řešení pro všechny velikosti talířů, kde součet šířky a výšky je maximálně patnáct (15) (a dokonce velikost 8x8 od konce roku 2015) (18. února 2006). Kvarto Vyřešil Luc Goossens (1998). Dva dokonalí hráči vždy remizují. Tic-tac-toe 3D  (in) (nebo Qubic ) Slabé řešení: Oren Patashnik (1980) a Victor Allis. První hráč vyhrává. Hra typu Renju bez otevíracích pravidel Tvrdí, že jej vyřeší János Wagner a István Virág (2001). Vítězství prvního hráče. Sim Slabě vyřešené: vítězství druhého hráče. Teeko Vyřešil Guy Steele (1998). V závislosti na variantě první hráč buď vyhraje, nebo získá remízu. Tři muži Morris  (en) Triviálně řešitelné. Každý hráč může hru přinutit k remíze. Tři mušketýři Silně vyřešen Johannesem Laireem v roce 2009. Je to vítězství modrých figurek (mužů kardinála Richelieua nebo nepřítele). Piškvorky Triviálně řešitelné. Každý hráč může hru přinutit k remíze. Bagh Chal Slabě vyřešen Yew Jin Limem (2007). Tato hra je remíza.

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

Šachy Úplné řešení šachové partie zůstává nedosažitelné a předpokládá se, že složitost hry může zabránit jejímu vyřešení. Tím, retrográdní počítačovou analýzou , finálové stoly (silné roztoky) byly nalezeny ve všech finále se třemi až sedmi kusů, a některé s osmi kusů, počítání dva krále mezi kusy. Některé varianty šachové hry na menší desce se sníženým počtem figurek ( Mini-šachy ) byly vyřešeny. Byly vyřešeny i některé další variace; například nízké rozlišení Maharajah a Sepoys je snadno zapamatovatelná série pohybů, která zajišťuje vítězství hráče Sepoy . Jít Deska 5 × 5 je u všech úvodních tahů slabě vyřešena. Lidé obvykle hrají na desce 19 × 19, což je řádově složitost přes 145krát větší než deska 7 × 7. Herní dámy Všechny pozice v koncovce se dvěma až sedmi figurami byly vyřešeny, stejně jako kombinace 4 × 4 a 5 × 3 s každou stranou, která má jednu královnu nebo méně, pozice s pěti figurkami a čtyřmi figurkami, pozice s pěti figurkami proti třem figurkám a královna, stejně jako pozice se čtyřmi pěšci a králem proti čtyřem pěšcům. Finále vyřešil v roce 2007 Američan Ed Gilbert. Počítačová analýza ukázala, že je velmi pravděpodobné, že skončí remízou, pokud oba hráči budou hrát perfektně. Mlýnek Je triviální ukázat, že druhý hráč nemůže vyhrát; viz ukázka strategickým letem. Téměř všechny případy byly slabě vyřešeny pro k ≤ 4. Některé výsledky jsou známé pro k = 5. Hry jsou nulové pro k ≥ 8. Reversi (Othello) Slabě vyřešen na desce 4 × 4 a 6 × 6 pro vítězství druhého hráče tím, že Červenec 1993Joel Feinstein. Na desce 8 × 8 (standard) to není matematicky vyřešeno, i když počítačová analýza ukazuje pravděpodobnou nulu. Nelze odhadovat, že šance prvního hráče (černého) na výhru rostou na deskách 10 × 10 a výše.

Podívejte se také

Reference

(fr) Tento článek je částečně nebo zcela převzat z anglického článku Wikipedie s názvem „  Vyřešená hra  “ ( viz seznam autorů ) .
  1. V. Allis, Hledání řešení ve hrách a umělé inteligenci.
  2. H. Jaap van den Herik, Jos WHM Uiterwijk, Jack van Rijswijck, Hry vyřešeny: Nyní a v budoucnosti , Umělá inteligence 134 (2002) 277–311.
  3. „  Heads-up limit hold'em poker je vyřešen  “, Science , sv.  347,ledna 2015, str.  145–9 ( PMID  25574016 , DOI  10.1126 / science.1259433 )
  4. Philip Ball, „  Herní teoretici Crack Poker,  “ na Scientific American ,8. ledna 2015( DOI  10.1038 / nature.2015.16683 , přístup 13. ledna 2015 )
  5. (en-US) Robert Lee Hotz, „  Počítač dobývá Texas Hold 'Em, říkají vědci  “ , Wall Street Journal ,8. ledna 2015( číst online )
  6. Jonathan Schaeffer , „  Dáma je vyřešena,  “ Věda,19. července 2007(zpřístupněno 20. července 2007 )
  7. „  Project - Chinook - mistr světa v kontrole dámských strojů  “ (zpřístupněno 19. července 2007 )
  8. Justin Mullins , „  Dáma„ vyřešena “po letech křehkého počtu,  “ zpravodajská služba NewScientist.com,19. července 2007(zpřístupněno 20. července 2007 )
  9. (ja) Údaje o rozlišení Dobutsu shogi.
  10. P. Henderson, B. Arneson a R. Hayward [webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf, řešení 8 × 8 hex], Proc.
  11. Hexapawn
  12. „  Jak vždy vyhrát hůlky  “ , wikiHow (přístup 28. dubna 2013 )
  13. Řešení Kalah Geoffrey Irving, Jeroen Donkers a Jos Uiterwijk.
  14. Řešení (6,6) -Kalaha od Anderse Carstensena.
  15. Pro všechny odpovědi na 1. e3 kromě 1 ... c5 a 1 ... b6 viz: Mark Watkins , „  Vyřešené otvory v Losing Chess  “ ,10. září 2014(zpřístupněno 15. ledna 2015 )
  16. Morris devíti mužů je remíza od Ralpha Gassera
  17. Pangki je silně vyřešen jako Draw od Jasona Doucette
  18. Geoffrey Irving: „Pentago vyhrává jako první hráč“ http://perfect-pentago.net/details.html
  19. Hilarie K.Orman: Pentominoes: Výhra prvního hráče v hrách bez šance , Publikace MSRI - svazek 29, 1996, strany 339-344.
  20. John's Connect Four Playground
  21. http://archive.ics.uci.edu/ml/datasets/Connect-4
  22. Teeko , autor E. Weisstein
  23. Tři mušketýři , J. Lemaire
  24. Yew Jin Lim. Při prořezávání vpřed při hledání stromu hry . Ph.D. práce, National University of Singapore , 2007.
  25. 5 × 5 Go řeší Erik van der Werf
  26. Počítání právních pozic v Go , Tromp a Farnebäck, zpřístupněno 24. 8. 2007.
  27. Některé z devítidílné tabulky koncovek od Eda Gilberta
  28. 6 × 6 Othello slabě vyřešil „archivovanou kopii“ (verze internetového archivu 1. listopadu 2009 )

Další čtení

externí odkazy