Umělá inteligence I

Umělá inteligence I - cvičení, 2020/21

Obecné informace

Jedná se o cvičení k předmětu Umělá inteligence I (NAIL069). Moje cvičení budou vedená v češtině. Pro informace o anglické verzi kontaktujte Adama Dingleho.
For english speaking students: These workshops will be in czech. For information about an english version please contact Adam Dingle.
Cvičení probíhá v pondělí od 10:40. Střídají se dvě skupiny po 2 týdnech. Na cvičení budeme používat jazyk C#.
Oficiální stránky předmětu a látku probíranou na přednáškách včetně slajdů najdete na stránkách profesora Bartáka.
E-mail na cvičícího:

Průběh cvičení

Cvičení budou letos probíhat distančně přes platformu zoom.us. ID zoom události spolu s přístupovým heslem najdete v SISu v popisu rozvrhového lístku. Zoom událost se bude konat vždy v čase, kdy je cvičení rozvržené a účast není povinná.

Dále nabídnu individuální i skupinové konzultace - opět distanční formou, viz níže.

Podmínky pro získání zápočtu

V průběhu semestru budu zadávat úlohy, za které můžete získávat body. Jedinou podmínkou pro získání zápočtu je mít na konci semestru aspoň 50% z celkového počtu vypsaných bodů. Body můžete získat za následující činnosti:

účast na cvičení - každá účast bude hodnocená 20-ti body
plnění úkolů na cvičení
odevzdávání domácích úkolů
účast v turnajích
bonusové body za velmi kvalitní, zajímavé nebo originální řešení

Domácí úkoly budou různého typu - teoretické, praktické, programovací, písemné a podobně a bude jich poměrně dost. Smyslem je, aby si každý účastník mohl částečně vybrat, který typ úloh mu vyhovuje. Není tedy třeba dělat úplně všechny. U každé úlohy bude stanovený termín a způsob odevzdávání.

Všechny úlohy jsou samostatná práce! Můžete se samozřejmě o úlohách bavit mezi sebou, ale řešení by měl vypracovat každý sám. Pokud budete podvádět např. víc lidí se pokusí odevzdat stejné řešení, nedostanete za úlohu žádné body a navíc všem účastníkům podvodu odečtu 2*(maximální počet bodů, které lze získat za danou úlohu). Všechna řešení, která pošlete se archivují, čili případné podvody lze odhalit i zpětně. Pokud by někdo podváděl dlouhodobě nebo závažně, může to mít za následek udělení hodnocení "Nezapočteno" z tohoto předmětu bez ohledu na počet bodů, nebo i vyloučení ze studia (viz disciplinární řád).

Pokyny pro odevzdávání domácích úkolů:

Úkoly budou vypsané zde na stránce cvičení a odevzdávání bude probíhat přes SIS. V modulu "Studijní mezivýsledky" naleznete položku pro každou úlohu. Řešením bude typicky soubor se zdrojovými kódy, které řeší danou úlohu. Vkládejte pokud možno celý projekt, ne jen vybrané soubory, vždy jako archiv ve formátu zip, rar, 7z a podobně. SIS umožňuje vkládat pouze soubory menší než 5MB, proto před zabalením smažte z projektu všechny spustitelné soubory nacházející se ve složce bin/Debug nebo bin/Release. Toto lze jednoduše provést pomocí Build -> Clean solution ve Visual Studiu. Typicky zadávám na každém cvičení jednu jednoduchou úlohu, kterou je třeba odevzdat ještě během cvičení a jednu o něco těžší úlohu, na kterou budete mít 2 týdny (čili do následujícího cvičení). V průběhu semestru zadám také několik dlouhodobých úloh. Obsah cvičení včetně všech zadaných úloh a termínů pro jejich odevzdání najdete zde na stránce cvičení.

Termín konzultací

V hlasování bylo jako nejvhodnější termín konzultací zvolené pondělí od 17:20. Konzultace tedy budou probíhat v tomto čase, opět přes platformu zoom. ID místnosti a heslo najdete v SISu v popisu rozvrhového lístku. Místnost otevřu vždy kolem 17:20. Pokud se během 15-ti minut nikdo nedostaví, tak konzultaci ukončím.

Celkem bylo možné na cvičení získat 785 bodů, čili pro udělení zápočtu je nutné mít aspoň 393 bodů.

Co bylo na cvičení

První zápočtová úloha: zadání zde

Druhá zápočtová úloha: zadání zde

Třetí zápočtová úloha: zadání zde

7. cvičení - rezoluční metoda

Rezoluční metoda - základní princip, vlastnosti, použití ve výrokové logice
Rezoluce v predikátové logice, unifikace, skolemizace, redukce kvantifikátorů.
Příklady zde

6. cvičení - logické odvozování

Opakování základních pojmů z logiky: formule, model, splnitelnost, tautologie, dokazatelnost, logický důsledek
Základní způsoby odvozování: model checking, rezoluční metoda, převedení na problém splnitelnosti
Řešení hry Hledání min pomocí logického odvozování.
Zdrojové kódy zde. (Starý archiv pro .NET framework zde)
Archiv obsahuje:
- Implementaci hry Hledání min, včetně vizualizace
- Generátor výchozích pozic
- Jednoduchý hladový algoritmus pro řešení
- Nástroje pro testování řešičů (generování několika vstupů, řešení, automatické vyhodnocení výsledků)
- SAT solver Sat4J včetně návodu a popisu formátu vstupu
Úkoly:
- Implementujte a otestujte řešič založený na ověřování modelů. (Metoda Deliberate() ve třídě ModelCheckingSolver.) Využít můžete už implementovanou metodu isThereAModel() (20 bodů).
- Navrhněte a popište způsob, jak lze problém existence modelu převést na SAT. Na vstupu tedy bude situace ze hry Hledání min a na výstupu bude logická formule v CNF, která bude splnitelná právě tehdy, když bude možné rozmístit miny na neodhalená políčka tak, aby byla splňena pravidla hry (tzn. rozmístění min nebude v rozporu s informacemi na již odhalených políčkách). Stačí slovně/matematicky popsat, jak se formule vytvoří a dokázat nebo aspoň vhodně argumentovat korektnost převodu. Nemusíte převodní algoritmus implementovat. Popište také, jak bude výsledná formule velká (počet proměnných a klauzulí) v závislosti na velikosti zadání. Termín: Obě skupiny do 5. 1. 2021 30 bodů
- Implementujte a otestujte převodní algoritmus z předchozího bodu. Nahraďte tělo metody isThereAModel() voláním SAT solveru s využitím vašeho převodního algoritmu a srovnejte efektivitu tohoto přístupu s metodou, kterou jsme vytvořili na cvičení. Můžete využít solver Sat4J, který je součástí archivu. Je přiložený i návod k použití a informace o formátu vstupů. (Pro volání externího programu z .NET aplikace je vhodné využít objekt System.Diagnostics.Process) Termín: Obě skupiny do 5. 1. 2021 Dalších 30 bodů

5. cvičení - hraní her

Hry dvou hráčů - definice problému, připomenutí základních algoritmů
Minimax, Alfa-beta prořezávání, další podpůrné techniky
Přehled některých her a úspěšnost nejlepších herních algoritmů ve srovnání s nejlepšími lidskými hráči
Hra 4-v-řadě - zdrojové kódy zde. (Starý archiv pro .NET framework zde.) Archive obsahuje hru 4-v-řadě (Connect Four) včetně vizualizace a několika enginů
Úkol: Implementujte vlastní statickou ohodnocovací funkci pro alfa-beta prořezávání, nebo celý vlastní algoritmus a otestujte jej proti implementovaným technikám. Vlastní ohodnocovací funkci můžete vytvořit dopsáním těla funkce eval ve třídě AlphaBetaExperimentalEngine.
Nový vlastní algoritmus můžete implementovat vytvořením potomka třídy Player a dopsáním metody selectMove.
Váš algoritmus by měl vyžadovat zhruba stejné množství času jako vestavěné alfa-beta prořezávání a dávat lepší výsledky (tzn. porážet ho, nebo porážet jiné enginy, které vestavěný engine nedokáže porazit). Termín: první skupina: 15.prosince, druhá skupina 22. prosince, 25 bodů.

4. cvičení - lokální prohledávání

Lokální prohledávání - fungování, srovnání s dopředným prohledáváním, vlastnosti, výhody a nevýhody
Připomenutí některých algoritmů - Hill climbing, Simulované žíhání, Metaheuristiky, Genetické algoritmy
Varianty HC
- standardní HC
- HC s náhodnými restarty
- HC první volby
- Enforced HC
- HC pomocí náhodné mutace
Problém obchodního cestujícího - zdrojové kódy zde. (Starý archiv pro .NET framework zde)
Archiv obsahuje:
- Model problému TSP, generátor instancí, vizualizaci výsledků
- Několik řešících algoritmů
Implementujte a otestujte některou z variant algoritmu HC. (Metoda DoLocalStep() ve třídě HillClimbingSolver) 10 bodů.
Domácí úkol: Implementujte jednoduchý genetický algoritmus pro řešení problému TSP (implementujte rozhraní TSPSolver, použijte interface LSUnaryOperator a LSBinaryOperator pro mutaci a křížení. Pro mutaci můžete použít existující implementace.). Termín: První skupina: 1. prosince, druhá skupina: 8. prosince, 30 bodů

3. cvičení - informované prohledávání

Rozdíly mezi informovaným a neinformovaným prohledáváním
Heuristiky - definice, základní vlastnosti, použití
Algoritmus A* a jeho vlastnosti
Hra Sokoban, její řešení pomocí prohledávání, stručná zmíňka o modelování problémů, obecné postupy při návrhu heuristik
Návrh heuristiky pro hru Sokoban
Zdrojové kódy zde (Starý archiv pro .NET framework zde)
Archiv obsahuje:
- Model hry Sokoban, včetně načítání vstupů ze souboru a vizualizace řešení
- Algoritmus A* a několik heuristik
- Informační výpisy a další podpůrné funkce umožňující monitorovat průběh prohledávání
- Několik instancí problému Sokoban a editor map, který umožňuje případně vytvářet další
Úkoly:
- Seznamte se se zdrojovými kódy, vyzkoušejte prohledávací algoritmus na několika problémech, srovnejte chování algoritmu při různých nastaveních a s různými heuristikami.
- Úkol na cvičení: navrhněte a implementujte vlastní heuristiku pro hru Sokoban, která bude při prohledávání efektivnější než Slepá heuristika. (Třída BlindHeuristic, vrací vždy nulu.) 10 bodů.
- Domácí úkol: navrhněte a implementujte vlastní heuristiku, která porazí vestavěnou heuristiku SimpleDistanceHeuristic nebo AdvancedDistanceHeuristic.
  Tyto heuristiky (vaši a některou z vestavěných) experimentálně srovnejte na několika problémech a o výsledcích srovnání napište krátkou zprávu (max 2 strany A4). Zpráva by měla obsahovat stručný slovní popis vaší heuristiky, tabulku výsledků, kde bude uvedeno: celkový čas běhu, kvalita nalezeného řešení, počet expandovaných vrcholů a případně další charakteristiky, které vám přijdou zajímavé, a jednoduchý graf, kde budou tyto výsledky porovnané.
  Při porovnávání heuristik sledujte kritéria celkový čas, kvalita řešení, počet expandovaných vrcholů. Vaše heuristika by měla v těchto kritériích být srovnatelná s vestavěnými (na všech problémech) a aspoň na jednom větším problému by měla být lepší ve všech třech kritériích.
  Termín: První skupina: 17. listopadu, druhá skupina: 24. listopadu, 30 bodů

2. cvičení - neinformované prohledávání

Úvod, model kombinatorických problémů, přehled standardních řešících technik
Zdrojové kódy zde (Staré zdrojové kódy pro .NET framework jsou zde)
Projekt obsahuje:
- Obecný model kombinatorického problému - reprezentace stavů, generování následníků, testování cílového stavu. (Třída State)
- Tři příklady problémů - Lloydova 15-ka, Problém obchodního cestujícího a Rubikova kostka. Načítání počátečního stavu, vizualizace řešení.
- Funkční kostru prohledávacího algoritmu UCS (Třída SearchEngine).
- Kontrolní výpisy pro sledování průběhu prohledávání
Úkol na cvičení: implementujte algoritmy BFS a DFS a otestujte je na všech problémech. Srovnejte chování obou algoritmů (čas, paměť, kvalita řešení, a podobně). Můžete vytvořit potomka třídy SearchEngine a předefinovat metody AddToOpenList, AddToClosedList a/nebo Search, nebo napište celý algoritmus sami. 15 bodů.
Domácí úkol: implementujte jeden z algoritmů Bi-Search nebo Iterative Deepening, otestujte ho na daných problémech a srovnejte jejich chování a výsledky. Termín: 1. skupina: 3. listopadu, 2. skupina: 10. listopadu. 25 bodů.

1. cvičení - Úvod + reflexní agenti

Organizační záležitosti. Podmínky pro získání zápočtu a bodový systém.
Trocha teorie, stručný úvod do umělé inteligence a reflexních agentů.
Jednoduchý fotbalový simulátor
- Zdrojové kódy jsou zde
- Vytvořte reflexního agenta/agenty pro hraní fotbalu
- Agenty implementujte vytvořením nového potomka abstraktní třídy AgentPlayer a předefinováním metody SelectAction. Soubor SimpleAgents.cs obsahuje pár příkladů.
- Pak je potřeba na označeném místě upravit soubor Form1.cs a přidat váš nový tým do hry.
- Při tvorbě agentů je možné využívat vestavěné podpůrné funkce z objektu utils
- Je možné vytvořit více typů agentů zastávajících různé funkce v týmu, a pak z nich tým poskládat
Úkol na cvičení: navrhněte agenty a postavte z nich tým, který porazí vestavěného protivníka TJ Sokol Nekopnemsi - 10 bodů
Domácí úkol: postavte ze svých agentů tým, který porazí vestavěného protivníka Barcelona FC. Termín: 1. skupina: 20. října, 2. skupina: 27. října, 20 bodů.,