Razvoj računalnog igrača za igru šah

završni rad

• Naslov (engleski): Computer-based Chess Player Development
• Autor: Matej Ištuk
• Mentor: Marko Čupić (mentor)
• Član povjerenstva: Marko Čupić (predsjednik povjerenstva)
• Član povjerenstva: NIna Drobac (član povjerenstva)
• Član povjerenstva: Filip Karlo Došilović (č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: 2023-07-06, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovom radu izrađen je računalni igrač za igru šah pomoću programskog jezika Java.
Sustav koji ostvaruje računalnog igrača sastoji se od: računalne reprezentacije igre, generatora poteza, pretraživača stabla igre, funkcije vrednovanja i knjige otvaranja. Računalni igrač određuje najbolji potez za dano stanje igre pomoću pretrage prostora stanja nadomještenog heurističkom funkcijom vrednovanja.
Reprezentacija šahovske ploče izvedena je pomoću bitploča. Pretraga prostora stanja ostvarena je algoritmom negamax te kako bi se ubrzala, korištene su tehnike podrezivanja alfa-beta, transpozicijskih tablica i Zobristovog raspršivanja. Znanje o igri je igraču preneseno preko raznih heuristika vrednovanja stanja igre i odabira redoslijeda poteza pri pretraživanju prostora stanja.

Sažetak (engleski)

The result of this paper is an engine for the game of chess that was created using the Java programming language. The system that realizes the computer player consists of a computer representation of the game, a move generator, a game tree searcher, an evaluation function, and an opening book. The chess engine determines the best move for a given game state by searching the state space, aided by a heuristic evaluation function.
The representation of the chessboard is made using bitboards. The search of the state space was realized with the negamax algorithm, and the following techniques were used in order to speed it up: alpha-beta pruning, transposition tables, and Zobrist hashing. Knowledge about the game is given to the player through various heuristics for evaluating the state of the game and sorting moves during the state-based search.

• Ključne riječi: računalni igrač; šah; pretraživanje prostora stanja; minimax; negamax; podrezivanje alfa-beta; transpozicijska tablica; Zobristovo raspršivanje; heuristika; vrednovanje stanja igre
• Ključne riječi (engleski): computer player; chess; chess engine; state based search; minimax; negamax; alfa-beta pruning; transposition table; Zobrist hashing; heuristic; game state evaluation
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:059661
• 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-10-11 09:05:46