Mikroservisna web aplikacija za igranje šaha protiv umjetne inteligencije

master's thesis

• Title (english): Microservice web application for playing chess against artificial intelligence
• Author: Marino Totić
• Mentor: Marina Bagić Babac (mentor)
• Committee member: Marina Bagić Babac (predsjednik povjerenstva)
• Committee member: Vedran Mornar (član povjerenstva)
• Committee member: Tomislav Kos (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-09-20, Croatia

Abstract

Cilj ovog diplomskog rada bio je izraditi umjetnu inteligenciju koja igra šah i inkorporirati ju u web aplikaciju mikroservisne arhitekture kako bi se omogućilo igranje šaha protiv računala i analiziranje šahovskih partija. Umjetna inteligencija je napisana pomoću minimax algoritma sa alfa beta podrezivanjem koristeći programski jezik C++. Budući da sama logika igre, generiranje poteza i evaluacija pozicija zahtjeva ogromnu količinu procesorskih operacija izabran je C++ zbog svoje prepoznatljive brzine u odnosu na ostale moderne objetkno orijentirane programske jezike. Uz određene heurističke funkcije implementirane su optimizacije poput Zobristovog hashiranja kako bi se dodatno poboljšala učinkovitost evaluiranja. Osim same evaluacije pozicija implementirana je u potpunosti logika šaha i sva pravila, kao i generiranje svih mogućih poteza u zadanim pozicijama. Zbog optimizacije korištenja memorije i bržeg pronalaska mogućih poteza korišten je princip bitboard-ova, princip koji pohranjuje informacije o figurama i pozicijama u binarnom obliku u 64 bita. Na taj način se korištenje vremenski skupih operacija poput petlji zamijenilo klasičnim logičkim operacijama. Rad prikazuje rezultate opisanih optimizacija na različitim dubinama evaluacije brojčano i vizualno. Za izradu aplikacije korištene su tehnologije Express.js, web framework Node.js-a, React.js, PostgreSQL, MongoDB i mnoge druge dok je za povezivanje Docker kontejnera i razmjenu poruka između backend-a i umjetne inteligencije korištena ZeroMQ.

Abstract (english)

The purpose of this master’s thesis was to develop artificial intelligence capable of playing chess (chess engine) and incorporate it into a microservices architecture web application, enabling users to play chess against a computer and analyse chess games. The chess engine was implemented using the minimax algorithm with alpha-beta pruning in the C++ programming language. Given that the game’s logic, move generation, and position evaluation require a significant number of computational operations, C++ was chosen due to its well-known speed compared to other modern object-oriented programming languages. In order to boost the efficiency of position evaluation, apart from heuristic functions, the implementation included various optimizations, such as Zobrist hashing. Apart from evaluating positions, the entire set of rules and chess logic, along with the generation of all potential moves within specified positions, were also implemented. To optimize memory usage and the search for possible moves, the bitboard principle was employed. This principle stores information about pieces and their positions in binary form within 64 bits, replacing time-consuming operations with classic logical operations. The thesis presents the results of the described optimizations numerically and visually at various evaluation depths. For application development, technologies such as Express.js, the Node.js web framework, React.js, PostgreSQL, MongoDB, and others were utilized. ZeroMQ was used to enable communication between Docker containers and exchange messages between the engine and the back-end.

• Keywords: Šah; umjetna inteligencija; minimax algoritam; alfa-beta podrezivanje; C++; web aplikacija
• Keywords (english): Chess; artificial intelligence; minimax algorithm; alpha-beta pruning; C++; web application
• Language: english
• URN:NBN: urn:nbn:hr:168:208106
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2024-03-28 07:55:59