Table of Contents
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.
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.
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
Geneinterface. -
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
IChromosomeinterface. -
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.
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.
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);
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:
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
-
Throughout the algorithm, maintain a set of unique loops found (_loops). Also maintain a set of visited rows (_visited).
-
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.
-
Create a candidate loop instance starting with dice number found in the 2nd step. Let's call this loop 'current'.
-
Traverse 'current' in the following fashion:
-
Take the last index i in the 'current' loop (representing the last dice in the loop candidate).
-
Look through mi row performing step 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).
-
-
When finished traversing, remove the last index in the 'current' loop.
-
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.
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:
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:
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.
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 stone per grid cell, stones are identical, each stone blocks the view behind itself.
-
1 stone per grid cell, stones can be of two types - big and small ones, big stones block the view, small don't.
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:
-
FOV is calculated as if the observer stands precisely in the center of a hex.
-
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.
-
If a single pixel of a hex is visible, then the whole hex is considered to be visible.
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.
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.
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.
-
We need to "direct" GA towards an ideal solution (
N-1stones visible), so, let's give bigger score to the solutions where the number of visible stones is closer toN-1. -
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.
-
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
Nstones 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.
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.
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:
We can also try to make the viewing area surround the garden:
And in the end, let's look what we have for 2-kind stones problem:
In the picture above, blue stones are small ones (they don't block the view). Blocking stones are shown with
red.
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.
-
Wikipedia's entry on "Nontransitive dice"
Has examples of various nontransitive dice sets, including ones with additional symmetries or properties.
-
Wikipedia's entry on "Japanese rock garden"
Good explanation of what it is plus some photos.
-
Visual structure of a Japanese Zen garden
Somewhat obscure article from Nature's "Brief Communications", but it has an aerial shot of Ryoanji garden and its viewing area.
-
Excellent write-up on hexagonal grid problems, including FOV algorithm.
-
Two related articles in this blog:
No comments:
Post a Comment