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.

Vaším úkolem je vytvořit dvě doplňující se součásti:

1. Inteligence pro hledání cíle (kopec zlata) v neznámém bludišti
2. 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 se pohybuje v bludišti, což je čtvercová mřížka. Pohyb v bludišti se řídí následujícími pravidly:

• 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í 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ě).

1. 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.
2. 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.

Vaším úkolem je vytvořit agenta v tříde Agent v souboru agent.py s následující specifikací

Stav předávaný agentovi je instance třídy State. Instance třídy State má 4 parametry:

1. position je aktuální pozice agenta uložená jako 2-tuple (r,c), např. na obrázku je to (12,3)
2. 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ě.

Vaším úkolem je vytvořit tvůrce bludiště v třídě MazeGenerator v souboru maze_generator.py s následující specifikací:

Máte k dispozici zdrojové kódy simulátoru a kostry implementace agenta a tvůrce bludiště: 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.

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).

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'