Eternity II (aktualizováno)

Eternity II je poněkud netradiční puzzle čtvercového tvaru skládající se z 256 dílků, za jehož složeni čeká prvního úspěšného řešitele odměna ve výši 2 milionů dolarů, tedy něco kolem 40 milionů Korun. Jedná se o dokonalý marketingový tah s důkladně promyšlenou strategií, který již podruhé upoutal pozornost milionů lidí po celém světě a vydělal tak nemalý obnos peněz. Text, který právě čtete, se ovšem nezabývá přímo pravidly hry, úvahami, zda je možné puzzle složit v reálném čase ani jak velkou roli při tom hraje náhoda, nýbrž teoreticky se zaměřuje na jeden z algoritmů vhodných ke složení hry Eternity II pomocí osobního počítače, clusteru či gridu.

Tento článek jsem začal psát na podzim minulého roku a nikdy jej nedokončil, ani nedokončím. Přesto jsem se rozhodl zveřejnit alespoň poznámky, které jsem si k tomuto koníčku sepsal a pro lepší představu připojil i pár názorných obrázků a animaci. Bohužel ne všechny poznámky se mi po takové době podařilo rozluštit, tudíž u některých úvah chybějí argumenty. Ty případným zájemcům doplním v komentářích.

Pokud o hře Eternity II slyšíte poprvé, přečtěte si nejprve oficiální pravidla hry, případně jiné články, na něž odkazuji na konci toho mého, neboť pro pochopení samotného algoritmu je znalost a pochopení hry podmínkou. Snad nejvíce ocení tento článek lidé, kteří se již dříve pokusili vytvořit si vlastní solver a poznali tak, že to není nic jednoduchého. Přesto věřím, že se uvedené poznámky stanou alespoň malým přínosem pro zapálené řešitele zmiňované hry a pro ostatní přinejmenším zábavným procvičením logického myšlení.

Obecné poznámky

Rozměry hracího pole: 16 x 16 dílků (A1 - P16)
Výchozí dílek: No. 139 na pozici I8
Celkový počet dílků: 256
Počet vzorů na dílku: 4
Celkový počet vzorů: 23

Počet nápověd (stop): 4
První stopa: No. * na pozici N3
Druhá stopa: No. * na pozici C14
Třetí stopa: No. * na pozici N14
Čtvrtá stopa: No. * na pozici C3

*) čísla dílků nápověd bohužel zveřejnit nemohu

• Každý dílek je originální
• Žádný z dílků neobsahuje na všech 4 pozicích stejný vzor
• Žádný z dílků neobsahuje 2 páry stejných vzorů
• Úspěšně složené puzzle nepředstavuje žádný pravidelný vzor
• Stejně jako u stop existuje pravděpodobně více správných řešení
• Nesouměrnost vzorů na dílcích je vadou při tisku, nikoliv vodítkem
• Existuje možnost účastnit se distribuovaného řešení pomoci gridu (projekt BOINC)

Vizuální znázornění hrací plochy včetně výchozího dílku 139 a všech čtyř stop (nápověd):

Frekvenční analýza

Frekvence výskytu vzorů:
50x - 12 vzorů
48x - 5 vzorů
24x - 5 vzorů (nacházejí se pouze ve vnějším prstenci)
64x - 1 vzor (šedý obvod)

Okrajové dílky [60]:
Rohové: 4
Protější stejné: 14
Čtyřvzorové: 42

Středové dílky [196]:
Rohové: 41
Trojkové: 3
Protější stejné: 20 (stopa 2)
Čtyřvzorové: 132 (stopa 1,3,4)

Legenda:
Rohové: 2 stejné vzory vedle sebe
Trojkové: 3 stejné vzory vedle sebe
Protější stejné: protější vzory jsou shodné, zbývající dva rozdílné
Čtyřvzorové: každá ze čtyř pozic na dílku obsahuje jiný vzor

Strategie postupu

Použitý algoritmus
Backtracking, viz Wikipedia.

Použitý programovací jazyk
Cokoliv kromě interpretovaných jazyků (kvůli rychlosti).

Start
V levém dolním rohu (nejbližší roh k výchozímu dílku 139).

Výchozí dílek 139, stopy, pevný okraj a tvar
Všechny tyto body snižují počet správných řešení, zároveň však i počet kombinací a dohromady tvoří kontrolní stanoviště pro použitý algoritmus.

Pořadí dílků v seznamu
Rozložení jednotlivých dílků v seznamu a jejich následné umísťování na hrací plochu rovněž ovlivňuje rychlost algoritmu. Návrh rozmístění dílků v seznamu:

• Krajní dílky (zde se automaticky nachází i všech 5 vzorů s frekvencí 24x)
• Krajní rohové dílky
• Ostatní nijak neuspořádané dílky (uspořádání by skládání naopak zkomplikovalo)

Směr a způsob skládání
Spirála nebo řady? Od středu ven či naopak? Ani jedno. V případě Backtrack algoritmu jsou pro nás totiž nesmírně důležitá tzv. kontrolní stanoviště, které nás upozorní na to, zda postupujeme správně či nikoliv a máme se vrátit. Důvěryhodnost kontrolních stanovišť je následující (od nejvyšší po nejnižší):

• trojka (pokládaný dílek je ze tří stran obklopen již položenými dílky)
• okraj (dílek se dotýká okraje hrací plochy - šedý vzor)
• nápověda (dílek se dotýká stranou jedné z nápověd nebo dílku 139)
• příhraniční (dílek je položen ve druhém vnějším prstenci hrací plochy)
• blízko nápovědám (blízkost nápověd teoreticky zvyšuje koncentraci správných dílků)
• blízko okraje (blízkost okraje teoreticky zvyšuje koncentraci správných dílků)
• ostatní

Vizuální znázornění koncentrace správně položených dílku se zahrnutím startovací pozice a výše uvedených pravidel by tedy vypadalo následovně, včetně i beze stop (v případě aplikace stop se jedná pouze o ilustrační zobrazení, neboť je konkrétní koncentrace silně závislá na zvoleném postupu skládání):





Použití stop hledání řešení zpomaluje, a to právě díky dodatečným kontrolním stanovištím, pokud tedy není naším cílem kompletní složení celého puzzle, nýbrž dosažení co nejvyššího počtu bodů (položených kamenů), pak bychom se měli použití stop vyvarovat.

Pravidelná pozice všech 4 stop na hracím poli nám skládání usnadňuje, neboť se nachází na jediném prstenci, jehož důvěryhodnost (jakožto kontrolního stanoviště) se tak zvyšuje. Tato situace nahrává do karet strategii spirály od vnějšího okraje směrem ke středu, což je pravděpodobně nejvhodnější postup pro ty, kteří se snaží poskládat Eternity II ručně a využívají při tom všech dostupných nápověd. Aplikováním výše uvedených pravidel však můžeme postup výrazně zdokonalit a využít efektivněji důvěryhodnějších kontrolních stanovišť v okolí dříve, než by tomu bylo právě v případě spirály. Při průchodu špatnou větví jsme tak na chybu upozorněni včas a můžeme začít ihned prozkoumávat jednu z dalších variant.

Nápověda je pro nás zajisté dostatečně důvěryhodným kontrolním bodem, snažíme-li se najít tvůrcem "vnucované" řešení. Pokud však všechny nabízené stopy aplikujeme, sníží se nám výrazným způsobem množství správných řešení na minimum, teoreticky až na jedno jediné. I v tomto případě si ale můžeme pomoci, a to odhalením dalších zaručeně správně položených kamenů. K tomu je zapotřebí spustit více instancí solveru, pokaždé s jinými kameny v každém rohu hrací desky. Jisti si prozatím můžeme být pouze výchozím hracím dílkem číslo 139 a čtyřmi stopami, tedy celkem pěti pozicemi. Chceme-li si být jisti pozicí šestého kamene (respektive druhého v případě hraní bez nápověd), musíme spustit 4 instance naší aplikace, pro sedm jich musí být 12 a pro devět zaručeně správně položených kamenů jsme nuceni spustit již 24 instancí. To je naštěstí stále reálné a my tak rozšíříme počet našich stop na dvojnásobek!

Dílky je nutné pokládat přesně dle výše uvedené legendy, aby tak algoritmus při svém skládání prošel co možná nejvíce důvěryhodnými kontrolními stanovišti a včas odhalil špatnou větev.

Vizuální znázornění postupu bez přítomnosti stop vyvozené z předchozích informací si můžete prohlédnout na následující animaci:

Další relevantní informace

• Oficiální stránky hry Eternity II [cz]
• Weblog Martina Žaloudka
• Hlavolam za 2 miliony USD
• Fórum na téma Eternity II
• Jiné fórum na stejné téma
• Wikipedia: Backtrack algoritmus
• Distribuované řešení pomocí BOINC [en]