Original title: Algoritmy strojového hraní Hackenbushe s využitím surreálních čísel
Translated title: Algorithms for Automated Play of Hackenbush Using Surreal Numbers
Authors: Matyáš, Václav ; Veigend, Petr (referee) ; Zbořil, František (advisor)
Document type: Bachelor's theses
Year: 2026
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tato bakalářská práce se zabývá návrhem a implementací dvou metod převodu kombinatorické hry do algebraické formy. První metoda se zaměřuje na specifickou hru Hackenbush, která obsahuje červené a modré hrany. Pozici v této hře převádí na dyadické číslo rekurzivním procházením možných tahů levého a pravého hráče. Druhá metoda převádí kombinatorickou hru na krátkou hru. Tento převod je nejprve demonstrován na hře Hotpotch (Hackenbush se zelenou hranou), algoritmus je poté zobecněn a je navrženo rozhraní, které může libovolná kombinatorická hra implementovat. Správnou implementací tohoto rozhraní je pak možné převést libovolnou kombinatorickou hru do formy krátké hry. Pro obě metody je následně vytvořeno grafické rozhraní, společně s modulem krátkých her v jazyce Python. This bachelor's thesis deals with the design and implementation of two methods for converting a combinatorial game into algebraic form. The first method focuses on the specific game of Hackenbush, which contains red and blue edges. It converts a position in this game into a dyadic number by recursively traversing the possible moves of the left and right player. The second method converts a combinatorial game into a short game. This conversion is first demonstrated on the game of Hotpotch (Hackenbush with a green edge), after which the algorithm is generalised and an interface is proposed, which any combinatorial game can implement. By correctly implementing this interface, it is then possible to convert any combinatorial game into the form of a short game. For both methods, a graphical interface is subsequently developed, together with a short game module in Python.
Keywords: canonical form; combinatorial game theory; dyadic numbers; Hackenbush; Hotpotch; memoization; short games; solver; dyadická čísla; Hackenbush; Hotpotch; kanonická forma; kombinatorická teorie her; krátké hry; memoizace; řešič

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/258897

Permalink: http://www.nusl.cz/ntk/nusl-775390


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses