20.500.12556/RUL-131577 Kombinatorična igra Brstički Sprouts - a combinatorial game 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. 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. brstički nepristranske kombinatorične igre ravninski grafi sprouts impatial games planar graphs true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2021-09-29 15:25:00 2021-09-29 15:25:02 2022-09-10 04:12:34 0000-00-00 00:00:00 2021 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 31602 79848195 Kuhar_Janez_-_Kombinatoricna_igra_Brsticki.pdf Kuhar_Janez_-_Kombinatoricna_igra_Brsticki.pdf 1 6A31AE2A5CBF718938056C211D300E13 79a2e89833c4511b581bf8b5e5fcdabfa5f2dd49b5800b1129bbf746f7c02e39 5e5a97ef-2128-11ec-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=148945 Fakulteta za računalništvo in informatiko 0 0 0