Kombinatorična igra Brstički

KUHAR, JANEZ (author), Fijavž, Gašper (mentor)

V delu obravnavamo igro Brstički (angl. Sprouts). Igralca na listu papirja izmenjaje rišeta poteze in z njimi dodajata nove brstičke. Zmagovalec je tisti, ki nariše zadnjo potezo. Brstički so nepristranska kombinatorična igra in zato po Sprague-Grundyjevem izreku enakovredni igranju igre Nim. Osnovo za modeliranje igre predstavljajo ravninski grafi. Kombinatorično lahko igro opišemo kot ravninski graf, kjer so brstički vozlišča, poteze pa povezave. Geometrijsko lahko poteze predstavimo z Bézierjevimi zlepki. Naš prispevek je pajčevina. Gre za navidezne povezave na začetku igre, ki brstičke povežejo v vpeto drevo. Pajčevina zagotavlja povezanost slike igre skozi celo igro, s čimer je vsaka poteza nedvoumno določena. V sklopu dela smo izdelali tudi aplikacijo za igranje.

• Language: Slovenian
• Keywords: brstički, nepristranske kombinatorične igre, ravninski grafi
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2021
• PID: 20.500.12556/RUL-131577
• COBISS.SI-ID: 79848195
• Publication date in RUL: 29.09.2021

KUHAR, JANEZ, 2021, Kombinatorična igra Brstički [online]. Bachelor’s thesis. [Accessed 16 March 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=131577

Secondary language

• Language: English
• Title: Sprouts - a combinatorial game

Abstract

Sprouts is a paper-and-pencil game where two players take turns connecting sprouts and adding a new sprout along the connection. The player who makes the last move wins. The game of Sprouts is an impartial combinatorial game and thus by Sprague-Grundy theorem equivalent to a game of Nim. Planar graphs are the basis for a computer representation of Sprouts. Combinatorically, a game is a planar graph with sprouts as its vertices and moves as its edges. In addition, player's moves also have geometric components. Each move is a sequence of Bézier splines. Our contribution is the cobweb. A cobweb is comprised of the virtual edges which connect the initial sprouts into a spanning tree. The cobweb guarantees uniqueness of moves by maintaining a connected structure. As part of this work, a multi-platform application for playing Sprouts has been developed.

• Keywords: sprouts, impatial games, planar graphs