Računalna igra Gold Digging Game

završni rad

• Naslov (engleski): Gold Digging Game for the Computer
• Autor: Andrija Nakić
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Kristijan Kilassa Kvaternik (član povjerenstva)
• Član povjerenstva: Matija Livaić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-06-30, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Za realizaciju ovog završnog zadatka implementirana je računalna igra Gold Grabbing Game, koja ilustrira istoimeni problem. Za strategiju računala predviđene su tri razine: laka, srednja i teška. Razine se razlikuju u broju koraka koje računalo računa unaprijed i u broju vrhova stabla. Za svaki list stabla računalo računa koja je vjerojatnost da će pobijediti ako ga izabere. Optimizacija se provodi zbog određivanja poteza koji vodi do pobjede računala.
U mom završnom radu opisivao sam problem dodjele (eng. assigment problem) i problem k-bojanja vrhova grafa. Opisi problema uključuju opis algoritama poznatih rješenja, analizu vremenske složenosti i klasifikaciju složenosti.

Sažetak (engleski)

To realize this final task, the computer game Gold Grabbing Game was implemented, which illustrates the problem of the same name. There are three levels for the computer strategy: easy, medium and hard. The levels differ in the number of steps that the computer calculates in advance and in the number of tree vertices. For each leaf of the tree, the computer calculates the probability that it will win if it is chosen. Optimization is carried out in order to determine the optimal move that should lead to the victory of the computer.
In my final paper, I described the assignment problem and the k-coloring problem of graph vertices. Problem descriptions include the description of known solution algorithms, time complexity analysis, and complexity classification.

• Ključne riječi: optimizacija; teorija grafova; bojanje grafova; gold-grabbing game; složenost; nezavisni skup; dinamičko programiranje; kromatski broj
• Ključne riječi (engleski): optimization; graph theory; graph coloring; gold-grabbing game; complexity; independent set; dynamic programming; chromatic number
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:813039
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-07-13 10:23:43