prikaz prve stranice dokumenta Rješavanje problema igre Poveži četiri primjenom umjetne inteligencije
  Download
PDF 1.1 MB
undergraduate thesis
Rješavanje problema igre Poveži četiri primjenom umjetne inteligencije
Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2023. urn:nbn:hr:200:686429
Šimić, Leon
Josip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
Department of Software Engineering
Chair of Visual Computing

Institutional repository: Faculty of Electrical Engineering, Computer Science and Information Technology Osijek

Cite this document

Šimić, L. (2023). Rješavanje problema igre Poveži četiri primjenom umjetne inteligencije (Undergraduate thesis). Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek. Retrieved from https://urn.nsk.hr/urn:nbn:hr:200:686429

Šimić, Leon. "Rješavanje problema igre Poveži četiri primjenom umjetne inteligencije." Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2023. https://urn.nsk.hr/urn:nbn:hr:200:686429

Šimić, Leon. "Rješavanje problema igre Poveži četiri primjenom umjetne inteligencije." Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2023. https://urn.nsk.hr/urn:nbn:hr:200:686429

Šimić, L. (2023). 'Rješavanje problema igre Poveži četiri primjenom umjetne inteligencije', Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, accessed 13 May 2024, https://urn.nsk.hr/urn:nbn:hr:200:686429

Šimić L. Rješavanje problema igre Poveži četiri primjenom umjetne inteligencije [Undergraduate thesis]. Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek; 2023 [cited 2024 May 13] Available at: https://urn.nsk.hr/urn:nbn:hr:200:686429

L. Šimić, "Rješavanje problema igre Poveži četiri primjenom umjetne inteligencije", Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, Osijek, 2023. Available at: https://urn.nsk.hr/urn:nbn:hr:200:686429

Metadata
TitleRješavanje problema igre Poveži četiri primjenom umjetne inteligencije
Title (english)Solving Connect four game using AI
AuthorLeon Šimić
MentorČaslav Livada (mentor)
Committee memberAlfonzo Baumgartner (predsjednik povjerenstva)
GranterJosip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
(Department of Software Engineering)
(Chair of Visual Computing)
Osijek
Defense date and country2023-09-08, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Data Processing
Abstract
Zadatak ovog rada bio je primjenom OpenGL biblioteke napraviti igru Poveži četiri koja omogućuje igranje 2 igrača i protiv računala. Također, implementirani su različiti algoritmi koji predstavljaju umjetnu inteligenciju: osnovni algoritam, minimax, minimax s alpha-beta rezanjem, negamax i negamax s alpha-beta rezanjem. Od tih 5 algoritama trebao se odabrati najbolji. Objašnjena je njihova funkcionalnost i prikazan je implementirani kod. Ključna komponenta u svim ovim algoritmima je heuristička funkcija, koja je važna jer se pomoću nje odlučuje koliko je svaki potez dobar te se onda vrše usporedbe tih poteza. Kako ovi algoritmi imaju različit kod, njihovo vrijeme izvršavanja nije jednako. Na tu vremensku učinkovitost također utječe i vrijednost dubine pretrage stabla igre. Što je ona veća, algoritmi dublje pretražuju grananja u stablu igre te im je potrebno više vremena za izvršavanje. Osim ove vremenske analize, prikazani su pobjednici međusobnih dvoboja algoritama. Iz svih rezultata zaključeno je da je negamax s alpha-beta rezanjem pri dubini pretrage 6 optimalan algoritam.
Abstract (english)
The task of this paper was to create a Connect Four game using the OpenGL library, enabling gameplay between two players and against a computer opponent. Additionally, various algorithms representing artificial intelligence were implemented: basic algorithm, minimax, minimax with alpha-beta pruning, negamax and negamax with alpha-beta pruning. Among these five algorithms, the goal was to determine the most effective one. Their functionality was explained and their implemented code was presented. A key component in all these algorithms is the heuristic function, which plays a crucial role in evaluating the quality of each move, leading to comparisons between these moves. Due to the different code structures of these algorithms, their execution times vary. The efficiency of these algorithms is also influenced by the depth value of the game tree search. A higher depth value leads to deeper exploration of the game tree branches, thereby increasing the execution time. Alongside this time analysis, the winners of algorithm duels were displayed. Based on all the results, it can be concluded that negamax with alpha-beta pruning at a search depth of 6 is the optimal algorithm.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:200:686429
Study programmeTitle: Undergraduate University Study Programme in Computer Engineering
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 resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2023-09-28 07:52:25