====== Týmová úloha: Maze Keeper ====== V rámci týmové úlohy, která je obsahem posledních 2 cvičení RPH, je Vaším úkolem naprogramovat rozhodování pro agenta ztraceného v bludišti a generátor bludišť které má vytvářet co nejzáludnější bludiště pro cizí agenty. Odevzdání týmové úlohy není povinné, ale můžete za ni získat až **9 bodů**, viz **Hodnocení úlohy**. Na úloze budete pracovat týmově, v každém týmu mohou být **maximálně 2 studenti**, kteří spolu na úloze mohou bezmezně spolupracovat. ====== Úkol ====== Vaším úkolem je vytvořit dvě doplňující se součásti: - Inteligence pro hledání cíle (kopec zlata) v neznámém bludišti - Generátor bludišť pro skrývání cíle (kopce zlata) v bludišti Hodnocení bude na základě toho, v kolika krocích dokáže váš agent v neznámém cizím bludišti najít svůj cíl a v kolika krocích najdou cizí agenti cíl ve vašem bludišti. ===== Agent a bludiště ===== Agent se pohybuje v bludišti, což je čtvercová mřížka. Pohyb v bludišti se řídí následujícími pravidly: {{ :courses:b4b33rph:cviceni:rph-maze-keeper-maze_example.png?400|}} * Agent má k dispozici čtyři akce pohybu ve čtyřech směrech, na sever (''NORTH''), jih (''SOUTH''), východ (''EAST'' ) a západ (''WEST''). * Objekty v bludišti jsou startovní pozice (''START''), překážka (''OBSTACLE''), zlato (''GOLD'') a volné místo (''EMPTY''). * Pokud agent použije akci posunu na políčko na kterém je překážka, zůstane stát na místě. To samé platí pro pokus o přesun na souřadnici mimo bludiště. * Bludiště je matice MxN, první index reprezentuje řádek (souřadnice r), druhý index sloupec (souřadnice c). Sloupce a řádky jsou indexovány od nuly. * Simulace končí přesunem agenta na políčko se zlatem nebo po ''step_limit'' krocích (krok je každé volání akce, i takové při kterém se agent nepohne). * Startovní pozice agenta a pozice zlata je určená bludištěm. Agent v každém kroku zná svou pozici i pozici zlata. * Agent v každém kroku "vidí" (''vision''), zná svou vzdálenost k překážce nebo k okraji bludiště v každém směru (N, S, E, W). Cílem agenta je dostat se ze své počáteční pozice na známou pozici zlata v co nejmenším počtu kroků. Tvurce bludište se snaží vytvořit bludiště ve kterém bude agent hledat zlato co nejdéle. Hodnoceni budete na základě toho, jak dlouho bude trvat vašemu agentovi najít zlato v cizím bludišti a jak dlouho bude cizím agentům trvat najít zlato ve vašem bludišti. ==== Hodnocení ==== Hodnocení bude na základě automatické evaluace proti benchmark řešení (až 5 bodů) a počtu bodů získaných ve dvou turnajích (až 4 body). Pro turnaje bude zvoleno několik velikostí bludiště (ne nutně čtvercová bludiště). - V prvním turnaji bude měřítkem počet kroků které váš agent potřebovat pro vyřešení všech cizích bludišťích. Čím méně, tím lepší bude pořadí agenta. - V druhém turnaji bude měřítkem úspěšnosti kolik celkem stráví cizí agenti kroků ve vašich bludištích. Čím více, tím lepší bude pořadí tvůrce bludiště. Pokud agent v bludišti nenajde zlato, bude to bráno jako že v bludišti strávil maximální možný počet kroků. Pokud vaše bludiště bude infeasible (nebude tam cesta), bude to bráno jako že v něm cizí agenti strávili hledáním zlata 0 kroků. Turnaj bude vyhodnocen po deadline úlohy. ==== Agent (Agent) ==== Vaším úkolem je vytvořit agenta v tříde ''Agent'' v souboru ''agent.py'' s následující specifikací ^ metoda ^ vstupní parametry ^ výstupní parametry ^ vysvětlení ^ | ''__init__'' | ''maze_size'', ''step_limit'', ''gold_position'', ''agent_position'' | |''maze_size'' je velikost bludiště zadaná jako 2-tuple, MxN kde M je počet řádků a N je počet sloupců. ''step_limit'' je počet kroků po kterém bude hledání v bludišti ukončeno, bez ohledu na to, zda agent zlato nalezl či nikoliv. ''gold_position'' je pozice zlata v bludišti jako 2-tuple (r,c) a ''agent_position'' je počáteční pozice agenta v bludišti jako 2-tuple (r,c).| | ''action'' | ''state'' | ''action'' | ''state'' je aktuální stav prostředí. Je to instance třídy ''State'' která má 2 parametry: ''position'' a ''vision'' (viz níže). Metoda vrací akci, kterou chce agent v daném stavu vykonat, jednu ze stringů '''NORTH', 'SOUTH', 'WEST', 'EAST''', též klíče ve slovníku ''ACTIONS'' v modulu ''maze_keeper.py'' | Stav předávaný agentovi je instance třídy ''State''. Instance třídy ''State'' má 4 parametry: - ''position'' je aktuální pozice agenta uložená jako 2-tuple (r,c), např. na obrázku je to ''(12,3)'' - ''vision'' je slovník, pod klíčem světového směru obsahuje počet políček k nejbližší zdi překážce (Obstacle) nebo okraji bludiště. Na obrázku by to například bylo ''{'NORTH': 6, 'SOUTH': 1, 'WEST': 0, 'EAST': 6}'' Pokud se agent pokusí posunout směrem do překážky nebo mimo bludiště, zůstane na místě. Simulace končí po přesunu agenta na zlato (Gold). Agent si smí (a je to doporučno) držet historii stavů a z ní budovat znalost bludiště. ==== Tvůrce bludiště (Maze generator) ==== Vaším úkolem je vytvořit tvůrce bludiště v třídě ''MazeGenerator'' v souboru ''maze_generator.py'' s následující specifikací: ^ metoda ^ vstupní parametry ^ výstupní parametry ^ vysvětlení ^ | ''__init__'' | ''maze_size'', ''step_limit'' | |''maze_size'' je velikost bludiště zadaná jaku 2-tuple, MxN kde M je počet řádků a N je počet sloupců. ''step_limit'' je počet kroků po kterém bude hledání v bludišti ukončeno, bez ohledu na to, zda agent zlato nalezl či nikoliv.| | ''generate'' | | ''layout'' | ''layout'' je plán bludiště. Plán je 2-D pole o rozměrech MxN, které obsahuje stringy '''EMPTY', 'OBSTACLE', 'GOLD', 'START'''. Hodnoty '''GOLD''' a '''START''' musejí být v plánu právě jednou. Plány vracená touto metodou musí být "feasible", tzn. musí v něm existovat cesta po polích '''EMPTY''' z pole '''START''' na pole '''GOLD''' (přesuny po diagonále nejsou povoleny).| ==== Zdrojové kódy a vizualizace==== {{:courses:b4b33rph:cviceni:rph-maze-keeper-sim_screenshot.png?400 |}} Máte k dispozici zdrojové kódy simulátoru a kostry implementace agenta a tvůrce bludiště: {{ :courses:b4b33rph:cviceni:rph-maze-keeper.zip |}} Soubor obsahuje následující moduly: * ''agent.py'' - sem vložte implementaci svého agenta. * ''maze_generator.py'' - sem vložte implementaci svého tvůrce bludiště. * ''simulation.py'' - Tento modul můžete použít pro testování svého agenta a tvůrce bludiště. Pokud chcete, můžete v konstruktoru zapnout také konzolovou vizualizaci průchodu agenta bludištěm. * ''visualization.py'' - nástroje pro vizualizaci, tento soubor nepotřebujete modifikovat. * ''maze_keeper.py'' - Odsud můžete importovat konstanty a třídu State. Třída MazeKeeper ovládá interakci agenta a bludiště. Tento soubor nemodifikujte. Agent smí s bludištěm interagovat POUZE pomocí třídy ''MazeKeeper''. Agent má zakázáno snažit se získat více informací o bludišti než je uvedeno ve specifikaci. ==== Odevzdání ==== Do BRUTE nahrajte soubor maze_keeper.zip který musí obsahovat soubor ''agent.py'' a ''maze_generator.py'' s třídami Agent a MazeGenerator. (Samozřejmě pokud ve svém řešení využijete import z některého dalšího modulu (např. maze_keeper), musíte nahrát i tento soubor). ====PSA: MazeObjects ==== Kvůli problému s automatickou evaluací byl z template řešení odstraněn enum MazeObjects. Pokud vaše verze řešení obsahuje MazeObjects jako enum a ne jako dictionary, stahněte si novou verzi zadání. Pro opravu kódu pak stačí nahradit např. ''MazeObjects.GOLD'' stringem '''GOLD'''