GHOST
GHOST

GHOST documentation

# Introduction

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

The source code is available at github.com/richoux/GHOST, and the documentation pages at richoux.github.io/GHOST. GHOST is under the terms of the GNU GPL v3 licence.

## Scientific papers:

• Florian Richoux, Jean-François Baffier and Alberto Uriarte, GHOST: A Combinatorial Optimization Solver for RTS-related Problems (to appear).
• Florian Richoux, Alberto Uriarte and Santiago Ontañón, Walling in Strategy Games via Constraint Optimization (to appear in AIIDE 2014 proceedings).
• Santiago Ontañón, Gabriel Synnaeve, Alberto Uriarte, Florian Richoux, David Churchill and Mike Preuss, A Survey of Real-Time Strategy Game AI Research and Competition in StarCraft, Transactions on Computational Intelligence and AI in Games, IEEE, 2013.

# A short CSP/COP tutorial

## Intuition behind CSP and COP

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:

• A CSP models a satisfaction problem, that is to say, a problem where all solutions are equivalent, so you just want to find one of them. Example: find a solution of a Sudoku grid. Several solutions may exist, but finding one is sufficient, and no solutions seem better than another one.
• A COP models an optimization problem, where some solutions are better than others. Example: you may have several paths from your home to your workplace, but some of them are shorter.

Let start by defining a CSP. To model your problem by a CSP, you need to define three things:

• V, the set of variables of your CSP.
• D, the domain of your CSP, that is to say, the set of values your variable can take.
• C, the set of constraint symbols of your CSP.

Let's take a simple example:

• V = {x, y, z}. The variables of our CSP would be x, y and z.
• D = {0, 1, 2}. Our variable x, y and z can take a value from D, ie, be either equals to 0, 1 or 2. We can have for instance x = 1, y = 1 and z = 0.
• C = { =, ≠, < }. We have three types of constraint symbols here: equal, different and less than.

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)

## A first example of a CSP formula

Concider the following CSP:

• V = {a, b, c, d}.
• D = {0, 1, 2}.
• C = { =, ≠, < }.

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.

## A concrete problem modeled by a CSP formula

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?