Temy rocnikovych projektov (a potencialne Bc. praci) Jan Hric, KTIML 28.2.2005, 4.3., 28.8.2005 9.2.2007, 1.3.2007 25.2.2008 24.2.2009 25.2.2010 28.2.2011 Temy/oblasti obvykle potrebuju upresnenie. Je vhodne, ak je z vaseho navrhu jasne, co vas zaujima. Rozpracujem(e) a upresnim(e) :-) alebo Vas odmietnem :-( Ak uz tema bola zadana a zaujima vas, ponuknem (obvykle) variantu. Roky v zatvorkach oznacuju vymyslenie temy (pre mna). Vy si mozete si vyberat bez ohladu na roky. (Otaznik znamena, ze temu je nutne upresnit a al. dovymysliet) Terminy: Strucna specifikacia: 30.3. Podrobna specifikacia: 30.4. Beta verzia dokumentacie 20.6. Beta verzia programu koniec skuskoveho (~30.6.) Preferovane oblasti zadavania: Pocitacove hry (go, koncovky) Umela inteligencia (prehladavanie, heuristiky) Spracovanie textov --------- rok 2011: MCTS s inou strategiou riadenia - MCTS riadene PNS - MCTS riadene Min-Max - MCTS a iterative deepening MCTS pre riadenie GA (genetickych algoritmov) MCTS a lokalne vzory ? MCTS pre hry ? MCTS pre hlavolamy (SP-MCTS, Single Player) Specialne: ... ? MCTS a replay - specialne SP-MCTS - v go - lokalne dohladavanie ? MCTS a dalsie heuristiky pre go ? MCTS a male go - resp. koncovka ? SP-MCTS a globalne omedzenia SP-MCTS a usporiadane omedzenia - kakuro, ?sudoku Prehladavanie velky priestorov specialne: - koordinovana paralelizacia (neprekryvanie) - vhodne datove struktury Ucenie pokera (pomocou reinforcement learning) GGP pre single-player -? aj dynamicke GGP a lokalne vzory ? PNS - Rešeršia MCTS: Monte Carlo Tree Search PNS: Proof Number Search GGP: General Game Playing --------- rok 2010: ?Metoda Survey Propagation SP.1) len RP: Reimplementacia, +field, +dynamicke nastavovanie sily SP.2) RP+Bc: upravit SP pre usporiadane domeny aplikacie: 3SAT! (podm. s <), Max-SAT (kriterium s <), jaskyne (determ. zmena), stromy (nedet. zmena), ... ine hlavolamy (SP.3) ?? Propagacia pre rozne podmienky SP.4) RP+Bc: upravit pre omedzujuce podmienky (CSP) SP.5) add: propagacia aktivacie (pri vypocte na 1 procesore) SP.6) add: replay pre podmienky; nahodny vyber pre propagacie SP.7) add: usporiadanie a zametanie zlava a sprava Survey Propagation (SP) je metoda pre riesenie problemu SAT (CNF), kde si klauzule a premenne posielaju spravy o pravdepodobnosti nesplnenia klauzule a vynutenia premennej. Metoda dobre riesi aj tazke pripady splnitelneho SAT. Niektore navrhy upravuju SP pre omedzujuce podmienky, kde premenne mozu nadobudat viac hodnot nez 2 (ako v SAT). Museli by sa vybrat vhodne typy podmienok. SAT.1) len RP: SAT s nutenym vyberom (1x True, ostatne False) rozsirovanie, restart (s pamatou) - #oblasti RP+Bc: add: +metoda 2 pointrov, +ucenie klauzuli ?? moznost paralelizacie (SAT.2) add: replay pre ohodnotenia (SAT.3) add: vyberanie premennej podla celkoveho ohodnotenia Koncovka pre hru Arimaa: Ar.1) RP+Bc: Adaptovat lambda-search pre arimuu Ar.2) RP+Bc: Adaptovat proof-number search pre arimuu var: ciel je vyhra alebo takticke ciele: branie, frame, blokada Arimaa v 1 tahu obsahuje 4 kroky jednoho hraca. Cielom je upravit metodu lambda-search, resp. proof-number search pre takto zobecnenu hru. rok 2009: (z jednoho zadania je mozne pripadne vyrobit niekolko rocnikovych problemov, resp. bc. praci), rozroznenim a upresnenim zadani 2009.1 Kombinovanie gen.alg., lok. optimalizacie a Monte Carlo. (Pre vhodnu ulohu: TSP, QCP, SAT) - Problem obchodneho cestujuceho, Quasigroup Completion Problem, Splnitelnost Gen.alg. optimalizovat, pritom lok. optimalizacia (ak je mozna) vnasa nove riesenia (resp. casti rieseni, napr. hladovo). MC kontroluje celkove prehladavania. O-1: inicializacia (#pokusov), a vyber premennych (a ich poradia) O-2: Velke/male omedzenia, priemer grafu O-3: vplyv druhov propagacie (Alldiff, 8_z_9, almostAllDiff, farbenie grafu, huste/riedke omedzenia, priama/pozdrzana propagacia (alldiff/any_v_SAT), viditelnost (a QCP) O-4: Ako sa vyhnut neperspektivnym oblastiam (..heuristiky, beam search) (Multikriterialny beamsearch, skracovanie hranice) 2009.2 Monte Carlo pre optimalizacne ulohy. (na BcP. potrebne upresnit/rozsirit) Skusit techniky zname z MCTS (Monte Carlo Tree Search) pouzit na testovacie ulohy z Differencialnej optimalizacie (viz Umela inteligence 4) Otazky: O-1: Poradi si MC s viac/mnohymi dimenziami O-2: Ako delit intervaly. Pamatat si presne body a vysledky alebo len statistiku pre intervaly O-3: Okrajove podmienky a hladanie mimo hranice O-4: Ktore techniky z MCTS su vhodne (a z inych oblasti) (kratky/dlhy MC search, killery, history heuristic, simulacia), (2009.3 ?? Technika spatneho spracovania) aplikacia: TSP 2009.4 Restarty a uplne prehladavanie Navrhnut efektivnu dat. strukturu, ktora umozni kombinovat vysledky (mnohych) restartov do uplneho prehladavania. Idealne bez prekryvania rieseni. O-1: urcenie smeru rozsirovania O-2: urcenie slubnosti rozsirovania 2009.5 SAT solver Technikou odspodu. O-1: vyber premennych, pre rozsirenie O-2+ delenie premennnych: velke/male skupiny, prekryvanie skupin O-3: moct zadat nosne a odvodene premenne; zisti nosne a odvodene p. zistit skupiny p. (heuristicky) (2009.6 Generovanie tazkych zadani) Modelove prostredie pre CSP, rozne druhy problemov a omedzeni (viz 2009.1,O-3) O: Malo rieseni O: iste riesenie, viac rieseni, chorda rieseni O: hniezdo rieseni a jeho udrziavanie lokalne, stack+beam+restart, ne/cielene vylucovanie 2009.7 Monte Carlo v taktickych ulohach Go. (2009.8 Planovanie v skoro-prazdnych priestoroch) Sokoban, Fish Fillets - pomocou odstranovania chyb (2009.9 PN-search pre constrainty; pre SAT) O-1: kriterium optimality O-2: uplnost O-3: premenne za neuspechom: ich priradenie? (2009.10 Geneticke programovanie) ... na vhodnej ulohe reprezentacia: stromy, konecne automaty, pravidla 2009.11 Monte Carlo pre strategicku hru Pre vhodnu strategicku hru (Metro, ?Carcassone) navrhnut parametrizovatelneho Monte Carlo hraca. Pouzit triky z MCTS. Hra: Metro ---- 1. Pocitacove go. (2005-07) 1.1. Go: analyza statusu skupin (2005-07) (riešenie uloh a generovanie), ---- 1.1a Celodoskova Koncovka pre (malé) go (2005-07) Hladanie optimalnej koncovky, pripadne spocitanie ceny tahov. ---- 1.2 Male go (2005,2007) (Vy)Riesenie go na malej doske (5x6, 6x6, 7x7). Vyuzit triky a heuristiky zname z pocitacovych sachov (hasovacie tabulky, killery, ID, okienka ...). O.zadanie: Cílem práce je implementovat program pro (vy)řešení go na malých deskách (5x6, 6x6, 7x7). Protože celkové vyřešení je těžké (a nepravděpodobné), program by měl umožnit spočítat hodnotu hry (tj. pozice) po nějakém zahájení. V rámci práce by měl student využít známé optimalizační techniky z počítačových her (šach, dáma) jako transpoziční tabulky, killery, ... Varianty: (Ak go nehrate, su to vhodnejsie varianty - a jednoduchsie na porozumenie) 1.2.2 Atari-go na malych doskach. 2007-Tomas Stary Atari-go je go, v ktorom vyhrava hrac, ktory prvy berie superovi kamen. Specialne, ak hra skonci bez ziskania zajatca, hraci dalej hraju striedavo do svojho uzemia (pretoze sa nesmie pasovat) a teda vyhra ten, ktory mal vacsie uzemie. Program dokaze spocitat hodnotu hry, pozicie, postupnosti pozicii (v partii). Dokaze navrhnut spravne tahy a ukazat chyby. 1.2.3 Riesenie taktickych cielov v go Riesenie taktickych(-eho) cielov(-la) v go (spojenie/rozdelenie, zivot/smrt, 1oko, boj-semeai, zajatie/ohranicenie/utek - invazia do uzemie/preniknutie k strane, tahy dvoch ucelov, cena tahu, zivot alebo utek) Pomocou (nejakej varianty) pn-search (alebo alfa-beta). Pravdepodobne pre jeden konkretny ciel. 1.2.4 Pn-search pre atari-go Atari-go viz hore, pn-search viz literatura. Proof-number search je algoritmus pre (neuniformne) prehladavanie stromu hry s boolovskym cielom (typicky "vyhrat" v koncovke). Stavy vrcholu mozu byt: Vyhra(proved)=ciel_splneny, prehra(disproved)=ciel_nesplneny, unknown=hodnota_vrcholu_neznama. PN-search (a jeho varianty) je best-first algoritmus, tzn. rozvija vzdy najlepsi vrchol (list na "najlepsej" ceste - min pn pre MAX, min dn pre MIN). Pre vrcholy si pamata tzv. proof a disproof number. Pre utocnika (ktory chce splnit ciel, MAX) sa proof-n urci ako minimum pn synov, disproof-n je sucet dn synov. Pre obrancu (MIN) opacne, pn je sucet, dn je minimum. Cisla pn a dn su pre proved uzol 0 a nekonecno, a pre diproved nekonecno a 0. Strom je vyrieseny, ak je root 0 alebo nekonecno. Najlepsi syn je minimum z pn synov v MAX uzle a minimum z dn synov v MIN uzle. Snaha je urcit hodnotu korena stromu, tj. danej pozicie. Varianty - porovnat na atari-go: pn (Allis 1994), pn2 (Breuker 1998), pn* (Seo 2001) PDS (Nagai 2002), DF-PN (Nagai 2002), PDS-PN (Winands 2003, LinesOfAction) Fast_PN_Low_memory (2006 JakubPawlewicz, Lukasz Lew) MonteCarlo_PN (Saito 2006) [1] http://www.cs.unimaas.nl/m.winands/documents/PN_PN2_AND_PNstar_%20IN_LOA.pdf http://www.cs.unimaas.nl/m.winands/ najst lepsiu literaturu :-) 1.2.5 Pn-search a prerezavanie Pretoze pn search je best-fist, pamata si vrcholy. Ak mu dojde pamat, zahodi najmenej perspektivnu cast stromu. Preskumat suvislosti. Porovnat strategie zahadzovania vrcholov/podstromov z hladiska najdenia riesenia a poctu preskumanych uzlov. Mozem zahadzovat len neperspektivne stromy z hladiska jednoho hraca, takze sa sustredujeme na (ne)splnenie ciela z hladiska druheho. ---- Prehladavacie algoritmy , a ich kombinacie - pn-search (proof-number), hrozby, prerezavanie, (lambda-search) Ine hry ... ---- nevhodne, lahke 1.3 Sprava databazy partii (2005) Hm. Vyhladavanie, vypisovanie, sprava variant a doprovodnych textov. ---- 1.4 Analyza goistickych tesuji (2005) Na zaklade prikladov (a protiprikladov) nejakeho tesuji najst podmienky, kedy tesuji funguje. Podmienky sa tykaju obsadenia plochy, poctu slobod, spojenia skupin, ... ---- Nevykrystalizovane Prehladavanie stromov hier (VIII 2005) RP,BC,?DP (1.5a Proof number search ... a) [Allis94] (1.5b Threat search ... v pocitacovych hrach) [Cazenave98,02] (1.5c Conspiracy number search) [Schaeffer89],[McAllester93] (1.6 Prehladavanie v omedzenej pamati ) ---- 1.7 Budovanie kniznice zahajeni (VIII.2005) RP, BC; 2006 zadane Radoslav Sopoliga Pre niektoru hru (Quoridor, Atari-Go, Go, ...) navrhnut a implementovat metody na budovanie kniznice zahajeni. Sucastou je implementacia (jednoducheho) hracieho programu. Metody pre budovanie kniznice by mali byt dobre oddelene od znalosti o konkretnej hre. Metody by mali byt tak obecne, aby sa dali pouzit nielen pre budovanie kniznice zahajeni pre pociatocnu poziciu hry (primarny ciel), ale aj na poziciu v "strednej" hre (alebo koncovke). V tychto pripadoch bude vyslednom "rozbor", s optimalnou hrou za jednu (alebo obidve) strany. (Q: Aky je vplyv kvality hraca?) [Schaeffer] - pre chechers (damu) http://www.cis.uab.edu/hyatt/ Autor:hyatt pgm:Crafty chess http://cito.atspace.com/crafty.html Crafty site ftp://ftp.cis.uab.edu/pub/hyatt/book/ Crafty book opening ---- 1.8 Graficke prostredie pre permutacne hlavolamy. (2006) zadane Konfigurovatelne. Zamerane na grafiku. Zadanie zobrazenia, zadanie tahov. Podpora prehladavania, podpora makrotahov - najdenie, zapamatanie. Priklady: Rubikova kocka, Cube 21, Lloydova 15, 3 kruhy, Oslik, ... Kocky su rozne velke (tvarovane), nie vsetky tahy su vzdy povolene, niektore sucasti su zamenitelne (rovnako ofarbene), 2D a 3D ... ---- nevhodne: programatorsky lahke 1.9 Analyza transpozicnych tabuliek. (2006) Pre kombinatoricke suctove hry (combinatorial game theory) zmerat na simulovanych datach efektivnost transpozicnych tabuliek, tj. roznych strategii vymeny dat v tabulkach. Simulovane data su suctom n(=5..7) hier pevnej hlbky d(=2-4 ply) s nahodnym rozlozenim vysledkov okolo strednej hodnoty. Pocet tahov je typicky 1 (pre kazdeho hraca), niektore vetvy mozu byt ukoncene skor, niekde mozu byt dva tahy pre sente/gote. Pre simulovanie zavislosti su v niektorych (aj vnutornych) vrcholoch tokeny (so znamienkom) a dve hry s tokenom maju zavisle vysledky, ak sa ziska token dvakrat/viackrat. (ako simulovat tahy dvojho ucelu? - tokeny su asi nedostatocne.) Pri znamych velkostiach hry je znamy pocet prehladavanych pozicii (a pocet ciest do nich). idea teoretickej prace: hladanie strategii (priblizneho) vyhodnocovania a prerezavania ---- nevykrystalizovane 1.10 Vynutene koncovky (2007) Tazke, skor na DP [Cazenave98,02] Algoritmy zobecnenych hrozieb. ---- 1.11 Porovnanie pn-searchov. (2007-) Naprogramovanie roznych variant algoritmov zalozenych na proof-numbers. Porovnanie na vhodnej hre (mnozine testovacich pozicii) a syntetickych datach (generovane nahodne stromy s danymi charakteristikami). ---- Nevykrystalizovane 1.a.1 Prehladavanie velkych stavovych priestorov (2005) Nevykrystalizovane Prostredie pre prehladavanie, parametricky popis priestoru. (Hm. napr. pre go.) Aplikacie: (1.5a Permutacne hlavolamy) ((1.5b Drotove hlavolamy)) Len RP, nie Bc. praca (Sokoban - viz [Schaeffer a spol.]) (!rybicky: 2! agenti, rozne velki, +padajuce predmety) (nahodne restarty) (1.a.2a Prehladavanie hier v omedzenej pamati - viz inde) (1.a.2b Prehladavanie stavovych priestorov v omedzenej pamati - viz inde) 1.a.3 Prostredie pre tvorbu hlavolamov (VIII.2005) RP, BC? Pre vhodny druh hlavolamov navrhnut sposob popisu (~jazyk) hlavolamov, (napr. vratane popisu symetrii) a kriteria pre ... Druhy pre Hlavolamy: _skladacie_; dynamicke - soliter, sokoban; 2D/3D, permutacne (aj abstraktne): Rubikova kocka, Cube21; ... ---- Hry: Go, Atari-Go, Piskvorky, Hex, Quarto, Quoridor, (LOA - Lines of Action) ... --------- 2. Spracovanie textov. ---- 2.1 Konfigurovatelne vyhladavanie entít (2005) Petr Koval o.zadanie: Cílem práce je vytvořit systém, který na základě zadaných částí textu (od slov a frází až po dokumenty) s relevantními entitami určí typické kontexty pro hledané entity. Následně systém bude schopen podle kontextu najít entity v dalších textech. Typické hledané entity jsou faktografické údaje jako jména osob, institucí, měst, výrobků ... Konfigurovatelnost systému by měla dovolit využívat v kontextu všechny dostupné informace o textu, tj. nejen sousednost slov, ale i syntaktickou strukturu. popis: jedna zo znamych uloh je (konfigurovatelne) vyhladavanie entit v texte: bez domenoveho rozlisenia sa vyhladavaju - mena - osob, firiem/institucii, geograficke (miest), ... vyrobkov - datumy a casy - meny a financne udaje v konkretnych domenach: napr. vyrobky, sluzby, nazvy genov, chemikalii, funkcie ludi a ich tituly, nazvy prednasok, konferencii, ich domovske stranky... a navazujuce ulohy - asi mimo rozsah projektu a Bc. prace vlastnosti "objektov" vztahy medzi nimi rozpoznavanie udalosti (events) a vyplnovanie ich "poloziek" Mozny pristup je ucenie vztahov _kontextu a entity_ (dost obecne a povrchne povedane), tj. ktora entita sa vyskytuje v akom kontexte (a ako casto). Obvykle poziadavky su - velke data, - malo "uciacich prikladov" - malo pracne pre ucitela, a s tym suvisiaca prenositelnost (medzi domenami) technicke vlastnosti, ktore by system mal mat: konfigurovatelnost kontextu (co je povazovane za kontext) moznost priebezneho riadenia a usmernovania (hm, ?sposob integracie) ? bootstraping ? pouzitelne na ceske/slovenske data (problem s testovacimi datami) (Iny pristup k ulohe je vyhladavanie podla syntaktickych podobnosti (pevne vzory) - nevhodne pre Bc. pracu, nutne podrobnejsie premysliet a popisat) ---- 2.1.1 Bayesovske Vyhladavanie entit. (08'2006-07) Popis ulohy - viz minule zadanie 2.1 . Student sa zoznami s pristupom Bayesovskeho rozpoznavania spamov (napr. [1]). Pre urcovanie, ci kontext urcuje relevantnu entitu, sa pouzije (naivny) Bayesovsky pristup. (Entita je pred/za slovom (v urc. vzdialenosti), vo vete/paragrafe; slovo je entita, resp. sucastou entity). Primarne urcenie programu na identifikaciu entit, ale mozne pouzit aj na urcenie relevancie vacsich casti textu: viet, paragrafov, dokumentov. Pre Bc. pracu nejake integrovanie prostredie (pre podporu bootstrapingu a vyrobu treningovych/testovacich), ktore bude ponukat (vhodnych sposobom) uzivatelovi na odsuhlasenie predspracovane data (entity a/alebo kontexty). Uschova sessions. Trenovacie data - ceske texty z Prague Dependency Treebank. Konkretne oznackovanie entit nie je dostupne. Options: velkost okolia, ucenie z neistych/neoznacenych dat, prahy. (Testy, bootstraping a hlasovanie, validacia) [1] http://www.paulgraham.com/ -> A Plan for Spam ---- 2.1.2 Rozpoznávanie spamových obrázkov. (2007) (vhodne na Softwarový projekt?) Literatúra viz vyššie. [1] http://www.paulgraham.com/ Vytvorit program, ktory dokaze rozpoznat (niektore, typicke) spamove obrazky. Sucastou je určovanie (výber) vhodných fíčur (tj. rysov), update - prisposobovanie fíčur, fíčury vyšších rádov. Rysy sa ziskaju: lokálna analýza (hrany, farby, smery, histogramy, prahovanie), globálne vlastnosti (histogramy, mediany), spicpiky. Stačí pre jeden (jednoducho analyzovateľný) druh formátu - vstupu. (Vybudovanie korpusu?) (Testovanie užívateľom zadaných fíčur, optimalizácia parametrov) Bayesovký prístup je možný, ale nie nutný. Možné využiť i textové informácie zo súboru. (jednoduchsia) Varianta: Vyhodnocovaci system, ktory by pre uzivatelom zadane navrhy filtrov a podmienok (aj parametrickych) urcil, ci dane filtry dokazu rozlisit urcite triedy obrazkov. Dopocital by vhodne parametry (aj naivnymi metodami) pre rozlisenie. Napr. Existuje nejaky prah jasu, ze obrazok ma charakteristiky textu? (a aky je prah?) Existuje smer (a aky), v ktorom je histogram farieb riedky? (tj. cely sikmy riadok je rovnakej farby.) ---- 2.2 Analyza inzeratov (2005-07) Konfigurovateľné prostredie (ručne, automaticky), ktoré umožní analyzovať zadané čiastočne štrukturované texty, napr. inzeráty (rozneho druhu) alebo citacie. Vysledkom analyzy je naplnenie položiek, typickych pre analyzovany druh vstupu. (Druhy poloziek (a podpoloziek ...) su sucastou konfiguracie.) Mozny je aj vystup v XML. ---- Nevykryštalizované 2.3 Hladanie definicii (2005) (Ina uloha je extrakcia definicii z textu (popis pojmov/technickych_terminov), taktiez su pouzitelne vzory - ?nevhodne pre Bc. pracu, nutne podrobnejsie premysliet a popisat) ---- Nevykrystalizovane. 2.4 Koncepty. (2005) Prostredie pre pracu s konceptami. Možná Aplikacia: parsovanie ---- Nevykrystalizovane. 2.5 Analyza archivov (2006) Zamerane na analyzu textovych dat, menej na on-line webove rozhranie. Druhy analyzy: Klastrovanie, extrakcia entit (viz), extrakcia FAQ, sledovanie vlaken, zaradenie paragrafov/viet (konfigurovatelne), ... Druhy dat: FAQ, archivy mailinglistov, ... - hub/authority ---- 2.6 Burrow-Wheeler kodovanie pre extrakciu entit (2006) Nevykrystalizovane. ---- 2.7.1 Prekladovy slovnik (2008) K dispozicii su prelozene vety pre cesky a anglicky jazyk [1] - tzv. paralelny korpus. Cielom tohoto projektu je poskytnut uzivatelovi nastoje (prostredie), pomocou ktorych bude na zaklade korpusu schopny vygenerovat prekladovy slovnik. Prostredie ma uzivatelovi umoznit vygenerovat pociatocny slovnik, uschovavat a nacitat ho, rozsirovat a upravovat ho (interaktivne a) automaticky pomocou roznych (bohato parametrizovatelnych) metod nazaklade dat. Nastroj by mal byt skalovatelny a schopny spracovat velke data. Pri interaktivnej praci si nastroj pamata rozhodnutia uzivatela (typicky najdene chyby) a neopakuje ich. System predpoklada a je urceny pre situaciu, ked paralelne data su spravne a zmysluplne preklady. V zakladnej verzii hlada preklady slov 1:1, je mozny obecnejsi pristup 1:n (a pripadne preklady fraz, tj. m:n). Rozsirujuca cast (alebo varianta zamerania - 2.7.2 ): Na zaklade aktualneho slovnika system najde v korpusoch kandidatov na sparovanie viet (1:1 alebo obecnejsie) [1] http://ufal.mff.cuni.cz/czeng/ CZENG 0.7 [2] http://www.statmt.org/moses/ frazovy preklad Dalsie mozne rozsirenia: (factored words: slova maju dalsie informacie - POS, lemu, ... ) (frazy) ------------- 3. System pre kontrolu prikladov. (2005-07) Nie - Riesene inde Implementacny jazyk: Prolog/Haskell System umoznujuci (automaticku) kontrolu prikladov formalizovanych predmetov, napr. Automaty a gramatiky, (logika), ... Rozsiritelny, co sa tyka druhov uloh a ich rieseni. Volitelne: sprava uzivatelov (testovanie kalkulu) -------------- 4.1 Genetické algoritmy. (2007) Nastroj pre podporu implementacie genetickych algoritmov, nezavisly na domene. Podpora pre implementaciu roznych strategii, parametrizaciu populacii, selekcie, mutacii a krizeni. Podpora metastrategii (napr. elitizmus) a niekolkych populacii (ostrovy). (a dalsie: prepocitavanie fitness ...) Zaklad je kniznica, pripadne prostredie, rozsirenie je skriptovaci jazyk. Dalsie mozne rozsirenia je integracia vlastnych (domenovo zavislych) technik inicializacie, mutacie, krizenia, ... (Varianta je zameranie na prezentaciu vysledkov a zobrazovanie statistik - nevykrystalizovane) a) Prostredie umoznujuce na udržiavanie diverzity populácie b) Prostredie (a vhodná úloha: TSP) zamerané na vkladanie dobrých lokálnych riešení [1] Umela inteligence 4, kap. 5 - pozn. zlozitost projektu zavisi na zvolenom sposobe integracie kniznice -------- 4.1.2 Geneticke programovanie (2008) a) prostredie b) na vhodnej modelovej ulohe (z lit.: ucenie explitnej reprezentacie) c) prostredie pre podporu (a analyzu strategii): sutazivi agenti ("broucci") 2009: niekolko kast; (staticky _pri_narodeni_ alebo dynamicky dane), umoznia modelovanie pohlavia, predatorstva, ?pachovych stop, spracovania spec. potravy a ine dovednosti - (v lit: ustne predavanie dovednosti) - (modelovanie urodnych oblasti a pusti - lokalita vyskytu; dozrievania potravy, agenti rozpoznaju urodnu podu - pre svoj druh rastliny) - (zaslapavanie plevelu - za penalizaciu, priprava - vedome pestovanie) - Q: ako dobra al. rychla bude adaptacia po urcitom celkovom pocte vyhodnoteni) - prilis zlozite modely :-(( ---- Nevykryštalizované 4.2 Datamining (2007) ... ---- 4.3 Heuristické riešenie omedzení. (2007) Vytvoriť prostredie, ktoré pre úlohy s omedzeniami v konečných doménach umožní heuristické prehľadávanie založené na odstraňovaní konfliktov. Súčasťou práce je navrhnúť sposob popisu omedzení, idealne rozsiritelny (prilinkovaním ...) Cieľová funkcia je nastaviteľná staticky, prípadne dynamicky (väčšia váha pre ťažšie splniteľné omedzenia) Omedzenia možu mať stupne (ne)splnenia a možu sa splňovať postupne. (Omedzenia sú zložité: allDifferent(), ...) Výpis štatistík - počty prehľadaných stavov, ... Typy úloh: Hlavolamy, farbenie grafu, sudoku ... Varianta: často použité hodnoty (dvojice, n-tice) si pamatam a penalizujem (tj. tabu search / reinforcement learning) Varianta: zúplniť prehľadávanie, sústrediť sa na stratégie (rozširovanie domén, spojovanie podpriestorov, restart ...) ---- 4.4 Prostredie pre Reinforcement learning (2007) predbezne: Martin Sladecek 2008 Implementovať prostredie pre reinforcement learning (kniznicu a/alebo skriptovaci jazyk) a aplikovať ho na vhodnu ulohu :-) (resp. triedu uloh) Mozne ulohy: - ucenie vzorov v hrach (preferujem go), ucenie ohodnocovacej funkcie, (a umele hry) - optimalizacie: problem obchodneho cestujuceho, splnitelnost CNF - SAT - (ucenie reaktivneho agenta - chodenie, ...) [1] Richard S. Sutton, Andrew G. Barto: Reinforcement Learning: An Introduction, MIT Press 1998, http://www.cs.ualberta.ca/~sutton/book/the-book.html ---- 4.5 Prekladac omedzeni na problem SAT (2007) Pre ulohy s omedzujucimi podmienkami (send+more=money, sudoku) navrhnut jazyk a sposob prekladu na (NP-uplnu) ulohu SAT pouzivajucu konjunktivnu normalnu formu formuli. Ak sa podari ulohu vyriesit, previest ziskane riesenie do terminologie povodnej ulohy. Sucastou by mal byt nejaky (napr. naivny alebo heuristicky) algoritmus pre riesenie problemu SAT. Jadro prace je v navrhu jazyka a prekladaci, nie v solveri SAT. literatura: doplnit :-( --znovu najst ---- 4.6 Editor (datovych) binarnych suborov (2005) Len Rocnikovy projekt (2007) Tento editor by mal pomocou konfiguracneho suboru (napr. v XML) porozumiet binarnemu (datovemu) suboru a umoznit uzivatelovi upravovat subor a nasledne ulozit. Pre jednotlive polozky v datovom subore by boli k dispozicii popisy v konfiguracnom subore (napr. vyznam konstant), tzn. uzivatel by nemusel vediet binarnu reprezentaciu. Editor by poskytoval uzivatelske prostredie, ktore by umoznilo nacitat subor a previest ho do zrozumitelnych pojmov, menit subor a vypisat. Mozne typicke pouzitie je editovanie "hlavicky". Datove subory by mohli obsahovat zakladne data ako cisla a retazce (pevne a premenne), dalej bitove polia, urcovanie dlzky usekov, binarne (neurcene) data, opakovanie "blokov" ... Na Bc. pracu by mohli byt integritne omedzenia. Alebo transformacia medzi binarnou a zrozumitelnou (XML) formou. (varianta: N3 notacia) ---- 4.7 Recovery Studio Nevhodne - Prilis lahke. Navrhnut system pre spravu a vyrobu opravnych informacii k suborom a opravovanie poskodenych suborov. Integracia s technikami detekcie chyb (CRC, MD5 ...). Interface bude graficke prostredie (a pripadne prikazova riadka). Technika je zalozena na konecnych okruhoch/telesach?, preto su vhodne zakladne znalosti z algebry. (Su mozne streamove operacie?) (Su mozne delenia blokov? A bloky roznej dlzky?) -------------- X. A dalsie 4.2 XMLGen (2005) Lahke: Len rocnikovy projekt, nie Bc, praca ... 4.3 Interpret Prologu 2006, na ziadost - Petr Svec, nezadane 4.4 Interpret Scheme (Funkc.Programov) 2006 4.5 Podpora L-systemov (na ziadost, 2006) Vojtech Polak, nezadane ------------- 5. UCT a hry, omedzenia ... (2007) 5.1 DP: UCT pre go a ine hry 5.2 DP: Riesenie CSP s vyuziti UCT (UCT pre omedzenia) Vypisane 2007 5.3 DP: UCP pre optimalizacne ulohy 5.4 DP: UCT pre diskretne optimalizacne ulohy 5.5 DP: UCT pre rozvrhovanie 5.6 DP: PN search a omedzenia 5.7 DP: Vyuzivanie lokalnych optimalizacii v prehladavani 5.8 DP: UCT a sprisnujuce sa penalizacie 5.9 DP: UCT a Branch and Bound 5.10.1 DP: Integracia heuristik do uplneho prehladavania stavoveho priestoru 5.10.2 DP: UCT v heuristikach 5.10.3 DP: Specialne heuristiky: Iterative Greedy, lokalne dohladavanie, RAVE, Lokalne vypustenie ... 5.10.4 DP: kopirovanie lokalnych optim a UCT (a pridavanie a vypustanie) 5.11 DP,BP: PN search a pod. 5.11.2 DP: PN search pre otvorene goisticke problemy 5.12 DP: Geneticke programovanie a DSEL 5.13 DP: Ucenie vzorov pre go Vypisane 2007 5.14 DP: Heuristiky pre urcenie poradia premennych 5.20 BC: DSEL pre geneticku evoluciu 5.21 BC: Generovanie tazkych instancii (prikladov) vypisane 2007 Nahodne generovane priklady pre rozhodovacie NP-uplne ulohy typu CSP (Constraint Satisfaction Problem) su obvykle lahko riesitelne, pretoze maju bud prilis vela rieseni alebo ziadne. Prvy pripad nastava, ak je omedzeni malo a druhy, ak je omedzeni (prilis) vela. Tazke instancie problemov (pre rozne typy uloh) sa obvykle vyskytuju pri spravnom pocte omedzeni blizko hranice, kde je instancia riesitelna - neriesitelna. Cielom prace je navrhnut metody a prostredie pre generovanie tazkych instancii (pre urcity typ uloh, napr. vo forme skriptovacieho jazyka). [fazovy prechod, kostra riesenia, zakazovanie rieseni z poolu] [Russel, Norvig: AIMA ch.5] [...] 6.1. Dokazovy kalkulator: ala JAPE Vykonavanie pravidiel, user friendly, (konfigurovatelna logika), zobrazovanie stavu dokazu - ciastocneho, historia schovana vedla: replay, what_if; - integrovat prepisovanie (pravidlo, smer, poziciu). a minule DP: ... ---------------- a dalsie (nevykrystalizovane) ... fyl. stromy gen_b.search distribuovane vypocty distribuovane constrainty waveletove prostredie fraktalova kompresia prostredie pre GA pre koncepty pre reinforcement learning pre riešenie omedzeni - heuristicke - restart a spajanie lokalnych vypoctov - s reinforcement learning - s urcovanim tazkych omedzeni (urcovanie poradia) pre riesenie hlavolamov (a CSP) pre navrh hlavolamov datamining ... Ohodnocovaci funkce v Atari Go (Kudelka 2007) Student navrhne vhodnou reprezentaci pro ohodnocovací funkce pro hru atari-go a následně systém, který umožní oceňovat kvalitu ohodnocovací funkce (bez zásahu člověka). Hrou funkcí proti sobě nalezne dobré ohodnocovací funkce. Častá forma ohodnocovací funkce je vážená lineární kombinace rysů ohodnocované pozice. Vhodné rysy (a jejich kombinace) závisí na konkrétní hře a důležitost rysů se systém má naučit. Prostředí pro hru Atari Go Student má naprogramovat prostředí pro hru Atari-go. Program bude umět hrát proti sobě i člověku. Umožní sehrát, uložit, načíst a přehrát partii. Prostředí bude mít parametry ovlivňující kvalitu hry a dovolí je uživateli nastavit. --2008 "Radovan Duga" inzeraty: prevod plocheho textu do struktury (napr. XML) prekladovy slovnik: naucenie-vytvorenie slovnika z prelozenych viet gen alg. - navrh kniznice/skriptovacieho jazyka --2008Bc/Dp DP: kozelek Aplikujte metodu UCT (Upper Confidence for Trees) [1] na hru Arimaa. Rozeberte varianty a vylepseni UCT popsane v literature [2] a vhodne je adaptujte pro tuto hru. Dale prozkumejte moznosti vyuziti (a integrace) staticke ohodnocovani funkce pro zlepseni hry a moznost a vhodnost jeji integrace s metodou UCT. [1] [2] [3] Russell, Norvig: Artificial Intelligence, A Modern Approach BcP: Aplikujte reinforcement learning DP: kozelek Aplikujte metodu UCT (Upper Confidence for Trees) [1] na hru Arimaa. Rozeberte varianty a vylepseni UCT popsane v literature [2] a vhodne je adaptujte pro tuto hru. Dale prozkumejte moznosti vyuziti (a integrace) staticke ohodnocovani funkce pro zlepseni hry a moznost a vhodnost jeji integrace s metodou UCT. [1] [2] [3] Russell, Norvig: Artificial Intelligence, A Modern Approach -- 2. varianta: (implementačná) Navrhněte a implementujte prostředí pro hru Arimaa a počítačového hráče pro tuto hru, který bude založený na metodě UCT (Upper Confidence for Trees). Vyzkoušejte varianty a rozšíření UCT (popsané v literatuře např. pro hru go [2]) a upravte je pro hru Arimaa. Dále prověřte možnost integrace UCT s heuristickou ohodnocovací funkcí. BcP: Aplikujte reinforcement learning na problém obchodního cestujícího (TSP). Vyzkoušejte různé strategie pro hledání skoro optimální cesty a vliv parametrů na strategie. -- Vytvořte prostředí a porovnejte různé strategie a jejich parametry pro řešení TSP. BCP: Hamplová: Použití vzorů při hře Go Naprogramujte řešič nestabilních situací (semeai) pro hru Go. Navrhněte vhodné reprezentace vzorů pro zachycení typických situací a jejich řešení a integrujte využívání vzorů do řešiče úloh. Rozeberte a porovnejte různé možnosti reprezentace a použití vzorů. -- pozn: vzory s rozložením pravdepodobnosti zahrani - včetně tenuki a bez ohledu na kontext, pro každý bod pravd. výhry, propagace tahů a/nebo rozložení, exploitation vzorů, vzor jako strom do určité hloubky, při učení discounted minulé partie - napr. po blokoch, 2x viac partií, ale minule sa dekrementují/diskontují (dalsie ťahy preberajú relevantnejšiu časť stromu) UCT rozširuje strom o 3 tahy dopredu, (napr. pre prvých 1000 simulácií, pretože aj tak dojde na podriadené vrcholy), využitie: hranie do ťahu súpera (za prehrávajúcu stranu), prvé ťahy možu byť sekvencia-like, zásobník rozpracovaných vzorov, poradie (niekoľkých prvých) nevyskúšaných ťahov preberané z okolia: ded, bratranci (s pravd.) ... Učenie vzorov, učenie ťahov, iné informácie prepočítať na UC level -- varianta: 3 ťahy dopredu a heuristický odhad bez simulácie z int. (0,1), časom začať simulovať viac/všetko, Que: ktoré ťahy/simulácie majú ísť až do konca (a koĺko, a ako často?) -- použitie transpozičných tabuliek (a riadené zahadzovanie hodnot - ála SMA), vraciam hodnotu a spoľahlivosť(?) odhadu (tj. odlíšim tiché pozície), Que: ako to prepočítať na Confidence Level? (a zaintegrovať do UCT) -- idea z nakade: nestabilné pozicie: zahrajem tam, ak sa dialo niečo okolo, propagacia ťahov a rozloženia (napr. formou FPU) -- z lit.: až po ladení parametrov/koeficientov sa vypepšenia začali vyplácať, niektoré vylepšenia sú pre veľké počty simulácií, konštanty sú závislé na počte simulácií, prvotná informácia ide zadať cez RAVE/AMAF: Rapid Action Value Estimation, All Moves As First: určitým ťahom (druhom ťahov) sa priradí počiatočný nenulový počet vyhratých-prehratých simulácií. -- počítanie (aj) Min-Max skore pre vykonané ťahy: použiť pre odhad kvality a usporiadanie ťahov -- propagácia území navrch - uprednostňovať ťahy na hranici územia, CFG: Common Fate Graph 2008: "Tom  Caithaml" DP: oblast Funkcionálního programování 3) Kombinátory/DSEL pro konkrétní doménu a) škálování b) data mining (i pro rekurzivní struktury?) c) Genetické algoritmy d) RDF (a XML) [1] 1) DSEL 2) Návrhové vzory 4) ? Typové systémy pozn: typové systémy pro dokazování (hi-ord) 5) generický Quickcheck ad 2) Návrhové vzory používané pro objektově-orientované programování upravte pro funkcionální programování. Porovnejte je s programátorskými technikami funkcionálního programování. ad 1) Rozeberte postupy používané při tvorbě DSEL - Domain Specific (Embedded) Languages. Zaměřte se na funkcionální programování, případně deklarativní a logické, a rozeberte vhodnost funkcionálních jazyků pro tvorbu DSEL. ad 5) Systém Quickcheck umožňuje testování, zda program splňuje podmínky, které zadá uživatel. Generický Quickcheck generuje typické podmínky (tranzitivita, asociativita, komutativita, distributivita k funkci - např. length, složení ...) a nejsilnější z nich poskytne uživateli. Systém si pamatuje splněné podmínky z minulé verze a retestuje je. ---------- Jakub Tomek OK Analyza zahajeni v2009 Je mozne sa zamerat na niektoru hru dvoch hracov, pripadne jednoho hraca (hlavolamy , riesenie podmienok - constraints) Ak s go nemate skusenosti, asi nie je vhodne, piskvorky su "okoukane", quarto a quoridor je mozny (aj dalsie hry ...), podla druhu ulohy. Ak by ste chcel robit kniznicu zahajeni (tj. analyzu situacie), navrhujem pouzit nejaku kombinaciu metod (Monte Carlo - a varianty, Proof number search, history heuristiku a killery, varianty "playoutov") a preskumat rozumnost a pouzitelnost (niekolkych) jednotlivych variant "ohodnocovania". Pozn.: Povodna uloha bola navrhnuta v trochu inom kontexte, pripadne vysvetlim ustne - protitahy: reakcie na supera (spocitatelne rychlo) - aplikovatelne aj v omedzeniach (constraints) - hranie do tahu supera _ alebo blizky tah, odblokovanie (lambda search) - vyber z viac playoutov, so zabudanim/bez zabudania hry, _s omedzenim zab. - prehladavanie: iteracne depth-first so zabudanim - chcem najslubnejsie dohravky - kde a kedy ukoncit zahajenie? (rozbor situacie)