Botníček

Botníček je vývojové prostředí rozšiřující možnosti řízení dialogu v jazyce AIML. Jde o zajímavý výsledek mé bakalářské práce, vedené na Matematicko-fyzikální fakultě Univerzity Karlovy v Praze.

Jazyk AIML vznikl jako nástroj na tvorbu jednoduchých konverzačních agentů. Proto postrádá některé z vlastnosti pokročilých dialogových systémů. Jednou z nich je podpora pro řízení dialogu. Ta je přitom užitečná v mnoha aplikacích, v nichž byl jazyk díky své popularitě nasazen. Práce řeší problém implementace řízení dialogu v čistém AIML. A to nasazením rozšířených přechodových sítí při návrhu a generování zdrojového kódu. Jejím výsledkem je vývojové prostředí, které podporuje zvolený postup, a podstatně tak usnadňuje návrh složitějších robotů, aniž by bylo nutné uchýlit se k rozšíření standardního interpretu.

The AIML language was created with a goal of authoring of simple chat bots. Therefore it lacks some of the features of advanced dialog systems. One of them is the support for dialog management, which is beneficial in many applications that the language has already spread into due to its popularity. This thesis solves the problem of dialog management implementation in pure AIML by using the augmented transition networks in design and code generation. It results in a development environment that supports the chosen solution, thus facilitating the design of more complex bots, while maintaining compatibility with standard interprets.

Její text, zdrojové soubory a další náležitosti jsou k dispozici na univerzitních stránkách ZDE.

Plakát práce

Plakát práce

Pazaak Den

Herní plán - ukazatel skóre, jména hráčů, vyložené a speciální karty.

Herní prostředí v Pazaak Den

Pazaak je varianta karetní hry blackjack či oko, jež se poprvé objevila ve videohře Star Wars Knights of the Old Republic. V základu je pro dva hráče. Cílem každého z nich je dosáhnout s pomocí karet, které si tahají z balíčku, lepší hodnoty než soupeř. K tomu jim pomáhají speciální karty, které drží v ruce, a kterými mohou upravovat hodnotu součtu.

V programu Pazaak Den je pazaak implementován ve dvou verzích. Ve volné hře má hráč k dispozici prakticky neomezené množství a druhy speciálních karet do ruky. Z nich si vybere 10 a z těch se mu náhodně do ruky vylosuje 5. S těmi hraje proti podobně vybavenému počítačovému protivníkovi.

V režimu kariéra má za úkol popořadě porazit celé osazenstvo pazaakového doupěte. Začíná se základním balíčkem speciálních karet a menší sumou republikových kreditů (peněz) na nákup dalších. Poté se stejným systémem jako ve volné hře utká se všemi protivníky s tím, že po každém zápasu má šanci svůj balíček speciálních karet rozšířit za vydělané peníze. V případě výhry obdrží 1 000 kreditů, v případě prohry nic a musí nastoupit proti stejnému soupeři znovu.

Program vznikl jako zápočtová práce na předmět Programování v C++ na MFF UK. Dokumentace je zde. Zdrojové soubory lze stáhnout zde. Program samotný zde.

Autodráha

Dětská autodráha na zeleném pozadíJednoduchá závodní hra napsaná v Javě 6, která vznikla jako zápočtový program na předmět Java. Zde je stručná uživatelská dokumentace, zde jsou zdrojové kódy s build.xml pro Ant, a zde přímo spustitelný JAR archiv. Hodně zábavy!

Aktualizace: Opraveny zásadní chyby (nefunkční simultánní stisk a držení kláves, špatné kódování názvů drah) a doplněna dokumentace o popis formátu autodráhy.

Polleva – vytváření webových anketek

Screenshot z aplikace PollevaV rámci předmětu Internet jsem vypracoval jednoduchou zápočtovou aplikaci s využitím XHTML, CSS, PHP, MySQL a JavaScriptu, která pomáhá uživatelům vytvářet a sdílet jednoduché webové anketky. Na výsledek své kvapné práce nejsem moc hrdý, nicméně aplikace funguje. Není ovšem rozhodně určená k byť jen trochu vážnějšímu nasazení, protože postrádá některé důležité bezpečnostní mechanismy zabraňující zneužití. Její demonstrační verze běží na www.polleva.php5.cz. Můžete si jí vyzkoušet, stačí se zaregistrovat a na e-mail vám přijde heslo (které lze po přihlášení měnit). V aplikaci můžete vytvářet anketky, spravovat je, nastavovat jejich vlastnosti, přiřazovat jim různé styly, které si sami upravíte. Lze nastavovat Ukázka anketkymíru zabezpečení vůči opakovaným hlasováním, možnost výběru více odpovědí a další drobnosti. Výsledek pak můžete přes odkaz či vygenerovaný kód rámečku vložit do jiné stránky dle libosti.

Zdrojové kódy se nacházejí zde, stručná dokumentace pak zde.

Převod formule do prenexního normální tvar (a jádra do CNF či DNF)

Každou formuli predikátové logiky 1. řádu lze převést na formuli v tzv. prenexním normálním tvaru, která je původní formuli ekvivalentní. Formule v tomto tvaru začíná kvantifikátory (obecné a existenční), které kvantifikují za nimi následující jádro. Jádro je otevřená formule, tj. formule, která neobsahuje kvantifikované proměnné. Pro převod formule do prenexního tvaru existuje několik málo pravidel, které formuli rekurzivně převádějí.

Přehled prenexních pravidel

Prenexní pravidla

Jádro lze dále převést do konjunktivního, resp. disjunktivního normálního tvaru (CNF, resp. DNF). Formule v CNF (DNF) je stručně řečeno konjunkce disjunkcí (disjunkce konjunkcí). Opět s pomocí několika jednoduchých pravidel lze ve třech krocích každou otevřenou formuli do normálního tvaru převést.

Přehled pravidel převodu do CNF a DNF

Pravidla převodu do CNF a DNF

Výše uvedené převody formulí byly předmětem mé zápočtové práce z předmětu Neprocedurálního programování. Jde o program v Prologu, který ke svému spuštění vyžaduje nainstalovaný interpret SWI-Prolog, který je dostupný pro všechny rozšířené platformy.

Hermiona používá Prolog

Útržek zdrojového kódu

Závěrečná hádanka s lektvary z knihy Harry Potter a Kámen mudrců (kterou Hermiona úspěšně vyřešila, a tak přispěla porážce Voldemorta i výhře školního poháru pro Nebelvír) vyřešená v Prologu. Stačí si nainstalovat interpret (například SWI-Prolog), spustit program a zadat

riddle(Jedna, Dva, Tri, Ctyri, Pet, Sest, Sedm).

včetně tečky. Sedí na verzi na Pottermore.com.

Datová struktura skip list

Skip list je datová struktura dosahující s vysokou pravděpodobností logaritmické časové složitosti pro běžné operace (přidání prvku, odebrání, nalezení podle klíče). Indexovaný skip list je jeho rozšířením, které navíc umožňuje i přístup k prvkům pomocí indexů v logaritmickém čase.

Ilustrace rozvržení spojů ve skip listu

Ilustrace rozvržení spojů ve skip listu

Je zajímavou alternativou vyvážených vyhledávacích stromů pro některé druhy aplikací (lze například dobře rozšířit pro užití ve vícevláknových aplikacích), navíc se oproti nim díky své eleganci poměrně snadno naprogramuje.
Předmětem mé zápočtové práce na předmět Algoritmy a datové struktury II byla právě implementace základní verze této struktury.