Repositório Digital

A- A A+

Solving atomix exactly

.

Solving atomix exactly

Mostrar registro completo

Estatísticas

Título Solving atomix exactly
Outro título Encontrando soluções exatas para atomix
Autor Gliesch, Alex Zoch
Orientador Ritt, Marcus Rolf Peter
Data 2015
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Assunto Algoritmos
Heurística
[en] A*
[en] Algorithms
[en] Atomix
[en] Heuristic search
[en] Sliding block puzzles
Abstract This work proposes an algorithm based on heuristic search to solve Atomix. Atomix is a video game puzzle developed in the 1990s. It falls under the category of sliding block puzzles, which also contains popular games such as Sokoban, Rush Hour, and the (n2 􀀀1)-puzzle, which have all been well studied in the literature. The Atomix puzzle takes place on an integer rectangular grid, where pieces (called atoms) can be moved by the player through sliding operations. A sliding operation consists of moving a single atom horizontally or vertically on the grid; once a move is made, the atom will slide over the grid until it reaches an obstacle, which could be another atom or a ‘wall’ (a static obstacle). The objective of the game is to arrange the atom in a certain configuration called a molecule. Since the place of the molecule is not specified there are often multiple possible goal states. Atomix’s complexity was first studied by Holzer and Schwoon (2004), who have proved it to be PSPACE-complete. Heuristic search methods for Atomix were studied by Hüffner et al. (2001); however, the heuristic proposed by the article is somewhat uninformed, leaving several instances of the standard testbed unsolved. In this work, we study domain-dependent heuristic functions for Atomix based on pattern databases (CULBERSON; SCHAEFFER, 1996), in the hopes of advancing the contributions made by (HÜFFNER et al., 2001). We also study a number of tie-breaking rules for the A* algorithm, as well as some implementation-specific optimizations. Finally, an improved solution is proposed.
Resumo Este trabalho propõe um algoritmo baseado em busca heurística para resolver Atomix. Atomix é um puzzle de video game desenvolvido nos anos 90. Ele cai na cadegoria de puzzles de blocos deslizantes, que também contem jogos populares como Sokoban, Rush Hour, e o (n2 􀀀 1) 􀀀 puzzle, todos os quais têm sido bem estudados na literatura. O puzzle Atomix ocorre em uma grade retangular inteira, onde peças (chamadas átomos) podem ser movidas pelo jogador através de operações deslizantes. Uma operações deslizante consiste em mover um único átomo horizontalmente ou verticamente sobre a grade; uma vez que um movimento foi feito, o átomo irá deslizar sobre a grade até que encontre um obstáculo, que pode ser outro átomo ou uma parede (um obstácilo estático). O objetivo do jogo é montar os átomos em uma certa configuração chamada molécula. Como o lugar da molécula não é especificado, é comum haver mais de um estado final. A complexidade de Atomix foi primeiro estudada por Holzer and Schwoon (2004), que o provou ser PSPACE-completo. Técnicas de busca heurísica para Atomix foram estudadas por Hüffner et al. (2001); porém, a heurística proposta pelo artigo é relativamente desinformada, deixando várias instâncias não resolvidas. Neste trabalho, nós estudamos heurísticas dependendes de domínio para Atomix baseadas em bancos de dados de padrões (CULBERSON; SCHAEFFER, 1996), na esperança de avançar as contribuições feitas por (HÜFFNER et al., 2001). Nós também estudamos técnicas de desempate para o algoritmo A*, além de algumas otimizações específicas à implementação. Finalmente, uma solução melhorada é proposta.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/138215
Arquivos Descrição Formato
000988714.pdf (2.417Mb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.