2
$\begingroup$

Hello I am trying to solve the AlienTiles problem described at alientiles.com using the A* algorithm but I cannot find any good heuristic function so far.

In AlienTiles you have a board with $N \times N$ tiles, all coloured red. By clicking on a tile, all tiles in the same row and column advance to the next color, with the colour order being red $\rightarrow$ green $\rightarrow$ blue $\rightarrow$ purple, resetting to red after purple. A goal state is a state where every tile has the same colour, as long as its not red.

Is there any good point to start? I am completely frustrated about how I am supposed to handle the problem. An easy function that I came up with was the distance of the colour of the current tile with the target tile, but it is very slow.

$\endgroup$
  • $\begingroup$ I think your specification of one move in the game is clear enough but you should specify start and end configuration more clearly. $\endgroup$ – Raphael Jan 28 '14 at 8:13
  • $\begingroup$ How slow is "very slow"? How much better are you hoping to do? Is there a particular reason you insist on A*? $\endgroup$ – Juho Jan 28 '14 at 14:13
  • $\begingroup$ I am very impressed that the game is presented as a brand new brain-teaser in the webpage, but it is not! This is just a simple variant of the Merlin's Machine and so many other variants are very easy to obtain. $\endgroup$ – Carlos Linares López Jan 29 '14 at 7:34
  • $\begingroup$ What about stackoverflow.com/questions/21221509/…? $\endgroup$ – user13187 Jan 29 '14 at 12:34
3
$\begingroup$

One candidate approach: for each color $c \in \{\text{green}, \text{blue}, \text{purple}\}$, try to define a distance heuristic $f_c(\cdot)$ that approximates the distance to the specific goal of getting all tiles to be the color $c$. For instance, if $s$ is a state, then $f_\text{green}(s)$ should be an estimate of the distance to the all-green state.

Next, given these heuristics, define a distance heuristic

$$f(s) = \min(f_\text{green}(s), f_\text{blue}(s), f_\text{purple}(s)).$$

Then you could use $f$ as your distance heuristic with $A^*$.

I leave it up to you to see if you can find a suitable definition of $f_c(s)$. One candidate would be the number of tiles in $s$ whose color is not $c$, but that's probably not going to work; you'll probably need something smarter.


If you're willing to use something other than the $A^*$ algorithm, there is an elegant solution to this problem using linear algebra.

Identify the colors red, green, blue, purple with the integers $0$, $1$, $2$, $3$, taken modulo 4 (so you are working in $\mathbb{Z}/4\mathbb{Z}$). Now you can solve the problem using linear algebra. In particular, the state $s$ is a $N^2$-vector over $\mathbb{Z}/4\mathbb{Z}$. Clicking on a tile at position $i,j$ corresponds to updating the state from $s$ to $s+v_{i,j}$, where $v_{i,j}$ is a fixed $N^2$-vector over $\mathbb{Z}/4\mathbb{Z}$. Thus, you can get from state $s$ to state $s'$ if and only if $s'-s$ is in the linear span of the $v_{i,j}$. If it is in the span, then find coefficients $c_{i,j} \in \mathbb{Z}/4\mathbb{Z}$ such that

$$s' - s = \sum_{i,j} c_{i,j} v_{i,j},$$

and this will give you a solution method: for each $i,j$, click on tile $i,j$ exactly $c_{i,j}$ times (order is irrelevant). You can use generalized Gaussian elimination to check whether $s'-s$ is in the span, and if so, to find the coefficients $c_{i,j}$.

$\endgroup$
  • $\begingroup$ That's nice D.W.! Among other things you consider the repeated application of the same operator (everytime $c_{i,j}>1$) which is pretty uncommon in heuristics. I was wondering if you could find optimal solutions using your method. $\endgroup$ – Carlos Linares López Jan 29 '14 at 7:36
  • $\begingroup$ @D.W. thx a lot for your time and solution! I will try to put it to action right away $\endgroup$ – Mario Jan 29 '14 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.