# Algorithm for optimising a match game with known queue

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.

• I did once work out that the search space of some complex game I was working on would be 32Gb. At the time (I had a 20Mb disk drive) that would have been unfeasible, but these days it's just about doable in RAM for some computers. – Jonathan May 29 '13 at 13:05
• Do flowers with only one color disappear entirely when matched? And can flowers with two colors match their outer layer against the single color of a one-color flower? I presume so on both counts, but these are never explicitly specified in the problem description... – Steven Stadnicki May 29 '13 at 16:07
• @StevenStadnicki Thanks! I've added that information to the original question. – user849924 May 29 '13 at 16:24
• As a small note, incidentally, it's overwhelmingly likely that the 'boolean' version of this problem (is there some way of placing the flowers in the queue to leave the board completely empty at the end?) is NP-complete; it bears obvious similarities to the Clickomania problem ( erikdemaine.org/clickomania ) which is NP-complete, and the problem is no harder than NP because given a purported solution (of polynomial length) it's easy to verify by just running the simulation. This means that the optimization problem is probably in FP^NP. – Steven Stadnicki May 29 '13 at 17:13

At first glance, this seems to me to be a single agent search problem. That is: you have one agent (the AI "player"). There's a game state representing the state of the game board and queue, and you have a successor function that can generate new states from a given state.

There's also a goal criteria that tells you when the state is the "solved" state. And a path cost - the cost of advancing to a given state (always "1 move" in this case).

One prototypical puzzle of this kind is the 15 Puzzle. And the typical way to solve it is with an informed search - for example, the classic heuristic search A* and its variants.

However there's a problem with this at-first-glance approach. Algorithms like A* are designed to give you the shortest path to a goal (for example: smallest number of moves). In your case, the number of moves is always fixed - there is no shortest path - so a heuristic search will just give you a path to a completed game.

What you want is a sequence of moves that gives you the best completed game state.

So what you must do is turn the problem around a bit. Instead of the game board being the "state", the sequence of moves becomes the "state". (I.e.: Place the items in the queue at positions "D2, A5, C7, B3, A3, ...")

This means we don't really care how those states are generated. The board itself is incidental, required only to evaluate the quality of a given state.

This turns the problem into an optimisation problem, which can be solved with a local search algorithm (which basically means creating states around a given state, and selecting the best state, without caring about the path between states.)

The prototypical puzzle of this kind is the Eight Queens Puzzle.

In this class of problem, you are searching the state space to find a good solution, where "good" is evaluated by an objective function (also called an evaluation function or, for genetic algorithms, a fitness function).

For your problem, an objective function might return a value between 0 and N, for the number of items in the queue that were used up before reaching a failure state (where N is the length of the queue). And, otherwise, a value of N + M, where M is the number of blank spaces left on the board after the queue is empty. As such - the higher the value, the "objectively better" the solution.

(It is worth noting, at this point, that you should optimise the crap out of the code that runs the game - that turns a state into a finished board that can be used for the objective function.)

As for examples of local search algorithms: The basic pattern is a hill-climbing search that takes a given state, mutates it, and moves towards the next state that gives a better result.

Obviously this can get stuck in local maximums (and the like). In this form it's called a greedy local search. There are a bunch of variations to deal with this and other issues (Wikipedia has you covered). Some of which (eg: local beam search) keep track of multiple states at once.

One particular variation on this is the genetic algorithm (Wikipedia). The basic steps for a genetic algorithm are:

1. Determine some way to convert a state into a string of some kind. In your case this might be a string of queue-length digits from 1 to 49 (representing all the possible placements on a 7x7 board, probably stored 1 byte each). (Your "spade" piece could be represented by two subsequent queue entries, for each phase of the move.)
2. Randomly select a breeding population, giving higher probability to states that have better fitness. The breeding population should be the same size as the original population - you can choose states from the original population multiple times.
3. Pair up states in the breeding population (first goes with second, third goes with fourth, etc.)
4. Randomly select crossover points for each pair (a position in the string).
5. Create two offspring for each pair by swapping the portion of the string after the crossover point.
6. Randomly mutate each of the offspring states. For example: randomly choose to change a random position in the string to a random value.
7. Repeat the process with the new population until the population converges on one or more solutions (or after a given number of generations, or a sufficiently good solution is found).

A genetic algorithm solution feels like it might be appropriate for your problem - with some adjustment. The biggest difficulty I see is that, with the above string representation, you will find that switching the tail halves of states with very different front halves is likely to result in "dead" states (due to conflicting moves between the two halves, that result in a low fitness score).

Perhaps it is possible to overcome this problem. One idea that comes to mind is making it more likely for states with similar front-halves to become breeding pairs. This could be as simple as sorting the breeding population of states, before pairing them up. It may also help to gradually move the likely position of the crossover, from the start to the end of the string, as the generation number increases.

It may also be possible to come up with a representation of moves within a state that is more resistant (perhaps even entirely immune) to encountering the "square is full" failure state. Perhaps representing moves as relative coordinates from the previous move. Or having moves select the closest empty space to the given position.

As with all non-trivial AI problems like this, it will require some significant tinkering.

And, as I mentioned before, the other major challenge is simply optimising your objective function. Making this faster will allow you to search a large amount of space, and to search for solutions to games with longer queues.

For this answer, particularly to get all the terminology right, I had to dig out my university AI textbook, "Artificial Intelligence: A Modern Approach" by Russell and Norvig. Not sure if it's "good" (I don't have any other AI texts to compare it with), but it's not bad. At least it's quite big ;)

• I identified that problem with a crossover as well: it's very well possible that a child has more items placed than available in the queue (kind of lack GA for TSP: he might visit cities twice or more (or not at all!) after a crossover. Maybe an ordered crossover (permutationcity.co.uk/projects/mutants/tsp.html) could work. This is especially applicable when you make the sequence of moves the state. – user849924 May 29 '13 at 16:02
• Not sure that is quite right - in my mind, the failure state is that a piece is placed at a position that is already occupied (thus ending that game early, resulting in a low fitness score). So the queue length matches the length of the genetic string - it is never the wrong length. Still - you may be onto something with the idea of swapping and ordering. If a given order results in a completed game, and you swap two moves, I imagine that there is a much better chance of the mutated state also being a completed game than if you were to simply set one (or two?) move's positions randomly. – Andrew Russell May 29 '13 at 17:10
• The failure state is when you have no more options to place moves, i.e. when you run out of empty spaces and no matches occur with that move. Similar to what you're saying: you have to place it on a position that's already occupied (but that's only true when there are no more places to begin with). The crossover I posted could be interesting. Chromosome A has items placed on A1, B1, ..., G1, A2, B2 and C2, and chromosome B on G7 ... A7, G6, F6 and E6. Select a few randoms from A and keep their index. Select A's complement from B and keep their index and merge for a child. – user849924 May 29 '13 at 21:56
• 'Problem' with this crossover is that multiple moves on the same spot is allowed. But that should be easily solvable with something similar to SimulateAutomaticChanges from Stefan K's solution: apply the moveset/state of the child to the base state (simply apply all moves, one by one) of the playing field and if the acceptance state (empty queue) can't be achieved (because you have to place a flower on an occupied spot), then the child is invalid and we'll need to breed again. Here's where your failure condition pops up. I get that one now, heh. :D – user849924 May 29 '13 at 22:00
• I'm accepting this as the answer, for two reasons. First: you gave me the idea I needed to get GA to work for this problem. Second: you were first. ;p – user849924 Jun 1 '13 at 16:38

## Categorization

The Answer isn't easy. The game theory has some classifications for games, but there seems to be no clear 1:1-match for that game to a special theory. It's a special form of combinatorial problem.

It's not traveling salesman, which would be deciding for an order in which you visit "nodes" with some cost to reach the next node from the last one. You can't reorder the queue, nor do you have to use all fields on the map.

Knapsack doesn't match because some fields become empty while putting some items into the "knapsack". So it's maybe some extended form of that, but most possibly the algorithms will not be applicable because of this.

Wikipedia gives some hints on categorization here: http://en.wikipedia.org/wiki/Game_theory#Types_of_games

I would categorize it as "discrete-time optimal control problem" (http://en.wikipedia.org/wiki/Optimal_control), but I don't think this will help you.

## Algorithms

In case you really know the complete queue, you could apply tree search algorithms. As you said, the complexity of the problem grows very fast with the queue length. I suggest to use an algorithm like "Depth-first search (DFS)", which doesn't require much memory. As the score does not matter to you, you could just stop after having found the first solution. To decide which sub-branch to search first, you should apply a heuristic for ordering. That means you should write an evaluation function (e.g.: number of empty fields; the more sophisticated this one is, the better), that gives a score to compare which very next move is the most promising.

You then only need the following parts:

1. model of the game state, that stores all information of the game (e.g. board status / map, queue, move number / position in queue)
2. a move generator, which gives you all valid moves for a given game state
3. a "do move" and a "undo move" function; which apply / undo a given (valid) move to a game state. Whereas the "do move" function should store some "undo information" for the "undo" function. Copying the game state and modifying it in each iteration does slow down the search significantly! Try at least to store the state on the stack (= local variables, no dynamic allocation using "new").
4. an evaluation function, which gives a comparable score for each game state
5. search function

Here is an incomplete reference implementation for depth-first search:

public class Item
{
// TODO... represents queue items (FLOWER, SHOVEL, BUTTERFLY)
}

public class Field
{
// TODO... represents field on the board (EMPTY or FLOWER)
}

public class Modification {
int x, y;
Field originalValue, newValue;

public Modification(int x, int y, Field originalValue, newValue) {
this.x = x;
this.y = y;
this.originalValue = originalValue;
this.newValue = newValue;
}

public void Do(GameState state) {
state.board[x,y] = newValue;
}

public void Undo(GameState state) {
state.board[x,y] = originalValue;
}
}

class Move : ICompareable {

// score; from evaluation function
public int score;

// List of modifications to do/undo to execute the move or to undo it
Modification[] modifications;

// Information for later knowing, what "control" action has been chosen
public int x, y;   // target field chosen
public int x2, y2; // secondary target field chosen (e.g. if moving a field)

public Move(GameState state, Modification[] modifications, int score, int x, int y, int x2 = -1, int y2 = -1) {
this.modifications = modifications;
this.score = score;
this.x = x;
this.y = y;
this.x2 = x2;
this.y2 = y2;
}

public int CompareTo(Move other)
{
return other.score - this.score; // less than 0, if "this" precededs "other"...
}

public virtual void Do(GameState state)
{
foreach(Modification m in modifications) m.Do(state);
state.queueindex++;
}

public virtual void Undo(GameState state)
{
--state.queueindex;
for (int i = m.length - 1; i >= 0; --i) m.Undo(state); // undo modification in reversed order
}
}

class GameState {
public Item[] queue;
public Field[][] board;
public int queueindex;

public GameState(Field[][] board, Item[] queue) {
this.board = board;
this.queue = queue;
this.queueindex = 0;
}

private int Evaluate()
{
int value = 0;
// TODO: Calculate some reasonable value for the game state...

return value;
}

private List<Modification> SimulateAutomaticChanges(ref int score) {
List<Modification> modifications = new List<Modification>();
// TODO: estimate all "remove" flowers or recoler them according to game rules
// and store all changes into modifications...
if (modifications.Count() > 0) {
foreach(Modification modification in modifications) modification.Do(this);

// Recursively call this function, for cases of chain reactions...
List<Modification> moreModifications = SimulateAutomaticChanges();

foreach(Modification modification in modifications) modification.Undo(this);

} else {
score = Evaluate();
}

return modifications;
}

// Helper function for move generator...
private void MoveListAdd(List<Move> movelist, List<Modifications> modifications, int x, int y, int x2 = -1, int y2 = -1) {
foreach(Modification modification in modifications) modification.Do(this);

int score;
List<Modification> autoChanges = SimulateAutomaticChanges(score);

foreach(Modification modification in modifications) modification.Undo(this);

movelist.Add(new Move(this, modifications, score, x, y, x2, y2));
}

private List<Move> getValidMoves() {
List<Move> movelist = new List<Move>();
Item nextItem = queue[queueindex];
const int MAX = board.length * board[0].length + 2;

if (nextItem.ItemType == Item.SHOVEL)
{

for (int x = 0; x < board.length; ++x)
{
for (int y = 0; y < board[x].length; ++y)
{
// TODO: Check if valid, else "continue;"

for (int x2 = 0; x2 < board.length; ++x2)
{
for(int y2 = 0; y2 < board[x].length; ++y2) {
List<Modifications> modifications = new List<Modifications>();

Item fromItem = board[x][y];
Item toItem = board[x2][y2];

MoveListAdd(movelist, modifications, x, y, x2, y2);
}
}
}
}

} else {

for (int x = 0; x < board.length; ++x)
{
for (int y = 0; y < board[x].length; ++y)
{
// TODO: check if nextItem may be applied here... if not "continue;"

List<Modifications> modifications = new List<Modifications>();
if (nextItem.ItemType == Item.FLOWER) {
// TODO: generate modifications for putting flower at x,y
} else {
// TODO: generate modifications for putting butterfly "nextItem" at x,y
}

}
}
}

// Sort movelist...
movelist.Sort();

return movelist;
}

public List<Move> Search()
{
List<Move> validmoves = getValidMoves();

foreach(Move move in validmoves) {
move.Do(this);
List<Move> solution = Search();
if (solution != null)
{
solution.Prepend(move);
return solution;
}
move.Undo(this);
}

// return "null" as no solution was found in this branch...
// this will also happen if validmoves == empty (e.g. lost game)
return null;
}
}


This code isn't verified to work, nor is it compileable or complete. But it should give you an idea how to do it. The most important work is the evaluation function. The more sophisticated it is, the the wrong "tries" the algorithm will try (and have to undo) later. This extremely reduces the complexity.

If this is too slow you can also try to apply some methods of two-person-games as HashTables. For that you'll have to calculate an (iterative) hash key for each game state that you evaluate and mark states that do not lead to a solution. E.g. every time before the Search() method returns "null" a HashTable entry must be created and when entering Search() you'd check if this State has been already reached so far with no positive result and if so return "null" without further investigation. For this you'll need a huge hash table and would have to accept "hash collisions" which could cause that you probably don't find a existing solution, but which is very unlikely, if your hash functions is good enough and your table is big enough (its a risk of calculate-able risk).

I think there is no other algorithm to solve this problem (as described by you) more efficient, assumed your evaluation function is optimal...

• Yes, I can know the complete queue. Would an implementation of the evaluation function also consider a valid, but potentially bad placement? Potentially bad being a move like placing it next to the flower of a different colour when there's a similar colour already on the field? Or placing a flower somewhere which blocks of a totally different match because of lack of space? – user849924 May 29 '13 at 15:54
• This answer gave me ideas for the model and how to work with the game rules, so I'll upvote it. Thanks for your input! – user849924 Jun 1 '13 at 16:40
• @user849924: Yes, of course the evaluation function must calculate an evaluation "value" for that. The more the current game state becomes worse (near to loosing), the worse the returned evaluation value should be. The most easiest evaluation would be to return the number of empty fields. You can improve this by adding 0.1 for each flower placed next to a flower of similar color. To verify your function choose some random game states, calculate their value and compare them. If you think state A is better than state B, the score fore A should be better than the one for B. – SDwarfs Jun 4 '13 at 12:42