Bachelor's Thesis

Vytvoření online hry Scrabble s možností analýzy partie pomocí umělé inteligence

Final Thesis 3.53 MB

Author of thesis: Bc. Michal Pavlíček

Acad. year: 2024/2025

Supervisor: Ing. Lukáš Semerád, Ph.D.

Reviewer: Ing. Gabriela Nečasová, Ph.D.

Abstract:

This bachelor's thesis deals with the design and implementation of an online Scrabble game with integrated artificial intelligence for game analysis. The thesis describes the development of a web application enabling online gameplay, playing against a computer, and analysis of completed games. The implemented artificial intelligence uses the GADDAG data structure for fast move generation, Monte Carlo simulations, and Alpha-beta pruning for optimization of game strategies. Experiments confirm performance improvements when using advanced methods compared to a simple greedy approach. The resulting web application is freely available and enables playing Scrabble online with a modern user interface.

Keywords:

Scrabble, artificial intelligence, Monte Carlo, Alpha-beta pruning, GADDAG, Rust, SvelteKit, FastAPI

Date of defence

20.06.2025

Result of the defence

Defended (thesis was successfully defended)

znamkaAznamka

Grading

A

Process of defence

Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm A.

Topics for thesis defence

  1. Jakým způsobem je řešeno škálování serverové části aplikace v případě vysoké zátěže (např. stovky paralelních her)?
  2. Vyhodnotil jste implementovanou AI i proti člověku? Jaká je její úspěšnost?

Language of thesis

Czech

Faculty

Fakulta informačních technologií

Department

Department of Intelligent Systems

Study programme

Information Technology (BIT)

Composition of Committee

prof. RNDr. Alexandr Meduna, CSc. (předseda)
Ing. Martin Hrubý, Ph.D. (člen)
Ing. Tomáš Milet, Ph.D. (člen)
Ing. Zbyněk Křivka, Ph.D. (člen)
Ing. Marcela Zachariášová, Ph.D. (člen)

Supervisor’s report
Ing. Lukáš Semerád, Ph.D.

Vzhledem k bezproblémové spolupráci, ukázkové samostatnosti studenta a skvělému výsledku navrhuji práci hodnotit stupněm výborně (A).

Evaluation criteria Verbal classification
Informace k zadání

Ačkoliv se zadání jeví jako standardně obtížné, student nechtěl pouze implementovat existující nástroje, ale vytvořit si kompletní řešení sám. Z toho důvodu bylo zadání změněno v průběhu. Z důvodu kompletní tvorby webové aplikace proto hodnotím zadání jako mírně náročnější. Výsledné řešení je velice zdařilé a dokonce i veřejně přístupné.
Práce s literaturou

Student sháněl literární zdroje samostatně, s jejich výběrem souhlasím.
Aktivita během řešení, konzultace, komunikace

Se studentem jsme komunikovali na pravidelné bázi po celou dobu spolupráce. První konzultace proběhly již před rokem.
Aktivita při dokončování

Práce byla dokončena s předstihem a její finální text s aplikací mi byl včas představen.
Publikační činnost, ocenění

Výsledné dílo je veřejně dostupné na webových stránkách studenta.
Points proposed by supervisor: 95

Grade proposed by supervisor: A

Reviewer’s report
Ing. Gabriela Nečasová, Ph.D.

Pěkná práce. Na hodnocení má největší vliv kvalita práce a výsledků.
Dále velmi pozitivně hodnotím kapitolu 4, která pojednává o návrhu a pbsahuje i důkladnou analýzu existujících řešení. Kapitola 5 se věnuje podrobnému popisu implementace a kapitola 6 evaluaci zvoleného řešení. Dále oceňuji, že student již do práce uvedl možná budoucí rozšíření (závěr kapitoly 6).


Doporučuji práci k obhajobě a práci hodnotím stupněm A (90 bodů).

Evaluation criteria Verbal classification Points
Náročnost zadání

Evaluation level: průměrně obtížné zadání
Prezentační úroveň technické zprávy

Práce vykazuje vysokou prezentační úroveň. Práce je velmi dobře strukturovaná, logicky členěná a jednotlivé kapitoly na sebe přirozeně navazují. Text je uspořádán podle jasné a přehledné osnovy. Začíná teoretickým úvodem do pravidel Scrabblu a dále postupuje přes metody umělé inteligence, návrh architektury systému, implementaci, až po testování a závěr. 

 95
Formální úprava technické zprávy

Formální úprava je na dobré úrovni, ovšem lze v ní najít několik drobných jazykových nedostatků, které mírně snižují její formální úroveň. Níže uvádím nejvýznamnější z nich:

  • Podsekce 2.2.1 - Bodování: místo čtyř odrážek by bylo lepší použít jednu větu. Odrážky dávají smysl v případě delších vět. Podobné jeto v podsekci 2.2.2 a 3.4.1.
  • Sekce 3.1 - „Nevlézt se“ je výraz běžný v mluvené češtině, ale v odborném nebo formálním textu působí nepatřičně. Např. věta: "Na jeho displej se nevlezla celá herní plocha..." by měla být nahrazena, např. "Na jeho displej se nevešla celá herní plocha" apod. Obdobná situace se vyskytuje i v sekci 3.2.
  • V některých částech textu je typografikcky nejednotná sazba anglických ekvivalentů k českým slovům (neproporciální písma, použití uvozovek nebo normální font). Opět se jedná spíše o detail.
  • V některých částech textu se vyskytuje poměrně hodně odstavců, což může působit mírně rušivě. Nicméně se jedná o detail, který nesnižuje kvalitu práce.
  • Podsekce 4.4.1 obrat "malé mobilní obrazovky" možná není zcela přesný, domnívám se, že jde spíše o rozlišení. 
  • V práci se vyskytují hovorovější výrazy, např. "vyskakovací okno", "nevleze se na obrazovku", "achievementů", "embedded systémy", "na chvostu souboru", "kvůli obrovskému času", atd.
  • Pár překlepů (nepoužití velkách písmen) ve slovech "javascript", "webassembly", "sveltekit", apod.
  • V sekci 6.2 jsou v tabulkách desetinná čísla sázena s tečkou, kdežto v textu s čárkou, což působí rušivě. 
 80
Realizační výstup

Student navrhl a implementoval plnohodnotnou webovou aplikaci pro hru Scrabble, která zahrnuje:

  • online hru více hráčů,

  • hru proti umělé inteligenci,

  • a možnost analýzy odehraných partií.

Systém zahrnuje klientskou část (SvelteKit), serverovou část (FastAPI v Pythonu) a výkonný backend pro AI v jazyce Rust. Architektura je promyšlená, modulární a srozumitelná. Použité algoritmy (včetně GADDAG, Monte Carlo simulací a Alfa-beta ořezávání) byly správně zvoleny vzhledem k požadované funkcionalitě. Aplikace byla reálně nasazena na webu skrebl.cz což potvrzuje její funkčnost a použitelnost.

Dokumentace implementace je velmi podrobná, přehledná a pokrývá jak architektonické rozhodnutí, tak konkrétní algoritmické řešení. Nechybí diagramy, pseudokód, příklady datových struktur (např. GADDAG), popis jednotlivých komponent a ukázky použití. Popis je dostatečně technický, přesto srozumitelný i méně zasvěcenému čtenáři. Dokumentace splňuje akademické i praktické standardy.

Student provedl sérii testů:

  • uživatelské testování aplikace (včetně zpětné vazby),

  • evaluaci výkonnosti jednotlivých strategií AI pomocí experimentů,

  • srovnání různých algoritmů pro generování a vyhodnocování tahů.

Celkově hodotím realizační výstup práce za velmi zdařilý.

 95
Využitelnost výsledků

Práce lze charakterizovat jako rozšiřující již publikované výsledky, zejména v oblasti algoritmů pro Scrabble a metod umělé inteligence, s významnými implementačními inovacemi, vlastním návrhem architektury online platformy, a s praktickým přesahem díky funkční aplikaci dostupné veřejnosti online.

Student přizpůsobil existující AI metody pro českou jazykovou mutaci Scrabblu (což je méně prozkoumaná oblast), navrhl funkční integraci komplexní AI do reálné webové aplikace, provedl vlastní evaluaci účinnosti jednotlivých strategií, a vytvořil modulární systém připravený pro budoucí rozšíření (např. přizpůsobení pro jiné jazyky, trénink AI na základě historických her).

Výsledná webová aplikace má okamžité praktické využití:

  • pro běžné hráče Scrabble jako tréninkový nebo analytický nástroj,

  • pro organizátory soutěží jako platforma pro online turnaje,

  • a potenciálně jako výuková pomůcka při výuce AI a programování herních agentů.
Rozsah splnění požadavků zadání

Evaluation level: zadání splněno

Všechny body zadání jsou splněny.
Rozsah technické zprávy

Evaluation level: přesahuje obvyklé rozmezí

Text je rozsáhlejší (přibližně 90 normostran), ovšem je to v pořádku vzhledem k charakteru práce. 
Práce s literaturou

Student zvolil literaturu vhodnou k dané problematice, citoval z 37 zdrojů. Všechny citace jsou úplné a v souladu se zvyklostmi a normami. Zdroje jsou relevantní.

 90
Topics for thesis defence:
  1. Jakým způsobem je řešeno škálování serverové části aplikace v případě vysoké zátěže (např. stovky paralelních her)?
Points proposed by reviewer: 90

Grade proposed by reviewer: A

Responsibility: Mgr. et Mgr. Hana Odstrčilová