MASARYKOVA UNIVERZITA FAKULTA INFORMATIKY. Online simulátor logické hádanky Tents puzzle. Martin Vardan

MASARYKOVA UNIVERZITA FAKULTA INFORMATIKY

Online simul´ ator logick´ e h´ adanky Tents puzzle Bakaláˇrská práce Martin Vardan

Brno, jaro 2011

Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze tato bakal´ aˇrsk´ a práce je m´ ym p˚ uvodn´ım autorsk´ ym d´ılem, jeˇz jsem vypracoval samostatnˇe. Vˇsechny zdroje, prameny a literaturu, které jsem pˇri vypracov´ an´ı pouˇzil nebo z nich ˇcerpal, v práci ˇrádnˇe cituji s uveden´ım u ´plného odkazu na pˇr´ısluˇsn´ y zdroj.

Vedouc´ı pr´ ace: Mgr. Petr Jaruˇsek III

Podˇ ekov´ an´ı Na tomto m´ıstˇe bych r´ ad podˇekoval vedouc´ımu práce, kter´ ym je Mgr. Petr Jaruˇsek, i Mgr. Radku Pel´ ankovi, Ph.D. za ochotu, cenné rady a pˇripom´ınky pˇri veden´ı této pr´ ace.

IV

Shrnut´ı Pr´ ace se zab´ yv´ a n´ avrhem a implementac´ı dvou variant hry ”Stany a stromy” (Tents puzzle) a jejich zapojen´ım do v´ yukového systému Tutor. Jsou téˇz pops´ any principy hry a r˚ uzné v´ yhern´ı strategie. Souˇcást´ı práce je i gener´ ator zad´ an´ı a automatick´ y ˇreˇsiˇc hry. C´ılem práce je umoˇznit sb´ırat data od uˇzivatel˚ u a na z´ akladˇe tˇechto dat navrhovat adekvátnˇe nároˇcná zadán´ı. Posb´ıran´ a data byla analyzována a v´ ysledky jsou v práci uvedeny.

V

Abstract The thesis focuses on project and implementation of two versions of the Tents Puzzle game, and their application in the Tutor educational system. Includes also description of the game’s objective, rules and various winning strategies, as well as the automatic game solver and the settings generator. The simulator was designed to help collecting user data, essencial for effective customization of the game according to the level of player’s skills. All collected data was analyzed and results were included in the thesis.

VI

Kl´ıˇ cov´ a slova online simul´ ator, logick´ a h´ adanka, v´ yhern´ı strategie, Stany a stromy, Tents puzzle, Javascript, Java

VII

Obsah ´ 1 Uvod

1

2 Logick´ e hry 2.1 Historie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Hry pro v´ yzkum . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Podobné pr´ ace na FI . . . . . . . . . . . . . . . . . . . . . . .

3 3 4 4

3 Hra 3.1 3.2 3.3 3.4

Stany a stromy“ ” Verze hry . . . . . . . . . . . Popis hry . . . . . . . . . . . Splnˇen´ı omezuj´ıc´ıch podm´ınek V´ yhern´ı strategie . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

5 5 5 6 6

4 Online simul´ ator 4.1 Definice poˇzadavk˚ u . . . . . . . . . . . 4.2 Volba programovac´ıho prostˇred´ı . . . . 4.3 Implementace . . . . . . . . . . . . . . 4.3.1 HTML . . . . . . . . . . . . . . 4.3.2 Javascript . . . . . . . . . . . . 4.4 Zapojen´ı simul´ atoru do Tutor systému 4.4.1 PROSO Tutor . . . . . . . . . 4.4.2 Komunikace se systémem . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

9 9 10 11 11 13 15 15 16

5 Gener´ ator zad´ an´ı a ˇ reˇ siˇ c 5.1 Anal´ yza hry . . . . . . 5.2 Koncept Flow . . . . . 5.3 Pouˇzité n´ astroje . . . 5.4 Gener´ ator zad´ an´ı . . . 5.5 Automatick´ y ˇreˇsiˇc . . 5.6 Implementace . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

17 17 20 22 23 24 26

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . . . .

6 Anal´ yza v´ ysledk˚ u 28 6.1 Velikost vzorku dat . . . . . . . . . . . . . . . . . . . . . . . . 28 6.2 Rozsah obt´ıˇznosti . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.3 Detailn´ı anal´ yzy . . . . . . . . . . . . . . . . . . . . . . . . . 35 7 Z´ avˇ er A Pˇ r´ıloha A.1 Adres´ aˇr Simulator A.2 Adres´ aˇr Generator A.3 Adres´ aˇr Tutor . . A.4 Adres´ aˇr Analyzy .

38

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

41 41 41 41 41

VIII

1

´ Uvod

Vzdˇel´ av´ an´ı je proces, jehoˇz prostˇrednictv´ım si ˇclovˇek osvojuje poznatky a ˇcinnosti, které uˇcen´ım pˇretváˇr´ı ve vˇedomosti, dovednosti a návyky. V souˇcasné dobˇe existuje ˇrada studi´ı zab´ yvaj´ıc´ıch se zp˚ usoby vzdˇeláván´ı, jejich efektivnost´ı a psychologick´ ym dopadem. Problematikou vzdˇel´ av´ an´ı se zab´ yvá i skupina Proso na Fakultˇe informatiky Masarykovy univerzity. Konkrétnˇe v systému Tutor1 , kter´ y nab´ız´ı logické h´ adanky a zkoum´ a, jak je lidé ˇreˇs´ı. Systém tutor vyuˇz´ıvá psychologii Flow, rovnˇeˇz oznaˇcovanou ˇcesky jako stav plynut´ı“. Jedná se o stav ra” dosti, soustˇredˇen´ı, naprostého zaujet´ı ˇcinnost´ı, pˇri kterém ˇclovˇek zapom´ıná na ub´ıhaj´ıc´ı ˇcas. Pˇri osvojován´ı nov´ ych znalost´ı a dovednost´ı lze tohoto dos´ ahnout zvolen´ım odpov´ıdaj´ıc´ı nároˇcnosti. Tato metoda jiˇz patˇr´ı ke klasickému uˇcivu obecné psychologie, nicménˇe v´ yzkumy v této oblasti se ˇrad´ı ke st´ ale popul´ arnˇejˇs´ım. Smyslem pˇredloˇzené bakaláˇrské práce je vytvoˇrit simulátor konkrétn´ı logické hry a zapracovat jej do existuj´ıc´ıho Tutor systému. Tento systém umoˇzn ˇuje ˇreˇsit logické h´ adanky, pˇrizp˚ usobovat se schopnostem ˇreˇsitel˚ u a doporuˇcit jim vhodn´ y pr˚ uchod u ´lohami v souladu s psychologi´ı Flow. Zaznamen´ av´ a informace o pr˚ ubˇehu ˇreˇsen´ı a ty jsou dále pouˇzity pro v´ yzkum, jak´ ym zp˚ usobem se lidé uˇc´ı. Pro vypracov´ an´ı jsem si zvolil logickou u ´lohu s názvem Stromy a stany (Tents puzzle v origin´ ale). C´ılem hry je um´ıst’ovat stany ke strom˚ um tak, aby byly splnˇeny podm´ınky zadán´ı. V práci budeme rozliˇsovat dvˇe varianty této hry. Pro simul´ ator je nutné vytvoˇrit dostateˇcn´ y poˇcet r˚ uzn´ ych zadán´ı hry. Ta poskytuje gener´ ator n´ ahodn´ ych zadán´ı. Tato zadán´ı jsou poté ruˇcnˇe a s vyuˇzit´ım programu simuluj´ıc´ıho lidské ˇreˇsen´ı ohodnocena a jsou vybrána zad´ an´ı maj´ıc´ı zaj´ımavé vlastnosti. Jednou z tˇechto vlastnost´ı je i poˇcet moˇzn´ ych ˇreˇsen´ı. Dalˇs´ı podstatnou souˇcást´ı programu je tud´ıˇz algoritmus schopn´ y libovolné zad´ an´ı vyˇreˇsit a nalézt vˇsechna jeho správná ˇreˇsen´ı. Hotov´ y program bude zakomponován do Tutor systému, kter´ y umoˇzn ˇuje ˇreˇsit h´ adanky skrze webové rozhran´ı. Z toho d˚ uvodu jsem jako technické ˇreˇsen´ı zvolil pˇr´ımo jazyk HTML a pro v´ ypoˇcty a jednotlivé funkce hry byl pouˇzit jazyk Javascript. V´ ysledkem pr´ ace je hotov´ y program, simuluj´ıc´ı logickou hru Stany a stromy. S uˇzivatelem komunikuje skrze webové, graficky pˇr´ıvˇetivé prostˇred´ı. Tento simul´ ator je pˇripojen ke stávaj´ıc´ımu tutor systému a shromaˇzd’uje data od jeho ˇreˇsitel˚ u. Data jsou vyhodnocována a budou pouˇzita pro dalˇs´ı v´ yzkum. 1 Rozs´ ahlejˇs´ı systém, sb´ıraj´ıc´ı data z r˚ uzn´ ych logick´ ych h´ adanek. V´ıce viz. kapitola 4.4.1 PROSO Tutor.

1

´ 1. UVOD

N´ asleduj´ıc´ı kapitola je vˇenována logick´ ym hrám a prac´ım na toto téma. Tˇret´ı kapitola obsahuje podrobnosti o hˇre Stany a stromy a zp˚ usobu ˇreˇsen´ı. ˇ Ctvrt´ a kapitola se zab´ yv´ a implementac´ı pˇrehrávaˇce a jeho zapojen´ım do systému. V p´ até kapitole se zamˇeˇr´ım na rozbor hry, generátor zadán´ı a ˇreˇsiˇc. ˇ a kapitola obsahuje anal´ Sest´ yzy a v´ ysledky. Závˇereˇcná kapitola pak pˇrináˇs´ı zhodnocen´ı v´ ysledného produktu a návrh moˇzn´ ych rozˇs´ıˇren´ı pro navazuj´ıc´ı pr´ aci.

2

2

Logick´ e hry

Logické hry se v dneˇsn´ı dobˇe tˇeˇs´ı stále vˇetˇs´ı oblibˇe u ˇsiroké veˇrejnosti. O to se ve velké m´ıˇre zaslouˇzila pˇredevˇs´ım logická hra Sudoku, p˚ uvodem z Japonska. D´ıky rozˇs´ıˇren´ı internetu je dnes velmi snadné dostat se i k jin´ ym typ˚ um logick´ ych her. Existuj´ı spousty webov´ ych stránek, nab´ızej´ıc´ıch nepˇreberné mnoˇzstv´ı ménˇe ˇci v´ıce obt´ıˇzn´ ych logick´ ych her a hádanek.

2.1

Historie

Mezi jednu z nejstarˇs´ıch a nejznámˇejˇs´ıch her vyˇzaduj´ıc´ıch logické myˇslen´ı patˇr´ı bezpochyby hra ˇsachy. Obt´ıˇznost ˇsach˚ u, jako i ostatn´ıch deskov´ ych her tohoto typu (d´ ama, go) je dána konfrontac´ı s druh´ ym hráˇcem, nikoli obt´ıˇznost´ı hry samotné. V této práci se budeme zab´ yvat sp´ıˇse hrami, jeˇz vyˇzaduj´ı sloˇzitˇejˇs´ı logické u ´vahy i bez pˇr´ıtomnosti druhého hráˇce. Za jedny z prvn´ıch se povaˇzuj´ı hry, kde je c´ılem z premis vyvodit logick´ y závˇer. Napˇr´ıklad: Hlavn´ı pˇredpoklad: Vˇsichni lidé jsou smrteln´ı. Vedlejˇs´ı pˇredpoklad: Sokrates je ˇclovˇek. Z´ avˇer: Sokrates je smrteln´ y. Za tv˚ urce tohoto typu logick´ ych her je povaˇzován Lewis Carroll, kter´ y je zn´ amˇejˇs´ı jako autor knihy Alenka v ˇr´ıˇsi div˚ u. V druhé polovinˇe 20. stolet´ı pak matematik Raymond M. Smullyan na tyto slovn´ı logické hry nav´ azal a ve sv´ ych knihách pˇredstavil hru Ryt´ıˇri a lh´ aˇri. Ryt´ıˇr mluv´ı vˇzdy pravdu a lháˇr za vˇsech okolnost´ı lˇze. C´ılem pak m˚ uˇze b´ yt napˇr´ıklad pomoc´ı vhodn´ ych dotaz˚ u zjistit, zda mluv´ıme s ryt´ıˇrem, ˇci nikoliv. Problém tˇechto logick´ ych her je vˇsak zˇrejm´ y. Jsou vázány na konkrétn´ı jazyk, ˇci kulturu, tud´ıˇz ani hry tohoto typu nejsou pro v´ yzkum pˇr´ıliˇs vhodné.

Obr´ azek 1: Patn´ actka. Hr´ aˇc má za u ´kol pˇresunout kameny tak, aby byly vzestupnˇe seˇrazeny.

3

´ HRY 2. LOGICKE

Pˇribliˇznˇe ve stejné dobˇe jako Lewis Carroll zaˇcal na vym´ yˇslen´ı r˚ uzn´ ych logick´ ych her pracovat i americk´ y ˇsachista Sam Loyd. Jeho hry byly ˇcasto velmi jednoduché s jasnou formou, ale s obt´ıˇzn´ ym ˇreˇsen´ım. Mezi jeho známé 1 ˇ hry patˇr´ı tˇreba Rozdˇelovaˇcka , C´ıselná skákaˇcka1 nebo Patnáctka (viz. obr. ˇ 1/str. 3), kter´ a byla v minulosti velmi populárn´ı i v Ceskoslovensku.

2.2

Hry pro v´ yzkum

Na rozd´ıl od her se slovnˇe formulovan´ ym zadán´ım jsou tyto snadno mezikulturnˇe i mezi-jazyˇcnˇe pˇrenositelné. Jsou tedy vhodné pro testován´ı na velkém vzorku lid´ı. Dalˇs´ı v´ yhodou je moˇznost je matematicky a informaticky popsat a tud´ıˇz i naprogramovat generátory jejich zadáni a jejich automatické ˇreˇsiˇce. Na tomto typu her lze poté zkoumat na ˇcem závis´ı jejich obt´ıˇznost a které typy zad´ an´ı jsou pro ˇclovˇeka nároˇcné. Vhodné jsou hry typu Sokoban1 , Nurikabe1 nebo v této práci ˇreˇsená hra Stany a stromy1 .

2.3

Podobn´ e pr´ ace na FI

Zaj´ımavost a obl´ıbenost logick´ ych hádanek a v´ yzkum˚ u s nimi spojen´ ych je patrn´ a i z ˇcetnosti prac´ı na toto téma na Fakultˇe informatiky Masarykovy Univerzity. Jedn´ a se napˇr´ıklad o bakaláˇrskou práci zkoumaj´ıc´ı metriky pro urˇcov´ an´ı obt´ıˇznosti a sbˇer dat u her Sokoban a Ruˇsná hodinka [2] nebo diplomovou pr´ aci zab´ yvaj´ıc´ı se moˇznostmi generován´ı hry HEX a návrhem algoritm˚ u pro pr´ aci s touto u ´lohou [9]. Dalˇs´ı u ´lohou, zkoumanou v diplomové pr´ aci, byla hra Nurikabe. Autor zkoumal obt´ıˇznost hry a za t´ımto u ´ˇcelem vytvoˇril ˇreˇsiˇc simuluj´ıc´ı lidské chován´ı [1]. Ve vˇsech tˇechto prac´ıch, i v mnoha dalˇs´ıch, bylo dosaˇzeno zaj´ımav´ ych v´ ysledk˚ u zejména na poli urˇcov´ an´ı obt´ıˇznosti hry pro ˇclovˇeka.

1

Hru je moˇzno si zahr´ at na str´ ank´ ach Tutora. URL: http://tutor.fi.muni.cz/ 4

3

Hra Stany a stromy“ ”

Tento hern´ı ˇz´ anr vymyslel Léon Balmaekers a poprvé ho publikoval v hoˇ anek se jmelandském ˇcasopisu Breinbrekers (= Hlavolamy) v roce 1989. Cl´ noval Alle Ballen verzamelen“. ”

3.1

Verze hry

V pr´ aci rozliˇsujeme dvˇe verze této hry. Klasická varianta hry, kterou zde budeme naz´ yvat ”s ˇc´ısly”, umoˇzn ˇuje vˇzdy jen jedno správné ˇreˇsen´ı1 . Jedn´ım ze zkouman´ ych faktor˚ u ovlivˇ nuj´ıc´ıch obt´ıˇznost zadán´ı pro ˇclovˇeka je vˇsak i poˇcet moˇzn´ ych ˇreˇsen´ı. Proto zavád´ıme i verzi ”bez ˇc´ısel”, jeˇz umoˇzn ˇuje 2 libovoln´ y poˇcet ˇreˇsen´ı .

3.2

Popis hry

Obˇe verze hry se hraj´ı na ˇctvercovém poli. Ve verzi s ˇc´ısly jsou vpravo a pod polem omezuj´ıc´ı ˇc´ısla. Zad´ an´ım hry je prázdné pole s náhodnˇe rozm´ıstˇen´ ymi stromy (viz. obr. 2/str. 5). Ve verzi s ˇc´ısly budeme pracovat se zadán´ımi velikosti 6 × 6, 8 × 8 a 10 × 10. Ve variantˇe bez ˇc´ısel pak s velikostmi 8 × 8, 10 × 10 a 12 × 12. Na menˇs´ıch hrac´ıch pol´ıch je ˇreˇsen´ı ˇcasto triviáln´ı.

1 0 1 1 0

2

0

1

Obr´ azek 2: (vlevo)Zad´ an´ı s ˇc´ısly pro hrac´ı pole velikosti 4 × 4. (vpravo) Zad´ an´ı bez ˇc´ısel pro pole 4 × 4. Pravidla C´ılem hry je um´ıstit ke kaˇzdému stromu stan tak, aby se spolu dot´ ykaly horizont´ alnˇe nebo vertik´ alnˇe (hranou). Stany navzájem se vˇsak nesm´ı dot´ ykat ani diagon´ alnˇe (pˇres roh). Ve verzi s ˇc´ısly je taktéˇz nutné dodrˇzet maximáln´ı poˇcet stan˚ u na ˇr´ adku (viz. obr. 3/str. 6). Poˇcet stan˚ u je vˇzdy schodn´ y s poˇctem strom˚ u. 1 2

Ve velmi specifick´ ych pˇr´ıpadech i v´ıce neˇz jedno. V´ıce v kapitole 6.1 Anal´ yza hry Rozsah poˇctu ˇreˇsen´ı z´ avis´ı na velikosti hrac´ıho pole. V´ıce v kapitole 6.1 Anal´ yza hry 5

3. HRA STANY A STROMY“ ”

1 0 1 1 0

2

0

1

Obr´ azek 3: (vlevo)Jediné moˇzné ˇreˇsen´ı. (vpravo) Jedno z moˇzn´ ych ˇreˇsen´ı. Zaˇ razen´ı podle tutora V Tutoru jsou logické u ´lohy tˇr´ı typ˚ u. • Transportn´ı: proch´ azen´ı stavového prostoru pomoc´ı tah˚ u“ (napˇr. ” Sokoban) • CSP: constraint satisfaction problem“, problém splnˇen´ı omezuj´ıc´ıch ” podm´ınek (napˇr. Sudoku) • V´ yukov´ e: r˚ uzné typy v´ yukov´ ych aplikac´ı (napˇr. Robotiak)

3.3

Splnˇ en´ı omezuj´ıc´ıch podm´ınek

Velké mnoˇzstv´ı logick´ ych her, tak jako i hra Stany a stromy, spadá do kategorie CSP [8]. Problém splˇ nov´ an´ı podm´ınek (CSP) je definován jako trojice (X, D, C), kde: • X = {x1 , . . . , xn } je koneˇcná mnoˇzina promˇenn´ ych, • D = D1 ∪. . .∪Dn je koneˇcná mnoˇzina hodnot promˇenn´ ych, kde xi ∈ Di • C = {c1 , . . . , cn } je koneˇcná mnoˇzina omezen´ı definovan´ ych na X. ˇ sen´ım CSP je u Reˇ ´plné ohodnocen´ı promˇenn´ ych (d1 , . . . , dn ) ∈ D1 ×. . .×Dn , které splˇ nuje vˇsechna omezen´ı ci ∈ C.

3.4

V´ yhern´ı strategie

C´ılem hry je spr´ avnˇe rozm´ıstit stany do pole tak, aby byly splnˇeny omezuj´ıc´ı podm´ınky dané verze hry. Nezáleˇz´ı pˇritom na poˇrad´ı um´ıst’ován´ı. Je jedno, kter´ y stan um´ıst´ıme prvn´ı a kter´ y posledn´ı. Rozhoduj´ıc´ı je v´ ysledné rozm´ıstˇen´ı. V obou verz´ıch hry je v´ıce moˇzn´ ych postup˚ u jak se m˚ uˇze hráˇc dopracovat k v´ ysledku. Jednou z moˇznost´ı by bylo prohledávat pole do hloubky, 6

3. HRA STANY A STROMY“ ” tedy stejnˇe jako to dˇel´ a grafov´ y algoritmus DFS (Depth first search). Tento postup je vˇsak silnˇe z´ avisl´ y na velikosti pole a uˇz na pomˇernˇe mal´ ych pol´ıch doch´ az´ı k velkému vˇetven´ı. Protoˇze lidé neum´ı systematicky procházet velké mnoˇzstv´ı moˇznost´ı, nen´ı tento postup pˇr´ıliˇs vhodn´ y. Z tohoto pohledu se jako vhodnˇejˇs´ı jev´ı hled´ an´ı pomoc´ı náhodné procházky“. Pokud maj´ı lidé ” s dan´ ym problémem zkuˇsenosti, dokáˇz´ı dobˇre odhadnout po které vˇetvi se vydat[6]. Tento postup se uk´ azal jako efektivn´ı hlavnˇe u verze bez ˇc´ısel. Naopak u verze s ˇc´ısly, kde je v´ıce omezuj´ıc´ıch podm´ınek, je uˇz na mal´ ych pol´ıch nedostaˇcuj´ıc´ı. Ve verzi s ˇc´ısly se jako vhodnˇejˇs´ı jev´ı vyuˇzit´ı jednoduch´ ych heuristik. Heuristiky: Soubor jednoduch´ ych pravidel, napomáhaj´ıc´ıch k nalezen´ı správného ˇreˇsen´ı. Kombinace tˇechto krok˚ u ˇcasto vede k v´ ysledku, avˇsak ne vˇzdy. 1. Oznaˇc´ıme vˇsechna pole, kde stan rozhodnˇe b´ yt nem˚ uˇze: (a) nedovol´ı to omezuj´ıc´ı ˇc´ısla (jen ve verzi s ˇc´ısly); (b) nen´ı v dosahu ˇz´ adn´ y neobsazen´ y strom; (c) je v okol´ı jiˇz postaven´ y stan. 2. Zkontrolujeme, zda se poˇcet voln´ ych pol´ı na ˇrádku nebo ve sloupci neshoduje s omezuj´ıc´ım ˇc´ıslem, pokud ano, um´ıst´ıme stany (jen ve verzi s ˇc´ısly). 3. Provˇeˇr´ıme pozice, které umoˇzn ˇuj´ı pouze jedno rozestaven´ı. 4. Propoj´ıme k sobˇe patˇr´ıc´ı stromy a stany. 5. Znovu opakujeme vˇsechny kroky 1-4. Vzorov´ eˇ reˇ sen´ı vyuˇ z´ıvaj´ıc´ı heuristiky: 2

2

0

0

2

2

0

0

1 2

0

1

0

2

1 2

0

1

0

2

Obr´ azek 4: Vzorové ˇreˇsen´ı. Krok 1 (vlevo) a krok 2 (vpravo). Krok 1: Zad´ an´ı hry Stany a stromy ve verzi s ˇc´ısly. Krok 2: Pouˇzijeme u ´vahu 1(a) a vyznaˇc´ıme pole, kde ˇzádn´ y stan nedovoluj´ı ˇc´ısla.

7

3. HRA STANY A STROMY“ ” 2

2

0

0

2

2

0

0

1 2

0

1

0

2

1 2

0

1

0

2

Obr´ azek 5: Vzorové ˇreˇsen´ı. Krok 3 (vlevo) a krok 4 (vpravo). Krok 3: S pomoc´ı pravidla 1(b) vyznaˇc´ıme pole, jeˇz nemaj´ı v dosahu strom. Krok 4: V prvn´ım sloupci a posledn´ım ˇrádku se schoduje omezuj´ıc´ı ˇc´ıslo s poˇctem voln´ ych pol´ı. Um´ıst´ıme do nich tedy stan podle pravidla 2.

2

0

1

0

2

2

0

0

2

2

0

0

1

1

2

2

0

1

0

2

Obr´ azek 6: Vzorové ˇreˇsen´ı. Krok 5 (vlevo) a krok 6 (vpravo). Krok 5: Pouˇzijeme pravidlo 4. a propoj´ıme stany se stromy. ´ Krok 6: Uvaha 1(b). Oznaˇc´ıme pole bez volného stromu v dosahu.

2

2

0

0

2

2

0

0

1 2

0

1

0

2

1 2

0

1

0

2

Obr´ azek 7: Vzorové ˇreˇsen´ı. Krok 7 (vlevo) a krok 8 (vpravo). Krok 7: Na prvn´ım ˇr´ adku a v prostˇredn´ım sloupci dopln´ıme stan podle pravidla 2. Krok 8: Vˇsechny stromy maj´ı správnˇe pˇriˇrazen´ y stan. Nalezli jsme správné ˇreˇsen´ı.

8

4

Online simul´ ator

Pro v´ yzkum toho, jak´ ym zp˚ usobem lidé ˇreˇs´ı problémy a co je pro nˇe nároˇcné, je nezbytné z´ısk´ an´ı velkého mnoˇzstv´ı dat o postupu jejich ˇreˇsen´ı. D´ıky dostupnosti internetu i osobn´ıch poˇc´ıtaˇc˚ u a d´ıky obl´ıbenosti webov´ ych portál˚ u s hrami, je ide´ aln´ım ˇreˇsen´ım právˇe online simulátor. V´ yhod tohoto pˇr´ıstupu je hned nˇekolik. V prvn´ı ˇradˇe t´ım odpadá nutnost ˇreˇs´ıc´ıho ˇclovˇeka fyzicky sledovat pˇri hˇre a zaznamen´ avat, co dˇelá. V d˚ usledku toho je moˇzné testovat velké mnoˇzstv´ı lid´ı souˇcasnˇe. Také t´ım odpadá nebezpeˇc´ı zkreslen´ı v´ ysledku kv˚ uli trémˇe subjektu. Dalˇs´ı v´ yhodou je snadné z´ıskán´ı nov´ ych ˇreˇsitel˚ u napˇr´ıklad s vyuˇzit´ım ˇs´ıˇren´ı webov´ ych stránek po sociáln´ıch s´ıt´ıch. V neposledn´ı ˇradˇe je tento zp˚ usob pˇr´ıjemn´ y pro uˇzivatele a nab´ız´ı vysokou interaktivitu napˇr´ıklad v podobˇe okamˇzité odezvy na tah ˇci srovnán´ı v´ ysledk˚ u s ostatn´ımi hr´ aˇci.

4.1

Definice poˇ zadavk˚ u

Poˇzadavky na obˇe verze hry jsou prakticky stejné, proto bude následuj´ıc´ı text popisovat obˇe verze najednou a jen u ´daje, ve kter´ ych se liˇs´ı, budou konkrétnˇe jmenov´ any. Základn´ım poˇzadavkem je pˇrenést veˇskeré moˇznosti pap´ırové verze hry i do simul´ atoru. Jedn´ a se o moˇznost postavit stan a vyznaˇcit si pole, na nˇemˇz stan b´ yt nem˚ uˇze. D´ıky interaktivitˇe webov´ ych technologi´ı vˇsak nen´ı nutné z˚ ust´ avat jen u toho. Samozˇrejmost´ı je kromˇe moˇznosti stan postavit také moˇznost stan libovolnˇe-krát zbourat, nebo pˇresunout jinam. Stejnˇe tak znaˇcit a odznaˇcovat pole nen´ı nutné po jednom, ale je moˇzné znaˇcit v´ıce pol´ı tahem. Velmi uˇziteˇcn´ a se uk´ azala také moˇznost si spojovat stany se stromy, pokud jistˇe v´ıme, ˇze k sobˇe patˇr´ı. Od simul´ atoru oˇcek´ av´ ame, ˇze bude nejen pˇrenáˇset tahy uˇzivatele na hrac´ı plochu na monitoru, ale ˇze nab´ıdne také pˇr´ıvˇetivé grafické prostˇred´ı a zjednoduˇsen´ı pro hr´ aˇce. Chceme, aby simulátor hl´ıdal poˇcet postaven´ ych stan˚ u a v pˇr´ıpadˇe jeho pˇrekroˇcen´ı n´ as informoval. Stejnˇe tak pokud postav´ıme stan na zak´ azaném poli1 , nebo v kontaktu s jin´ ym stanem, simulátor to zjisti a adekv´ atnˇe na to zareaguje. Hra je navrˇzena tak, aby hráˇce pokud moˇzno nijak neomezovat. Pokud se tedy rozhodne postavit v´ıce stan˚ u neˇz je povoleno, nebo na zakázaném poli, nen´ı jeho tah zablokov´ an, ale je pouze graficky upozornˇen, ˇze tah nebyl v poˇr´ adku. V z´ avislosti na chybˇe, které se dopustil, jsou volena r˚ uzná upozornˇen´ı, pˇr´ıpadnˇe jejich kombinace. Stejnˇe tak spojován´ı stan˚ u a strom˚ u, znaˇcen´ı pol´ı a dalˇs´ı pom˚ ucky, které simulátor nab´ız´ı, nejsou nijak vyˇzadovány a pro spr´ avné ˇreˇsen´ı je rozhoduj´ıc´ı pouze rozm´ıstˇen´ı stan˚ u. 1

Pole, jeˇz nem´ a v dosahu ˇza ´dn´ y strom.

9

´ 4. ONLINE SIMULATOR

Posledn´ım, ale velmi podstatn´ ym poˇzadavkem na simulátor, je moˇznost jeho zapojen´ı do Tutor systému. Je nutné, aby dokázal správnˇe naˇc´ıtat uˇzivatelsk´ a data a odes´ılat data o postupu ˇreˇsen´ı. Tutor se stará o funkce zobrazen´ı n´ apovˇedy, ukonˇcen´ı hry a o restart. Z tohoto d˚ uvodu jiˇz nejsou stejné funkce v simul´ atoru nutné.

4.2

Volba programovac´ıho prostˇ red´ı

Vzhledem k v´ yˇse zm´ınˇen´ ym poˇzadavk˚ um na simulátor je nutné zvolit vhodné programovac´ı prostˇred´ı s dostateˇcnou funkcionalitou. Pro funkce simulátoru a zapojen´ı do webov´ ych str´ anek Tutor systému je v hodn´ y Java Aplet nebo 2 Javascript . Java Aplet[7][11] je speci´ aln´ı typ programu Java, kter´ y lze stáhnout z internetu a spustit v prohl´ıˇzeˇci. Aplet je obvykle vloˇzen do webové str´ anky a spouˇst´ı se v kontextu prohl´ıˇzeˇce. Aplet mus´ı b´ yt podtˇr´ıdou tˇr´ıdy java.applet.Applet, která poskytuje standardn´ı rozhran´ı mezi apletem a prostˇred´ım prohl´ıˇzeˇce. V´ yhodou Apletu je nezávislost na operaˇcn´ım systému a webovém prohl´ıˇzeˇci. Bˇeˇz´ı na stranˇe klienta, ˇc´ımˇz odlehˇcuje práci serveru. Nev´ yhodou je nutn´ a podpora Javy. Nˇekteré prohl´ıˇzeˇce a operaˇcn´ı systémy ji standardnˇe nepodporuj´ı a je nutno instalovat plug-in. Pˇri spouˇstˇen´ı Apletu se souˇcasnˇe mus´ı také spustit JVM3 , coˇz celé naˇc´ıt´ an´ı nepˇr´ıjemnˇe zpomaluje. Javascript[10] je multiplatformn´ı, objektovˇe orientovan´ y skriptovac´ı jazyk. Jazyk vytvoˇrila koncem minulého stolet´ı spoleˇcnost Netscape, kv˚ uli zvyˇsuj´ıc´ım se poˇzadavk˚ um na interaktivitu World Wide Webu. T´ım také v´ yvoj´ aˇr˚ um internetov´ ych stránek bylo poskytnuto v´ıce moˇznost´ı pro tvorbu a str´ anky tak mohly z´ıskat na dynamice. V´ yhodou skriptu je, podobnˇe jako u Apletu, spouˇstˇen´ı na stranˇe uˇzivatele4 a t´ım menˇs´ı zátˇeˇz pro server. Javascript nedovoluje zapisovat a naˇc´ıtat u ´daje ze soubor˚ u, ˇc´ımˇz pˇrisp´ıvá ke zv´ yˇsené bezpeˇcnosti pro n´ avˇstˇevn´ıka stránky. Dalˇs´ı v´ yhodou je, ˇze vyuˇz´ıvá jen HTML prvky a pˇrisp´ıvá tak k celistvˇejˇs´ımu vzhledu stránky. 2

I pˇres podobn´ y n´ azev nem´ a s jazykem Java nic spoleˇcného. Jazyk se p˚ uvodnˇe naz´ yval LiveScript, ale kv˚ uli boomu okolo jazyka Java byl z marketingov´ ych d˚ uvodu pˇrejmenov´ an na Javascript. 3 Java Virtual Machine - sada poˇc´ıtaˇcov´ ych program˚ u a datov´ ych struktur, kter´ a vyuˇz´ıv´ a modul virtu´ aln´ıho stroje ke spuˇstˇen´ı dalˇs´ıch poˇc´ıtaˇcov´ ych program˚ u a skript˚ u vytvoˇren´ ych v jazyce Java. 4 Javascript je moˇzné pouˇz´ıt i na stranˇe serveru. Poprvé byl implementov´ an Javascript na stranˇe serveru firmou Netscape v roce 1996 pod n´ azvem LiveWire. 10


Nev´ yhodou Javascriptu je nejednotnost verz´ı a nˇekter´ ych funkc´ı v prohl´ıˇzeˇc´ıch. Dalˇs´ı nev´ yhodou je nemoˇznost pracovat se soubory5 , to ale v naˇsem pˇr´ıpadˇe nepotˇrebujeme. Java Aplet je siln´ y n´ astroj, jenˇz je vhodn´ y pokud potˇrebujeme napˇr´ıklad sloˇzitˇejˇs´ı animace nebo prvky, které nenab´ız´ı HTML. V naˇsem pˇr´ıpadˇe si vˇsak vystaˇc´ıme s funkcionalitou HTML kódu s Javascriptem. T´ım doc´ıl´ıme rychlejˇs´ıho spouˇstˇen´ı hry i pˇr´ıjemnˇejˇs´ıho vzhledu stránky. Dalˇs´ım d˚ uvodem pro Javascript je systém, kter´ ym Tutor otev´ırá nápovˇedu pro hru. Okno s n´ apovˇedou se vysunuje taktéˇz Javascriptov´ ym pˇr´ıkazem, ˇc´ımˇz dojde ke zmˇenˇe na str´ ance a k opˇetovnému naˇcten´ı Apletu. Pˇri tomto naˇcten´ı se hra restartuje a hr´ aˇc pˇrijde o vˇsechny dosavadn´ı tahy, coˇz je uˇzivatelsky velmi nepˇr´ıjemné. Po zhodnocen´ı v´ yˇse zm´ınˇen´ ych pro a proti se nejvhodnˇejˇs´ı jev´ı pouˇzit´ı Javascriptu.

4.3

Implementace

Hra je implementov´ ana pomoc´ı HTML kódu a pro jednotlivé interaktivn´ı funkce je vyuˇz´ıv´ an Javascript. O spuˇstˇen´ı hry v Tutoru se stará PHP skript, jenˇz také poskytne nutné informace o zadán´ı, ˇreˇsen´ı i o uˇzivateli a vygeneruje HTML. V´ıce o tomto skriptu v kapitole 4.4.2 Komunikace se systémem. Simul´ ator lze tedy rozdˇelit na dvˇe ˇcásti. HTML ˇcást s Javascriptov´ ymi prvky a extern´ı Javascript obstar´ avaj´ıc´ı vˇsechny funkce simulátoru. 4.3.1

HTML

Hra Stany a stromy se hraje na ˇctvercovém poli. Proto byla pro zobrazen´ı hry zvolena tabulka. V Tutoru jsou zavedena zadán´ı o velikosti maximálnˇe 12 × 12 pol´ı, proto m´ a tabulka rozsah pouze 14 × 14. Kaˇzdé pol´ıˇcko tabulky má pˇriˇrazeno unik´ atn´ı ID a jeden styl, implicitnˇe se jedná o styl empty. Dále jsou pro kaˇzdé pole nastaveny události, na které toto pole reaguje. 0000 0001 0002 0003 0100 0101 0102 0103 0200 0201 0202 0203 0300 0301 0302 0303

Obr´ azek 8: Ukázka pˇriˇrazován´ı ID v tabulce. 5 To je nev´ yhodou pro v´ yvoj´ aˇre. Naopak pro n´ avˇstˇevn´ıka je to v´ yhodou, jak jiˇz bylo zm´ınˇeno.

11


Jednotliv´ a ID jsou volena tak, aby odpov´ıdala souˇradnic´ım daného pole v tabulce (viz. obr. 8/str. 11). V levém horn´ım rohu tabulky je prvn´ı pole . V opaˇcném rohu tabulky, na 13. ˇrádku, ve 13. sloupci je pak pole posledn´ı . D´ıky tomuto typu znaˇcen´ı nen´ı problém pˇristupovat k sousedn´ım pol´ım. Napˇr´ıklad nad polem s ID 0808 je pole 0708, vpravo je pole 0809, atd. Tohoto je s v´ yhodou vyuˇzito v extern´ım Javascriptu, kde ˇcasto pro vykonán´ı operace v poli potˇrebujeme znát styl sousedn´ıch pol´ı. Pro jednotliv´ a pol´ıˇcka je definováno celkem 24 r˚ uzn´ ych styl˚ u. Jedná se o 21 obr´ azkov´ ych styl˚ u, 2 textové a 1 prázdn´ y (empty). Vˇsechny styly, s v´ yjimkou stylu empty, nastavuj´ı ˇs´ıˇrku i v´ yˇsku pole na 39 px. Styl empty je nastaven na 0 px, v prohl´ıˇzeˇci se pole s t´ımto stylem tedy v˚ ubec nezobraz´ı. Obr´ azkové styly maj´ı nastaveno jedno z 21 r˚ uzn´ ych pozad´ı (viz. obr. 9/str. 12). Textové styly jsou vyuˇzity pouze ve verzi s ˇc´ısly. Jedná se o styly black a red, mˇen´ıc´ı barvu omezuj´ıc´ıch ˇc´ısel.

Obr´ azek 9: Obrázkové styly simulátoru. Jednotlivé styly jsou naˇc´ıt´ any vˇetˇsinou pˇri kliknut´ı do pole. Je tˇreba, aby nov´ y obr´ azek naskoˇcil okamˇzitˇe a nevznikla nepˇr´ıjemná prodleva mezi kliknut´ım a jeho naˇcten´ım. I pˇresto, ˇze vˇsechny obrázky jsou uloˇzeny v 32 bitové barevné hloubce v bezztr´ atovém formátu PNG6 , je pr˚ umˇerná velikost jednoho asi 500 bajt˚ u. I s na dneˇsn´ı dobu podpr˚ umˇern´ ym internetem by nemˇelo doch´ azet k v´ yraznému zpoˇzdˇen´ı mezi kliknut´ım a naˇcten´ım obrázku. Pˇresto je vˇsak veˇsker´ a grafika radˇeji naˇctena pˇredem. V HTML kódu je zaˇrazen Javascript, kter´ y naˇcte vˇsechny obrázky do pamˇeti prohl´ıˇzeˇce jeˇstˇe pˇredt´ım, neˇz je simul´ ator spuˇstˇen. Skript pro naˇcten´ı vypadá následovnˇe: <script> promenna = new Image(); promenna.src = "obrazek.png"; Posledn´ı souˇc´ ast´ı kaˇzdého pole je definice Javascriptov´ ych událost´ı7 , na 6 7

Portable Network Graphics Pod pojmem ud´ alost se rozum´ı zmˇena nˇekteré ze stavov´ ych veliˇcin. K ud´ alosti doch´ az´ı 12


které pole reaguje. V simul´ atoru jsou vyuˇzity události onMouseDown (reakce na stisk tlaˇc´ıtka myˇsi), onMouseUp (reakce na uvolnˇen´ı tlaˇc´ıtka myˇsi) a onMouseOver (reakce na pˇrejet´ı ukazatelem nad urˇcitou oblast´ı). K posledn´ımu poli s ID 1313 je pˇriˇrazena událost onLoad (reakce na dokonˇcen´ı naˇc´ıt´ an´ı). Ud´ alost onLoad nastane ve chv´ıli, kdy je celá stránka naˇctená (vˇcetnˇe vˇsech obr´ azk˚ u). V této chv´ıli je celá hra pˇripravena a zadán´ı m˚ uˇze b´ yt zobrazeno hr´ aˇci. 4.3.2

Javascript

Prvn´ı funkc´ı Javascriptu, která se spouˇst´ı, je funkce nactiHru(), jeˇz je vyvol´ ana ud´ alost´ı onLoad (viz. obr. 10/str. 13). Pomoc´ı volán´ı dalˇs´ıch funkc´ı vyˇcist´ı hern´ı pole, zobraz´ı zadán´ı, naˇcte omezuj´ıc´ı ˇc´ısla (jen ve verzi s ˇc´ısly) a pˇrevede ˇreˇsen´ı z textové podoby do pole. Zadán´ı, ˇreˇsen´ı, velikost hern´ıho plánu i omezuj´ıc´ı ˇc´ısla jsou z Tutoru pˇredány ve formˇe ˇretˇezce do promˇenné game. Naˇc´ıt´ an´ı hry prob´ıh´ a s pomoc´ı této promˇenné. Vˇsechny reakce simul´ atoru jsou prov´ adˇeny zmˇenou stylu jednotliv´ ych pol´ı. Vˇsechny ud´ alosti, jimi vyvolávané funkce a následná komunikace mezi funkcemi, jsou zobrazeny na následuj´ıc´ım schématu: onMouseUp onMouseDown onMouseOver onLoad spoj()

klikni()

spojTo()

zn() postavStan()

kontrolaStanu()

checkSolution()

oznac()

nactiHru()

makeFree() nactiReseni() nactiCisla() checkNumbers()

kontrolaSousedů()

ˇ ˇ Obr´ azek 10: Cervenˇ e: Javascriptové události. Cernˇ e: Funkce. V zeleném rámeˇcku: Funkce, které odes´ılaj´ı data o provedeném tahu na interface Tutora. Zb´ yvaj´ıc´ı tˇri ud´ alosti jsou vˇsechny vyvolány myˇs´ı. Jedná se o události, napˇr´ıklad pˇri kliknut´ı myˇs´ı, stisku kl´ avesy, naˇcten´ı str´ anky, odesl´ an´ı formul´ aˇre apod. V Javascriptu lze ud´ alosti sledovat, a pokud k nˇejaké dojde, je moˇzné situaci vyuˇz´ıt a provést skript[10].

13


které zp˚ usobuje uˇzivatel pˇri hran´ı hry. Pro pochopen´ı tˇechto událost´ı je nutné nejprve definovat ovl´ adán´ı hry. Ovl´ ad´ an´ı: I pˇresto, ˇze hra nab´ız´ı v´ıce moˇznost´ı, bylo snahou umoˇznit veˇskeré ovládán´ı pouze pomoc´ı dvou tlaˇc´ıtek myˇsi. Pro postaven´ı i zboˇren´ı stanu slouˇz´ı levé tlaˇc´ıtko. Oznaˇcen´ı i odznaˇcen´ı pol´ı, kde stan b´ yt nem˚ uˇze, se provád´ı kliknut´ım pravého tlaˇc´ıtka, popˇr´ıpadˇe jeho tahem pˇres v´ıce pol´ı. Dalˇs´ı funkc´ı hry je moˇznost si stromy a stany spojovat a t´ım zv´ yraznit, ˇze patˇr´ı k sobˇe. Tato funkce je prov´ adˇena taktéˇz tahem myˇsi z jednoho pole na druhé (ze stromu na stan). Lze ji provést jak prav´ ym8 , tak lev´ ym tlaˇc´ıtkem myˇsi. Rozpojen´ı lze provést smaz´ an´ım stanu nebo pˇrepojen´ım stanu k jinému stromu. Postaven´ı/zboˇ ren´ı stanu a znaˇ cen´ı pr´ azdn´ ych pol´ı: Je vyvol´ ano ud´ alost´ı onMouseDown, která spouˇst´ı funkci klikni(). Funkce pˇred´ av´ a ID pole, do nˇehoˇz uˇzivatel klikl a tlaˇc´ıtko, kter´ ym bylo kliknut´ı provedeno. Podle toho, které tlaˇc´ıtko bylo stisknuto, je pˇredána ˇc´ıselná hodnota. Bohuˇzel ne vˇsechny prohl´ıˇzeˇce pouˇz´ıvaj´ı stejné znaˇcen´ı. Znaˇcen´ı v nejpouˇz´ıvanˇejˇs´ıch9 prohl´ıˇzeˇc´ıch je uvedeno v tabulce:

Prohl´ıˇzeˇc Firefox Chrom IE Opera Safari

navigator.appName N´ azev Netscape Netscape Microsoft Internet Explorer Opera Netscape

Levé 0 0 1 0 0

event.button Prostˇredn´ı Pravé 1 2 1 2 4 2 2 1 2

Tabulka 1: Jména prohl´ıˇzeˇc˚ u a hodnoty tlaˇc´ıtek v Javascriptu. V simul´ atoru je vyuˇzito pouze levé a pravé tlaˇc´ıtko, jedin´ y rozd´ıl tedy nast´ av´ a v pˇr´ıpadˇe Internet Exploreru. Funkce klikni() podle stisknuté klávesy rozhodne, jestli dále pˇredá ID funkci zn(), kter´ a oznaˇc´ı zelenˇe pole, nebo funkci postavStan(), která postav´ı nebo zboˇr´ı stan, v z´ avislosti na obsahu pole. Pokud je v poli strom nebo oznaˇcené pole, funkce neprovede nic. Pokud je v poli stan, je smazán, pokud je pole pr´ azdné, je stan naopak postaven. V obou pˇr´ıpadech funkce kontroluje okoln´ı pozice. Funkce mus´ı rozhodnout, jestli postavit klasick´ y modr´ y stan, nebo nˇekter´ y z ˇcerven´ ych (viz. obr. 9/str. 12), indikuj´ıc´ıch, ˇze 8

V prohl´ıˇzeˇci Opera slouˇz´ı tah pravého tlaˇc´ıtka pro vyvol´ an´ı menu a pˇrechod na pˇredchoz´ı str´ anku, proto je v Opeˇre moˇzno spojovat stany pouze tlaˇc´ıtkem lev´ ym. 9 K 1.5.2011: Firefox (42,9%), Chrome (25,6%), Internet Explorer (24,3%), Safari (4,1%) a Opera (2,6%). Statistiky podle serveru w3schools.com.

14


na daném ID by stan st´ at nemˇel. Znaˇ cen´ı pr´ azdn´ ych pol´ı tahem: Pro znaˇcen´ı pol´ı tahem je vyuˇzita událost onMouseOver a následná funkce oznac(). Ud´ alost je vyvol´ ana pˇri kaˇzdém pˇrejet´ı kurzoru myˇsi nad polem. K oznaˇcen´ı pole vˇsak dojde jen pokud je souˇcasnˇe s touto událost´ı zmáˇcknuto i pravé tlaˇc´ıtko myˇsi. Tuto podm´ınku hl´ıdá funkce klikni(). Spojov´ an´ı strom˚ u a stan˚ u: Pˇri ud´ alosti onMouseDown je zaznamenáno ID. Událost onMouseUp vyvolá funkci spoj() a ta porovn´ a obˇe ID. Pokud se jedná o dvˇe sousedn´ı pole, kde v jednom z nich je stan a ve druhém strom, provede jejich spojen´ı pomoc´ı funkce spojTo().

4.4

Zapojen´ı simul´ atoru do Tutor syst´ emu

Posledn´ım krokem, nutn´ ym aby simulátor fungoval, je jeho zapojen´ı do Tutora. Nejdˇr´ıve si ale ˇrekneme nˇekolik informac´ı o tomto systému i o skupinˇe Proso, pod kterou je vyv´ıjen. 4.4.1

PROSO Tutor

Proso10 je v´ yzkumn´ a skupina p˚ usob´ıc´ı na Fakultˇe informatiky Masarykovy univerzity. Jej´ı v´ yzkum spad´ a do oblasti kognitivn´ıch vˇed – propojen´ı poˇc´ıtaˇcov´ ych vˇed, psychologie, umˇelé inteligence a vzdˇeláván´ı. Otázky, na které se snaˇz´ı odpovˇedˇet, jsou napˇr´ıklad: • D´ıky ˇcemu je problém pro ˇclovˇeka nároˇcn´ y? • Které problémy jsou n´ aroˇcné pro ˇclovˇeka a které naopak pro poˇc´ıtaˇc? • Jak si mohou poˇc´ıtaˇce a lidé navzájem pomoci pˇri ˇreˇsen´ı obt´ıˇzn´ ych u ´kol˚ u? • M˚ uˇzeme pouˇz´ıt doporuˇcuj´ıc´ı algoritmy ke zlepˇsen´ı vzdˇeláván´ı? V souˇcasné dobˇe se pak jedn´ a hlavnˇe o dvˇe témata: Obt´ıˇ znost probl´ emu. Co stoj´ı za rozd´ılnou nároˇcnost´ı? Snahou pˇri v´ yzkumu je navrhnout model lidského chován´ı pˇri ˇreˇsen´ı u ´loh a d´ıky nˇemu pˇredpov´ıdat obt´ıˇznost. Proso Tutor. Vyuˇzit´ı e-komerce11 a doporuˇcuj´ıc´ıch algoritm˚ u ve vzdˇeláv´ an´ı a ve zlepˇsov´ an´ı schopnosti ˇreˇsit zadan´ y problém. Tato doporuˇcen´ı 10 11

Problem Solving, neboli ˇreˇsen´ı problém˚ u. V souˇcasnosti je e-komerce vyuˇz´ıv´ ana hlavnˇe k doporuˇcov´ an´ı zboˇz´ı na internetu. 15


nejsou postavena na pˇredem nastaven´ ych kriteri´ıch, ale sp´ıˇse na kolektivn´ım chov´ an´ı vˇsech uˇzivatel˚ u. 4.4.2

Komunikace se syst´ emem

HTML k´ od hry je generov´ an dynamicky pomoc´ı PHP. Stejn´ ym zp˚ usobem jsou pˇred´ av´ ana i data nutn´ a pro spuˇstˇen´ı simulátoru. V okamˇziku naˇc´ıtán´ı hry zpˇr´ıstupn´ı Tutor simul´ atoru vˇsechny globáln´ı promˇenné a simulátor si je naˇcte. Konkrétnˇe se jedn´ a o tyto globáln´ı promˇenné: $problem (id typu hry), $instance id (id levelu), $instance name (název levelu), $user id (id uˇzivatele), $instance plan (zadán´ı levelu), $session hash (syntaktick´ y cukr12 ), $session id (id hry + levelu + hráˇce). V simul´ atoru se o pˇred´ an´ı hodnot do Javascriptu stará následuj´ıc´ı PHP kód. Pˇred´ an´ı dat do simul´ atoru prob´ıhá tedy pouze jednou – pˇri jeho spuˇstˇen´ı. Simul´ ator zpˇet do tutora naopak pos´ılá data ihned po proveden´ı kaˇzdého tahu. Tahem se rozum´ı jak´ akoliv zmˇena na hrac´ı ploˇse. Pˇr´ı nalezen´ı správného ˇreˇsen´ı se kromˇe v´ıtˇezného tahu odes´ılá i informace o v´ yhˇre. Souˇc´ ast´ı informace o tahu je i kontroln´ı hash (syntaktick´ y cukr), id levelu a id hry. D´ ale se odes´ıl´ a poˇcet tah˚ u, respektive poˇrad´ı právˇe odehraného tahu. Posledn´ı souˇc´ ast´ı je kl´ıˇcové slovo move popˇr´ıpadˇe win, které udává zda odes´ıl´ ame informace o tahu ˇci o v´ yhˇre. V´ ysledn´ y ˇretˇezec v pˇr´ıpadˇe hry Stany a stromy vypad´ a n´ asledovnˇe: var query = "session_id="+id_game+ "&session_hash="+check_hash+ "&move_number="+pocetTahu+ "&move="+souradniceTahu; ˇ ezec je poté pˇred´ Retˇ an na interface Tutora. Interface je klasick´ y PHP script a k odesl´ an´ı dat se vyuˇz´ıvá funkce sendDataTointerface(query), jenˇz je implementov´ ana uˇz v Tutoru. Funkce vyuˇz´ıvá asynchronn´ı komunikace se serverem, kterou umoˇzn ˇuje framework MooTools. PHP skript poté zap´ıˇse data do datab´ aze. 12

32 znak˚ u pro kontrolu prohl´ıˇzeˇce 16

5

Gener´ ator zad´ an´ı a ˇ reˇ siˇ c

Simul´ ator si naˇc´ıt´ a zad´ an´ı hry z Tutora, souˇcást´ı této práce je tedy i vytvoˇren´ı zad´ an´ı a jejich vloˇzen´ı do databáze systému. Jako záruka toho, ˇze zad´ an´ı je opravdu ˇreˇsitelné, a pro urˇcen´ı vˇsech moˇzn´ ych ˇreˇsen´ı, je souˇcást´ı pr´ ace i automatick´ y ˇreˇsiˇc. Dále je nutné alespoˇ n pˇribliˇznˇe odhadnout obt´ıˇznost daného zad´ an´ı. K tomuto u ´ˇcelu je vyuˇzit simulátor lidského ˇreˇsen´ı pro Sudoku, upraven´ y pro ˇreˇsen´ı Strom˚ u a stan˚ u1 . Pˇred naprogramován´ım simul´ atoru a ˇreˇsiˇce je vhodné nejprve provést anal´ yzu hry a stanovit rozsah a vlastnosti zad´ an´ı, které budeme generovat.

5.1

Anal´ yza hry

Pro generov´ an´ı zad´ an´ı je nutné nastavit nˇekolik parametr˚ u. Jedná se o rozsah velikosti pole, poˇcet stan˚ u v poli a poˇcet ˇreˇsen´ı. C´ılem je zvolit takové parametry, aby hra nebyla pˇr´ıliˇs snadná ani neˇreˇsitelná a zároveˇ n aby dané parametry umoˇzn ˇovaly vytvoˇrit co nejvˇetˇs´ı mnoˇzstv´ı r˚ uzn´ ych zadán´ı a daly tak prostor pro jejich rozmanitost. Velikost pole byla zvolena tak, aby nebylo zadán´ı pˇr´ıliˇs snadné. Pro Stany s ˇc´ısly je dostaˇcuj´ıc´ı pole 6 × 6, pro Stany bez ˇc´ısel bylo jako minimáln´ı zvoleno pole o velikosti 8 × 8. Maximáln´ı velikost byla zvolena jako 12 × 12, z d˚ uvodu velikosti tohoto pole. Je ˇzádouc´ı, aby hern´ı plán mˇel jen takovou velikost, aby se veˇsel na obrazovku cel´ y najednou. Do Tutoru bylo vloˇzeno pro kaˇzdou verzi hry asi 60 zadán´ı. Pro následné anal´ yzy v´ ysledk˚ u je vhodné, aby byla kaˇzd´ a velikost pole zastoupena v´ıcekrát a nedoˇslo tak k pˇr´ıliˇsnému rozmˇelnˇen´ı statistik. Proto byly zvoleny jen konkrétn´ı velikosti pole. Pro verzi s ˇc´ısly to jsou 6 × 6, 8 × 8 a 10 × 10, pro verzi bez ˇc´ısel 8 × 8, 10 × 10 a 12 × 12. D´ ale bylo nutné zvolit poˇcet stan˚ u, kter´ y bude na kaˇzdém poli rozm´ıstˇen. Pokud je zvoleno stan˚ u m´ alo, lze vytvoˇrit jen málo kombinac´ı a zadán´ı jsou také velmi snadn´ a. Stejnˇe tak pokud je zvoleno stan˚ u moc, je moˇzné vytvoˇrit velké mnoˇzstv´ı r˚ uzn´ ych zad´ an´ı, ale jen velmi malé procento tˇechto zadán´ı má ˇreˇsen´ı. Poˇcet vˇsech zad´ an´ı pro verzi bez ˇc´ısel, které lze vytvoˇrit, se spoˇc´ıtá vzorcem pro kombinace bez opakován´ı: Ck (n) =

n k

!

=

n! k!(n − k)!

kde n je poˇcet pol´ı a k je poˇcet stan˚ u. Poˇcet vˇsech ˇreˇsiteln´ ych pol´ı byl zjiˇstˇen algoritmicky tak, ˇze byla vygenerov´ ana a vyˇreˇsena kompletnˇe vˇsechna zadán´ı pro danou velikost pole a poˇcet stan˚ u. Jelikoˇz se jedn´ a o v´ ypoˇcetnˇe nároˇcnou operaci2 a s velikost´ı pole roste 1 2

Tento simul´ ator nen´ı souˇca ´st´ı pr´ ace. V pr´ aci je pouze vyuˇzit. Uˇz pro pole 6 × 6 dostaneme pˇri dev´ıti stanech v´ıce neˇz 93 milion˚ u zad´ an´ı. 17

´ ´ Í A RE ˇ SI ˇC ˇ 5. GENERATOR ZADAN

i ˇcas potˇrebn´ y pro tento v´ ypoˇcet, bylo poˇc´ıtáno jen pro pole 4 × 4, 5 × 5 a 6 × 6 (viz. graf 1/str. 18). Velmi podobné v´ ysledky se vˇsak daj´ı oˇcekávat i u pol´ı vˇetˇs´ıch. 90000 80000 70000 60000 50000 40000 30000 20000 10000 0

14000000 10000000 Počet řešení

Počet řešení

12000000 8000000 6000000 4000000 2000000 0 3

4

5

6

7

5

8

6

7

8

9

Počet stanů

Počet stanů

Graf 1: Poˇcet vˇsech ˇreˇsiteln´ ych zadán´ı v závislosti na poˇctu stan˚ u, pro verzi bez ˇc´ısel. Pro pole 5 × 5 (vlevo) a 6 × 6 (vpravo). Z grafu 1 je vidˇet, ˇze nejv´ıce ˇreˇsiteln´ ych zadán´ı bez ˇc´ısel lze dostat, pokud stany zaplˇ nuj´ı 20-30% pol´ı. U této verze je dalˇs´ım podstatn´ ym ukazatelem rozsah poˇctu ˇreˇsen´ı3 a rozloˇzen´ı tˇechto ˇreˇsen´ı4 . Rozloˇzen´ı udává následuj´ıc´ı graf (Graf 2), rozsah n´ asleduj´ıc´ı tabulka (Tabulka 2): 14000

3 stany 4 stany 5 stanu 6 stanu 7 stanu

12000

Násobnost

10000 8000 6000 4000 2000 0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Počet řešení

Graf 2: Rozloˇzen´ı poˇctu ˇreˇsen´ı pro pole velikosti 5 × 5. Napˇr. pˇri pˇeti stanech (ˇzlut´ a) lze vygenerovat 3044 r˚ uzn´ ych zadán´ı o ˇsesti moˇzn´ ych ˇreˇsen´ıch. 3

Rozsah poˇctu ˇreˇsen´ı ud´ av´ a, jak´ y je maxim´ aln´ı poˇcet ˇreˇsen´ı, kter´ y m˚ uˇze zad´ an´ı s danou velikost´ı a poˇctem stan˚ u m´ıt. 4 Rozloˇzen´ı ukazuje, kolik r˚ uzn´ ych zad´ an´ı s dan´ ym poˇctem ˇreˇsen´ı lze vygenerovat.

18


Poˇcet stan˚ u 3 pole 5 × 5 31 pole 6 × 6 -

4 58 -

5 48 238

6 31 256

7 20 177

8 10 96

9 20

Tabulka 2: Rozsah poˇctu ˇreˇsen´ı v závislosti na poˇctu stan˚ u pro pole 5 × 5 a 6 × 6. Podle tˇechto u ´daj˚ u byl jako ideáln´ı poˇcet stan˚ u zvolen pro vˇsechny velikosti poˇcet pˇribliˇznˇe 20% vˇsech pol´ı. Pro verzi bez ˇc´ısel n´ as zaj´ımaj´ı pouze zadán´ı, jeˇz maj´ı právˇe jedno ˇreˇsen´ı. Nejv´ıce rozd´ıln´ ych zad´ an´ı lze taktéˇz vygenerovat, pokud stany zab´ıraj´ı asi 20% pol´ı. Poˇcet tˇechto zad´ an´ı je ˇrádovˇe vˇetˇs´ı neˇz poˇcet zadán´ı pro stejnˇe velké pole ve verzi bez ˇc´ısel. Poˇcet ˇreˇsiteln´ ych zadán´ı pro verzi s ˇc´ısly je zobrazen na n´ asleduj´ıc´ım grafu: 350000

100000000

300000 Počet zadání

200000 150000 100000 50000

Počet zadání

80000000

250000

60000000 40000000 20000000 0

0 3

4

5

6

7

8

Počet stanů

5

6

7

8

9

Počet stanů

Graf 3: Poˇcet vˇsech ˇreˇsiteln´ ych zadán´ı v závislosti na poˇctu stan˚ u, pro verzi s ˇc´ısly. Pro pole 5 × 5 (vlevo) a 6 × 6 (vpravo). Poˇcet vˇsech moˇzn´ ych zadán´ı lze vypoˇc´ıtat pouze pro zadán´ı bez ˇc´ısel. Poˇcet ˇreˇsiteln´ ych zad´ an´ı pro obˇe verze je tˇreba zjiˇst’ovat algoritmicky. Sloˇzitost v´ ypoˇctu je vˇsak silnˇe z´ avislá na velikosti pole, proto pro vˇetˇs´ı pole nemus´ı b´ yt tento v´ ypoˇcet v praxi provediteln´ y5 . Lze vˇsak na základˇe zjiˇstˇen´ ych u ´daj˚ u stanovit pˇribliˇzn´ y v´ ypoˇcet a t´ım poˇcet ˇreˇsen´ı pro vˇetˇs´ı pole odhadovat. Verze s ˇ c´ısly - zaj´ımav´ e vlastnosti: Ve verzi s ˇc´ısly m´ a drtiv´ a vˇetˇsina zadán´ı právˇe jedno ˇreˇsen´ı. Tato vlastnost je d´ ana omezuj´ıc´ımi ˇc´ısly, které tuto vlastnost zajiˇst’uj´ı. Ve velmi ojedinˇel´ ych pˇr´ıpadech vˇsak m˚ uˇze doj´ıt k situaci, kdy jsou stany a ˇc´ısla rozloˇzeny 5 V´ ypoˇcet je moˇzn´ y vˇzdy, avˇsak pro vˇetˇs´ı pole je ˇcasovˇe a pamˇet’ovˇe natolik n´ aroˇcn´ y, ˇze na souˇcasn´ ych poˇc´ıtaˇc´ıch ho nen´ı moˇzno provést.

19


tak, ˇze umoˇzn´ı i v´ıce ˇreˇsen´ı (viz. obr. 11/str. 20). Taková zadán´ı jsou v rámci v´ yzkumu neˇz´ adouc´ı a proto jsou vyˇrazena.

1

1

0

1

1

0

0

1

1 1

1

0

Obr´ azek 11: Zad´ an´ı s ˇc´ısly umoˇzn ˇuj´ıc´ı dvˇe r˚ uzná ˇreˇsen´ı. Jak bylo zm´ınˇeno, hra nab´ız´ı moˇznost spojovat stromy a stany, které k sobˇe patˇr´ı. Toto spojen´ı vˇsak nen´ı vyˇzadováno. Jedn´ım z d˚ uvod˚ u je i v´ yskyt zad´ an´ı, u kter´ ych je tento problém nerozhodnuteln´ y (viz. obr. 12/str. 20).

Obr´ azek 12: Zad´ an´ı hry, kde nen´ı moˇzné rozhodnout, kter´ y stan náleˇz´ı kterému stromu.

5.2

Koncept Flow

Jak jiˇz bylo zm´ınˇeno v u ´vodu, Tutor vyuˇz´ıvá prvk˚ u psychologie Flow. V pr´ aci, i v celém Tutor systému, je c´ılem z´ıskávat data od ˇreˇsitel˚ u. Je tedy d˚ uleˇzité nab´ıdnout problém odpov´ıdaj´ıc´ı nároˇcnosti tak aby neodradil, ale naopak pˇrimˇel k ˇreˇsen´ı i dalˇs´ıch zadán´ı. Jin´ ymi slovy je snahou u uˇzivatel˚ u systému navodit stav Flow. Toto je velmi d˚ uleˇzité i pˇresto, ˇze psychologie sama o sobˇe nen´ı souˇc´ ast´ı v´ yzkumu. Lidé v systému Tutor totiˇz ˇreˇs´ı hádanky pouze dobrovolnˇe, ve svém volném ˇcase a nejsou za poskytován´ı tˇechto dat ˇzádn´ ym zp˚ usobem placeni. Aby mohly b´ yt uˇzivatel˚ um poskytnuty zadán´ı odpov´ıdaj´ıc´ı nároˇcnosti, je tedy nutné umˇet vygenerovat velmi rozd´ılná zadán´ı. Je tedy nutné aby 20


gener´ ator dok´ azal vygenerovat zadán´ı jak r˚ uzné velikosti, tak i r˚ uzn´ ych vlastnost´ı ovlivˇ nuj´ıc´ıch obt´ıˇznost. P˚ uvod Flow S konceptem Flow se setk´ aváme nejen v modern´ı psychologii, ale m˚ uˇzeme jej nalézt i v historii a v nejr˚ uznˇejˇs´ıch kulturách. Prvky této psychologie nach´ az´ıme jiˇz v buddhismu ˇci józe. Avˇsak vˇedecky se t´ımto fenoménem v´ıce zab´ yval aˇz psycholog Mih´ aly Cs´ıkszentmihályi. Kolem roku 1975 pˇri jeho v´ yzkumu popisovali testovan´ı lidé pocit plynut´ı ˇcasu, odtud také pocház´ı název Flow psychology ( psychologie stavu plynut´ı“). ” Stav plynut´ı

Úroveň výzvy

Vysoká

Pˇri pr´ aci, uˇcen´ı se nebo i pˇri ˇreˇsen´ı logick´ ych u ´loh se snaˇz´ıme o dosaˇzen´ı ide´ aln´ıho stavu. Ten naléz´ ame ve chv´ıli, kdy naˇse schopnosti odpov´ıdaj´ı poˇzadavk˚ um na n´ as kladen´ ym v takovém rozsahu, ˇze jsou pro nás v´ yzvou, ale z´ aroveˇ n nejsou nepˇrekonatelné. V tomto stavu lidé ˇcasto projevuj´ı velké zaujet´ı ˇcinnost´ı a ztr´ ac´ı pojem o ub´ıhaj´ıc´ım ˇcase. Rozloˇzen´ı pocit˚ u ˇreˇsitel˚ u v z´ avislosti na obt´ıˇznosti ˇreˇsen´ı a schopnostech je patrné z grafu (viz. obr. 13/str. 21).

Stres

Vzrušení

Trápení

Kontrola

Nuda

Odpočinek

Nízká

Apatie

Stav plynutí (Flow)

Nízká

Úroveň dovednosti

Vysoká

Obr´ azek 13: Flow psychologie. Byla zdokumentov´ ana také silná korelace mezi stavem Flow a dobr´ ymi v´ ysledky pˇri vzdˇel´ av´ an´ı se a uˇcen´ı v nejr˚ uznˇejˇs´ıch oborech. Konkrétnˇe vˇedci zjistili, ˇze tento stav v´ yraznˇe prosp´ıvá ve v´ yuce (Cs´ıkszentmihályi, 1996), v uˇcen´ı (Cs´ıkszentmih´ alyi et al., 1993) i ve sportech (Jackson, Thomas, Marsh, Smethurst, 2002; Stein, Kimiecik, Daniels, Jackson, 1995)[12].

21


5.3

Pouˇ zit´ e n´ astroje

Pro implementaci automatického reˇsiˇce i generátoru náhodn´ ych zadán´ı byl vyuˇzit jazyk Java. Jako v´ yvojové prostˇred´ı bylo zvoleno prostˇred´ı NetBeans IDE. Java Jazyk Java je v dneˇsn´ı dobˇe jeden z nejpouˇz´ıvanˇejˇs´ıch programovac´ıch jazyk˚ u. Jedn´ a se o objektovˇe orientovan´ y jazyk tˇret´ı generace6 (3GL). Pˇredch˚ udcem Javy je jazyk C, respektive jeho objektová verze C++, která Javˇe vtiskla z´ akladn´ı podobu. Z konceptuáln´ıho hlediska dokázali návrháˇri Javy eliminovat z p˚ uvodn´ıho C++ spoustu chyb, a tak je v´ ysledn´ y jazyk mnohem ˇcistˇs´ı“ neˇz jeho pˇredch˚ udce[7]. Java je vyv´ıjena od roku 1991, ale prvn´ı ” verze byla vyd´ ana aˇz v roce 1995 pod jménem Java 1.0. Od kvˇetna 2007 je vyv´ıjena jako open source[13]. V´ yznamn´ y vliv na v´ ybˇer Javy mˇely také mé pˇredchoz´ı zkuˇsenosti s t´ımto nástrojem. V´ yhodou Javy je snadn´ a pˇrenositelnost. Nen´ı závislá na operaˇcn´ım systému ani na architektuˇre platformy. Má k dispozici rozsáhlou online dokumentaci. Vyuˇz´ıv´ a garbage collector pro odkl´ızen´ı nepouˇziteln´ ych objekt˚ u. K dispozici je v´ ybˇer z ˇrady kvalitn´ıch v´ yvojov´ ych prostˇred´ı. Podporuje psan´ı kvalitn´ı dokumentace (JavaDoc). Nev´ yhodou je zejména pomalé spouˇstˇen´ı aplikac´ı. Na rozd´ıl od C nebo C++ je nutné program kompilovat aˇz pˇred startem aplikace, coˇz spuˇstˇen´ı prodluˇzuje. Dalˇs´ı nev´ yhodou je vyˇsˇs´ı pamˇet’ová nároˇcnost u mal´ ych program˚ u. Obˇe nev´ yhody jsou vˇsak v dneˇsn´ı dobˇe kompenzovány rostouc´ım v´ ykonem koncov´ ych zaˇr´ızen´ı.

NetBeans IDE NetBeans je open source v´ yvojové prostˇred´ı, které umoˇzn ˇuje programátor˚ um ps´ at, pˇrekl´ adat, ladit a ˇs´ıˇrit programy. Projekt je vyv´ıjen v Javˇe a dˇel´ı se na dva hlavn´ı produkty: v´ yvojové prostˇred´ı NetBeans (NetBeans IDE) a v´ yvojov´ a platforma NetBeans (NetBeans Platform). Prostˇred´ı je prim´ arnˇe urˇceno pro jazyk Java, ale lze v nˇem vyv´ıjet i programy v C/C++, PHP nebo Ruby. Alternativou pro NetBeans m˚ uˇze b´ yt napˇr´ıklad prostˇred´ı Eclipse nebo IntelliJ IDEA.

6 Patˇr´ı sem také jazyky Pascal, C/C++, Basic, atd. Jazyky tˇret´ı generace se vyznaˇcuj´ı vˇetˇs´ı pˇr´ıvˇetivost´ı k program´ atorovi.

22


5.4

Gener´ ator zad´ an´ı

Jak jiˇz bylo zm´ınˇeno, zad´ an´ı nejsou vytváˇrena pˇr´ımo v simulátoru, ale jsou pˇripravov´ ana pˇredem. O pˇr´ıpravu se stará generátor náhodn´ ych zadán´ı. C´ılem tohoto programu je vygenerovat náhodná zadán´ı, která splˇ nuj´ı pˇredem definované poˇzadavky na velikost a poˇcet stan˚ u. Zadán´ı mus´ı m´ıt alespoˇ n jedno moˇzné ˇreˇsen´ı. Ve verzi s ˇc´ısly právˇe jedno moˇzné ˇreˇsen´ı. O provˇeˇren´ı ˇreˇsitelnosti se star´ a algoritmus schopn´ y zadán´ı vyˇreˇsit (viz. kapitola 5.5 Automatick´ y ˇreˇsiˇc/str. 24). Ke generov´ an´ı lze pˇristupovat v´ıce zp˚ usoby. V práci byly uvaˇzovány následuj´ıc´ı dva zp˚ usoby: Generov´ an´ı u ´ lohy pomoc´ı ˇ reˇ sen´ı Pˇri generov´ an´ı u ´lohy pomoc´ı ˇreˇsen´ı se postupuje tak, ˇze se nejprve um´ıst´ı do pole stany a k nim se teprve následnˇe um´ıst’uj´ı stromy. Ve verzi s ˇc´ısly se poté dopln´ı omezuj´ıc´ı ˇc´ısla podle rozloˇzen´ı stan˚ u. Stany se um´ıst’uj´ı do pole zcela n´ ahodnˇe. Pomoc´ı generátoru náhodn´ ych ˇc´ısel7 se vybere ˇc´ıslo z rozsahu 0–poˇcet pol´ı. Za pˇredpokladu, ˇze na tomto m´ıstˇe je volné pole a v dosahu nen´ı jin´ y stan, um´ıst´ı se nov´ y stan. Pokud pole podm´ınky nesplˇ nuje, je ˇc´ıslo zahozeno a vygenerováno nové. Takto se postupuje, dokud nejsou um´ıstˇeny vˇsechny stany. Poté jsou ke stan˚ um náhodnˇe rozm´ıstˇeny stromy, popˇr´ıpadˇe, podle verze hry, pˇridány omezuj´ıc´ı ˇc´ısla.

Obr´ azek 14: Pole 5 × 5, kde jiˇz nelze vygenerovat posledn´ı 5. stan. V´ yhodou tohoto postupu je pomˇernˇe velká rychlost generován´ı. Taktéˇz odpad´ a nutnost pole nejdˇr´ıve vyˇreˇsit. Je jisté, ˇze vygenerované zadán´ı je ˇreˇsitelné a z´ aroveˇ n staˇc´ı uloˇzit pozice vygenerovan´ ych stan˚ u, jeˇz tvoˇr´ı spr´ avné ˇreˇsen´ı. Nev´ yhodou je, ˇze rozm´ıstˇen´ı stan˚ u, které bylo uloˇzeno jako správné ˇreˇsen´ı, nemus´ı b´ yt jedin´ ym moˇzn´ ym ˇreˇsen´ım. Dalˇs´ı nev´ yhodou je nutnost po 7 V Javˇe je gener´ ator pseudon´ ahodn´ ych ˇc´ısel jiˇz implementov´ an. Pro generov´ an´ı je vyuˇzita metoda random z tˇr´ıdy Math.

23


kaˇzdém um´ıstˇen´ı nového stanu procházet celé pole a kontrolovat poˇcet voln´ ych pozic. Pokud by nebyla tato kontrola zahrnuta, mohl by se program zacyklit. Zacyklen´ı m˚ uˇze nastat ve chv´ıli, kdy jsou stany náhodnˇe um´ıstˇeny natolik nevhodnˇe, ˇze dalˇs´ı stany jiˇz nen´ı moˇzné um´ıstit (viz. obr. 14/str. 23). Generov´ an´ı u ´lohy pomoc´ı ˇreˇsen´ı je tedy vhodné tam, kde je tˇreba velmi rychle vygenerovat ˇreˇsitelné zadán´ı. Tento postup by byl zvolen v pˇr´ıpadˇe, ˇze by hra slouˇzila jen pro zábavu a zadán´ı by nebyla dána pˇredem, ale generov´ ana n´ ahodnˇe vˇzdy na poˇzádán´ı hráˇce. Generov´ an´ı u ´ lohy pomoc´ı zad´ an´ı Dalˇs´ım zp˚ usobem jak generovat u ´lohu je pomoc´ı zadán´ı. V tomto pˇr´ıpadˇe ’ nejsou rozm´ıst ov´ any stany, ale stromy. Tak jako v pˇredchoz´ım pˇr´ıpadˇe je vygenerov´ ano n´ ahodné ˇc´ıslo. Na pozici urˇcenou t´ımto ˇc´ıslem je um´ıstˇen strom. Jedin´ ym poˇzadavkem je, aby bylo pole volné. Takto vygenerované zadán´ı je poté pˇred´ ano automatickému ˇreˇsiˇci, kter´ y nalezne vˇsechna ˇreˇsen´ı a pˇr´ıpadnˇe rozhodne, ˇze u ´loha ˇreˇsen´ı nemá. Omezuj´ıc´ı ˇc´ısla jsou jako v pˇredchoz´ım pˇr´ıpadˇe stanovena aˇz podle rozm´ıstˇen´ı stan˚ u, tedy aˇz po vyˇreˇsen´ı u ´lohy. V´ yhodou je, ˇze pˇri tomto postupu je jednoznaˇcnˇe urˇcen poˇcet ˇreˇsen´ı. Taktéˇz jsou uloˇzena vˇsechna moˇzná ˇreˇsen´ı, ne jen jedno konkrétn´ı, jak tomu bylo v pˇredchoz´ım pˇr´ıpadˇe. Nev´ yhodou tohoto postupu je jeho pomalost. Velká ˇcást vygenerovan´ ych zad´ an´ı nem´ a ˇreˇsen´ı. Pˇredevˇs´ım zadán´ı pro vˇetˇs´ı pole, kde kaˇzdé vyˇreˇsen´ı trv´ a delˇs´ı ˇcas, se generován´ı velmi prodluˇzuje. Dalˇs´ı nev´ yhodou je nutnost programovat automatick´ y ˇreˇsiˇc, bez nˇehoˇz by tento postup nebylo moˇzné pouˇz´ıt. Pouˇzit´ı tohoto postupu je tedy vhodné v pˇr´ıpadˇe, kdy zadán´ı nen´ı potˇreba vygenerovat rychle, ale je nutné zaruˇcit jeho ˇreˇsitelnost a urˇcit vˇsechna moˇzn´ a ˇreˇsen´ı. Jde tedy o pˇr´ıpad vhodn´ y pro pouˇzit´ı pˇri generován´ı zadán´ı pˇredem, tak jak se generuj´ı v rámci systému Tutor.

5.5

Automatick´ yˇ reˇ siˇ c

V pˇr´ıpadˇe generov´ an´ı pomoc´ı zadán´ı je nutn´ y i automatick´ y ˇreˇsiˇc. Zp˚ usob˚ u jak automaticky ˇreˇsit Stany a stromy je v´ıce. Nˇekteré byly zbˇeˇznˇe naznaˇceny v kapitole 4.4 V´ yhern´ı strategie. Problém vˇetˇsiny algoritm˚ u pro hledán´ı ˇreˇsen´ı je ten, ˇze naleznou pouze jedno ˇreˇsen´ı. V r´ amci této práce je vˇsak tˇreba pouˇz´ıt ˇreˇsiˇc, kter´ y nalezne vˇsechna ˇreˇsen´ı. Z tohoto d˚ uvodu se jako nejjistˇejˇs´ı jev´ı vyuˇzit´ı algoritmu, kter´ y vyzkouˇs´ı vˇsechny kombinace. Pˇred popsán´ım tohoto postupu je tˇreba definovat pojem hern´ı prostor. 24


Hern´ı prostor je soubor pol´ı, na kter´ ych se odehrává hra. V nˇekter´ ych pˇr´ıpadech m˚ uˇze b´ yt velikost hern´ıho prostoru stejná jako velikost hrac´ıho pole8 , ale ve vˇetˇsinˇe pˇr´ıpad˚ u je hern´ı prostor menˇs´ı (viz. obr. 15/str. 25). Hern´ı prostor pˇredstavuje pole, která soused´ı s nˇekter´ ym stromem. Velikost hern´ıho prostoru pˇredstavuje poˇcet pol´ı, která tvoˇr´ı hern´ı prostor. 1 2 1 1 1 1 2

1

1

1

1

1

Obr´ azek 15: Hern´ı prostor pro pole 6 × 6. Velikost hern´ıho prostoru je 20. Algoritmus pro automatick´ y ˇreˇsiˇc hledá vˇsechna moˇzná ˇreˇsen´ı. Nepracuje ovˇsem s cel´ ym hern´ım polem, ale pouze s hern´ım prostorem. Nad t´ımto prostorem zkouˇs´ı algoritmus vˇsechny moˇzné kombinace jak rozm´ıstit stany.

Obr´ azek 16: Strom automatického ˇreˇsn´ı pro pole 3 × 3. Proch´ azen´ı funguje na principu DFS, neboli procházen´ı do hloubky. Algoritmus se vyd´ a po vˇetvi, která je nejv´ıce vlevo. V okamˇziku, kdy dojde 8 Velikost´ı hrac´ıho pole se rozum´ı poˇcet pol´ı, bez pol´ı se stromy. Napˇr´ıklad pro pole 6 × 6 je velikost hrac´ıho pole (6 · 6) − 7 = 29.

25


do c´ıle (nalezne ˇreˇsen´ı), nebo v okamˇziku, kdy uˇz nem˚ uˇze dále pokraˇcovat, se rekurzivnˇe vrac´ı a zkouˇs´ı prohledávat dalˇs´ı vˇetve (viz. obr. 16/str. 25). Spr´ avn´ a ˇreˇsen´ı si ukl´ ad´ a do pamˇeti. V pˇr´ıpadˇe stan˚ u s ˇc´ısly prob´ıhá ˇreˇsen´ı stejnˇe, pouze po dokonˇcen´ı prohledáván´ı jsou vˇsechna uloˇzená ˇreˇsen´ı jeˇstˇe porovn´ ana s omezuj´ıc´ımi ˇc´ısly.

5.6

Implementace

Program byl implementov´ an v jazyce Java. V práci bylo zvoleno pouze generov´ an´ı podle zad´ an´ı. Druh´ y zp˚ usob nen´ı v rámci této práce vhodn´ y, proto nebyl implementov´ an. C´ılem programu nen´ı hru pˇrehrávat, k tomuto u ´ˇcelu slouˇz´ı simulátor, ale pouze vygenerovat zad´ an´ı, provˇeˇrit jejich ˇreˇsitelnost a uloˇzit je v textovém form´ atu vhodném pro Tutor. Z tohoto d˚ uvodu nen´ı souˇcást´ı programu grafické rozhran´ı. Vygenerované zadán´ı je pouze vypsáno na standardn´ı v´ ystup a uloˇzeno do souboru. Cel´ y program se skl´ ad´ a ze dvou tˇr´ıd. Tˇr´ıdy Main, v n´ıˇz jsou metody pro generov´ an´ı a ˇreˇsen´ı, a tˇr´ıdy Game, jeˇz ukládá vygenerovanou sadu zadán´ı a vˇsechna jejich ˇreˇsen´ı. Ve tˇr´ıdˇe Main jsou z metody Main() volány metody zadaniSCisly(), zadaniBezCisel(int min, int max) a save(), jeˇz zapisuje vygenerovan´ a zad´ an´ı a ˇreˇsen´ı do souboru. Obˇe metody pro generován´ı postupuj´ı velmi podobnˇe. Cel´ y v´ ypoˇcet prob´ıh´ a nad dvourozmˇern´ ym polem, jehoˇz velikost je pˇred spuˇstˇen´ım ruˇcnˇe nastavena v glob´ aln´ı promˇenné velikostPole. Poˇcet zadán´ı, jenˇz se má vygenerovat, se nastav´ı v globáln´ı promˇenné pocetGenerovanychZadani. U metody zadaniBezCisel(int min, int max) je nutné nastavit vstupn´ı parametry. Promˇenn´ a min zastupuje minimáln´ı poˇcet ˇreˇsen´ı, jenˇz budou v´ ysledn´ a zad´ an´ı m´ıt. Promˇenná max urˇcuje maximáln´ı poˇcet ˇreˇsen´ı. U metody zadaniSCisly() je poˇzadováno vˇzdy jen jedno správné ˇreˇsen´ı, proto nen´ı tyto parametry nutné nastavovat. Uvnitˇr této metody naopak lze nastavovat konkrétn´ı poˇzadavky na velikost hern´ıho prostoru. Metoda po spuˇstˇen´ı opakovanˇe volá metody newGame() a solve(), dokud nen´ı vygenerov´ an pˇredem nastaven´ y poˇcet zadán´ı. Metoda newGame() generuje nov´ a n´ ahodn´ a zad´ an´ı, metoda solve() tato zadán´ı ˇreˇs´ı a ukládá do pamˇeti. Obˇe metody pracuj´ı tak, jak bylo teoreticky popsáno v kapitolách 6.3 Gener´ ator zad´ an´ı a 6.4 Automatick´ y ˇreˇsiˇc. Nakonec jsou zadán´ı zapsána do textového souboru pomoc´ı metody save() a vypsána na standardn´ı v´ ystup. Form´ at zad´ an´ı a ˇ reˇ sen´ı: Zad´ an´ı jsou vypisov´ ana i ukl´ adána v textovém formátu, se kter´ ym pracuje simul´ ator hry. Pro verzi bez ˇc´ısel vypadá formát následovnˇe (viz. obr. 17/str. 27): ˇ sen´ı1-...-souˇradniceReˇ ˇ sen´ıN-;hranaPole”. ”souˇradniceStrom˚ u:souˇradniceReˇ

26


0101 0202

Obr´ azek 17: Zad´ an´ı a dvˇe moˇzná ˇreˇsen´ı verze bez ˇc´ısel. Na obrazku vlevo naznaceny souradnice stromu. Zad´ an´ı pro hru na obr´ yzku 17 je uloˇzeno následovnˇe: ”01010202:01020302-02010203-;3” Pro verzi s ˇc´ısly (viz. obr. 18/str. 27), je form´ıt zadán´ı: ˇ sen´ı-;ˇc´ıslaVeSloupci:C´ ˇ ıslaNaR´ ˇ adku”souˇradniceStrom˚ u:souˇradniceReˇ ;hranaPole”.

1 0 2 0 2

0

0

1

Obr´ azek 18: Zadán´ı a ˇreˇsen´ı verze s ˇc´ısly. Zad´ an´ı pro hru na obr´ yzku 18 je uloˇzeno následovnˇe: ”010202010404:010103010304-;1020:2001-;4” V´ ybˇ er zad´ an´ı pro simul´ ator v Tutor syst´ emu: V´ ybˇer dat pro simul´ ator prob´ıhá rozd´ılnˇe pro obˇe verze hry. Pro verzi bez ˇc´ısel je rozhoduj´ıc´ı hlavnˇe poˇcet moˇzn´ ych ˇreˇsen´ı. Pro Tutor byla generována zad´ an´ı s poˇctem ˇreˇsen´ı 1, 2, 3, 5, 10, 20 a 50. Bylo vygenerováno asi 300 zad´ an´ı. Ta byla ruˇcnˇe vyˇreˇsena a na základˇe v´ ysledk˚ u vybrána zaj´ımavá zad´ an´ı pro Tutor. Ve verzi s ˇc´ısly byl pro v´ ybˇer pouˇzit simulátor lidského ˇreˇsen´ı, jenˇz byl p˚ uvodnˇe navrˇzen pro Sudoku. Bylo vygenerováno asi 1200 r˚ uzn´ ych zad´ an´ı. Ta byla pomoc´ı simulátoru strojovˇe vyˇreˇsena. Ke kaˇzdému zad´ an´ı simul´ ator vypsal vlastnosti tohoto zadn´ı9 . Na základˇe tˇechto vlastnost´ı a ruˇcn´ıho ˇreˇsen´ı byla vybrána zadán´ı do systému. 9 Poˇcet iterac´ı, pouˇzité techniky ˇreˇsen´ı a magic steps neboli kouzla“, kdy simul´ ator ” neumˇel pokraˇcovat d´ al a musel nahlédnout do ˇreˇsen´ı.

27

6

Anal´ yza v´ ysledk˚ u

Pro Tutor bylo vybr´ ano asi 70 zaj´ımav´ ych zadán´ı pro kaˇzdou verzi hry. Tato zad´ an´ı byla nahr´ ana do systému a byla zpˇr´ıstupnˇena pro ostatn´ı uˇzivatele. Systém zaznamen´ aval a ukl´ adal data o postupu ˇreˇsen´ı uˇzivatel˚ u. Souˇcást´ı této bakal´ aˇrské pr´ ace je i z´ akladn´ı anal´ yza sesb´ıran´ ych dat.

6.1

Velikost vzorku dat

Anal´ yzy byly provedeny na datech, která byla k dispozici v dobˇe odevzdán´ı pr´ ace1 . Verze s ˇc´ısly byla v provozu pˇribliˇznˇe 3 mˇes´ıce, verze bez ˇc´ısel 2 mˇes´ıce. Veˇsker´ a Tutorem zaznamenaná data pro anal´ yzu jsou k dispozici na pˇriloˇzeném CD (viz. pˇr´ıloha A/str. 41). Následuj´ıc´ı tabulka udává sumárn´ı statistiku dat, na nichˇz byly anal´ yzy provedeny.

Poˇcet zad´ an´ı Poˇcet hr´ aˇc˚ u Alespoˇ n5u ´loh vyˇreˇsilo Vˇsechny u ´lohy vyˇreˇsilo Celkem vyˇreˇseno u ´loh Celkem odehr´ ano tah˚ u Celkov´ y ˇcas hran´ı [h:m:s]

Stany s ˇc´ısly 69 87 60 11 2126 63410 49:58:22

Stany bez ˇc´ısel 72 147 94 6 2900 142773 65:31:42

Tabulka 3: Rozsah dat pouˇzit´ ych pro anal´ yzy.

Data pro Stany s ˇ c´ısly Pro verzi s ˇc´ısly byly anal´ yzy provádˇeny na následuj´ıc´ıch datech (viz. tabulka 4/str. 29-31). V tabulce jsou ke kaˇzdému zadán´ı uvedeny hodnoty z´ıskané z Tutoru: Med (ˇcas) – medi´ an ˇcasu vˇsech ˇreˇsitel˚ u, Avg (ˇcas) – pr˚ umˇern´ y ˇcas vˇsech ˇreˇsitel˚ u a Avg (tahy) – pr˚ umˇern´ y poˇcet tah˚ u nutn´ ych pro vyˇreˇsen´ı u ´lohy. D´ ale jsou uvedeny u ´daje zjiˇstˇené simulátorem lidského ˇreˇsen´ı: IT – poˇcet iterac´ı potˇrebn´ ych pro vyˇreˇsen´ı a MS – magic steps, neboli poˇcet zaseknut´ı, kdy simul´ ator neumˇel pokraˇcovat a musel nahlédnout do v´ ysledk˚ u. V posledn´ıch dvou sloupc´ıch jsou uvedeny vlastnosti kaˇzdého zadán´ı. Jedná se o HP – velikost hern´ıho prostoru a HP-0 – velikost hern´ıho prostoru bez nul2 . N´ azev kaˇzdé u ´lohy zaˇc´ıná ˇc´ıslem 6, 8 nebo 10, ˇc´ımˇz znaˇc´ı, ˇze se jedná o pole 6 × 6, 8 × 8 nebo 10 × 10.

1

Data byla staˇzena ze serveru a analyzov´ ana 17.5.2011. Pole, jenˇz jsou na ˇr´ adku ˇci ve sloupci omezeném nulou, se nepoˇc´ıtaj´ı i pˇresto, ˇze maj´ı v dosahu strom. 2

28

´ ´ ˚ 6. ANALYZA VYSLEDK U ´ Uloha 6b 6f 6h 6i 6d 6s 6g 6j 6a 6c 6l 6p 8r 6m 6r 6o 6q 6n 8k 8d 8i 8o 6t 6e 6e 8e 8f 8n 8j 8v 8a 8u

Med(ˇcas) 0:19 0:22 0:22 0:25 0:27 0:27 0:28 0:30 0:31 0:31 0:31 0:31 0:35 0:35 0:35 0:36 0:37 0:42 0:44 0:47 0:47 0:47 0:47 0:49 0:49 0:51 0:53 1:01 1:02 1:04 1:09 1:09

Avg(ˇcas) 0:21 0:26 0:34 0:33 0:32 0:33 0:35 0:36 0:37 0:40 0:40 0:37 0:39 0:48 0:46 0:39 0:46 0:51 0:49 0:54 0:51 0:52 0:52 1:00 1:00 56 1:13 1:06 1:14 1:09 1:59 1:21

Avg(tahy) 10 11 13 13 15 13 16 15 14 17 15 16 19 19 15 13 20 18 18 24 25 25 21 19 19 27 30 25 28 25 46 34

MS 0 0 1 0 0 0 0 0 0 0 3 0 0 1 1 0 2 1 2 0 0 1 1 1 1 2 0 0 2 1 2 2

IT 6 14 16 5 11 11 15 14 10 11 14 12 4 17 8 17 13 9 24 9 21 10 11 10 10 21 22 16 20 25 22 18

HP 17 13 18 20 16 18 18 18 15 19 19 18 30 20 18 19 16 17 27 28 32 27 17 18 18 31 30 27 30 28 31 31

HP-0 8 10 16 17 10 15 16 15 12 16 17 12 14 16 18 17 16 14 27 15 23 19 17 18 18 23 29 22 24 28 28 31

Tabulka 4 - ˇcást 1: Data pro verzi s ˇc´ısly.

29

´ ´ ˚ 6. ANALYZA VYSLEDK U ´ Uloha 8l 6k 8w 10w 10b 8h 8p 10q 8s 10g 8c 10u 10k 8t 8g 10f 10y 10d 10t 8b 10i 10n 10e 10s 10h 8m 8q 10a 10c 10o 10x 10l

Med(ˇcas) 1:13 1:13 1:13 1:17 1:20 1:29 1:29 1:33 1:34 1:40 1:42 1:42 1:48 1:51 1:53 1:48 2:03 2:04 2:04 2:07 2:07 2:07 2:10 2:10 2:16 2:17 2:29 2:34 2:40 2:47 2:49 3:01

Avg(ˇcas) 1:19 1:22 1:26 1:36 1:41 2:05 1:40 2:12 2:46 2:24 2:09 1:57 1:45 2:33 2:45 1:59 2:19 2:04 2:21 2:30 2:23 2:19 2:20 2:37 2:26 2:32 2:39 2:26 2:56 2:45 3:12 3:40

Avg(tahy) 31 33 37 50 48 49 34 43 42 55 40 51 43 51 60 41 51 42 51 54 53 50 52 50 42 42 50 55 66 57 54 69

MS 2 2 0 0 0 2 0 0 1 0 1 0 0 3 2 0 1 0 0 1 5 5 2 3 1 3 1 4 1 1 3 5

IT 25 11 21 10 10 21 10 28 20 28 21 24 16 21 20 30 20 16 31 22 37 32 28 42 21 21 15 29 32 32 37 36

HP 19 20 29 48 46 30 29 46 37 40 37 49 47 32 31 51 48 46 50 37 51 47 49 54 47 31 37 51 52 52 53 54

HP-0 17 20 22 29 32 28 26 46 37 45 37 43 38 32 26 45 45 36 42 37 41 41 49 48 44 28 37 51 38 52 53 54

Tabulka 4 - ˇcást 2: Data pro verzi s ˇc´ısly.

30

´ ´ ˚ 6. ANALYZA VYSLEDK U ´ Uloha 10p 10r 10v 10j 10m

Med(ˇcas) 3:04 3:06 3:25 3:30 5:16

Avg(ˇcas) 4:43 4:45 4:33 5:32 6:09

Avg(tahy) 116 59 82 75 86

MS 4 1 2 3 2

IT 36 22 35 25 34

HP 51 56 52 56 56

HP-0 41 56 38 56 56

Tabulka 4 - ˇcást 3: Data pro verzi s ˇc´ısly. Data pro Stany bez ˇ c´ısel Pro verzi bez ˇc´ısel byly anal´ yzy provádˇeny na datech uveden´ ych v tabulce 5 na stran´ ach 31-33. Jedn´ a se opˇet o hodnoty z´ıskané z Tutora: Med (ˇcas), Avg (ˇcas) a Avg (tahy). D´ ale je uveden Hern´ı prostor, respektive jeho velikost a Poˇcet ˇreˇsen´ı. N´ azvy u ´loh zaˇc´ınaj´ı ˇc´ısly 8, 10 nebo 12 podle toho, zda se jedn´ a o pole velikosti 8 × 8, 10 × 10 nebo 12 × 12. ´ Uloha 81c 85b 81a 81b 82c 85a 8b5 8c5 82a 82b 85c 8b1 8d1 8b3 8c3 8e1 102b 8a5 105a 101c 102d 105b

Med(ˇcas) 0:22 0:23 0:24 0:24 0:24 0:24 0:25 0:25 0:25 0:25 0:26 0:28 0:28 0:28 0:33 0:34 0:42 0:46 0:46 0:48 0:50 0:50

Avg(ˇcas) 0:30 0:34 0:29 0:36 0:35 0:38 0:36 0:37 0:36 0:30 0:34 0:36 0:57 0:40 0:47 0:49 1:17 1:10 1:17 1:09 1:23 1:21

Avg(tahy) 20 21 22 23 26 23 23 22 24 20 24 26 26 30 30 31 50 43 48 42 49 50

Hern´ı prostor 28 29 30 30 29 30 26 28 28 25 25 28 26 28 30 25 45 29 46 48 46 45

Poˇcet ˇreˇsen´ı 10 50 10 10 20 50 5 5 20 20 20 1 1 3 3 1 20 5 50 10 20 50

Tabulka 5 - ˇcást 1: Data pro verzi bez ˇc´ısel.

31

´ ´ ˚ 6. ANALYZA VYSLEDK U ´ Uloha 8a3 10a1 10e1 10b3 105c 8c1 10a3 10c5 122d 10a5 10d5 105d 125c 101b 8a1 125a 122c 101d 102a 12a5 102c 122b 10b5 125b 12c5 10c1 12e1 12c3 121c 12a2 121d 121b

Med(ˇcas) 0:54 0:54 0:54 0:56 0:57 0:58 1:00 1:02 1:02 1:06 1:07 1:07 1:07 1:09 1:10 1:11 1:14 1:20 1:20 1:24 1:26 1:27 1:29 1:30 1:32 1:39 1:39 1:39 1:39 1:48 1:49 1:51

Avg(ˇcas) 1:07 1:10 1:16 1:04 1:22 1:05 1:20 1:14 1:17 1:38 1:50 1:20 1:27 2:00 1:13 1:32 1:25 1:48 2:23 1:52 1:38 1:59 1:38 1:43 2:33 2:20 2:22 1:55 2:22 2:39 2:11 2:09

Avg(tahy) 39 51 49 43 51 43 51 47 59 66 62 50 57 71 52 62 54 60 68 73 66 82 63 73 73 91 90 75 80 92 89 78

Hern´ı prostor 26 44 46 49 45 28 47 44 67 47 47 48 64 48 30 68 63 46 47 66 53 69 46 67 70 46 67 64 69 66 72 70

Poˇcet ˇreˇsen´ı 3 1 1 3 50 1 3 5 20 5 5 50 50 10 1 50 20 10 20 5 20 20 5 50 5 1 1 3 10 2 10 10


32

´ ´ ˚ 6. ANALYZA VYSLEDK U ´ Uloha 12d5 125d 10c3 121a 12b1 10d1 10d3 12c1 12a3 101a 12b2 10b1 12b3 122a 12a1 12c2 12b5 12d1

Med(ˇcas) 1:53 1:59 2:05 2:06 2:09 2:10 2:12 2:25 2:32 2:44 2:48 3:05 3:15 3:53 4:13 5:06 7:18 10:09

Avg(ˇcas) 2:22 3:02 2:09 2:24 3:15 2:37 2:33 3:39 2:41 4:04 3:52 3:24 4:09 5:49 4:30 8:46 7:36 13:31

Avg(tahy) 98 115 83 98 108 100 83 129 119 96 109 122 137 171 159 244 221 396

Hern´ı prostor 71 70 48 69 69 49 48 70 68 50 67 50 69 74 71 73 68 68

Poˇcet ˇreˇsen´ı 5 50 3 10 10 1 3 1 3 10 2 1 3 20 1 2 5 1


6.2

Rozsah obt´ıˇ znosti

Z tabulek 4 a 5 (v obou jsou zadán´ı seˇrazena dle mediánu ˇcasu nutného na vyˇreˇsen´ı) je patrné, ˇze r˚ uzné velikosti zadán´ı se navzájem prol´ınaj´ı. Obt´ıˇznost zad´ an´ı tedy nen´ı ovlivnˇena pouze jeho velikost´ı. Následuj´ıc´ı grafy (viz. graf 4/str. 33 a graf 5/str. 34) ukazuj´ı prol´ınán´ı ˇcas˚ u (mediánu) na ˇreˇsen´ı i rozsah ˇcasu mezi nejlehˇc´ım a nejtˇeˇzˇs´ım zadán´ım. Velikost pole 6x6 8x8 10x10 Čas (s) 0

60

120

180

240

300

360

Graf 4: Verze s ˇc´ısly.

33

´ ´ ˚ 6. ANALYZA VYSLEDK U

Velikost pole 8x8 10x10 12X12 Čas (s) 60

0

120

180

240

300

360

420

480

540

600

Graf 5: Verze bez ˇc´ısel. Z graf˚ u 4 a 5 je vidˇet, ˇze jsou velké rozd´ıly mezi ˇcasem na vyˇreˇsen´ı i v r´ amci jedné velikosti zad´ an´ı. S rostouc´ı velikost´ı zadán´ı je tento rozd´ıl stále vˇetˇs´ı. Ve verzi s ˇc´ısly byla zadán´ı velikosti maximálnˇe 10 × 10. Pˇrestoˇze vˇsechna takto velk´ a zad´ an´ı maj´ı stejn´ y poˇcet pol´ı i strom˚ u a stan˚ u, jsou mezi dobami ˇreˇsen´ı pro r˚ uzn´ a zadán´ı velké rozd´ıly (viz. obr. 19/str. 34). 3

3

2

2

1

2

2

1

1

2

1

2

3

1

2

2

1

3

4 4

1

0

3

0

5

0

4

0

3

2 2

3

1

2

2

2

1

3

1

3

´ ´ Obr´ azek 19: (vlevo) Uloha 10w s mediánem ˇreˇsen´ı 77s. (vpravo) Uloha 10m s medi´ anem ˇreˇsen´ı 316s. Obˇe zad´ an´ı maj´ı na prvn´ı pohled velmi podobné vlastnosti. Pˇri d˚ ukladnˇejˇs´ım rozboru se vˇsak z´ asadnˇe liˇs´ı. Napˇr´ıklad poˇcet iterac´ı pro vyˇreˇsen´ı zad´ an´ı vlevo je 10, kdeˇzto pro zadán´ı vpravo 34. V´ yraznˇe se také liˇs´ı ve velikosti hern´ıho prostoru bez nul. Pro zadán´ı 10w je velikost 29, zat´ımco pro zad´ an´ı 10m je velikost 56. Pro verzi bez ˇc´ısel byla maximáln´ı velikost pole 12 × 12. Rozd´ıly mezi ˇcasy ˇreˇsen´ı pro zad´ an´ı jsou jeˇstˇe vˇetˇs´ı neˇz u verze s ˇc´ısly, kde byla maximáln´ı velikost 10 × 10. Pˇr´ıklad lehkého a tˇeˇzkého zadán´ı je uveden na následuj´ıc´ım obr´ azku (viz. obr. 20/str. 35). Základn´ı vlastnosti obou zadán´ı, jako je poˇcet strom˚ u a stan˚ u a velikost pole, jsou pro obˇe hry stejné. Pˇresto vˇsak medián ˇcasu na vyˇreˇsen´ı je u obt´ıˇznˇejˇs´ıho zadán´ı témˇeˇr 10ti násobn´ y oproti zadán´ı 34


snadnému. Velk´ y rozd´ıl je i v poˇctu tah˚ u. Zat´ımco na vyˇreˇsen´ı snadnˇejˇs´ıho zad´ an´ı staˇcilo hr´ aˇc˚ um v pr˚ umˇeru 59 tah˚ u, na obt´ıˇznˇejˇs´ı zadán´ı jich potˇrebovali v pr˚ umˇeru 396.

´ ´ Obr´ azek 20: (vlevo) Uloha 122d s mediánem ˇreˇsen´ı 62s. (vpravo) Uloha 12d1 s medi´ anem ˇreˇsen´ı 609s. I pˇri detailnˇejˇs´ım rozboru obou zadán´ı nejsou patrné velké rozd´ıly. Velikost hern´ıho prostoru pro zadán´ı vlevo je 67, pro zadán´ı vpravo 68. Jedin´ ym rozd´ılem je poˇcet ˇreˇsen´ı. Zad´ an´ı vlevo má 20 moˇzn´ ych ˇreˇsen´ı, zadán´ı vpravo pouze jedno. Avˇsak pokud zvol´ıme napˇr´ıklad zadán´ı 12e1 a 122a, dostaneme pˇresnˇe opaˇcn´ y v´ ysledek. Zad´ an´ı 12e1 má pouze jedno ˇreˇsen´ı a medián ˇcasu 99s. Zad´ an´ı 122a m´ a 20 ˇreˇsen´ı a medián ˇcasu 233s.

6.3

Detailn´ı anal´ yzy

Pˇri porovn´ av´ an´ı dvou konkrétn´ıch zadán´ı je velmi tˇeˇzké urˇcit, co ve skuteˇcnosti ovlivˇ nuje obt´ıˇznost. Lépe se dá odhadovat vliv dané vlastnosti na obt´ıˇznost, pokud se pod´ıv´ ame na vˇsechna zadán´ı souˇcasnˇe. Pro tento u ´ˇcel se dá dobˇre vyuˇz´ıt v´ ypoˇcet korelace ukazuj´ıc´ı vzájemnou závislost mezi hodnotami uˇzivatelsk´ ych ˇcas˚ u a tah˚ u a mezi vlastnostmi zadán´ı. Pro verzi s ˇ c´ısly

Med (ˇcas) Avg (ˇcas) Avg (tahy)

HP 0,86 0,81 0,84

HP-0 0,88 0,84 0,82

Iterace 0,73 0,69 0,73

Magic steps 0,48 0,48 0,50

Velikost 0,78 0,73 0,80

Tabulka 6: Vz´ ajemné korelace mezi daty ve verzi s ˇc´ısly. HP - hern´ı prostor; HP-0 - hern´ı prostor bez nulov´ ych ˇrádk˚ u a sloupc˚ u. 35


Ve verzi s ˇc´ısly jsou dosaˇzeny pomˇernˇe vysoké korelace pro vˇsechny vlastnosti (viz. tabulka 6/str. 35). Vysoká korelace je vˇsak dosaˇzena i pro velikost pole. Je tedy zˇrejmé, ˇze velikost pole silnˇe ovlivˇ nuje obt´ıˇznost a je tedy vhodnˇejˇs´ı spoˇc´ıtat korelace pro kaˇzdou velikost pole zvláˇst’. Korelace nez´ avislé na velikosti zad´ an´ı udávaj´ı následuj´ıc´ı tabulky:


HP 0,32 0,39 0,35

HP-0 0,62 0,70 0,58

Iterace -0,03 0,01 0,04

Magic steps 0,51 0,58 0,54

Tabulka 7: Vz´ ajemné korelace mezi daty ve verzi s ˇc´ısly pro pole 6 × 6.


HP 0,54 0,60 0,53

HP-0 0,69 0,74 0,63

Iterace 0,22 0,27 0,28

Magic steps 0,38 0,42 0,41

Tabulka 8: Vz´ ajemné korelace mezi daty ve verzi s ˇc´ısly pro pole 8 × 8.


HP 0,73 0,70 0,46

HP-0 0,61 0,58 0,21

Iterace 0,47 0,40 0,42

Magic steps 0,40 0,37 0,43

Tabulka 9: Vz´ ajemné korelace mezi daty ve verzi s ˇc´ısly pro pole 10 × 10. Z tabulek 7, 8 a 9 je vidˇet, ˇze korelace jsou niˇzˇs´ı, neˇz v pˇr´ıpadˇe tabulky 6. T´ım se potvrzuje pˇredpoklad, ˇze hodnoty v tabulce 6 jsou silnˇe ovlivnˇeny velikost´ı zad´ an´ı. Jedinou v´ yjimkou jsou hodnoty korelac´ı pro magic steps. Tato vlastnost nen´ı velikost´ı zadán´ı pˇr´ıliˇs ovlivnˇena. Korelace mezi ˇcasy ˇreˇsitel˚ u a hern´ım prostorem se zvˇetˇsuj´ı s rostouc´ı velikost´ı pole. Stejnou tendenci má i korelace mezi ˇcasy a poˇctem iterac´ı. Vz´ ajemn´ a z´ avislost mezi hern´ım prostorem bez nulov´ ych ˇrádk˚ u a sloupc˚ u a mezi ˇcasy je pak pomˇernˇe konstantn´ı pro vˇsechny velikosti pole. Korelace v jednotliv´ ych sloupc´ıch jsou vˇetˇsinou velmi podobné. To se oˇcek´ avalo, jelikoˇz vˇsechny tˇri u ´daje (Med (ˇcas), Avg (ˇcas) a Avg (tahy)) demonstruj´ı obt´ıˇznost hry pro stejné hráˇce. Jedinou v´ yjimkou je korelace mezi poˇctem tah˚ u a obˇema hern´ımi prostory u pole 10 × 10. Hlavnˇe závislost mezi pr˚ umˇern´ ym poˇctem tah˚ u a mezi HP-0 je pˇrekvapivˇe velmi malá.

36


Pro verzi bez ˇ c´ısel V´ ypoˇcty pro verzi bez ˇc´ısel byly také provedeny nejdˇr´ıve pro vˇsechny velikosti spoleˇcnˇe. V´ ysledky jsou uvedeny v následuj´ıc´ı tabulce (viz. tabulka 10/str. 37). V této verzi hry bylo poˇc´ıtáno také s poˇctem ˇreˇsen´ı. Pˇredpokladem bylo, ˇze ˇc´ım menˇs´ı je poˇcet moˇzn´ ych ˇreˇsen´ı, t´ım je zadán´ı obt´ıˇznˇejˇs´ı. Na rozd´ıl od ostatn´ıch v´ ysledk˚ u jsou tedy v pˇr´ıpadˇe korelac´ı s poˇctem ˇreˇsen´ı oˇcek´ av´ any z´ aporné hodnoty.


Hern´ı prostor 0,57 0,58 0,64

Poˇcet ˇreˇsen´ı Velikost pole -0,24 0,57 -0,22 0,57 -0,22 0,64

Tabulka 10: Vz´ ajemné korelace mezi daty ve verzi bez ˇc´ısel. I v této verzi hry je patrné, ˇze obt´ıˇznost je závislá na velikosti zadán´ı. Avˇsak ne tak silnˇe, jako v pˇr´ıpadˇe verze s ˇc´ısly. V´ ypoˇcty pro kaˇzdou velikost ’ pole zvl´ aˇst jsou shrnuty v n´ asleduj´ıc´ı tabulce (viz. tabulka 11/str. 37).


Pole 8 × 8 HP Poˇc. ˇreˇs. 0,03 -0,41 -0,06 -0,45 0,10 -0,44

Pole 10 × 10 HP Poˇc. ˇreˇs. 0,56 -0,38 0,50 -0,30 0,50 -0,39

Pole 12 × 12 HP Poˇc. ˇreˇs. 0,26 -0,35 0,33 -0,34 0,34 -0,34

Tabulka 11: Vz´ ajemné korelace mezi daty ve verzi bez ˇc´ısel. V´ ypoˇcty korelac´ı zvl´ aˇst pro pole velikosti 8 × 8, 10 × 10 a 12 × 12. V této verzi hry ani jedna ze zkouman´ ych vlastnost´ı v´ yraznˇe nepˇresahuje korelaci 0,5. Na rozd´ıl od verze s ˇc´ısly, kde byly nejlepˇs´ı v´ ysledky dosaˇzeny pro hern´ı prostory, v této verzi jsou korelace s hern´ım prostorem pomˇernˇe malé. V pˇr´ıpadˇe pole 8 × 8 pak ˇcasy ani tahy s touto vlastnost´ı nekoreluj´ı v˚ ubec. Byly oˇcek´ av´ any vysoké korelace mezi ˇcasy ˇreˇsitel˚ u a poˇctem moˇzn´ ych ˇreˇsen´ı, jak je ale patrné z tabulky 11, korelace jsou v tomto pˇr´ıpadˇe pomˇernˇe malé.

37

´ ER ˇ 7. ZAV

7

Z´ avˇ er

C´ılem pr´ ace bylo vytvoˇrit simulátor, generátor zadán´ı a automatick´ y ˇreˇsiˇc pro obˇe verze logické hry Stany a stromy. Generátor i ˇreˇsiˇc byl implementov´ an v jazyce Java v rámci jednoho programu. Pomoc´ı tohoto programu byla vygenerov´ ana a vyˇreˇsena vˇsechna zadán´ı obou verz´ı hry. Ve spolupr´ aci se simul´ atorem lidského ˇreˇsen´ı, vyvinutého p˚ uvodnˇe pro Sudoku, byla vybr´ ana zaj´ımav´ a zad´ an´ı a nahrána do systému Tutor. Simulátory byly implementov´ any v jazyce Javascript a zapojeny do Tutoru, kde sb´ıraly data a postupu ˇreˇsen´ı uˇzivatel. Na sesb´ıran´ ych datech byly provedeny základn´ı anal´ yzy a v´ ypoˇcty korelac´ı mezi vlastnostmi zadán´ı a ˇcasy ˇreˇsitel˚ u. Simul´ atory byly u ´spˇeˇsnˇe nasazeny a bˇehem provozu sesb´ıraly znaˇcné mnoˇzstv´ı dat. Byly zaznamenány velké rozd´ıly v dobˇe nutné na vyˇreˇsen´ı jednotliv´ ych zad´ an´ı. To svˇedˇc´ı o schopnosti generátoru vytvoˇrit zadán´ı s rozd´ılnou obt´ıˇznost´ı i s rozd´ıln´ ymi vlastnostmi. V anal´ yz´ ach byly zjiˇstˇeny zaj´ımavé korelace. Dle oˇcekáván´ı byla potvrzena z´ avislost obt´ıˇznost´ı zad´ an´ı na velikosti pole. Naopak pˇrekvapen´ım byla pomˇernˇe mal´ a korelace mezi obt´ıˇznost´ı zadán´ı a poˇctem ˇreˇsen´ı. Zaj´ımav´ ym v´ ysledkem je vysok´ a korelace mezi ˇcasy ˇreˇsen´ı a v této práci definovan´ ym hern´ım prostorem ve verzi s ˇc´ısly. Na sesb´ıran´ ych datech budou provedeny rozsáhlejˇs´ı anal´ yzy, zkoumaj´ıc´ı napˇr´ıklad stavov´ y prostor hry. Data také obsahuj´ı pˇresné ˇcasy tah˚ u vˇsech uˇzivatel. Jejich postupy tedy mohou b´ yt rekonstruovány a dále zkoumány.

38

Reference [1] Babinˇc´ ak, P.: Analýza chov´ an´ı lid´ı pˇri ˇreˇsen´ı Nurikabe. Brno 2010. Dokument dostupn´ y na URL . (Adresa platná k 9. 5. 2011.) [2] Bouda, O.: Sbˇer z´ aznam˚ u postup˚ u ˇreˇsen´ı logických u ´loh. Brno 2010. Dokument dostupn´ y na URL . (Adresa platná k 9. 5. 2011.) [3] Csikszentmihalyi, M.: O ˇstˇest´ı a smyslu ˇzivota: M˚ uˇzeme ovl´ adat své proˇzitky a ovlivˇ novat jejich kvalitu? Jak dos´ ahnout ˇst’astného ˇzivota bez ohledu na vnˇejˇs´ı okolnosti. Praha 1996. [4] Havrlant, L.: Zkr´ acené HTML z´ apisy. Dokument dostupn´ y na URL . (Adresa platn´ a k 9. 5. 2011.) [5] Champeon, S.: JavaScript: How Did We Get Here? O’Reilly Web Devcenter 2001. Dokument dostupn´ y na URL . (Adresa platná k 9. 5. 2011.) [6] Pel´ anek, R.: O lidech, poˇc´ıtaˇc´ıch a logických u ´loh´ ach. Brno 2010. Dokument dostupn´ y na URL . (Adresa platná k 9. 5. 2011.) [7] Pitner, T.: Java - zaˇc´ın´ ame programovat. Podrobný pr˚ uvodce zaˇc´ınaj´ıc´ıho uˇzivatele. Praha 2002. [8] Rudov´ a, H.: Programov´ an´ı s omezuj´ıc´ımi podm´ınkami (Studijn´ı materi´ aly pˇredmˇetu PA163) Dokument dostupn´ y na URL (Adresa platná k 9. 5. 2011.) ˇ [9] Sabatov´ a, Z.: Gener´ ator logické u ´lohy. Brno 2009. Dokument dostupn´ y na URL . (Adresa platn´ a k 9. 5. 2011.) ˇ [10] Skult´ ery, R.: Javascript. Programujeme internetové aplikace. Brno 2004. [11] Zakhour, S. a kol.: Java 6. Výukový kurz. Brno 2007.

39

[12] Wikipedie: Flow (psychology). Dokument dostupn´ y na URL . (Adresa platn´ a k 9. 5. 2011.) [13] Wikipedie: Java (programming language). Dokument dostupn´ y na URL . (Adresa platn´ a k 9. 5. 2011.)

40

A

Pˇ r´ıloha

Na CD, pˇriloˇzeném k této práci, jsou uloˇzeny veˇskeré materiály, které byly v r´ amci této pr´ ace vypracov´ any nebo z´ıskány. Obsah CD je organizován do adres´ aˇr˚ u dle n´ asleduj´ıc´ı tabulky: Adres´ aˇr Text Simulator Generator Tutor Analyzy

A.1

Obsah tato pr´ ace v elektronické podobˇe zdrojové k´ ody a data k simulátor˚ um zdrojové k´ ody generátoru zadán´ı a ˇreˇsiˇce data zaznamenaná systémem Tutor o postupu uˇzivatel data ve formátu pouˇzitém pro anal´ yzy

Adres´ aˇ r Simulator

V adres´ aˇri Simulator jsou uloˇzeny simulátory pro obˇe verze hry. Je zde jak soubor simulator.php, kter´ ym se spouˇst´ı hra v rámci Tutor systému, tak soubor simulator.html, kter´ y umoˇzn ˇuje spustit hru i v PC, bez napojen´ı k Tutoru. Vˇsechny zdrojové kódy jsou podrobnˇe komentované.

A.2

Adres´ aˇ r Generator

V adres´ aˇri Generator jsou uloˇzeny zdrojové kódy generátoru zadán´ı a automatického ˇreˇsiˇce. Program je spustiteln´ y jako NetBeans projekt. Zdrojov´ y kód je podrobnˇe komentov´ an.

A.3

Adres´ aˇ r Tutor

Adres´ aˇr Tutor obsahuje soubory .txt staˇzené z webu Tutor systému. Soubory obsahuj´ı logy uˇzivatel, postupy pˇri ˇreˇsen´ı i korelaˇcn´ı data.

A.4

Adres´ aˇ r Analyzy

V adres´ aˇri Analyzy jsou data z adresáˇre Tutor pˇrevedeny do pˇrehlednˇejˇs´ıho tabulkového form´ atu.

41

MASARYKOVA UNIVERZITA FAKULTA INFORMATIKY. Online simulátor logické hádanky Tents puzzle. Martin Vardan

Recommend Documents