Solving atomix exactly

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.

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.