Algorithm for optimising a match game with known queue

Question

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.

Answer 1

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 ;)

Answer 2

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);

            // Add recursively generated moves...
            modifications.AddRange(moreModifications);
        } 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);

        modifications.AddRange(autoChanges);

        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];
                            modifications.Add(new Modification(x, y, fromItem, Item.NONE));
                            modifications.Add(new Modification(x2, y2, toItem, fromItem));

                            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
                    }

                    MoveListAdd(movelist, modifications, 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...