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

završni rad

• Naslov (engleski): Implementation of a Chess Engine Based on Min-max Method With Alpha-beta Pruning
• Autor: Berislav Paradžik
• Mentor: Marin Šilić (mentor)
• Član povjerenstva: Marin Šilić (predsjednik povjerenstva)
• Član povjerenstva: Lucija Šikić (član povjerenstva)
• Član povjerenstva: Davor Vukadin (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2021-07-08, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: zobrist mapiranje; heuristička funkcija; optimizacija
• Ključne riječi (engleski): zobrist hashing; heuristic function; optimization
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:342272
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-14 21:21:07