Algoritmus bohů - Gods algorithm - Wikipedia

Boží algoritmus je pojem pocházející z diskusí o způsobech řešení Rubikova kostka hádanka,[1] ale které lze použít i na jiné kombinační hádanky a matematické hry.[2] Odkazuje na jakýkoli algoritmus, který produkuje řešení s co nejmenším počtem tahů, myšlenkou je, že pouze vševědoucí bytost by poznala optimální krok z jakékoli dané konfigurace.

Rozsah

Definice

Pojem se vztahuje na hádanky který může předpokládat a konečný počet „konfigurací“, s relativně malým, dobře definovaným arzenálem „tahů“, které mohou být použitelné pro konfigurace a poté vedou k nové konfiguraci. Řešení hádanky znamená dosáhnout určené „konečné konfigurace“, jednotné konfigurace nebo některé ze sady konfigurací. K vyřešení hádanky se použije posloupnost tahů, počínaje libovolnou počáteční konfigurací.

Řešení

Algoritmus lze považovat za řešení takové hádanky, pokud bere jako vstup libovolnou počáteční konfiguraci a produkuje jako výstup posloupnost tahů vedoucích ke konečné konfiguraci (-li hádanka je z této počáteční konfigurace řešitelná, jinak signalizuje nemožnost řešení). Řešení je optimální, pokud je sekvence tahů co nejkratší. Tento počet je znám jako Boží číslo,[3] nebo, více formálně, minimax hodnota.[4] Boží algoritmus je tedy pro danou hádanku algoritmus, který hádanku řeší a vytváří pouze optimální řešení.

Někteří autoři, jako je David Joyner, se domnívají, že aby byl algoritmus správně označován jako „Boží algoritmus“, měl by být také praktický, což znamená, že algoritmus nevyžaduje mimořádné množství paměti nebo času. Například pomocí obra vyhledávací tabulka indexované podle počátečních konfigurací by umožnilo najít řešení velmi rychle, ale vyžadovalo by to mimořádné množství paměti.[5]

Místo požadavku na úplné řešení můžete ekvivalentně požádat o jediný tah z počáteční, ale nikoli konečné konfigurace, kde je tah první z některých optimálních řešení. Algoritmus pro verzi problému s jedním tahem lze změnit na algoritmus pro původní problém opakovaným vyvoláním při použití každého pohybu hlášeného k současné konfiguraci, dokud není dosaženo finálního. Naopak jakýkoli algoritmus pro původní problém lze změnit na algoritmus pro verzi s jedním tahem zkrácením jeho výstupu na jeho první tah.

Příklady

Známé hádanky odpovídající tomuto popisu jsou mechanické hádanky jako Rubikova kostka, Věže Hanoje a 15 puzzle. Hra pro jednoho člověka peg solitaire je také zahrnuto, stejně jako mnoho logické hádanky, tak jako problém misionářů a kanibalů. Společné je, že mohou být matematicky modelováno jako řízený graf, ve kterých jsou konfiguracemi vrcholy a přesouvá oblouky.

Mechanické hádanky

n-hádanky

The Patnáct puzzle lze vyřešit na 80 tahů po jedné dlaždici[6] nebo 43 tahů s více dlaždicemi[7] v nejhorším případě. Pro jeho zevšeobecnění n- hádanka, problém najít optimální řešení je NP-tvrdé.[8] Zda tedy existuje praktický Boží algoritmus pro tento problém, zůstává neznámý, ale zdá se nepravděpodobný.

Věže Hanoje

Pro Věže Hanoje hádanka, Boží algoritmus je známý pro jakýkoli daný počet disků. Počet tahů je v počtu disků exponenciální ().[9]

Rubikova kostka

Hlavní článek: Optimální řešení pro Rubikovu kostku

Algoritmus pro stanovení minimálního počtu tahů k vyřešení Rubikovy kostky publikoval v roce 1997 Richard Korf.[10] I když od roku 1995 bylo známo, že v nejhorším případě je 20 dolní meze počtu tahů řešení, v roce 2010 bylo prostřednictvím rozsáhlých počítačových výpočtů prokázáno, že žádná konfigurace nevyžaduje více než 20 tahů.[11] 20 je tedy a ostrý horní hranice na délce optimálních řešení. Matematik David Singmaster v roce 1980 „ukvapeně předpokládal“ toto číslo na 20.[4]

Nevyřešené hry

U některých dobře známých her s velmi omezenou sadou jednoduchých přesně definovaných pravidel a tahů nebyl nikdy stanoven jejich Boží algoritmus pro vítěznou strategii. Příkladem jsou deskové hry šachy a Jít.[12] Obě tyto hry mají s každým tahem rychle rostoucí počet pozic. Celkový počet všech možných pozic, přibližně 10154 pro šachy[13] a 10180 (na desce 19 × 19) pro Go,[14] je příliš velký na to, aby umožňoval řešení hrubou silou se současnou výpočetní technologií (porovnejte nyní vyřešené, s velkými obtížemi, Rubikova kostka na pouhých asi 4,3 × 1019 pozic[15]). Následkem toho není možné u těchto her stanovit hrubou sílu Božího algoritmu. I když byly postaveny šachové počítače schopné porazit i ty nejlepší lidské hráče, nevypočítávají hru až do konce. Tmavě modrá například prohledával pouze 11 tahů vpřed (počítá tah každého hráče jako dva tahy), čímž se zmenšil prostor hledání pouze na 1017.[16] Poté vyhodnotila každou pozici jako výhodu podle pravidel odvozených z lidské hry a zkušeností.

Ani tato strategie není u Go možná. Kromě toho, že má k vyhodnocení mnohem více pozic, dosud nikdo úspěšně nevytvořil sadu jednoduchých pravidel pro hodnocení síly Go pozice, jak tomu bylo u šachů.[17] Vyhodnocovací algoritmy jsou náchylné k základním chybám[18] takže ani při omezeném pohledu dopředu s cílem omezeným na nalezení nejsilnější mezilehlé polohy nebyl pro Go možný Boží algoritmus.

Na druhou stranu, pracovní verze (dáma), s povrchními podobnostmi se šachy, již dlouho existuje podezření, že ji „hrají“ její odborníci z praxe.[19] V roce 2007 Schaeffer et al. prokázal to tak, že vypočítal databázi všech pozic s deseti nebo méně kusy. Schaeffer má tedy Boží algoritmus pro všechny koncové hry draftu a pomocí toho dokázal, že všechny dokonale hrané hry draftů skončí remízou.[20] Koncepty však pouze s 5 × 1020 pozic[21] a ještě méně, 3,9 × 1013, v Schaefferově databázi,[22] je mnohem snazší problém rozluštit a má stejné pořadí jako Rubikova kostka.

Velikost množiny pozic hádanky ne zcela určuje, zda je možný Boží algoritmus. Již vyřešená hádanka Tower of Hanoi může mít libovolný počet dílků a počet pozic se exponenciálně zvyšuje . Algoritmus řešení je nicméně použitelný na jakýkoli problém s velikostí a protože doba běhu algoritmu je problém je NP-těžký.[23]

Viz také

Poznámky

  1. ^ Paul Anthony Jones, Jedburgh Justice and Kentish Fire: The Origins of English in Ten Phrases and Expressions, Hachette UK, 2014 ISBN  1472116224.
  2. ^ Viz např. Rubikův kubický kompendium Ernö Rubik, Tamás Varga, Gerzson Kéri, György Marx a Tamás Vekerdy ​​(1987, Oxford University Press, ISBN  0-19-853202-4), s. 207: „... Pyraminx je mnohem jednodušší než Magic Cube ... Nicholas Hammond ukázal, že Boží Algoritmus je nanejvýš 21 tahů (včetně čtyř triviálních vrcholných tahů). [V poslední době Boží algoritmus našli tři lidé. Maximální počet tahů je 15 (včetně čtyř vrcholných tahů).] "
  3. ^ Jonathan Fildes (11. srpna 2010). „Hledání Rubikovy kostky pro rychlé řešení končí“. BBC novinky.
  4. ^ A b Singmaster, str. 311, 1980
  5. ^ Joyner, strana 149
  6. ^ A. Brüngger, A. Marzetta, K. Fukuda a J. Nievergelt, Paralelní vyhledávací stolice ZRAM a její aplikace, Annals of Operations Research 90 (1999), str. 45–63.
  7. ^ „Fifteen Puzzle lze vyřešit ve 43 tahy". Doména fóra Cube
  8. ^ Daniel Ratner, Manfred K.Warmuth (1986). „Nalezení nejkratšího řešení pro rozšíření N-N 15-puzzle je neřešitelné“. v Sborník AAAI-86. Národní konference o umělé inteligenci, 1986. s. 168–172.
  9. ^ Carlos Rueda, „Optimální řešení hádanek Towers of Hanoj“.
  10. ^ Richard E. Korf, “Hledání optimálních řešení Rubikovy kostky pomocí vzorových databází ", Proc. Natl. Konf. o umělé inteligenci (AAAI-97), Providence, Rhode Island, červenec 1997, str. 700–705.
  11. ^ „Boží číslo je 20“. Cube20.org
  12. ^ Rothenberg, str. 11
  13. ^ Baum, str. 187
  14. ^ Baum, str. 199
  15. ^ Singmaster, 1981
  16. ^ Baum, str. 188
  17. ^ Baum, str. 197
    • Mohammadian, str. 11
  18. ^ Baum, s. 197
  19. ^ Fraser & Hannah, str. 197
  20. ^ Moore & Mertens, kapitola 1.3, „Hraní šachů s Bohem“
  21. ^ Schaeffer et al., str. 1518
  22. ^ Moore & Mertens, „Poznámky“ ke kapitole 1
  23. ^ Rueda

Reference

  • Baum, Eric B., Co je myšlenka?, MIT Press, 2004 ISBN  0262025485.
  • Davis, Darryl N .; Chalabi, T .; Berbank-Green, B., „Umělý život, agenti a Go“, Mohammadian, Masoud, Nové hranice ve výpočetní inteligenci a jejích aplikacích, str. 125–139, IOS Press, 2000 ISBN  9051994761.
  • Fraser, Rober (ed); Hannah, W. (ed), Týdenní časopis Draft Hráči, sv. 2, Glasgow: J. H. Berry, 1885.
  • David Joyner (2002). Dobrodružství v teorii skupin. Johns Hopkins University Press. ISBN  0-8018-6947-1.
  • Moore, Cristopher; Mertens, Stephan, Povaha výpočtu, Oxford University Press, 2011 ISBN  0191620807.
  • Rothenberg, Gadi, Katalýza, Boží algoritmus a Zelený démon, Amsterdam University Press, 2009 ISBN  9056295896.
  • Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, Steve Sutphen, „Dáma je vyřešena“, Věda, sv. 317, č. 58444, s. 1518–1522, 14. září 2007.
  • Zpěvák, David, Poznámky k Rubikově magické kostce, Penguin, 1981 ISBN  0-907395-00-7.
  • Singmaster, David, „Vzdělávací hodnota maďarské„ magické kostky ““, Sborník ze čtvrtého mezinárodního kongresu o matematické výchově, konané v Berkeley v Kalifornii, 10. – 16. srpna 1980, str. 307–312, Birkhauser Boston Inc, 1983 ISBN  978-0-8176-3082-9.