Implementacija šahovskog stroja zasnovana na metodi min-max pretraživanja s alfa-beta podrezivanjem

undergraduate thesis

• Title (english): Implementation of a Chess Engine Based on Min-max Method With Alpha-beta Pruning
• Author: Berislav Paradžik
• Mentor: Marin Šilić (mentor)
• Committee member: Marin Šilić (predsjednik povjerenstva)
• Committee member: Lucija Šikić (član povjerenstva)
• Committee member: Davor Vukadin (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-08, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Tema rada je implementacija šahovskog stroja zasnovana na metodi min-max pretraživanja s alfa-beta podrezivanjem. U radu su implementirane dodatne optimizacije alfa beta podrezivanja i spremanja izračunatih vrijednosti stanja zobrist mapiranjem. Koraci razvijanja šahovskog stroja podijeljeni su na poglavlja. U prvim poglavljima obrađuje se implementacija šaha i min-max pretraživanja. Nakon toga slijede poglavlja s alfa-beta podrezivanjem te dodatnim optimizacijama stroja. Svaka optimizacija je testirana, njeni rezultati su uspoređeni s rezultatima bez optimizacije. Nakon implementacije svih optimizacija, stroj je testiran na raznim šahovskim primjerima. U većini slučajeva stroj uspijeva pronaći točna rješenja.

Abstract (english)

The topic of the paper is the implementation of a chess engine based on the min-max search algorithm with alpha-beta pruning. Chess engine developed in this paper implements additional optimizations of alpha beta pruning and mapping the calculated values ​​of the chess board state by zobrist keys. The steps of developing a chess engine are divided into chapters. The first chapters deal with the implementation of chess and min-max search algorithm. Followed chapters deal with alpha-beta pruning and additional engine optimizations Each optimization was additionally tested. The results of each optimization was compared with the results without optimization. After implementing all the optimizations, the chess engine was tested on various chess examples. In most cases, the engine managed to find the right solution.

• Keywords: zobrist mapiranje; heuristička funkcija; optimizacija
• Keywords (english): zobrist hashing; heuristic function; optimization
• Language: croatian
• URN:NBN: urn:nbn:hr:168:342272
• 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-01-14 21:21:07