Jul 11, 2010

Nontransitive dices and Japanese rock garden (with genetic algorithms)

1. Introduction

This installment will be about two small problems, both solvable with genetic algorithms approach. "Solvable" here means we find a "good enough" solution rather than the ideal one.

The first problem would be to find a sorted set of dices (for example, 6-sides ones) having a property of every dice beating the next one, meaning it will give better scores on average. The last dice should beat the first one, a la "rock, paper, scissors" game. The fact that it's possible is usually a bit non-intuitive. I learned about this problem from one of Martin Gardner's excellent books on mathematical puzzles.

The second problem would be the "Japanese rock garden". Karesansui garden in Ryōan-ji Temple possesses an interesting property: a visitor can see only 14 rocks out of total 15 from any observation point (one and only one rock is always blocked by other rocks). We will try to find such a configuration of stones, not knowing the desired answer beforehand, and based on some assumptions about stones and garden/veranda configuration. Also, this will be done on hexagonal grid, using hexagonal variant of "field of view" algorithm.

There won't be a lot of code posted, so this is more like a descriptive write-up rather than a complete implementation guide.

2. Genetic algorithms

Let's start with a brief description of genetic algorithms. Basically, it's a random search directed towards a better solution. If we have means of numeric evaluation of a given solution, and a way to randomly mutate (and/or create an offspring for any two solutions) a solution, then GA is our friend. We would get a population of "organisms", representing possible solutions, and mate/mutate the most fit (according to our evaluation method) ones.

I think that's enough information to actually start using GAs (when aiming for realistic characteristics such as speed of evolution, or quantitative measurement of genotype diversity, etc is not a goal), but in any case, the more comprehensive explanation is always available at Wikipedia.

2.1. Brief JGAP introduction

JGAP stands for Java Genetic Algorithms Package. It is an easy to use, open source library perfectly suitable for our needs. Overhead of learning key library concepts is very small and it pays back when we won't need to implement GA logic ourselves.

Basically, we will need to familiarize with mere 3 concepts in terms of JGAP:

  • Gene - partial characteristic of a potential solution (a chromosome). As a Java class, it should know how to mutate its internal state, and how to set itself up from given representation. Implements Gene interface.

  • Chromosome - a potential solution, consisting of several (possibly different) genes. For example, one gene could have an internal state of a single integer value, whereas another gene in the same chromosome could be an array of floats. Implements IChromosome interface.

  • Fitness function - a method which evaluates given chromosome based on some criteria and returns the numeric result. The higher the returned value is, the better given chromosome fits criteria of a desired problem solution. Extends abstract class FitnessFunction.

These is a lot more to JGAP, but a good thing is that we don't need to know anything else when we are working on our simple problems.

3. Nontransitive dices

Simply put, a set of dices A, B, and C is called nontransitive when for given operator '>', A>B and B>C doesn't mean that A>C. Naturally, we define the '>' operator this way: A>B means that the dice A "wins" over the dice B. "Wins" here means that if a number of dice rolls is big enough, there will be more throws where dice A scores more than dice B. Or, more strictly, for any given roll of the two dices, the statistical probability of dice A scoring more than B is greater than 50% (let's say here we re-throw if both dices gave the same score).

So, for example, a set of 3 nontransitive dices has the property A>B>C>A.

As Martin Gardner stated in one of his books, this has a rather practical application due to the fact that the possibility of such a set is not always obvious. One can propose a dice game on the condition that every player uses their own dice from the set, and "grant" them the first pick (i.e. allowing the opponent to get the non-existent "best" dice). Then one always can pick the better dice from the set (fun fact: apparently, Bill Gates is proven to be immune to the trick).

Let's try to find such a set using GA. We will start with introducing data structures describing a set of M dices, each one N-sided, and then see if we can find a solution for particular N and M values.

3.1. Gene/chromosome set up

Since a potential solution is represented by a chromosome, it has to represent all M dices. Naturally, let's define a class DiceGene representing one N-sided dice, and construct our chromosomes from M DiceGenes:

Example 1. DiceGene implementation using JGAP

public class DiceGene extends BaseGene implements Gene, Serializable {
    private int[] _sideValues;

    public DiceGene(Configuration a_configuration) throws InvalidConfigurationException {
        this(a_configuration, 6);
    }

    public DiceGene(Configuration a_configuration, int numSides) throws InvalidConfigurationException {
        super(a_configuration);
        if (numSides < 0)
            throw new IllegalArgumentException("Number of sides must be positive, was " + numSides);
        _sideValues = new int[numSides];
    }
    // ...
}

So, a DiceGene instance represents N-sided dice (N=6 by default). _sideValues array simply holds integer values for the dice's sides.


In order for this Gene implementation to be successfully used by JGAP, we need to implement a couple more methods:

Example 2. DiceGene's get/set/size methods

    @Override
    protected Object getInternalValue() {
        return _sideValues;
    }

    @Override
    public void setAllele(Object from) {
        int[] array = (int[]) from;
        _sideValues = new int[array.length];
        System.arraycopy(array, 0, _sideValues, 0, array.length);
    }

    @Override
    public int size() {
        return _sideValues.length;
    }

size() method lets JGAP know the size of our custom gene (to be able to request particular element mutation), and setAllele() allows it to set the gene to hold specified values (for cross-over).


Finally, two more methods for setting initial values and random mutation:

Example 3. DiceGene's random initial value and mutation methods

    @Override
    public void setToRandomValue(RandomGenerator random) {
        for (int i = 0; i < _sideValues.length; i++) {
            _sideValues[i] = random.nextInt(_sideValues.length) + 1;
            assert (_sideValues[i] >= 1 && _sideValues[i] <= _sideValues.length) : "values check";
        }
    }

    @Override
    public void applyMutation(int index, double percentage) {
        assert (index >= 0 && index < _sideValues.length) : "bounds checking";
        // disregard percentage parameter for now
        _sideValues[index] = getConfiguration().getRandomGenerator().nextInt(_sideValues.length) + 1;
    }

We allow each side of the dice to have values in [1..N] range.


Now, the DiceGene class should be ready to use. Let's construct a chromosome out of 3 DiceGenes, there is an useful Chromosome class for that:

Example 4. Constructing a simple chromosome

    Configuration config = new DefaultConfiguration();

    Gene[] genes = new Gene[3];              // will search for 3-dices solution
    for (int i = 0; i < genes.length; i++)
        genes[i] = new DiceGene(config);     // use 6-sided dices by default

    IChromosome chromosome = new Chromosome(config, genes);


3.2. Fitness function

For each solution, or a chromosome in terms of JGAP (specifying M dices and all their side values), we need to be able to determine if there is a loop (A>B>C>A for 3-dice case). Let's construct a matrix of win/loss rates for a solution:

Table 1. Win/loss matrix for 3-dice solution

  A B C
A - 60% 30%
B 40% - 80%
C 70% 20% -

In the example matrix above, A wins over B with 60% rate, B over C (80%), and C>A (70%), thus A>B>C>A.

We need to construct a fitness function which would give solutions which have such win/loss matrices better score (and survival chance). Also, we are interested in longer loops (so all solution's dices are involved). And we should favor better winning rate percentage across the loop, in hope to find more "sound" solution.

There are several ways to construct the win/loss matrix. The one we are going to use takes draws into account, so sum mij+mji=100%:

Example 5. Win/loss matrix construction code

    // returns win rate of dice1 over dice2
    private static double getScore(DiceGene dice1, DiceGene dice2) {
        double score = 0;
        for (int i = 0; i < dice1.size(); i++) {
            for (int j = 0; j < dice2.size(); j++) {
                if (dice1.side(i) > dice2.side(j)) {
                    score += 1.0d;
                } else if (dice1.side(i) == dice2.side(j)) {
                    score += 0.5d;
                }
            }
        }
        return 100.0d * score / (double) (dice1.size() * dice2.size());
    }

Simple explanation of the method above: imagine we have two 6-sided dices. There are 36 equally probable outcomes for these dices throw. Let's take 36 points and distribute them between players for each possible outcome. Winning player takes 1 point, and in case of a draw each player takes 0.5 of a point. Given long enough series of dice throws, the returned value signifies what percentage of the prize fund is going to be won by the 1st dice.


Next, we need to determine if the constructed win/loss matrix has any loops, what is the max length of loops presents, etc. Once again, the searching for loops can be implemented in different ways. We will stick to the naive recursive one (it may be not the most efficient one, but it is good enough for our task).

The algorithms is outlined below:

Example 6. Loop searching algorithm

  1. Throughout the algorithm, maintain a set of unique loops found (_loops). Also maintain a set of visited rows (_visited).

  2. Look through the matrix in the row/column order, and find a non-visited row containing at least one win rate >50%.

    Update _visited with the found row index. If there is no such row, return the (possibly empty) _loops set.

  3. Create a candidate loop instance starting with dice number found in the 2nd step. Let's call this loop 'current'.

  4. Traverse 'current' in the following fashion:

  5. Take the last index i in the 'current' loop (representing the last dice in the loop candidate).

  6. Look through mi row performing step 7.

  7. If there is an element mij>50%, update _visited and try to grow the loop. This can have 2 outcomes:

    • j is already present in 'current' - then add loop (possibly shorter one) to the _loops set, and continue looking through mi (from step 6).

    • j is not in 'current' - add it there and traverse it recursively (step 4).

  8. When finished traversing, remove the last index in the 'current' loop.

  9. Continue from step 2 if there are still non-visited rows.


Ok, this doesn't look very clear to me, so here is the same thing in pseudo code:

Example 7. Loops searching in pseudo code

_loops ← empty set;
_visited ← empty set;

function getNextIndex() {
  if exist index i such that (mik>50% for arbitrary k) and (i is not in _visited set)
    then put i to _visited and return i;
    else return 'not found';
}

function findAllLoops() {
  i ← getNextIndex()
  if (i is not found) 
    then finish and return _loops;
  do {
    current ← new list having single element i;
    traverse(current);
    i ← getNextIndex();
  } while (i is valid);
}

function traverse('current' list) {
  i ← last element from 'current';
  for k=[0..M) {
    if (k == i) or (mik <= 50%)
      then continue;
    add k to _visited set and to 'current' as last element;
    if true loop detected inside 'current'
      then add found loop to _loops;
      else traverse('current');
  }
  remove last element from 'current' if present;
}


Hope that is more clear. Here is a small example of a matrix and loops found:

Example 8. Win/loss matrix and loops

example win/loss matrix:
     A   B   C   D
A {  0, 60, 20, 10 }
B { 40,  0, 30, 60 }
C { 80, 70,  0, 10 }
D { 90, 40, 90,  0 }

set of loops:
A > B > D > C > A
A > B > D > A
B > D > C >B


The remaining thing is to actually define the fitness function. Remember, it should favor longer loops over shorter ones, and loops with greater average win ratio over ones with smaller ratio. And it's even better, when the matrix has only one very long loop. So, here is how my fitness function looks like:

Example 9. Loop searching fitness function

class MinimizingLoops extends FitnessFunction {

    @Override
    protected double evaluate(IChromosome subject) {
        RollMatrix matrix = generateMatrix(subject);
        Set<RollLoop> loops = matrix.getAllLoops();

        double score = loops.size() == 0 ? 0 : 1000.0 / loops.size(); // single loop gives max score
        return score * getSumWinRatio(matrix, loops);                 // score is multiplied by sum of win ratios
    }
    //...
}

The idea is that multiplying score by summary win ratio over all loops favors longer loops, and dividing score by loops.size() favors smaller number of loops.


3.3. Resulted dices

First, let's see what solution we could get for 3 6-sided dices.

Example 10. Code fragment for solving 3 6-sided dice case

        Configuration.reset();
        Configuration config = new DefaultConfiguration();
        config.setPreservFittestIndividual(true);

        Gene[] genes = new Gene[3];
        for (int i = 0; i < genes.length; i++)
            genes[i] = new DiceGene(config);

        IChromosome chromosome = new Chromosome(config, genes);
        config.setSampleChromosome(chromosome);
        config.setPopulationSize(50);
        config.setFitnessFunction(new MinimizingLoops());
        Genotype population = Genotype.randomInitialGenotype(config);

        population.evolve(5000);


Turns out the simulation converges pretty quickly:

Figure 2. 3 6-sided nontransitive dices


For the solution above, the max win/loss ratio you can get is 66.7%, and average for all 3 dices is about 63%. This seems to be maximum possible win/loss ratio for a set of 3 dices.

It is possible to find more than 3-dice loops. Here is one with dodecahedron dices:

Figure 3. 4 dodecahedron nontransitive dices


Here, all dice pairs have the possibility of draw. Taking this into account, the average win/loss ratio for the loop is about 8.7%. Meaning in a game by these rules, the player with better dice from the loop above would get 58.7% of all points.

4. Japanese stone garden

4.1. Problem statement

Let's try to place a set of N stones on a 2d hexagonal grid in such a way that only N-1 stones are visible from any point inside some designated view area. Also, every stone should be visible from at least one viewpoint. In case of a need to impose some restrictions on the viewing area configuration, let's try to make viewing area as big as possible. Also, we will consider two cases:

  1. 1 stone per grid cell, stones are identical, each stone blocks the view behind itself.

  2. 1 stone per grid cell, stones can be of two types - big and small ones, big stones block the view, small don't.

4.2. Specifics of hexagonal field of view

Now, let's see how we are going to determine what is viewable from a given point on a grid. This is called the "field of view" problem, and I'm using here an implementation similar to the one described here: Clark Verbrugge’s Hex Grids (section 7).

The FOV algorithm has the following properties:

  1. FOV is calculated as if the observer stands precisely in the center of a hex.

  2. If a hex "blocks" the view, it means that every pixel in the hex blocks the view. In other words, the "object" blocking the view occupies the whole hex.

  3. If a single pixel of a hex is visible, then the whole hex is considered to be visible.

Figure 4. Example of the hexagonal FOV


In the picture above, gray hexes are blocked from view. Blue lines show corner-case rays. You can see that no blue line crosses gray hex (that's what makes them not visible). Because of rule (3) above, there are some artifacts like discontinuous areas of non-visible hexes. This rule can be improved (for example, consider a hex to be visible only when it's center is visible), but we will left it as is for now.

4.3. GA chromosome and fitness function

Since a chromosome must describe a potential solution, it should contain an information of where to put our N stones. And, for each stone, "know" what kind of a stone it is (in case we have 2 kinds of stones, big and small ones). If we have some point of origin (say, garden's center) then representing N stones is easy. We can do it, for example, in hexagonal coordinates.

Figure 5. 4-gene chromosome describes a way of putting down 4 stones


In the picture above, gray area designates the garden (i.e. the area where stones could be placed). The garden's center is at (0, 0) hex. Observation area is colored with pink (i.e. an observer can view the garden from any of 14 view points). This example chromosome describes where to put 2 big and 2 small stones on the area.

Example 11. Example stone garden gene implementation

public class StoneSpec {

    IStone _stone;                  // defines the stone's kind (big/small)
    IPoint _point;                  // defines the point, where the stone should be placed

    // ... lots of trivial stuff omitted (constructors/setters/getters/etc)
}


public class MoveGene extends BaseGene {

    private StoneSpec _stoneSpec;   // one gene is one stone
    
    public MoveGene(Configuration aConfiguration) throws InvalidConfigurationException {
        super(aConfiguration);
        _stoneSpec = new StoneSpec(PointRadial.ZERO, SmallStone.INSTANCE); // init with a small stone in the center
    }

    @Override
    protected Object getInternalValue() {
        return _stoneSpec;
    }

    @Override
    public int size() {
        return 3;
    }

    // ... the rest is omitted, it's analoguos to DiceGene described above
}

Interesting thing here is the gene's size. It's 3, because there are 3 things to change when mutating: X/Y coordinates of the stone, and its kind (big or small). We address this in the applyMutation() method:

    @Override
    public void applyMutation(int index, double intensity) {
        switch (index) {
        case 0: 
            // ... mutate radius
            break;
        case 1: 
            // ... mutate angle
            break;
        case 2: 
            // ... mutate stone type
            break;
        default:
            assert (false) : "shouldn't happen";
        }
    }

Note

When solving the problem with only one kind of stones, one can simply return 2 as a gene's size, thus never mutating stone kind.


A chromosome is now constructed easily, in a similar to the dice problem way:

Example 12. Stone garden chromosome construction

        Gene[] genes = new Gene[Globals.NUMBER_OF_STONES];
        for (int i = 0; i < genes.length; i++)
            genes[i] = new MoveGene(_config);

        IChromosome chromosome = new Chromosome(_config, genes);


Now, let's look at the fitness function structure.

  1. We need to "direct" GA towards an ideal solution (N-1 stones visible), so, let's give bigger score to the solutions where the number of visible stones is closer to N-1.

  2. Also, we are not interested in configurations where not every stone is visible from at least one observation point, so let's decrease their score.

  3. And finally, since our chromosome implementation doesn't take care of stones placed on the same hex, let's decrease score of configurations where less than N stones have unique hex coordinates.

Example 13. Fitness function pseudo code

for a given chromosome:
  put all stones to the garden
  if number of uniquely put stones < Ntotal
    return 1                                                // completely discard configuration if we are unable to put all stones uniquely
  
  fitness = 0
  for each allowed viewpoint
    build FOV and determine Nvisible
    put all visible stones to Svisible set
    fitness = fitness + 1000 * (Ntotal - |Nvisible-Ntarget|)  // add more to the fitness value if number of visible stones is close to ideal
  end for

  if number of stones in Svisible set is not Ntotal          // halve the value if not all stones can be viewed from whole viewing area
    fitness = fitness / 2

  return fitness
end

Here, Ntotal is total number of stones, or 15, Nvisible is number of stones visible from a viewpoint, Ntarget is number of stones we want to be visible from any given viewpoint (14 in our case), and Svisible is a set accumulating visible stones for the whole observation area.


4.4. Resulting gardens

Ok, it's time now to finally see some solutions. I have to admit, they are not as interesting as I hoped for them to be. But, original Japanese garden configuration turned out to be not so interesting either. More on this later.

Figure 6. Viewing area of 20 hex size ( full size, 442Kb )


Figure 7. Viewing area of 45 hex size (full size, 1Mb)


The two solutions above are somewhat lame, since only 2 stones are alternating when observer moves. We can try to change this by increasing viewing area length:

Figure 8. Viewing area of 27 hex size (full size, 578Kb)


We can also try to make the viewing area surround the garden:

Figure 9. 18-hex viewing area around the garden (full size, 497Kb)


And in the end, let's look what we have for 2-kind stones problem:

Figure 10. 28-hex viewing area, big/small stones (full size, 529Kb)


In the picture above, blue stones are small ones (they don't block the view). Blocking stones are shown with red.

5. Conclusion

We have seen how one can utilize genetic algorithms for solving of two problems - searching for a set of nontransitive dices and placing a number of stones so they have a certain properties. Found Japanese garden solutions are a little bit anticlimactic - there is no symmetry and no particular "secret" of creating such configurations. That being said, the real Japanese garden has somewhat disappointing configuration too - stones are of different sizes, placed in no apparent order, it seems that a small amount of stones are alternating between visible/invisible for different viewpoints (unconfirmed, but the number might be as little as 2 stones), and the viewing area is strictly confined (see, for example, Visual structure of a Japanese Zen garden, Brief Communications by Nature Publishing Group).

Possible directions for improvement are:

  • Using different-sized (occupying several hexes) rocks.

  • Try to create 360° viewing area, enclosing the garden inside.

  • Stop using hexagonal grid and move into purely continuous space.

6. Further reading

No comments:

Post a Comment

Google+ Badge