012345

}w !"#$%&'()+,-./012345
Masarykova univerzita Fakulta informatiky

Generátor a simulátor logické úlohy Replacement puzzle Bakalářská práce

Tomáš Křepský

Brno, podzim 2009

Prohlášení Prohlašuji, že tato bakalářská práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.

Vedoucí práce: Mgr. Petr Jarušek ii

Poděkování Rád bych poděkoval svému vedoucímu bakalářské práce, Mgr. Petru Jaruškovi, za nabídnutí zajmavého tématu, odbornou pomoc při výběru nástrojů, pravidelné konzultace ohledně implementace a přípravu kvalitního webového prostředí pro prezentaci hry. Dále bych chtěl poděkovat všem, kteří se zúčastnili výzkumu a přispěli tak ke sběru dat.

iii

Shrnutí Logické úlohy každým dnem nabývají na popularitě. Tato práce se zabývá tvorbou generátoru a simulátoru jedné takové úlohy, konkrétně hry Replacement puzzle. Pomocí vytvořených nástrojů byl proveden experiment, kdy bylo sledováno, na čem závisí složitost různých zadání úlohy. Výsledky experimentu jsou v této práci prezentovány.

iv

Klíčová slova Problem solving, puzzle, Java, Java Applet, MySQL, PHP.

v

Obsah 1 2

3

4

5

Úvod . . . . . . . . . . . . . . . . . . . . . . Úvod do problematiky . . . . . . . . . . . . 2.1 Co je to problém? . . . . . . . . . . . . . 2.2 Představení hry Replacement puzzle . . . Analýza problému . . . . . . . . . . . . . . 3.1 Požadavky na generátor . . . . . . . . . . 3.2 Požadavky na simulátor . . . . . . . . . . 3.3 Sběr dat . . . . . . . . . . . . . . . . . . 3.4 Požadavky na zpracování dat . . . . . . . Použité nástroje . . . . . . . . . . . . . . . . 4.1 Java . . . . . . . . . . . . . . . . . . . . 4.1.1 Výhody jazyka Java . . . . . . . 4.1.2 Nevýhody jazyka Java . . . . . 4.2 Java applet . . . . . . . . . . . . . . . . . 4.2.1 Výhody Java appletu . . . . . . 4.2.2 Nevýhody Java appletu . . . . 4.3 PHP . . . . . . . . . . . . . . . . . . . . 4.4 MySQL . . . . . . . . . . . . . . . . . . 4.5 Pajek . . . . . . . . . . . . . . . . . . . . 4.6 R . . . . . . . . . . . . . . . . . . . . . . 4.7 NetBeans IDE . . . . . . . . . . . . . . . Implementace . . . . . . . . . . . . . . . . . 5.1 Konvence pro popisování kódu v této práci 5.2 Implementace generátoru . . . . . . . . . 5.2.1 Popis funkčnosti generátoru . . Třída GeneratorGUI . . . . . . Třída Node . . . . . . . . . . . Třída Generator . . . . . . . . 5.3 Implementace appletu . . . . . . . . . . . 5.4 Vzhled a ovládání appletu . . . . . . . . . 5.5 Spouštění appletu . . . . . . . . . . . . . 5.6 Ukládání dat z appletu do databáze . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4 4 4 6 6 6 7 7 8 8 8 9 9 10 10 10 11 11 12 12 13 13 13 14 14 14 14 15 16 16 17 1

5.7

Popis funkčnosti a zdrojového kódu appletu . 5.7.1 Důležité metody třídy Kolecka . . 5.8 Implementace DataMineru . . . . . . . . . . 5.8.1 Třída RepairLog . . . . . . . . . . . 5.8.2 Třída RepairRelevant . . . . . . . . Formáty dat v souborech . . . . . 5.8.3 Třída PlayerTimes . . . . . . . . . 5.8.4 Třída GraphDraw . . . . . . . . . . 5.9 Ukládání dat do databáze . . . . . . . . . . . 5.9.1 Tabulka kolecka_games . . . . . . Struktura tabulky . . . . . . . . . 5.9.2 Tabulka kolecka_game_log . . . . Struktura tabulky . . . . . . . . . 5.9.3 Tabulka kolecka_games_relevant . Struktura tabulky . . . . . . . . . 5.9.4 Tabulka users . . . . . . . . . . . . 5.10 Webové prostředí . . . . . . . . . . . . . . . 5.10.1 Výběr úrovní . . . . . . . . . . . . 5.10.2 Herní prostředí . . . . . . . . . . . 5.10.3 Zobrazení statistik . . . . . . . . . 6 Výsledky výzkumu . . . . . . . . . . . . . . . . Popis tabulky s výsledky . . . . . 6.1 Časy řešení . . . . . . . . . . . . . . . . . . 6.2 Vliv počtu uzlů na složitost . . . . . . . . . . 6.3 Vliv počtu hran na složitost . . . . . . . . . . 6.4 Vliv poměru hran a uzlů na složitost . . . . . 6.5 Vliv minimálního počtu kroků k vyřešení hry 6.6 Vliv jiných faktorů na složitost . . . . . . . . 6.7 Srovnání stavových prostorů vybraných her . 7 Závěr . . . . . . . . . . . . . . . . . . . . . . . . A Obsah přiloženého DVD . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17 17 19 19 19 19 20 20 21 21 21 21 22 22 22 23 23 24 24 24 25 25 26 26 27 27 29 30 33 36 39

2

Kapitola 1

Úvod Dnes se stále populárnějšími stávají logické hádanky. O jejich velké rozšíření v poslední době má zásluhy především hra Sudoku, která se setkala s obrovským nadšením a popularitou. Vznikají stále další variace na tuto hru a základna řešitelů rychle narůstá. Díky Sudoku ovšem vzrostl zájem i o další logické úlohy, jako např. Kódované obrázky nebo Kakuro. S rostoucími schopnostmi řešit tyto úlohy se zvyšují požadavky na složitá a zajímavá zadání. Jednou méně rozšířenou logickou úlohou je hra Replacement puzzle [1]. Úkolem mé bakalářské práce bylo vytvořit pro ni generátor různých zadání a simulátor hry, který by zaznamenával informace o postupu jednotlivých hráčů při jejím řešení. Získaná data jsem měl za úkol analyzovat a pokusit se zjistit, co stojí za rozdílnou složitostí odlišných zadání. Výzkum těchto rozdílů může být přínosem pro vytváření nových a zajímavých zadání. Po úvodu následuje kapitola, která slouží k seznámení se s problematikou a představení hry Replacement puzzle. Třetí kapitola je zaměřena na analýzu problému. Ve čtvrté kapitole jsou představeny použité nástroje. Pátá kapitola se zabývá implementací generátoru hry, jejího simulátoru i webového prostředí pro provedení výzkumu. Závěrečná kapitola obsahuje zhodnocení výsledků výzkumu a návrh možných rozšíření pro další práci.

3

Kapitola 2

Úvod do problematiky 2.1

Co je to problém?

Co je to problém? Problém je nějaká neznámá entita, rozdíl mezi současným a koncovým stavem. Vyřešení problému musí mít určitý přínos, ať už sociální, kulturní nebo intelektuální. Hledání něčeho neznámého je proces řešení problému. Řešení problému vyžadují mentální reprezentaci situace. Skládá se z pochopení problému a hledání řešení. Problémy se dělí na dobře a špatně strukturované. Dobře strukturované problémy představí řešiteli všechny elementy problému, vyžadují aplikaci logických principů a pravidel. Mají jednoznačně správné a pochopitelné řešení. Příkladem může být slovní úloha v matematice nebo logická hra Sudoku. Špatně strukturované problémy obsahují elementy, které nejsou známé, mají více řešení, cest k řešení nebo nemusí mít řešení vůbec. Mají různá kritéria pro vyhodnocování problému a výsledku a není jasné, jaká pravidla a principy pro řešení použít. Často nutí řešitele vyjadřovat vlastní názor nebo domněnky a tudíž jsou závislé na interpretaci různých lidí. Může se jednat například o různé ekologické problémy nebo problematiku eutanazie. V každodenním životě je důležitější umět řešit špatně strukturované problémy, dobře strukturované problémy se ale lépe zkoumají. Řešení dobře a špatně strukturovaných problémů vyžaduje jiné sady schopností, nicméně je možné, že je mezi schopností řešit tyto kategorie nějaká spojitost. [2] Logické úlohy spadají do kategorie dobře strukturovaných problémů a tato práce se jednou takovou úlohou zabývá.

2.2

Představení hry Replacement puzzle

Hra byla převzata od profesora australské univerzity Ericha Friedmana z jeho stránek logických hádanek [3]. Ten jí vytvořil pod názvem Replacement puzzle. 4

2. Úvod do problematiky Hráč se má za úkol dostat ze startovní do koncové sekvence dvou různých znaků v daném počtu kroků, přičemž tato sekvence nikdy nesmí přesáhnout délku šesti znaků. K dosažení koncové sekvence mu slouží tři jednoduchá pravidla, pomocí kterých lze nahradit libovolnou část aktuálního řetězce znaků. Na obrázku 2.1 je ukázka zadání i postup řešení.

Obrázek 2.1: Ukázka hry Replacement puzzle. Obrázek pochází ze stránek autora hry [1]. V původní hře jsme upravili grafiku znaků, místo srdíček a lístečků používáme prázdná a plná kolečka, odtud název Kolečka, pod kterým jsme hru použili. Hra v této podobě se nám zdá přehlednější. Druhou úpravou je nezveřejňování počtu kroků k vyřešení hry. Uživatel nevidí, jak daleko je od cíle, což ho nutí více přemýšlet. Zároveň úlohu může vyřešit v jiném počtu kroků, než je předepsané. Tímto se hra více přibližuje předchozímu projektu, který byl zkoumán obdobně jako Kolečka.

5

Kapitola 3

Analýza problému 3.1

Požadavky na generátor

Cílem generátoru je vytvářet nová zadání her a dát uživateli jistou představu o jejich obtížnosti, aby mohl kvalifikovaně vybrat zajímavé hry, které budou relevantní pro výzkum. Jako jediný parametr pro generování her bude zadáván minimální počet kroků k vyřešení. Počet pravidel, jejich délka a maximální délka herního řetězce v libovolném stavu je neměnná. Hra je převzata od pana Ericha Friedmana[1], který má ve všech svých zadáních tyto parametry shodně a pevně nastaveny. Dále musí generátor vytvořit graf úplného stavového prostoru hry.

3.2

Požadavky na simulátor

Simulátor umožní hráčům sehrát různé úrovně hry a podrobné statistiky o každé hře bude ukládat do databáze. Musí být dostatečně jednoduchý a intuitivní, aby každý uživatel rychle pochopil princip ovládání. Příliš složitý simulátor by mohl některé hráče odradit ještě před samotným vyzkoušením hry a zvětšil by vliv učení, který se snažíme omezit, aby jím výsledky nebyly příliš ovlivněny. Rovněž by měl být graficky příjemný, aby dokázal zaujmout a přitáhnout pozornost začínajících řešitelů. Simulátor potřebuje nějakou formou komunikovat s databází na serveru a průběžně ukládat záznamy o hrách. Tato činnost by se měla dít bez vědomí hráče, aby ho neobtěžovala. Nemůže uživateli dovolit editovat odesílaná data nebo dokonce vytvářet a posílat data vlastní. Pokud dojde k výpadku webového serveru nebo databáze, hra by měla běžet dále nebo zhavarovat slušně a informovat hráče. Důležitým požadavkem je snadná, pokud možno žádná, instalace. Uživatelé nestojí o stahování a instalaci dalších, navíc neznámých, programů. Součástí simulátoru musí být jednoduchá nápověda k principu hry a ovládání, stejně tak vysvětlení, proč se o tuto úlohu zajímáme. 6

3. Analýza problému

3.3

Sběr dat

K výzkumu je potřeba zaznamenávat veškeré informace o tazích tak, abychom z nich později mohli zrekonstruovat přesný pohyb po stavovém prostoru včetně času, který každý pohyb trval. Dále je nutné zaznamenávat časy pro dohrání jednotlivých úrovní, aby bylo možné analyzovat rozdíly mezi úrovněmi a ověřovat naše hypotézy.

3.4

Požadavky na zpracování dat

Simulátor bude do databáze ukládat velké množství dat. Ne všechna data musí být nutně korektní, může dojít k výpadku databáze nebo jiné nečekané chybě. Uživatel také může od počítače na nějaký čas odejít a hru nechat spuštěnou. Tato data by nechtěně ovlivňovala výsledky výzkumu, a proto musí být vhodně zvoleným způsobem filtrována. Takto přefiltrovaná data je nutné zpracovat do přehledné podoby, do tabulek a grafů, aby z nich bylo možné vyčíst výsledky.

7

Kapitola 4

Použité nástroje 4.1

Java

Java je dnes jedním z nejrozšířenějších programovacích jazyků na světě. Jedná se o čistě objektově orientovaný jazyk. S výjimkou osmi primitivních datových typů jsou všechny ostatní datové typy objektové. Používá zjednodušenou a upravenou syntaxi jazyka C++ s vypuštěním složitých konstrukcí. Její vývoj začal v roce 1991 a v roce 1995 byla vydána společností Sun Microsystems jako Java 1.0. Od května roku 2007 je vyvíjena jako open source. Hlavní myšlenka Javy je write once, run anywhere. Kód javy není kompilovaný do strojového kódu, ale do tzv. bytecode, který interpretuje Java Virtual Machine (JVM) přímo na počítači uživatele. Dostupnost JVM na různých hardwarových a softwarových platformách umožňuje přenositelnost kódu na platformy s rozdílnou architekturou, jelikož kód nekompiluje programátor, ale JVM podle potřeb platformy, na které běží [4][5][6]. Významným faktorem při výběru Javy byly mé předchozí zkušenosti s tímto jazykem. 4.1.1

Výhody jazyka Java

∙

Je vyvíjen jako open source.

∙

Je přenositelný na různé platformy. Není závislý na operačním systému nebo architektuře platformy.

∙

Je jednoduchý. Používá zjednodušenou syntaxi C++ a nedovoluje složité a nepřehledné konstrukce.

∙

Má k dispozici vynikající online dokumentaci.

∙

Na internetu je obrovské množství volně dostupných knihoven.

∙

Je silně typovaný a vyžaduje zachycování výjimek. Tato skutečnost se může zdát jako příliš složitá a obtěžující při psaní malých projektů, 8

4. Použité nástroje nicméně nutí programátora k psaní čitelného a robustního kódu a buduje dobré návyky pro pozdější vývoj rozsáhlejších projektů. ∙

Má automatické odklízení nepoužitelných objektů.

∙

Vyšší efektivita práce programátora v Javě než například v C++.

∙

Podporuje psaní dokumentace (JavaDoc).

∙

K dispozici je zdarma řada vývojových prostředí.

∙

Stále víc je používán jako referenční jazyk.

∙

Má dobré vyhlídky do budoucna.

∙

Je bezpečný. Bezpečnost zajišťuje Java Virtual Machine.

4.1.2

Nevýhody jazyka Java

∙

Oproti jazykům se statickou kompilací (například C++) je start programů v Javě pomalejší, jelikož JVM musí nejdříve kód přeložit. Právě pomalost byla Javě dříve hodně vytýkána, dnes ale JVM používá algoritmy, které tuto činnost zrychlují a rozdíly v rychlosti se snižují. Některé aplikace v Javě již dokonce běží rychleji než v C++.

∙

U malých projektů je paměťově náročnější, jelikož se do paměti musí načíst celá JVM.

∙

Neumožňuje psát některé složité konstrukce, s čímž mohou mít ze začátku problém programátoři zvyklí na jiný jazyk.

4.2

Java applet

Java Applet je speciální případ programu v jazyce Java, který lze spouštět přes webový prohlížeč a běží na straně uživatele. Umožňuje v prohlížeči funkce, které samotné HTML neumí, jako například snímání pohybů myši, používání tlačítek nebo check boxů. Přibližuje vzhled a funkci klasickým desktopovým aplikacím, ale jako desktopová aplikace se nechová. Nemůže běžet samostatně a má omezená práva kvůli bezpečnosti. Jako jiné javoské programy je nezávislý na platformě, o přenositelnost se stará JVM [7]. 9

4. Použité nástroje 4.2.1

Výhody Java appletu

∙

Není závislý na operačním systému ani webovém prohlížeči.

∙

Java applet může běžet na veškerých verzích Java Runtime Environment. Některé funkce mohou vyžadovat novější verze, ale instalace nové verze prostředí je jednoduchá.

∙

Opětovné spouštění appletů je rychlejší než spuštění prvotní, kdy se musí spouštět JVM.

∙

Běží na straně klienta, tudíž odlehčuje práci serveru.

∙

Je bezpečný. Applet neumožňuje spouštění aplikací na počítači uživatele, má přístup jen do části paměti a smí se připojovat pouze na server, ze kterého byl spuštěn.

4.2.2

Nevýhody Java appletu

∙

Některé operační systémy a prohlížeče nepodporují standardně Javu a je nutné nainstalovat plug-in. Tento plug-in je však volně přístupný, jeho instalace je snadná a dnes ho má téměř každý uživatel. Plug-in je bohužel potřeba na systémech MS Windows, jelikož Microsoft přišel o licenci na javovské prostředí kvůli nedodržení kompatibility všech prostředí.

∙

Kvůli bezpečnosti neumožňuje některé funkce.

∙

Špatně napsané applety nemusí běžet na všech verzích javy.

4.3

PHP

PHP (název je rekurzivní zkratka PHP: Hypertext Preprocessor) je velmi rozšířený interpretovaný skriptovací jazyk používaný zejména k tvorbě dynamických webových aplikací. Může být začleněn do HTML kódu a běží na straně serveru, který musí mít nainstalovanou podporu PHP, aby jej mohl přeložit a vytvořit z něj webový obsah. PHP se velmi rychle rozšiřuje a je dnes používáno na více než dvaceti milionech webových stránek a milionu serverů. Je volně dostupné pod PHP licencí [8]. Syntaxe jazyka kombinuje několik programovacích jazyků (Perl, C, Pascal, Java). PHP obsahuje velké množství volně dostupných knihoven pro tvorbu webového obsahu, komunikaci s databázovými servery (např. MySQL, Oracle) nebo práci se soubory [9][10]. 10

4. Použité nástroje

4.4

MySQL

MySQL je databázový systém, vytvořený švédskou společností MySQL AB, dnes přidruženou k Sun Microsystems. Je k dispozici pod bezplatnou licencí GPL. Jedná se o meziplatformní databázi. Komunikace s ní probíhá přes jazyk SQL. Pro svou snadnou instalaci, rychlost a volnou šiřitelnost má velký podíl na dnes používaných databázích. MySQL využívají i velké projekty jako Google[11] nebo Facebook[12]. Velké programovací jazyky nabízejí knihovny pro komunikaci s touto databází [13].

4.5

Pajek

Název Pajek pochází ze slovinského slova, které znamená pavouk. Tvůrci programu jsou profesoři slovinské univerzity v Lublani, Vladimir Batagejl a Andrej Mrvar. Pajek slouží pro analýzu a vizualizaci rozsáhlých sítí. Dokáže zpracovávat grafy obsahující tisíce až miliony uzlů. Pro potřeby této bakalářské práce poslouží k zobrazování stavových prostorů jednotlivých her [14]. Pajek jsem zvolil z několika důvodů: ∙

Nedokážu předem určit, jak velké mohou být stavové prostory jednotlivých úrovní. Pajek lze použít s jejich libovolnou velikostí.

∙

Je velice jednoduchý na práci.

∙

Pro potřeby tohoto výzkumu vyžaduje tři vstupní soubory v jednoduchém formátu. Tyto soubory není obtížné v Javě vygenerovat.

Pro vyhodnocení výsledku je potřeba vygenerovat následující soubory. Jejich přesný formát naleznete na přiloženém DVD. ∙

.net - soubor slouží pro zadání počtu uzlů, jejich názvů a hran mezi nimi.

∙

.clu - soubor umožňuje shlukovat uzly do skupin. Pro potřeby této práce budou od ostatních uzlů barevně odlišeny uzly startovní a koncové.

∙

.vec - soubor pro nastavení velikosti uzlů. 11

4. Použité nástroje

4.6

R

R je jazyk a zároveň prostředí pro provádění statistických výpočtů a tvorbu grafických výstupů. Je to volně šiřitelný nástroj používaný mnoha statistiky. Umožňuje vykreslovat profesionální grafy a obrázky [15]. V této práci je použit k vykreslení některých statistik.

4.7

NetBeans IDE

NetBeans je volně šiřitelné vývojové prostředí, umožňující programátorům psát, překládat, ladit a šířit své programy. Primárně je určeno pro vývoj aplikací v jazyce Java, nicméně ve vyšších verzích podporuje i další programovací jazyky jako např. C++, PHP nebo Ruby. Vývoj NetBeans začal v roce 1996 jako projekt studentů na pražské univerzitě. V roce 1999 ho koupila společnost Sun Microsystems a následující rok ho zveřejnila jako open source. Dnes k projektu přispívá řada programátorů, nicméně velká část vývoje probíhá v pražské pobočce Sun Microsystems [16]. Prostředí NetBeans používám pro veškeré psaní kódu v Javě nebo PHP skriptů.

12

Kapitola 5

Implementace 5.1

Konvence pro popisování kódu v této práci

Při psaní metod nebudu uvádět jejich parametry, tj. metody jsou zapsány ve tvaru metoda(). V případě, že jsou některé parametry důležité, zmíním je v popisu funkčnosti metody. Při názvu tříd, proměnných a metod je použito konvencí pro psaní kódu v jazyce Java. Jména tříd začínají velkým písmenem, ostatní písmena jsou malá. Pokud se název třídy skládá z více slov, zapisují se tzv. CamelCase, např. MojeTřída. Metody a proměnné začínají malým písmenem, pokud se skládají z více slov, každé nové slovo začíná velkým písmenem. Při popisu atributů tabulek databáze jsou užita velká písmena, např. JMENO, CAS.

5.2

Implementace generátoru

Úlohou generátoru je umožnit uživateli vytvářet nová zadání her. Pro co největší usnadnění je generátor zpracován jako aplikace v jazyce Java s grafickým prostředím. Na přiloženém obrázku 5.1 můžete vidět, jak generátor vypadá. Uživatel zadává pouze počet kroků k vyřešení hry. Na základě toho se generují hry a jejich zadání je zobrazeno v levé spodní části okna. Informace o stavovém prostoru hry jsou potom v pravé dolní části. Pokud uživateli vygenerované zadání vyhovuje, stačí pro něj vymyslet název a tlačítkem Uložit tuto hru se vygenerují soubory se zadáním hry a soubory pro program Pajek, který z nich dokáže vykreslit graf stavového prostoru. Při práci s řetězci herních zadání a stavů nepoužívám jako znaky plná a prázdná kolečka, která jsou použita ve hře. Kvůli přehlednosti je plné kolečko nahrazeno znakem x, prázdné potom znakem y. Stejným způsobem jsou zadání her uložena i v databázi. 13

5. Implementace

Obrázek 5.1: Ukázka prostředí generátoru 5.2.1

Popis funkčnosti generátoru

Aplikace se skládá ze tří tříd. Třída GeneratorGUI Tato třída obsahuje grafické prostředí a získává od uživatele počet kroků k řešení úlohy. Třída Node Tato třída slouží k vytváření objektů typu Node, se kterými aplikace pracuje. Třída Generator Tato třída se stará o samotné generování a ukládání her. Skládá se z několika hlavních metod, setup(), start(), createRules(), go(), writeGame() a pajek(). ∙

metoda setup() - V této metodě se nastaví maximální délka řetězce v každém kroku, pro účely této práce je pevně nastavená na 6, ale pokud by někdy bylo potřeba generovat hry s jiným nastavením maximální délky řetězce, lze toho jednoduše dosáhnout přepsáním tohoto parametru. 14

5. Implementace Dále tato metoda převezme od třídy GeneratorGUI parametr počet kroků a vytvoří kolekce pro ukládání dat potřebných k chodu programu. ∙

metoda createRules() - Tato metoda má za úkol vytvářet pravidla. Vytvoří náhodné sekvence dvou znaků o délce 1-3 pro levé a pravé části tří pravidel. Dále vygeneruje startovní řetězec tak, aby na něj bylo možné v prvním kroku aplikovat alespoň jedno pravidlo.

∙

metoda go() - Tato metoda začíná s vygenerovanou startovní sekvencí znaků a zjišťuje, jestli jde některými pravidly přepsat. Pokud ano, vygeneruje všechny takto vzniklé řetězce, uloží je, pokud se doposud nevyskytly, a přes ně prochází v dalším kroku. Toto se děje do stavu, kdy už žádný nový řetězec nevzniká. V každém cyklu tedy vytvoří řetězce, do kterých se lze dostat v n+1 tazích hry. Pokud se nachází v kroku, který byl uživatelem zadán jako počet kroků k řešení, vybere z nově přepsaných řetězců jeden a ten zapíše do proměnné end jako cílový. Metoda si pamatuje, v kolikátém kroku přepisování skončilo. Toto číslo vrátí metodě, ze které je volána. Metoda si všechny nové sekvence znaků ukládá v podobě, ze které lze později sestavit graf stavového prostoru hry.

∙

metoda start() - Metoda start() se stará o to, aby aplikace vygenerovala úlohu, ve které lze do některého stavu přejít právě v zadaném počtu kroků. Na začátku běhu vrátí nastavení proměnných do původního stavu a spouští metody createRules() a go() do doby, než se úspěšně vygeneruje hra. O počtu kroků, kam přepisování dospělo, je informována návratovou hodnotou metody go().

∙

writeGame() a pajek() - Tyto metody mají za úkol uložit vygenerované zadání. Jsou spouštěny uživatelem přes grafické rozhraní třídy GeneratorGUI. Obě jako parametr přebírají název hry zadaný uživatelem. Metoda writeGame() do textového souboru uloží vygenerovaná pravidla a zadání hry. Metoda pajek() vytvoří soubory .net a .clu potřebné pro program Pajek k vykreslení stavového prostoru hry.

5.3

Implementace appletu

Hra samotná je zpracována jako java applet. Vedlo k tomu několik důvodů: ∙

Applet běží na straně uživatele a nezatěžuje tak server. 15

5. Implementace ∙

Applet lze začlenit do webové stránky, takže veškerý sběr dat bude probíhat prostřednictvím webu a uživatel nemusí nic instalovat.

∙

Při výpadku serveru applet zvládne fungovat dále.

∙

Hra se bude velmi podobat desktopové aplikaci. Lidé jsou na takové prostředí zvyklí a nebudou se muset učit pohybovat v něčem novém.

∙

Komunikace appletu se serverem není nijak viditelná, nebude hráče obtěžovat.

∙

Applet bude využívat část kódu generátoru.

∙

Podle našeho průzkumu používá prohlížeč s podporou Javy 97% uživatelů.

5.4

Vzhled a ovládání appletu

Vzhled appletu je velice jednoduchý a lze jej vidět na obrázku 5.2. V horní části je zadání hry, pod ním potom tři pravidla, která lze při řešení používat. Aktuální herní řetězec je umístěný vlevo dole. Tlačítko Zpět slouží k vrácení jednoho tahu, tlačítko Reset hru vrátí do startovního stavu. Samotná hra probíhá tak, že hráč v aktuálním řetězci vybere znak, kde začíná levá část pravidla, které by chtěl použít. Po kliknutí se tento znak zvýrazní a zaktivují se tlačítka s těmi pravidly, která lze použít. Klikem na tlačítko se řetězec přepíše. Pokud se hráč dostane do koncového stavu, vypíše se informace o úspěšném vyřešení hry s uvedením času, v jakém ji hráč vyřešil, a deaktivují se všechna tlačítka. Hráč si potom pomocí webového prostředí může vybrat jinou úroveň. Dlouho bylo zvažováno, zda hráči poskytnout informaci, která pravidla lze aplikovat. Nakonec byl tento postup použit. Zásadním způsobem to ovlivňuje hru a hráč může této funkce zneužívat tím, že nebude sám přemýšlet, jaké pravidlo a kde by šlo použít, ale stačí mu postupně vybrat všechny znaky v řetězci a možnosti tahu mu applet sám nabídne. Tuto vlastnost ale považujeme za součást hry a počítáme s ní.

5.5

Spouštění appletu

Webové prostředí nabídne hráči dostupné úrovně hry. Vybráním některé z her se spustí php skript, kterému se jako parametr předá číslo vybrané hry. Ten potom z databázové tabulky kolecka_games načte zadání úrovně a předá jej appletu. 16

5. Implementace

Obrázek 5.2: Vzhled appletu

5.6

Ukládání dat z appletu do databáze

Applet ukládá informace do databáze při každém hráčovu kliku na některé ze tří pravidel nebo tlačítko Zpět a Reset. Komunikace s databází probíhá přes php skript na serveru, kterému applet předá potřebné parametry. Skript se postará o zapsání těchto parametrů do databáze.

5.7

Popis funkčnosti a zdrojového kódu appletu

Celý applet je psán jako jedna třída Kolecka. Při spuštění applet vyžaduje parametry se zadáním všech levých a pravých pravidel, startovní a koncové sekvence znaků, číslo hry, id hráče, číslo pokusu daného hráče o vyřešení této hry, a informaci, jestli úlohu hráč již dříve vyřešil. Pokud hráč spustí už dohranou hru, data z ní nejsou ukládána, zajímáme se pouze o jeho prvotní řešení. 5.7.1

Důležité metody třídy Kolecka

∙

metoda loadInitData() - Tato metoda přebírá parametry z php skriptu, kterým byl applet spuštěn a zapisuje je do proměnných třídy.

∙

metoda setupGame() - Tato metoda nastaví hrací plán. Zadání přepíše 17

5. Implementace na sekvence plných a prázdných koleček a vše vykreslí do grafického prostředí appletu. Spuštěním této metody se začíná počítat čas hry. ∙

metoda writeData() - Tato metoda se spustí, pokud hráč klikne na některé z tlačítek pro aplikaci pravidel nebo na tlačítka Zpět a Reset. Jako parametry vyžaduje číslo pravidla, které bylo použito a stav herního řetězce před použitím pravidla, ostatní informace získává z proměnných třídy. Při spuštění také vyresetuje proměnnou, do které se ukládá čas pro jeden tah. Potom metoda zavolá php skript na serveru a předá mu potřebné parametry, které skript zapíše do tabulky kolecka_game_log.

∙

metoda possibleRules() - Metoda possibleRules() se stará o aktivaci tlačítek, pokud uživatel v řetězci vybere část, která lze některým z pravidel přepsat. Spouští se při každém hráčově kliknutí na znak z aktuálního herního řetězce. Zjistí, jestli z toho místa začíná řetězec, který lze přepsat některým z pravidel. Pokud ano, zaktivuje tlačítko pro aplikaci tohoto pravidla.

∙

metoda replaceGameString() -Tato metoda přepisuje aktuální herní řetězec, tedy stav hry, ve kterém se řešitel nachází. Spouští se při kliknutí na některé ze tří tlačítek pravidel nebo kliknutím na tlačítka Zpět a Reset. Zároveň deaktivuje všechna tlačítka s výběrem pravidel.

∙

metoda checkWin() - Metoda checkWin() při každém tahu hráče kontroluje, jestli se nedostal do koncového stavu. Pokud ano, deaktivuje všechna tlačítka hry a vypíše informaci o úspěšném vyřešení hry s údajem, kolik času hra řešiteli zabrala. Zároveň spustí metodu writeFinal(), která slouží pro zápis celých her do databázové tabulky kolecka_games_relevant.

∙

metoda writeFinal() - Tato metoda se může spustit dvěma způsoby. Jedním je zavolání z metody checkWin(), pokud hráč vyřešil úroveň. Druhý případ je opuštění appletu. Pokud hráč vypne okno s prohlížečem nebo stránky opustí a zároveň úroveň nedokončil, applet před skončením zavolá tuto metodu, aby byla informace o hře uložena. Vobou případech metoda volá php skript na serveru s parametry potřebnými pro zápis do tabulky kolecka_games_relevant.

Při výpadku webového serveru lze aktuálně spuštěnou hru nadále hrát bez povšimnutí. Problém nastane až při výběru hry nové. Kdyby tedy server 18

5. Implementace náhodou spadl jen na krátký okamžik, mnoho hráčů to ani nemusí postřehnout. Stejně tak výpadek databáze ovlivní jen spouštění hry a její statistiky. Samozřejmě by se během této doby neukládaly informace o tazích hráče, ale jelikož applet běží na straně uživatele a funguje normálně dál, v databázi by bylo možné dohledat, které tahy chybí.

5.8

Implementace DataMineru

Tento program byl zpracován jako offline desktopová aplikace v jazyce Java bez grafického prostředí. Jako vstup používá export kompletních tabulek z databáze ve formátu csv. Jeho prvním úkolem je vhodným způsobem přefiltrovat data, aby poškozené informace příliš neovlivňovaly výsledky. K tomu slouží dvě hlavní třídy, třída RepairLog a třída RepairRelevant. 5.8.1

Třída RepairLog

Tato třída RepairLog načte každý řádek záznamu v tabulce ze vstupního souboru kolecka_game_log.log a pokud některý z tahů hráči trval déle než tři minuty, je čas tahu zkrácen právě na tři minuty. Tento čas se jevil jako optimální. Překročení limitu tří minut na tah nejspíš znamená, že hráč byl při hře něčím vyrušen a nevěnoval jí plnou pozornost. Nechtěli jsme při porušení této podmínky zahazovat všechna data, jelikož postup při řešení úlohy je stále relevantní a není tolik závislý na čase. Upravené záznamy uloží do souboru kolecka_game_log_cor.log, se kterým program nadále pracuje. 5.8.2

Třída RepairRelevant

Třída Repair relevant načte každý řádek záznamu v tabulce ze souboru kolecka_game_relevant.log a pokud některá hra trvala déle než 30 minut, je čas hry zkrácen právě na tuto hodnotu. Pokud hráč strávil v jednom spuštění úrovně delší dobu, je velmi pravděpodobné, že se hře nevěnoval celou dobu, ale byl něčím vyrušen. Upravené záznamy uloží třídy do souboru kolecka_game_relevant_cor.log, se kterým program nadále pracuje. Formáty dat v souborech Každý řádek souboru odpovídá jednomu záznamu v tabulce a je uložen ve stejném pořadí jako záznamy v tabulce databáze, hodnoty informace jsou odděleny středníkem.

19

5. Implementace Druhou funkcí programu DataMiner je posbíraná a přefiltrovaná data zpracovat do podoby jednoduše čitelné a pochopitelné člověkem, do tabulek a grafů. K tomu slouží třídy DataMiner, GraphDraw a PlayerTimes. 5.8.3

Třída PlayerTimes

Tato třída slouží ke zpracování časů potřebných k vyřešení úrovní. Data načítá z opravené tabulky kolecka_games_relevant. Ze získaných časů pro každou úroveň zjistí průměrný čas a medián času k jejímu řešení. Tyto hodnoty uloží jako tabulky do souborů ve formátu snadno čitelném pro statistický program R, ve kterém jsou dále zpracovány. 5.8.4

Třída GraphDraw

Třída GraphDraw slouží k vykreslování grafů stavových prostorů. Generuje soubory .net, .clu a .vec potřebné pro program Pajek. Pomocí této třídy jsou vykresleny tři různé typy grafů: ∙

Prostý stavový prostor jednotlivých úrovní.

∙

Stavový prostor úrovní, ve kterém velikosti uzlů grafu odpovídají počtu navštívení daného uzlu hráči.

∙

Stavový prostor úrovní, ve kterém velikosti uzlů grafu odpovídají času strávenému hráči v daném uzlu.

Všechny tyto typy grafů pro každou úroveň jsou součástí obsahu přiloženého DVD. Poslední funkcí aplikace DataMiner je rekonstrukce tahů hráčů. Tato data nejsou v této práci použita, ale budou dále zkoumána vedoucím mé bakalářské práce, Mgr. Petrem Jaruškem. O činnost se stará třída LevelsLog, která informace načítá z opravené tabulky kolecka_game_log. Po zpracování dat je výstupní formát následující: ∙

Každá úroveň je uložena v jednom souboru.

∙

Řádek Player x, kde x je ID hráče, uvozuje část, kde jsou zapsány hry tohoto hráče.

∙

Pro každý hráčův pokus je vyhrazen jeden řádek.

∙

Záznamy tahů na řádku jsou ve formátu [uzel]:čas:pravidlo. Jednotlivé tahy jsou od sebou odděleny mezerou. 20

5. Implementace Tato data jsou součástí obsahu přiloženého DVD.

5.9

Ukládání dat do databáze

V databázi jsou vytvořeny tři tabulky: kolecka_games, kolecka_game_log a kolecka_games_relevant. Dále je využívána tabulku users, která již dříve sloužila pro předchozí projekt. 5.9.1

Tabulka kolecka_games

Tato tabulka slouží k uložení zadání her. Data do ní byla vložena manuálně. Při výběru dané úrovně na webu se data načítají z této tabulky, tudíž je jednoduché do hry přidávat další úrovně, stačí je zapsat do tabulky kolecka_games. Struktura tabulky ∙

ROOMNUMBER - ID hry, každá hra má unikátní RoomNumber, které slouží pro jednoznačnou identifikaci úrovně.

∙

STEPSNUMBER - minimální počet kroků od startu k cíli.

∙

NAME - název hry, který slouží uživatelům k výběru a identifikaci úrovní.

∙

LEFT1 - levá část prvního pravidla.

∙

LEFT2 - levá část druhého pravidla.

∙

LEFT3 - levá část třetího pravidla.

∙

RIGHT1 - pravá část prvního pravidla.

∙

RIGHT2 - pravá část druhého pravidla.

∙

RIGHT3 - pravá část třetího pravidla.

∙

START - startovní sekvence znaků.

∙

END - koncová sekvence znaků, řešení úlohy.

5.9.2

Tabulka kolecka_game_log

Do této tabulky se ukládají podrobná data o hrách. Je zde uložen každý hráčův tah. Z této tabulky lze vyčíst pořadí kroků, kterými řešitel prošel a čas, který v jednotlivých krocích strávil. 21

5. Implementace Struktura tabulky ∙

ID - záznamy v tabulce jsou číslovány.

∙

USER - ID uživatele, který daný krok odehrál.

∙

ROOMNUMBER - ID hry, ze které tah pochází.

∙

ATTEMPTNUMBER - číslo pokusu uživatele při řešení dané úlohy. Různé pokusy jsou od sebe odděleny, aby byly k dispozici přesné informace o postupu při řešení.

∙

MOVENUMBER - číslo tahu, který daný hráč v daném pokusu odehrál.

∙

STARTNODE - počáteční sekvence znaků, ze které byl tah odehrán.

∙

ENDNODE - sekvence znaků, do které se hráč tahem dostal.

∙

TIME - čas strávený tímto krokem v milisekundách.

∙

RULENUMBER - číslo pravidla, které hráč pro tento krok použil(1-3), 4 při použití tlačítka Zpět, 0 při použití tlačítka Reset.

5.9.3

Tabulka kolecka_games_relevant

Do této tabulky se ukládají informace o odehraných hrách. Slouží především pro webové statistiky, tabulka je oproti kolecka_game_log relativně malá a dotazy na ní jsou tudíž rychlejší. Odehranou hrou se myslí jedno načtení java appletu, tudíž buď vyřešení úlohy, nebo neúspěšné opuštění hry. Struktura tabulky ∙

GAME_ID - odehrané hry jsou číslovány.

∙

USER - ID uživatele, který úlohu řešil.

∙

ROOMNUMBER - ID řešené úlohy.

∙

ATTEMPTNUMBER - číslo pokusu řešení dané úlohy.

∙

TIME - celkový čas strávený v tomto pokusu hry.

∙

SOLVED - 0 pokud v tomto pokusu hráč úroveň nevyřešil, 1 pokud ano. 22

5. Implementace 5.9.4

Tabulka users

Z této tabulky používám pouze dvě hodnoty a to ID a přezdívku uživatele.

5.10 Webové prostředí Webové prostředí vytvořil vedoucí této bakalářské práce, Mgr. Petr Jarušek, a původně sloužilo pro předchozí projekt, který byl velice podobný tomuto. Nyní zde lze hrát dvě různé hry. Webové stránky naleznete na adrese http://organizatori.cz/puzzle. PHP skripty, psané mnou pro tuto práci, jsou k dispozici v příloze na DVD. Na obrázku 5.3 je možné vidět výběr levelů na webu.

Obrázek 5.3: Vzhled webového prostředí: výběr levelů. Mým úkolem bylo napsat tři php skripty pro obsluhu Koleček. Jeden slouží k výběru úrovní, druhý ke spouštění a hraní hry, třetí pro zpracování a zvěřejnění statistik hráčů. Dále potom pomocí redakčního systému sepsat 23

5. Implementace informace o hře Kolečka, popsat ovládání a vysvětlit, proč je výzkum prováděn. 5.10.1 Výběr úrovní Stránka s výběrem úrovní obsahuje informace o tom, jak vybrat a spustit některou z úrovní, co je k běhu hry potřeba a potom samotnou tabulku s výběrem úrovní. Tabulka obsahuje názvy úrovní, čas strávený řešením této úrovně do jejího prvního vyřešení, počet pokusů tuto hru dohrát a informaci, zda ji hráč již pokořil. Seznam her v tabulce dostává každý hráč v jiném pořadí, aby se omezil vliv učení. Kdyby byly úrovně všem nabídnuty ve stejném pořadí, našlo by se více uživatelů, kteří by hry řešili v tomto pořadí. Potom by nebylo možné srovnávat obtížnost prvních a posledních úrovní, jelikož by se hráči v průběhu s hrou seznámili a pozdější úrovně by řešili rychleji. 5.10.2 Herní prostředí V herním prostředí je kromě samotného appletu i stručný popis pravidel, informace o vyžadování javy k běhu hry a odkaz zpět na výběr úrovní, pokud se hráči daná hra nedaří. 5.10.3 Zobrazení statistik Bylo zvažováno, jaké statistiky na webu zobrazit, aby příliš neovlivňovaly hráče. Nakonec byla použita pouze tabulka uživatelů, kde je u každého uvedeno, kolik her vyřešil a jaký čas strávil řešením všech úrovní dohromady. Tabulka je řazena nejprve podle počtu odehraných her, pokud je u více lidí stejný, další řazení probíhá podle času.

24

Kapitola 6

Výsledky výzkumu K analýze bylo vybráno 40 úloh s různým minimálním počtem kroků k řešení (5-8), aby rozdílná složitost úloh motivovala hráče. Výzkumu se zúčastnilo 124 hráčů, kteří vyřešili 1570 sledovaných her a 347 tréninků. Z toho 27 hráčů vyřešilo všech 40 úrovní. Osloveni byli především lidé, kteří se účastnili již jednoho předchozího podobného projektu. Nemalou část také tvořili lidé, kteří často řeší jiné logické hádanky. Data byla sbírána po dobu jednoho měsíce. V tabulce na obrázku 6.1 jsou zveřejněny výsledky výzkumu. Zkoumán byl především vliv stavového prostoru úlohy na její obtížnost. Popis tabulky s výsledky ∙

Číslo hry - hry byly očíslovány 1-40, tréninky potom 1000, 1001 a 1002. Tréninkové úrovně v tabulce uvedeny nejsou.

∙

Počet kroků - minimální počet kroků, ve kterém jde hra vyřešit.

∙

Počet uzlů - počet uzlů v grafu úplného stavového prostoru.

∙

Počet hran - hran v grafu úplného stavového prostoru.

∙

Hrany/uzly - poměr hran a uzlů v grafu úplného stavového prostoru.

∙

Čas průměr (sekundy) - průměrný čas k řešení úlohy v sekundách.

∙

Čas medián (sekundy) - medián časů k řešení úlohy v sekundách.

∙

Zdroj - zdroj zadání hry. E u převzatých her od pana Ericha Friedmana, G u her vytvořených generátorem.

∙

Vyřešeno - Počet hráčů, kteří vyřešili danou úlohu. 25

6. Výsledky výzkumu

Obrázek 6.1: Tabulka se statistikami úloh.

6.1

Časy řešení

V grafu na obrázku 6.2 jsou vzkresleny box ploty pro časy řešení jednotlivých úloh. Graf ukazuje, že některé úlohy byly výrazně složitější než jiné. Čím to může být způsobeno?

6.2

Vliv počtu uzlů na složitost

Velikost stavového prostoru by podle našich odhadů měla výrazně ovlivňovat obtížnost úlohy. Pokud hráč musí řešení hledat ve velkém prostoru, přirozeně by mu to mělo trvat déle. V grafu na obrázku 6.3 jsou vykres26


Obrázek 6.2: Časy řešení jednotlivých úrovní leny výsledky našeho výzkumu. Na ose x jsou zaneseny počty uzlů, na ose y potom medián času k řešení dané úlohy. Z grafu oproti původním předpokladům vyplývá, že obtížnost úlohy na počtu uzlů ve stavovém prostoru nijak zásadně nezávisí.

6.3

Vliv počtu hran na složitost

Čím vyšší počet hran v grafu stavového prostoru, tím více rozhodování pro řešitele. Pokud řešitel v každém kroku dostane na výběr z mnoha možností jak táhnout, musí přemýšlet víc dopředu a propočítávat víc variant. Podle naší hypotézy by obtížnost úloh s rostoucím počtem hran měla růst také. V grafu na obrázku 6.4 jsou vykresleny výsledky. Na ose x jsou zaneseny počty hran, na ose y potom medián časů k řešení dané úlohy. Výsledky opět vyvrací prvotní myšlenku, z grafu se žádná zvyšující se doba řešení vyčíst nedá.

6.4

Poměr hran a uzlů

Poměr hran a uzlů v grafu udává, kolik možností tahů hráč průměrně v jednotlivých krocích má. Pokud je tento poměr vysoký, musí často volit z mnoha možností. Pokud je poměr nízký, nemá příliš na výběr, nemusí tolik přemýšlet a cesta k řešení je jednoduchá. V extrémním případě, kdy graf obsahuje n uzlů a n-1 hran, je jen jedna cesta v grafu a to ke správnému řešení. V tomto 27


Obrázek 6.3: Závislost doby řešení na počtu uzlů ve stavovém prostoru

Obrázek 6.4: Závislost doby řešení na počtu hran ve stavovém prostoru

28

6. Výsledky výzkumu případě by měla být hra takřka triviální. Výsledky z grafu na obrázku 6.5 toto ovšem nenaznačují. Naopak jednodušší se zdály být hry s velkým výběrem možností tahu. Dokonce i hra, u které každý možný tah vedl k cíly, zabrala hráčům téměř 3 minuty. Odůvodněním může být, že pro hráče je obtížné tuto jedinou cestu najít, jelikož dlouho hledají možnost, jak vůbec táhnout.

Obrázek 6.5: Závislost doby řešení na poměru uzlů a hran ve stavovém prostoru

6.5

Vliv minimálního počtu kroků k vyřešení hry

Obtížnost jednotlivých úloh by podle předpokladů měla záviset na délce řešení. Čím více kroků musí hráč udělat, tím více musí myslet dopředu a má více příležitostí k odbočení ze správné cesty. V tabulce na obrázku 6.6 jsou uvedeny časy řešení v závislosti na minimálním počtu kroků k vyřešení. Úlohy jsou rozdělené na vytvořené generátorem a převzaté od pana Ericha Friedmana, jelikož je možné, že úlohy vybíral jiným způsobem, než byly vybrány pro tuto práci a není vyloučeno, že se časy budou lišit.

Popis tabulky ∙

Počet kroků - minimální počet kroků ke správnému řešení dané úlohy. 29


Obrázek 6.6: Závislost doby řešení na počtu kroků ∙

Čas řešení celkem (s) - medián času řešení úloh v sekundách.

∙

Čas řešení generovaných úloh (s) - medián času řešení vygenerovaných úloh v sekundách.

∙

Čas řešení převzatých úloh (s) - medián času řešení převzatých úlohvsekundách.

Z tabulky vyplývá, že obtížnost úlohy na počtu kroků skutečně závisí. Odchylku při generovaných úlohách s počtem kroků 8 lze přisoudit postupu při výběru úloh. Je možné předpokládat, že čím víc kroků k řešení úlohy, tím důležitější je pečlivě vybírat pro výzkum zajímavé úlohy.

6.6

Vliv jiných faktorů na složitost

Výzkum tedy ukázal, že složitost hry na velikosti stavového prostoru nebo na počtu možností tahu nijak zásadně nezávisí. Na čem by tedy záviset mohla? Budeme se muset na stavové prostory podívat podrobněji. V grafu 6.7 je vykreslen stavový prostor hry číslo 26, která byla nejsložitější (čas řešení necelých 5 minut). V grafu 6.8 je stavový prostor hry číslo 39, jejíž řešení trvalo pouhých 45 sekund. Uzly grafu jsou stavy hry, šipky značí možný přechod z jednoho stavu do druhého. Počáteční stav je označen písmenem S, koncový potom písmenem C. V prvním grafu je vyznačena cesta od startu k cíli. Je možné si všimnout, že do koncového stavu vede pouze jedna šipka, stejně tak do předchozích stavů. To znamená, že je jediná možnost, jak se lze do koncového i do předchozích stavů, vedoucích k cíli, dostat. Naopak stavový prostor poskytuje spoustu příležitostí, jak ze správné cesty odbočit a bloudit mimo stavy vedoucích řešení. Jakmile řešitel jednou odbočí ze správné cesty, nelze se již vrátit. Zadání této hry proto nutí řešitele přemýšlet daleko dopředu. Oproti tomu na druhém grafu vedou do cílového uzlu dokonce čtyři šipky. Z další části grafu je zřejmé, že existuje spousta cest od startu k cíli. 30


Obrázek 6.7: Stavový prostor hry 26

Obrázek 6.8: Stavový prostor hry 39 Řešitel proto může po stavovém prostoru úspěšně bloudit, aniž by propočítával tahy dlouho dopředu. Když odbočí ze správné cesty, většinou existuje 31

6. Výsledky výzkumu možnost, jak se vrátit a z většiny uzlů je do cíle vidět. Tuto teorii potvrdily i další grafy, které naleznete v příloze na DVD. Ve stavovém prostoru tedy mohou obtížnost ovlivňovat následující výskyty: ∙

Slepé uličky (obrázek 6.9).

∙

Úzká hrdla (obrázek 6.10).

∙

Zpětné hrany (obrázek 6.11).

Obrázek 6.9: Slepé uličky

Obrázek 6.10: Úzké hrdlo V grafech stavových prostorů úloh hry Kolečka se vyskytují především slepé uličky. Úzká hrdla a zpětné hrany se kvůli principu hry objeví velmi zřídka. Následují grafy dvou jednoduchých a dvou složitých úloh. Startovní sekvence znaků je označena žlutě, koncová potom červeně. Velikosti uzlů značí, kolik v nich řešitelé trávili času. Velikost koncového uzlu je nastavená pevně, jelikož čas v něm nemá smysl zaznamenávat. 32


Obrázek 6.11: Zpětné hrany

6.7

Srovnání stavových prostorů vybraných her

Na grafech 6.12 a 6.13 jsou dvě úlohy s velmi malým stavovým prostorem. Řešení první úlohy přitom trvalo 4 minuty, řešení druhé pouze minutu. Na prvním grafu můžeme vidět několik slepých odbočení ze správné cesty, z nichž se již řešitel nemůže vrátit. Hráči v nich trávili překvapivě hodně času než zjistili, že postup nevede k řešení. Oproti tomu druhý graf nabízí pouze 3 možná odbočení, z každého ale vede cesta zpět, a to dokonce jediná možná cesta z tohoto uzlu. Hráč tudíž nemusí přemýšlet ve stavech nevedoucích k řešení, ale hra ho sama navede zpět na správný postup.

Obrázek 6.12: Stavový prostor úlohy 24 (složitá) Jako další příklad jsou uvedeny 2 větší grafy. První (obrázek 6.14) je ze hry 26, která byla vůbec nejsložitější ze všech (její řešení zabralo téměř 5 minut). Druhý graf (obrázek 6.15) je stavový prostor hry číslo 8, jejíž řešení trvalo přibližně minutu. Na grafu hry číslo 26 je znázorněna jediná možná cesta od zadání k řešení. Při jakémkoli odbočení z ní již není možné hru dokončit. Zároveň poskytuje velký prostor pro bloudění po špatné cestě. Jak je z grafu vidět, řešitelé v něm trávili hodně času. I když postupovali správným směrem, roz33


Obrázek 6.13: Stavový prostor úlohy 13 (jednoduchá)

Obrázek 6.14: Stavový prostor úlohy 26 (složitá) hodování jim zabralo poměrně hodně času. Druhý graf znázorňuje opačný extrém. Ze všech stavů, kromě modře označených, se lze k řešení dostat. Proto hru není obtížné dokončit.

34


Obrázek 6.15: Stavový prostor úlohy 8 (jednoduchá)

35

Kapitola 7

Závěr Mým úkolem bylo vytvořit generátor a simulátor pro logickou hru Replacement puzzle, která byla pro naše účely přejmenována na Kolečka. Pomocí generátoru jsem vytvořil zajímavá zadání úloh a zároveň s několika převzatými zadáními byly tyto úlohy podrobeny experimentu. Velkým úspěchem bylo, že nejtěžší ze všech čtyřiceti her byla hra vygenerovaná vytvořeným generátorem. To dokazuje, že umí vytvářet i složitá zadání. Experimentu se zúčastnilo velké množství řešitelů, díky nimž byla získána data, ze kterých se dají vyvodit relevantní výsledky. Výsledky překvapivě vyvrátily mé prvotní odhady. Když jsem s prací začínal, předpokládal jsem, že by složitost úloh mohla záviset na velikosti stavových prostorů, výzkum to však nepotvrdil. Jako rozšíření práce je s tímto poznatkem možné pomocí stávajícího generátoru vytvořit nová zadání podle jiného klíče, nezaobírat se velikostí stavových prostorů, ale spíše v nich hledat výskyty slepých uliček, úzkých hrdel nebo zpětných hran. Bylo by zajímavé s těmito úlohami provést nový experiment, získat více dat a potvrdit nebo vyvrátit tuto novou teorii. Jako další možné rozšíření práce je studium podobnosti různých logických úloh. Při řešení práce jsem se musel naučit pracovat s řadou nových nástrojů. Rozšířil jsem si znalosti PHP a Javy, naučil jsem se v praktické činnosti používat větší databáze. V průběhu vývoje jsem se setkal s řadou problémů, mezi ty největší patřila komunikaci mezi jednotlivými technologiemi. Na začátku vývoje jsem si zcela neuvědomoval rozsáhlost projektu, to se odráží především na přehlednosti kódu napsaného v Javě. Původně jsem měl jen velice jednoduchý generátor, na který se ale postupem času nabalovaly další funkce. Se psaním nových nástrojů pro zpracování dat jsem potřeboval upravovat dříve napsané aplikace. Kdybych problém zpracovával znovu, věnoval bych větší pozornost analýze a díval bych se do budoucnosti. Nicméně jsem se alespoň poučil a pro příště vím, jak to udělat lépe. Věřím ale, že jsem použité nástroje zvolil správně a ani po zkušenostech s prací bych je neměnil.

36

Literatura [1] Friedman, E.: Replacement Puzzles [online]. Dokument dostupný na URL http://www2.stetson.edu/ efriedma/replace/ (leden 2010). [2] Jonassen, D.: Toward a Design Theory of Problem Solving. ETR&D, Vol. 48, No. 4, 2000, p. 63-85. ISSN 1042-1629. [3] Friedman, E.: Erich’s Place. [online]. Dokument dostupný na URL http://www2.stetson.edu/ efriedma/ (leden 2010). [4] Wikipedie: Java (programming language) [online]. Dokument dostupný na URL http://en.wikipedia.org/wiki/Java_%28programming_language%29 (leden 2010). [5] Bosák, T.: Úvod do programovacího jazyka Java. Programujte.com, 2006 [online]. Dokument dostupný na URL http://programujte.com/?akce=clanek&cl=2006041804-uvod-doprogramovacieho-jazyka-java (leden 2010). [6] Pitner, T. Programování v jazyce Java (studijní materiály k předmětu PB162) [online]. Dokument dostupný na URL https://is.muni.cz/ ve studijních materiálech k předmětu PB162. (leden 2010). [7] Wikipedie: Java applet [online]. Dokument dostupný na URL http://en.wikipedia.org/wiki/Java_applet (leden 2010). [8] PHP.net: PHP Usage Stats [online]. Dokument dostupný na URL http://www.php.net/usage.php (leden 2010). [9] Wikipedie: PHP [online]. Dokument http://cs.wikipedia.org/wiki/PHP (leden 2010).

dostupný

na

URL

[10] Wikipedie: PHP [online]. Dokument http://en.wikipedia.org/wiki/PHP (leden 2010).

dostupný

na

URL

[11] Claburn, T.: Google Releases Improved MySQL Code InformationWeek.com, 2007 [online]. Dokument dostupný na URL 37

7. Závěr http://www.informationweek.com/news/internet/showArticle.jhtml? articleID=199201237 (leden 2010). [12] Sobel, J.: Keeping Up, Facebook, 2007 [online]. Dokument dostupný na URL http://blog.facebook.com/blog.php?post=7899307130 (leden 2010). [13] Wikipedie: MySQL [online]. Dokument dostupný http://cs.wikipedia.org/wiki/MySQL (leden 2010).

na

URL

[14] Pajek Wiki: Pajek [online]. Dokument dostupný http://pajek.imfm.si/doku.php?id=pajek (leden 2010).

na

URL

[15] Bína, V., Komárek, A., Komárková, L. Jak na jazyk R 2006 [online]. Dokument dostupný na URL http://www.karlin.mff.cuni.cz/ komarek/Rko/Rmanual2.pdf (leden 2010). [16] Wikipedie: NetBeans [online]. Dokument dostupný http://cs.wikipedia.org/wiki/NetBeans (leden 2010).

na

URL

38

Příloha A

Obsah přiloženého DVD ∙

V adresáři text: text této práce ve formátu .pdf a .tex.

∙

V adresáři java\generator: zdrojové kódy generátoru.

∙

V adresáři java\simulator: zdrojové kódy simulátoru.

∙

V adresáři java\dataminer: zdrojové kódy programu na zpracování získaných dat.

∙

V adresáři php: php skripty.

∙

V adresáři pajek\games: zdrojové kódy pro program Pajek k vykreslení grafů stavových prostorů jednotlivých her.

∙

V adresáři pajek\nodeGraphTime: zdrojové kódy pro program Pajek k vykreslení grafů stavových prostorů jednotlivých her s uzly velikostí odpovídajícím času v nich stráveném.

∙

V adresáři pajek\nodeGraphVisited: zdrojové kódy pro program Pajek k vykreslení grafů stavových prostorů jednotlivých her s uzly velikostí odpovídajícím počtu navštívení.

∙

V adresáři game_log jsou uloženy podrobné logy jednotlivých her.

39

012345

Recommend Documents