Název: Vývoj šachového enginu a počítačového protihráče pro Minecraft
Překlad názvu: Development of a Chess Engine and Computer Opponent for Minecraft
Autoři: HRONEK, Vojtěch
Typ dokumentu: Bakalářské práce
Rok: 2024
Jazyk: cze
Abstrakt: [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.
Klíčová slova: algoritmy hlubokého prohledávání; minimax algoritmus; počítačový šachový protihráč; vývoj hry; šachy; chess; computer chess opponent; deep search algorithms; game development; minimax algorithm
Citace: 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

Instituce: Jihočeská univerzita v Českých Budějovicích (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v digitálním repozitáři JČU.
Původní záznam: http://www.jcu.cz/vskp/76829

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-651678