GHOST (General meta-Heuristic Optimization Solving Tool) is a template C++11 library designed for StarCraft: Brood war. GHOST implements a meta-heuristic solver aiming to solve any kind of combinatorial and optimization RTS-related problems represented by a CSP. It is an generalization of the Wall-in project (see github.com/richoux/Wall-in).
Constraint Satisfaction Problems (CSP) and Constraint Optimization Problems (COP) are two close formalisms intensively used in Artificial Intelligence to solve combinatorial and optimization problems. They allow you to easily express what your problem is, and offer you a uniform way to solve all problems you can describe by a CSP or a COP.
The difference between a CSP and a COP is simple:
Let start by defining a CSP. To model your problem by a CSP, you need to define three things:
Let's take a simple example:
Ok, now what? Well, to describe our problem, we have to build a formula from our CSP. This is a bit like playing to Lego: you combine blocks to build bigger blocks, then you combien your bigger blocks to create an object.
Here, your blocks are your variables. You can combine them with a constraint symbol to build a bigger block, ie, a constraint. For instance, we can build the constraint (x=z), or the constraint (z≠y), etc.
Then, we can build a formula by combining constraints. Combining means here we have a conjuction, ie a "and"-operator linking two constraints. A formula with the CSP describe above could be for instance
(z=y) AND (y≠x) AND (x<z)
Concider the following CSP:
and suppose our problem is modeled by the formula
(a=b) AND (b≠d) AND (d<c) AND (b<c)
A solution of our problem is a good evaluation of each variable to a value of the domain D. In other words, if we find a way to give a value from D to each variable of V such that all constraints are true (we also say, are satisfyed), then we have a solution to our problem.
For instance, the evaluation a=1, b=1, c=2 and d=1 is not a solution of the formula, because the second constraint (b≠d) is not satisfyed (indeed (1≠1) is false).
However, the evaluation a=1, b=1, c=2 and d=0 satisfies all constraints of the formula, and is then a solution to our problem.
Ok, now how to model a problem through a CSP formula? This is not always trivial and require some experience. Let see how to model two famous graph problems with the CSP formalism.
I assume the reader know what a graph is; otherwise here is the main idea: it is a set of vertices where some of them are linked by an edge. See the picture below, an example of graph with four vertices (named A, B, C and D). Graphs are simple mathematical objects but expresive enough to model complex problems, like finding the shortest path between two cities (your GPS use graphs!).
Let consider the 3-COLOR problem: Given a graph, is it possible to colorize each vertex with one of the three available colors (say, red, blue and green) such that there is no couple of vertices linked by an edge sharing the same color?
Before continuing, think about: