Razvoj računalnog igrača za igru šah

undergraduate thesis

• Title (english): Computer-based Chess Player Development
• Author: Matej Ištuk
• Mentor: Marko Čupić (mentor)
• Committee member: Marko Čupić (predsjednik povjerenstva)
• Committee member: NIna Drobac (član povjerenstva)
• Committee member: Filip Karlo Došilović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-07-06, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

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