diplomsko delo
Janez Kuhar (Avtor), Gašper Fijavž (Mentor)

Povzetek

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.

Ključne besede

brstički;nepristranske kombinatorične igre;ravninski grafi;računalništvo in informatika;univerzitetni študij;diplomske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [J. Kuhar]
UDK: 004:51(043.2)
COBISS: 79848195 Povezava se bo odprla v novem oknu
Št. ogledov: 261
Št. prenosov: 38
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Sprouts - a combinatorial game
Sekundarni povzetek: 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.
Sekundarne ključne besede: sprouts;impatial games;planar graphs;computer and information science;diploma;Računalništvo;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS): Diplomsko delo/naloga
Študijski program: 1000468
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 38 str.
ID: 13587571