Analýza platných ťahov v hre Scrabble

Abstract

The bachelor thesis aims to create a program for the analysis of moves in Scrabble. The language dictionary is stored as a GADDAG structure, which enables fast searching of the words of the dictionary. The heuristics for the middlegame and the endgame are applied. These heuristics' goal is to reach the best score at the end of the game, so they also consider the strategic aspects of a position. Thus the program can be helpful even for advanced players. The simulations are made to compare the artificial intelligence using heuristics against artificial intelligence not using heuristics. Artificial intelligence with heuristics has significantly better performance in the games, whether it was starting or not. We create a graphical user interface that recommends the best moves based on the provingly effective heuristics. 1

Cieľom práce je vytvoriť program, ktorý slúži na analýzu ťahov v spoločenskej hre Scrabble. Slovník jazyka je uložený v dátovej štruktúre GADDAG, ktorá umožňuje rýchle vyhľadávanie slov v slovníku. Ťahy sú vyhodnocované na základe heuristík pre strednú hru a koncovku. Tieto heuristiky berú v úvahu aj strategické aspekty pozície a snažia sa o dosiahnutie čo najvyššieho počtu bodov na konci hry. To má za následok zvýšenie úrovne analýzy ťahov natoľko, že je program hodnotný aj pre skúsenejšieho hráča. Simuláciami je porovnávaná výkonnosť umelej inteligencie používajúcej heuristiku s umelými inteligen- ciami, ktoré heuristiku nepoužívajú. Umelá inteligencia s heuristikou dosahuje v partiách výrazne lepšie výsledky, či už hru začína prvá alebo druhá v poradí. Na analýzu ťahov v Scrabble je vytvorené grafické používateľské rozhranie, ktoré navrhuje najlepšie ťahy podľa preukázane výhodnej heuristiky. 1