Název: Implementace hry Sprouts
Překlad názvu: Implementation of the Sprouts game
Autoři: Čížek, Tomáš ; Balko, Martin (vedoucí práce) ; Pangrác, Ondřej (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2021
Jazyk: eng
Abstrakt: [eng] [cze]
Sprouts is a two-player pencil-and-paper game invented by John Conway and Michael Paterson in 1967. In the game, the players take turns in joining dots by curves according to simple rules, until one player cannot make a move. The Game of Sprouts is very popular and simple-looking, so it may come as a surprise that there are essentially no AI Sprouts players available. This lack of computer opponents is caused by the fact that the game hides a surprisingly high combinatorial complexity and implementing it involves fascinating programming challenges. We overcome all the implementation barriers and create the first user-friendly Sprouts application with a strong artificial intelligence after more than 50 years of the existence of the game. In particular, we combine results from the theory of nimbers with new methods based on Delaunay triangulations and crossing-preserving force-directed algorithms to develop an AI Sprouts player which plays a perfect game on up to 11 spots. 1 Sprouts je hra pro dva hráče s tužkou a papírem, kterou vymysleli John Conway a Michael Paterson v roce 1967. Hráči se v ní střídají ve spojování teček pomocí křivek podle jednoduchých pravidel, dokud jeden z hráčů nemůže udělat tah. Přestože je Sprouts velice populární a zdánlivě jednoduchá, nejsou dostupné téměř žádné UI hrající Sprouts. Tento nedostatek počítačových protivníků je způsobený tím, že hra skrývá překvapivě vysokou kombinatorickou složitost a její implementace zahrnuje fascinující programovací výzvy. Podařilo se nám překonat všechny tyto implementační bariéry a po 50 letech existence hry jsme vytvořili první uživatelsky přívětivou aplikaci Sprouts, která obsahuje silnou umělou inteligenci. Zkombinovali jsme zejména výsledky teorie nimberů s novými meto- dami, které jsou založené na Delaunayových triangulacích a force-directed algoritmech zachovávající počet křížení, abychom dokázali vytvořit UI hráče, který hraje perfektně až na jedenácti bodech. 1
Klíčová slova: Sprouts|Kombinatorická hra|Rovinné grafy|Umělá inteligence; Sprouts|Combinatorial game|Planar graphs|Artificial intelligence

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/148335

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-451984


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce