Računalna igra Gold Digging Game

undergraduate thesis

• Title (english): Gold Digging Game for the Computer
• Author: Andrija Nakić
• Mentor: Mario Osvin Pavčević (mentor)
• Committee member: Mario Osvin Pavčević (predsjednik povjerenstva)
• Committee member: Kristijan Kilassa Kvaternik (član povjerenstva)
• Committee member: Matija Livaić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-06-30, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: optimizacija; teorija grafova; bojanje grafova; gold-grabbing game; složenost; nezavisni skup; dinamičko programiranje; kromatski broj
• Keywords (english): optimization; graph theory; graph coloring; gold-grabbing game; complexity; independent set; dynamic programming; chromatic number
• Language: croatian
• URN:NBN: urn:nbn:hr:168:813039
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-07-13 10:23:43