Kombinatorična igra Brstički

KUHAR, JANEZ (avtor), 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.

• Jezik: Slovenski jezik
• Ključne besede: brstički, nepristranske kombinatorične igre, ravninski grafi
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2021
• PID: 20.500.12556/RUL-131577
• COBISS.SI-ID: 79848195
• Datum objave v RUL: 29.09.2021

KUHAR, JANEZ, 2021, Kombinatorična igra Brstički [na spletu]. Diplomsko delo. [Dostopano 16 marec 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=131577

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Sprouts - a combinatorial game

Izvleček

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.

• Ključne besede: sprouts, impatial games, planar graphs