Original title: Vývoj šachového enginu a počítačového protihráče pro Minecraft
Translated title: Development of a Chess Engine and Computer Opponent for Minecraft
Authors: HRONEK, Vojtěch
Document type: Bachelor's theses
Year: 2024
Language: cze
Abstract: [cze] [eng]
Tato bakalářská práce se zabývá vytvářením šachového enginu a počítačového protihráče v jazyce TypeScript, se kterým může uživatel intuitivně interagovat ve hře Minecraft. Byl implementován generátor legálních i pseudolegálních kroků včetně všech specifických kroků figurek. Vytvořený engine byl testován na generování všech stavů hry, tzv. perft, do hloubky 8. Zároveň byl ověřen na obvyklých testovacích pozicích 2 až 6. Engine prošel všemi testy. Počítačový protihráč byl implementován pomocí minimax algoritmu a minimaxu s - prořezáváním pro lepší výkon. Jeho efektivita byla ukázána srovnáním počtu prohledávaných stavů a dob výpočtu. Prohledávání bylo rozšířeno i o vyhledávání klidných pozic, čímž se zamezuje horizontovému efektu. Dále byl implementován algoritmus pro ukončování hry založený na vzdálenosti krále od kraje hracího pole. Pro vyhodnocování stavů je užita materiálová a poziční hodnotící funkce s obvyklými pozičními tabulkami podle (CPW, n.d.-b). Všechny výpočty potřebné pro počítačového hráče probíhají přímo v Minecraftu. Počítačový protihráč je schopný v naprosté většině případů porazit lidského hráče s hodnocením pohybujícím se okolo 800 ELO podle Chess.com. Díky výpočtům budoucích kroků hry se protihráč nedopouští v hloubce 4 žádných chyb, a aby ho člověk porazil, musel by plánovat více než 4 kroky dopředu. This bachelor's thesis focuses on creating a chess engine along with a computer opponent in TypeScript that allows users to intuitively interact with it in the game of Minecraft. A generator for legal and pseudo-legal moves, including all specific piece moves, was implemented. The created engine was tested for generating all game states, known as perft, up to a depth of 8. It was also verified on common test positions from 2 to 6. The engine passed all tests. The computer opponent was implemented using the minimax algorithm and minimax with - pruning for better performance. Its eiciency was demonstrated by comparing the number of searched states and computation times. The search was extended to include quiet positions with quiescence search to prevent the horizon effect. Additionally, an algorithm for game termination based on the distance of the king from the edge of the board was implemented. The material and positional evaluation function with standard positional tables as per (CPW, n.d.-b) is used for state evaluation. All computations needed for the computer opponent are carried out directly within Minecraft. The computer opponent is capable of defeating human players with a rating around 800 ELO according to Chess.com in the vast majority of cases. Thanks to calculations of future game moves, the opponent does not make any mistakes at a depth of 4, and to defeat it, a human would need to plan more than 4 moves ahead.
Keywords: chess; computer chess opponent; deep search algorithms; game development; minimax algorithm; algoritmy hlubokého prohledávání; minimax algoritmus; počítačový šachový protihráč; vývoj hry; šachy
Citation: HRONEK, Vojtěch. Vývoj šachového enginu a počítačového protihráče pro Minecraft. České Budějovice, 2024. bakalářská práce (Bc.). JIHOČESKÁ UNIVERZITA V ČESKÝCH BUDĚJOVICÍCH. Ekonomická fakulta

Institution: University of South Bohemia in České Budějovice (web)
Document availability information: Fulltext is available in the Digital Repository of University of South Bohemia.
Original record: http://www.jcu.cz/vskp/76829

Permalink: http://www.nusl.cz/ntk/nusl-651678


The record appears in these collections:
Universities and colleges > Public universities > University of South Bohemia in České Budějovice
Academic theses (ETDs) > Bachelor's theses