Back to search

Institutional Repository of Vilnius University

Roll the Ball žaidimo sprendimas pasitelkiant euristinius metodus /

Abstract

dc:description

In this paper, informed algorithms for the game Roll the Ball were analyzed. Two different heuristics have been proposed in the course of the work, which are able to compute a heuristic estimate of the game position. The first heuristic was based on state endpoints, and the second one on tile assignment using Manhattan distance. Two informed search algorithms, A* and IDA*, were applied to the Roll the Ball puzzle using the implemented heuristics. The aim of the paper was to compare the heuristics in terms of optimality and the algorithms in terms of solution time and memory usage. Three solving methods were chosen for the study: A* algorithm with state endpoints heuristics, A* and IDA* algorithms with tile assignment heuristics, which were used to solve 64 levels of the game. The results confirm that, unlike the first heuristic, the second heuristic was admissable and optimal, as it returned the shortest solutions. Additionally, A* algorithm with the first heuristic solved fewer game levels than algorithms with the second heuristic. Comparing the A* and IDA* algorithms, A* solved levels 50% faster than IDA* but used 300% more memory.

Degree

thesis:*
Grantor dc:publisher
Institutional Repository of Vilnius University
Year dc:date
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Notrumas, Laurynas,

Rights

dc:rights
Statement dc:rights
  • info:eu-repo/semantics/openAccess
Language dc:language
lit

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Notrumas, Laurynas,. Roll the Ball žaidimo sprendimas pasitelkiant euristinius metodus /. Institutional Repository of Vilnius University, 2023. https://repository.vu.lt/VU:ELABAETD192847127&prefLang=en_US