3

I am trying to find a good A* heuristic function for the problem "alien tiles", found at www.alientiles.com for a uni project.

In alien tiles you have a board with NxN tiles, all colored red. By clicking on a tile, all tiles in the same row and column advance by a color, the color order being red->green->blue->purple, resetting to red after purple. The goal is to change all tiles to the specified colors. The simplest goal state is all the tiles going from red to green, blue or purple. The board doesn't have to be 7x7 as the site suggests.

I've thought of summing the difference between each tile and the target tile and dividing by 2N-1 for an NxM board or or finding possible patterns of clicks as the minimum number of clicks, but neither has been working well. I can't think of a way to apply relaxation to the problem or divide it into sub-problems either, since a single click affects an entire row and column.

Of course I'm not asking for anyone to find a solution for me, but some tips or some relevant, simpler problems that I can look at (rubik's cube is such an example that I'm looking at).

Thanks in advance.

1
  • Can you describe the Alien Tiles problem in more detail? Jan 19, 2014 at 19:28

2 Answers 2

0

The problem you are trying to solve is similar to NIM FOCUS name. Please have a look at it. The solutions for it can be found in Stuart J. Russell book under heuristics section. Hope this helps

0

Although it is a relatively 'dumb' way of thinking around the problem, one heuristic mechanism i have found that drastically cuts down on the number of states that a star expands, tries to figure out a relationship between the cell that has been clicked most recently and the number of states that clicking on it again would expand. Its like telling a star: "If you have clicked on a cell in your last move, try clicking on another one this time." Obviously in special scenarios,

(e.g. having all the board on your target colour, say green, and only a purple cross where clicking on the center of the cross twice changes the cross colour to green and then you are done)

this way of thinking is actually detrimental. But, it is a place to start. Please let me know if u figure anything out, as it is something i am working on as well.

2
  • How can you make it into a function? It may work for genetic algorithms but the heuristic doens't have any memory, so you can't estimate somehow where the previous click occured so you will not hit the same tile again.
    – JmRag
    Jan 26, 2014 at 21:26
  • It depends on how you formulate the problem itself. In my implementation, i have added a set of data to the original problem to solve this issue. This set basically does nothing more than get iterated, everytime a click is made on each specific cell, for every specific cell.
    – Mark
    Jan 26, 2014 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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