Oslík:

Použitý software:

Jako interpretr prologu jsem použil SWI-Prolog, který je dodáván s vcelku přijatelnými licenčními podmínkami (a zdrojové kódy jsou součástí). Přikládám krátký patch, aby SWI-Prolog nepočítal percentuální podíly funkcí při profilování a vypnutí automatického garbage collectoru.

Profiling se mi hroutil díky nezablokování všech signálů při volání sigblock(), ale může to být jen problém mé instalace
Garbage collector se spouštěl na můj vkus příliš často, jeho automatické spouštění jsem tedy vypnul a volám jej explicitně z Prologu

Ačkoliv by oba programy (obě Prolog a jedna C verze) měly být spustitelné na jakékoliv platformě, uvádím testované/vývojové prostředí:

GNU/Linux, částečně RedHat 5.0 systém, kernel Linus-2.1.132, glibc-2.0.7-980507, gcc version pgcc-2.91.57 19980901 (egcs-1.1 release), GNU Make version 3.76.1, GNU textutils 1.22.
SWI-Prolog verze 3.1.2.

Díval jsem se také na BinProlog, ale zdrojové kódy nebyly vůbec k dispozici, a tudíž nepřipadl v úvahu.

Řešení úlohy:

Zadáním bylo převést hrací plochu ze vstupního tvaru:

  /-------\
  | {}{}# |
  | AB^#+ |
  | CDv#+ |
  | {}{}# |
  \-------/

postupným přesouváním kostek do tvaru:

  /-------\
  | ????? |
  | ???AB |
  | ???CD |
  | ????? |
  \-------/

kde znaky "?" samozřejmě představují políčka, na kterých nezáleží. Pro popis jednotlivých znaku bude lepší následující legenda:

AB CD - 2x2 {} - 2x1 ^ v - 1x2 # - 1x1 -volno-
+ - 1x1

Postupné stavy hrací plochy při jednotlivých krocích minimálního (nejkratšího) řešení jsou v souboru "minsol.txt". Rozbor řešení úlohy je sumarizován zde:

Velikost stavového prostoru	25955
Počet různých řešení	482 (+sym.)
Počet tahů nejkratšího řešení	116
Počet různých nejkratších řešení	1 (+sym.)
Počet tahů nejdelšího řešení	158
Počet různých nejdelších řešení	7 (+sym.)
Maximální počet tahů bez opakování	167

Všechny tyto výsledky lze získat ze všech verzí (Prolog assert / Prolog hash / C), z rychlostních důvodů ovšem doporučuji použít C verzi. Pro některé výsledky je třeba zapnout ladící výpisy (v obou verzích se zapínají různě a nezdokumentovaně).

Poznámka "(+sym.)" znamená, že takových řešení je ve skutečnosti dvojnásobný počet než je uvedeno, ale tato zbylá řešení jsou symetrická dle X-ové osy. To vyplývá ze symetričnosti zadání dle osy X a tomu, že všechny povolené tahy žádným způsobem neupřednostňují či neomezují směr pohybu.

Náročnost řešení:

Konfigurace: AMD-K6-2 350MHz, 256MB SDRAM, 100MHz FSB
kategorie \ verze	Prolog assert	Prolog hash	C
doba běhu bez výstupu	1m:55s=115s	4m:27s=267s	0m:0.22s=~1s
doba běhu s výstupem	4m:29s=269s	6m:19s=379s	0m:1.90s=~2s
paměťová náročnost	cca 50MB	cca 150MB (!)	cca 1MB

V Prologu assert se využívá funkcí assert a flag. Toto řešení je rychlejší i přehlednější než následující, ale neodpovídá duchu Prologovského programování.

V Prologu hash používám hashování s velikostí tabulky 150 položek (deklarace "geths(150).", čímž se snažím převést stavový prostor do čtvercového tvaru, aby Prolog lineárně procházel hash index i hash link-list celkově minimální čas.

Varování: Při standardním spuštění (přes SWI-Prolog) Oslíka budou obě Prologovské verze dumpovat velké množství ladících informací. Pro "production" použití slouží bash skript "do", který tyto ladící informace ve zdrojovém kódu zruší a spustí automaticky prolog. Při spuštění bez parametrů vypíše tento skript help. Nadefinování prázdného termu jako funkce pro ladící výpis mělo bohužel drtivý dopad na rychlost interpretace.

Obě Prologovské verze víceméně neobsahují žádné komentáře, doporučuji si případně k nim otevřít verzi v C, kde je vše zřejmé.

Průběh vývoje:

Velikost výpočtu

Původně jsem byl varován, že výpočet bude trvat příliš dlouho a pravděpodobně nedoběhne. Čekal jsem tedy počet stavů prostoru minimálně v řádu milonů, v horším případě miliard. Nynější "oslik.c" se původně jmenoval "stategen.c" a měl opravdu sloužit pouze k předgenerování všech možných stavů a jejich očíslování (mělo by se vejít do 32-bitů, jinak by to stejně asi nemělo smysl prohlédávat bez distributed.net for my pleasure). Byl jsem šokován, když program ihned doběhl (tj. i mě) s celkovým počtem 25955 stavů. Proto je také kód pro sledování průběhu výpočtu (makro "STSTEP") nyní jaksi nadbytečný a působí spíše humorným dojmem. Celý kód jsem se také snažil hned napoprvé napsat co možná nejrychlejší. Pro množinu stavů mám konstantní hashovací pole, seznam doposud nezpracovaných stavů i zpětné reference pro vypisování výsledku (tj. z kterého stavu jsme se do aktuálního dostali).

Struktura stavu

Stav se ukládá jako 20-ti (5x4) znakové pole, neukládám tedy polohu jednotlivých velkých kostek, ale naopak mám pro každé políčko hrací plochu uveden druh/část kostky na něm ležící ("oslík" je tedy ze 4 částí a tyto části můsí v každém korektním stavu ležet ve správném pořadí u sebe). Výchozí stav je tedy vyjádřen řetězcem "{}{}#AB^#+CDv#+{}{}#".

Struktura množiny stavů

Ústředním problémem Oslíka je udržování množiny stavů, které jsme již prohledali či jsme je již objevili, ale ještě nám zbývá je zpracovat. V "oslik-hash.pl" verzi (první v Prologu) to byl úplně nejdříve lineární seznam, což ovšem bylo časově neúnosné. Profiler mi potvrdil důvodné podezření na kvadratickou časovou složitost programu díky tomuto seznamu, musel jsem ho tedy vyměnit. Pro jednoduchost implementace jsem zvolil hash tabulku jako v C verzi, kterou jsem ovšem byl nucen implementovat jako lineární seznam jenotlivých políček a obsahem každého prvku seznamu byl vnořený seznam všech stavů, které mají stejnou hash hodnotu, a patří tedy k sobě. Bohužel v takovémto uspořádání neplatí obecné pravidlo hashů, že čím větší, tím rychlejší (samozřejmě až na úplně extrémní případy díky inicializaci a efektu memory cache). Při příliš velké hash tabulce by bylo bohužel příliš časově náročné dotraverzovat k případnému prvku na konci hash tabulky (a tedy i na konci hash seznamu). Vzhledem k tomu, že jsem již z C verze znal velikost úlohy, nastavil jsem velikost hash tabulky tak, aby byla přibližně stejná jako průměrný počet prvků v jednom hash políčku. Ve skutečnosti tedy vytvoří taková tabulka čtverec a velikost hash tabulky (tj. jeho jedna strana) by měla být odmocninou z celkového počtu prvků. Zvolil jsem 150 prvků (ideálně pro 22500 stavů).

Konverze stavu

Vyjádření stavu zůstalo jako 20-ti znakový řetězec (jako v C verzi), je-li třeba, dočasně jej konvertuji do seznamu a nazpět (predikát "string_to_list"). Řetězec by měl být paměťově efektivnější pro ukládání do množiny stavů, jemné (v assert verzi dle profileru bohužel hlavní) zpomalení díky dvojitým konverzím je pravděpodobně levnější než zvýšené paměťové nároky (i když jsem to reálně nezkoušel).

Přepsání do Prologu

Co se týče celkové implementace, přiznám se, že jsem víceméně přepsal tu C verzi s tím, že jsem některé cykly přepsal na rekurzi. Hlavní kontrolní dvourozměrná smyčka pro kontrolu korektnosti pohybu a smyčka pro přesun kostek zůstaly implementovány přes "forall", neboť se využívá číselných hodnot řídících proměnných pro adresaci polí stavu. Jména proměnných v predikátu "chkpos" zůstala zachována z C verze, lze ji tedy použít jako pomocný text, neboť je IMHO mnohem průhlednější a ilustrativnější.

Verze s assert/flag

Přepsání předchozí prologovské verze za využití "assert" a "flag" pro uchování množiny stavů místo předchozí hash table emulované dvojitým seznamem je v "oslik-assert.pl". Scope "assert"-u i "flag"-u je globální a odpadlo tedy velké množství nechutného tahání hash tabulky s sebou parametrem všech funkcí až dovnitř (jednou jako vstupní, podruhé jako výstupní) jako kočka koťata. Výsledkem bylo kromě velkého zpřehlednění a zjednodušení kódu také výrazné zlepšení rychlosti i paměťové náročnosti (více viz náročnost řešení). Určitě bych to byl býval psal tímto způsobem rovnou, bohužel jsem se o "assert"-u a "flag"-u dozvěděl až po napsání předchozí verze.

Atomizace

V Prologu jsem se původně potýkal s problémem nefungující unifikace nezatomizovaných řetězců, ale poté, co jsem objevil predikát "string_to_atom" již SWI Prolog unifikoval jak měl.

Dodané soubory:

oslik.zip	celý package (včetně Makefile-u apod.)
oslik-assert.pl	oslík v SWI-Prologu, assert verze
oslik-hash.pl	oslík v SWI-Prologu, hash verze
do	bash skript pro spuštění předchozích dvou programů
oslik.c	oslík v ANSI C (+BSD extenze)
minsol.txt	minimální řešení (CR/LF)
pl-3.1.2.diff	patch pro SWI-Prolog 3.1.2 (viz výše)

Autor:

Datum:	30. 12. 1998
Autor:	Jan Kratochvíl
Kontakt:	e-mail web@jankratochvil.net
Licence:	Public domain

Tento software je poskytnut bez jakýchkoliv záruk a autor nenese žádnou zodpovědnost za škody způsobené jeho používáním. Autor se také vzdává jakýchkoliv práv, ale i závazků, dle smyslu public domain licence.