I'm trying to write a solver in C# .NET for a game known as Flowerz. For your reference, you can play it on MSN, here: http://zone.msn.com/gameplayer/gameplayer.aspx?game=flowerz. I'm writing it for fun, not for any type of assignment or anything work related. Because of this, the only limit is my computer (an intel i7 core, with 8GB of RAM). It doesn't need to run anywhere else, as far as I'm concerned.
In short, its rules are like this:
- There's a queue filled with coloured flowers. Its length is arbitrary
- The queue cannot be influenced
- The queue is generated at the start of the level
- Flowers have either one or two colours.
- If there are two colours, then there's an outer colour, and an inner colour. In the case of two colours, the outer colour is used for matching.
- If there is a match, then the outer colour disappears and the flower is now a single colour flower with the same colour as the inner flower
- The goal of the game is to create matches of three (or more) of the same colour
- When a flower of a single colour is part of a match, it is removed from the playing field, creating an empty space
- You can match a single colour flower against the outer colour of a two-colour flower. In this case, the single colour flower disappears, the outer colour of two-colour flower disappears and the inner colour remains
- You win the round when the queue is empty and there's at least one empty space left over
- Cascading matches are possible. A cascade is when three (or more) outer flowers disappear, and when their inner colours form another chain of 3 (or more flowers).
- The playing field is always 7x7
- Some spaces on the field are covered by rocks
- You can't place flowers on rocks
- The queue can also contain a spade which you can use to move any placed flower to an unoccupied space
- You have to use the spade, but you don't actually have to move the flower: it's perfectly legal to place it right back from where it came
- The queue can also contain a coloured butterfly. When you use this butterfly on a flower, then the flower gets the colour of the butterfly
- Applying a butterfly to a flower with two colours, results in the flower getting only a single colour, namely that of the butterfly
- You can waste the butterfly on an empty space or a flower which already has this colour
- Clearing the field does not win the game
The goal of the solver is simple: find a way to empty the queue, with as many leftover spaces on the playing field as possible. Basically, the AI plays the game for me. The output of the solver is a list with moves it found. I'm not interested in score, but in surviving as long as possible, hence I'm interested in the moves that leaves as many open spaces as possible.
Needless to say, the search space grows quickly the larger the queue gets, so a brute force is out of the question. The queue starts at 15, and grows with 5 every two or three levels, if I remember right. And, of course, placing the first flower on (0,0) and the second on (0,1) is different from placing the first one on (1,0) and the second flower on (0,0), especially when the field is already populated with flowers from an earlier round. Such a simple decision could make the difference in making it or not.
The questions I have are the following:
- What kind of problem is this? (think travelling salesman, knapsack, or some other combinatorial problem). Knowing this could make my Google-fu a tad better.
- What kind of algorithm could give me good results, fast?
Regarding the latter: At first, I tried to write my own heuristic algorithm (basically: how would I solve it, if I knew queue?), but that results in a lot of edge cases and scoring matching that I might miss.
I was thinking of using a genetic algorithm (because I at least know how to use that...), but I'm having some problems deciding on a binary representation of the board. Then there's the crossover issue, but that can be solved with an ordered crossover operator or a similar type of operation.
My guess is that the solver must always know the board configuration and the queue it's trying to empty.
I know of a few other heuristic algorithms such as neural networks and fuzzy logic systems, but I lack the experience to know which one is best applicable, or if there are others which are better suited for the task at hand.