Rješavanje problema pametnog agenta za igru šah metodama pretraživanja prostora stanja

master's thesis

• Title (english): Solving the problem of a smart agent for the game of chess using state space search methods
• Author: Leo Goršić
• Mentor: Marko Đurasević (mentor)
• Committee member: Marko Đurasević (predsjednik povjerenstva)
• Committee member: Domagoj Jakobović (član povjerenstva)
• Committee member: Nikolina Frid (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2025-02-19, Croatia

Abstract

Igra Šah je jedna od najpoznatijih i najpopularnijih igara na svijetu. Šahovski programi
su od samih početaka računalne znanosti bili jedan od zahtjevnijih i zanimljivijih problema.
Iako je šah igra s pravilima koja su jednostavna, složenost igre dolazi iz velikog
broja mogućih poteza i pozicija. Međutim napretci u računalnoj snazi i algoritmima
omogućili su razvoj šahovskih programa koji su danas nemogući za pobijediti, čak i od
najboljih ljudskih igrača. Ovaj diplomski rad se bavi... More implementacijom šahovskog programa
koji koristi algoritam minimax pretrage s alfa-beta podrezivanjem i ostalim optimizacijama
opisanim u ovom radu. Program je implementiran u programskom jeziku C te koristi grafičko
korisničko sučelje implementirano u programskom jeziku Python koristeći biblioteku Pygame.
U ovom radu opisane su neke od ključnih tehnika i algoritama koji se koriste u šahovskim programima.
Opisane su tehnike pretrage, optimizacije i mjerenja performansi. Less

Abstract (english)

The game of Chess is one of the most famous and popular games in the world. Chess programs have been one of the most challenging and interesting problems since the beginning of computer science.
Although chess is a game with simple rules, the complexity of the game comes from the large number of possible moves and positions. However, advances in computing power and algorithms have enabled the development of chess programs that are now impossible to defeat, even by the best human... More players. This thesis deals with the implementation of a chess program that uses the minimax search algorithm with alpha-beta pruning and other optimizations described in this paper. The program is implemented in the C programming language and uses a graphical user interface implemented in the Python programming language using the Pygame library.
This paper describes some of the key techniques and algorithms used in chess programs.
Search, optimization, and performance measurement techniques are described.
Less

• Keywords: Šah; Minimax; Alfa-beta podrezivanje; Quiescence pretraga; Transpozicijske tablice; Zobrist hash funkcija; Pygame
• Keywords (english): Chess; Minimax; Alpha-beta pruning; Quiescence search; Transposition tables; Zobrist hash function; Pygame
• Language: croatian
• URN:NBN: urn:nbn:hr:168:870346
• 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: Open access
• Created on: 2025-03-12 11:08:24