ANSWER PART III: As you can see, the Genetic Algorithm is generally not the hard part. Again, it's a simple piece of code that is really meant to exercise another piece of code, the actor. Here, the actor is implemented in a Shooter class. These actor's are often modelled in the fashion of Turning Machines, in the sense that the actor has a defined set of outputs for a set of inputs. The GA helps you to determine the optimal configuration of the state table. In the prior answers to this question, the Shooter implemented a probability matrix like what was described by @SalvadorDali in his answer.
Testing the prior Shooter thoroughly, we find that the best it can do is something like:
BEST Ave=5, Min=3, Max=9
Best=Shooter:5:[(1,0), (0,0), (2,0), (-1,0), (-2,0), (0,2), (0,1), (0,-1), (0,-2), (0,1)]
This shows it takes 5 shots average, 3 at a minimum, and 9 at a maximum to sink a 3X3 battleship. The locations of the 9 shots are shown a X/Y coordinate pairs. The question "Can this be done better?" depends on human ingenuity. A Genetic Algorithm can't write new actors for us. I wondered if a decision tree could do better than a probability matrix, so I implemented one to try it out:
public class Branch {
private static final int MAX_DEPTH = 10;
private static final int MUTATE_PERCENT = 20;
private Branch hit;
private Branch miss;
private Position shot;
public Branch() {
shot = new Position(
(int)((Math.random()*6.0)-3),
(int)((Math.random()*6.0)-3)
);
}
public Branch(Position shot, Branch hit, Branch miss) {
this.shot = new Position(shot.x, shot.y);
this.hit = null; this.miss = null;
if ( hit != null ) this.hit = hit.clone();
if ( miss != null ) this.miss = miss.clone();
}
public Branch clone() {
return new Branch(shot, hit, miss);
}
public void buildTree(Counter c) {
if ( c.incI1() > MAX_DEPTH ) {
hit = null;
miss = null;
c.decI1();
return;
} else {
hit = new Branch();
hit.buildTree(c);
miss = new Branch();
miss.buildTree(c);
}
c.decI1();
}
public void shoot(Ship ship, Counter c) {
c.incI1();
if ( ship.madeHit(shot)) {
if ( c.incI2() == ship.getSize() ) return;
if ( hit != null ) hit.shoot(ship, c);
}
else {
if ( miss != null ) miss.shoot(ship, c);
}
}
public void mutate() {
if ( (int)(Math.random() * 100.0) < MUTATE_PERCENT) {
shot.x = (int)((Math.random()*6.0)-3);
shot.y = (int)((Math.random()*6.0)-3);
}
if ( hit != null ) hit.mutate();
if ( miss != null ) miss.mutate();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(shot.toString());
if ( hit != null ) sb.append("h:"+hit.toString());
if ( miss != null ) sb.append("m:"+miss.toString());
return sb.toString();
}
}
The Branch class is a node in a decision tree (ok, maybe poorly named). At every shot, the next branch chosen depends on whether the shot was awarded a hit or not.
The shooter is modified somewhat to use the new decisionTree.
public class Shooter implements Comparable<Shooter> {
private Branch decisionTree;
private int aveScore;
// Make a new random decision tree.
public Shooter newShots() {
decisionTree = new Branch();
Counter c = new Counter();
decisionTree.buildTree(c);
return this;
}
// Test this shooter against a ship
public int testShooter(Ship ship) {
Counter c = new Counter();
decisionTree.shoot(ship, c);
return c.i1;
}
// compare this shooter to other shooters, reverse order
@Override
public int compareTo(Shooter o) {
return o.aveScore - aveScore;
}
// mutate this shooter's offspring
public void mutate(Branch pDecisionTree) {
decisionTree = pDecisionTree.clone();
decisionTree.mutate();
}
// min, max, setters, getters
public int getAveScore() {
return aveScore;
}
public void setAveScore(int aveScore) {
this.aveScore = aveScore;
}
public Branch getDecisionTree() {
return decisionTree;
}
@Override
public String toString() {
StringBuilder ret = new StringBuilder("Shooter:"+aveScore+": [");
ret.append(decisionTree.toString());
return ret.append(']').toString();
}
}
The attentive reader will notice that while the methods themselves have changed, which methods a Shooter needs to implement is not different from the prior Shooters. This means the main GA simulation has not changed except for one line related to mutations, and that probably could be worked on:
Shooter child = shooters.get(l);
child.mutate( shooters.get(NUM_SHOOTERS - l - 1).getDecisionTree());
A graph of a typical simulation run now looks like this:
As you can see, the final best average score evolved using a Decision Tree is one shot less than the best average score evolved for a Probability Matrix. Also notice that this group of Shooters has taken around 800 generations to train to their optimum, about twice as long than the simpler probability matrix Shooters. The best decision tree Shooter gives this result:
BEST Ave=4, Min=3, Max=6
Best=Shooter:4: [(0,-1)h:(0,1)h:(0,0) ... ]
Here, not only does the average take one shot less, but the maximum number of shots is 1/3 lower than a probability matrix Shooter.
At this point it takes some really smart guys to determine whether this actor has achieved the theoretical optimum for the problem domain, i.e., is this the best you can do trying to sink a 3X3 ship? Consider that the answer to that question would become more complex in the real battleship game, which has several different size ships. How would you build an actor that incorporates the knowledge of which of the boats have already been sunk into actions that are randomly chosen and dynamically modified? Here is where understanding Turing Machines, also known as CPUs, becomes important.
PS> You will need this class also:
public class Counter {
int i1;
int i2;
public Counter() {i1=0;i2=0;}
public int incI1() { return ++i1; }
public int incI2() { return ++i2; }
public int decI1() { return --i1; }
public int decI2() { return --i2; }
}
