Solving Connect four game using AI

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.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