我有一个关于遗传编程的问题。我打算为名为战舰的游戏设计一种遗传算法。
我的问题是：我该如何确定AI进化的“决策”模型？这是如何实现的？
我已经阅读了多篇论文和多个回答，但没有找到具体的信息，不幸的是，我似乎需要在这个问题上思考。
我希望它能在多次迭代中进化并“学习”什么最好，但不确定如何以良好的方式保存这些“决策”（我知道要保存到文件中，但是“编码”应该如何进行？），以便它将会对先前的行动采取立场，并基于当前棋盘状态的信息。
我一直在考虑为AI构建一种“树形结构”来作为基础进行决策，但我不知道如何开始。
如果有人可以指点我正确的方向（链接？伪代码？之类的东西），那将不胜感激。我尝试了尽可能多地搜索谷歌，观看了多个有关此主题的YouTube视频，但我认为我只需要在正确的方向上得到一点推动。
我可能不知道该搜索什么，这就是为什么我在实现这个过程中找不到结果的原因。
Shooter的类，因为它会“射击”到一个位置。这里的假设是第一个位置已经被击中，现在射手正在试图击沉战舰。public class Shooter implements Comparable<Shooter> {
private static final int NUM_SHOTS = 100;
private List<Position> shots;
private int score;
// Make a new set of random shots.
public Shooter newShots() {
shots = new ArrayList<Position>(NUM_SHOTS);
for (int i = 0; i < NUM_SHOTS; ++i) {
shots.add(newShot());
}
return this;
}
// Test this shooter against a ship
public void testShooter(Ship ship) {
score = shots.size();
int hits = 0;
for (Position shot : shots) {
if (ship.madeHit(shot)) {
if (++hits >= ship.getSize())
return;
} else {
score = score - 1;
}
}
}
// get the score of the testShotr operation
public int getScore() {
return score;
}
// compare this shooter to other shooters.
@Override
public int compareTo(Shooter o) {
return score - o.score;
}
// getter
public List<Position> getShots() {
return shots;
}
// reproduce this shooter
public Shooter reproduce() {
Shooter offspring = new Shooter();
offspring.mutate(shots);
return offspring;
}
// mutate this shooter's offspring
private void mutate(List<Position> pShots) {
// copy parent's shots (okay for shallow)
shots = new ArrayList<Position>(pShots);
// 10% new mutations, in random locations
for (int i = 0; i < NUM_SHOTS / 10; i++) {
int loc = (int) (Math.random() * 100);
shots.set(loc, newShot());
}
}
// make a new random move
private Position newShot() {
return new Position(((int) (Math.random() * 6)) - 3, ((int) (Math.random() * 6)) - 3);
}
}
Shooter有最多100次射击机会，随机选择在X轴和Y轴上+-3之间。是的，100次射击可能过度了，但是无所谓。将一个Ship传递给Shooter.testShooter，它将自行评分，100分为最佳得分，0分为最差得分。Shooter演员具有reproduce和mutate方法，将返回一个后代，其10％的射击机会将被随机突变。总体思路是，最好的Shooters已经“学会”以尽可能快的速度以十字形（“+”）射击，因为船只朝向四个方向（北、南、东、西）中的一个。ShooterSimulation非常简单：public class ShooterSimulation {
private int NUM_GENERATIONS = 1000;
private int NUM_SHOOTERS = 20;
private int NUM_SHOOTERS_NEXT_GENERATION = NUM_SHOOTERS / 10;
List<Shooter> shooters = new ArrayList<Shooter>(NUM_SHOOTERS);
Ship ship;
public static void main(String... args) {
new ShooterSimulation().run();
}
// do the work
private void run() {
firstGeneration();
ship = new Ship();
for (int gen = 0; gen < NUM_GENERATIONS; ++gen) {
ship.newOrientation();
testShooters();
Collections.sort(shooters);
printAverageScore(gen, shooters);
nextGeneration();
}
}
// make the first generation
private void firstGeneration() {
for (int i = 0; i < NUM_SHOOTERS; ++i) {
shooters.add(new Shooter().newShots());
}
}
// test all the shooters
private void testShooters() {
for (int mIdx = 0; mIdx < NUM_SHOOTERS; ++mIdx) {
shooters.get(mIdx).testShooter(ship);
}
}
// print the average score of all the shooters
private void printAverageScore(int gen, List<Shooter> shooters) {
int total = 0;
for (int i = 0, j = shooters.size(); i < j; ++i) {
total = total + shooters.get(i).getScore();
}
System.out.println(gen + " " + total / shooters.size());
}
// throw away the a tenth of old generation
// replace with offspring of the best fit
private void nextGeneration() {
for (int l = 0; l < NUM_SHOOTERS_NEXT_GENERATION; ++l) {
shooters.set(l, shooters.get(NUM_SHOOTERS - l - 1).reproduce());
}
}
}
如您所见，它开始时的平均分数相当低，但学习速度很快。然而，船的方向不断变化，除了随机因素外还会产生一些噪声。偶尔会出现突变，但随着整个群体的改善，这种情况越来越少。public class Position {
int x;
int y;
Position(int x, int y ) {this.x=x; this.y=y;}
@Override
public boolean equals(Object m) {
return (((Position)m).x==x && ((Position)m).y==y);
}
}
更新：添加了Ship类，修复了一些错误：
public class Ship {
List<Position> positions;
// test if a hit was made
public boolean madeHit(Position shot) {
for (Position p: positions) {
if ( p.equals(shot)) return true;
}
return false;
}
// make a new orientation
public int newOrientation() {
positions = new ArrayList<Position>(3);
// make a random ship direction.
int shipInX=0, oShipInX=0 , shipInY=0, oShipInY=0;
int orient = (int) (Math.random() * 4);
if( orient == 0 ) {
oShipInX = 1;
shipInX = (int)(Math.random()*3)-3;
}
else if ( orient == 1 ) {
oShipInX = -1;
shipInX = (int)(Math.random()*3);
}
else if ( orient == 2 ) {
oShipInY = 1;
shipInY = (int)(Math.random()*3)-3;
}
else if ( orient == 3 ) {
oShipInY = -1;
shipInY = (int)(Math.random()*3);
}
// make the positions of the ship
for (int i = 0; i < 3; ++i) {
positions.add(new Position(shipInX, shipInY));
if (orient == 2 || orient == 3)
shipInY = shipInY + oShipInY;
else
shipInX = shipInX + oShipInX;
}
return orient;
}
public int getSize() {
return positions.size();
}
}
3x3 的区域，只有一艘 1x2 的船。
现在，您需要取一个空白区域，并将船放置在所有可能的位置上（存储船部件在矩阵元素中出现的次数）。如果您对一个 1x2 的船执行此操作，您将得到以下结果：
1 2 1
1 2 1
1 2 1
船可以朝另一个方向 2x1，这将给你以下矩阵：
1 1 1
2 2 2
1 1 1
2 3 2
3 4 3
2 3 2
这意味着最有可能的位置是中间那个（我们有4个的地方）。这就是你应该射击的地方。
现在假设你击中了船的一部分。如果重新计算可能性矩阵，将得到：
0 1 0
1 W 1
0 1 0
这个程序会告诉你下一步射击的四个不同可能位置。
例如，如果你在上一步中没有命中，你将得到以下矩阵：
2 2 2
2 M 2
2 2 2
答案第二部分：遗传算法本身并不是目的，而是实现目标的手段。在这个战舰游戏的例子中，目标是制作出最好的射手。我在之前版本的程序中添加了一行代码来输出最佳射手的射击模式，并发现了一些问题：
Best shooter = Shooter:100:[(0,0), (0,0), (0,0), (0,-1), (0,-3), (0,-3), (0,-3), (0,0), (-2,-1) ...]
这个模式中的前三枪是在坐标（0,0）处，即使它们击中同一点，在这个应用程序中也是保证命中的。在战舰游戏中，多次击中同一点是违反规则的，因此这个“最佳”射手之所以最佳，是因为它学会了作弊！
因此，显然需要改进程序。为了做到这一点，我更改了Ship类，如果已经击中了一个位置，则返回false。
public class Ship {
// private class to keep track of hits
private class Hit extends Position {
boolean hit = false;
Hit(int x, int y) {super(x, y);}
}
List<Hit> positions;
// need to reset the hits for each shooter test.
public void resetHits() {
for (Hit p: positions) {
p.hit = false;
}
}
// test if a hit was made, false if shot in spot already hit
public boolean madeHit(Position shot) {
for (Hit p: positions) {
if ( p.equals(shot)) {
if ( p.hit == false) {
p.hit = true;
return true;
}
return false;
}
}
return false;
}
// make a new orientation
public int newOrientation() {
positions = new ArrayList<Hit>(3);
int shipInX=0, oShipInX=0 , shipInY=0, oShipInY=0;
// make a random ship orientation.
int orient = (int) (Math.random() * 4.0);
if( orient == 0 ) {
oShipInX = 1;
shipInX = 0-(int)(Math.random()*3.0);
}
else if ( orient == 1 ) {
oShipInX = -1;
shipInX = (int)(Math.random()*3.0);
}
else if ( orient == 2 ) {
oShipInY = 1;
shipInY = 0-(int)(Math.random()*3.0);
}
else if ( orient == 3 ) {
oShipInY = -1;
shipInY = (int)(Math.random()*3.0);
}
// make the positions of the ship
for (int i = 0; i < 3; ++i) {
positions.add(new Hit(shipInX, shipInY));
if (orient == 2 || orient == 3)
shipInY = shipInY + oShipInY;
else
shipInX = shipInX + oShipInX;
}
return orient;
}
public int getSize() {
return positions.size();
}
}
在我这样做之后，我的射手们停止了“作弊”，但这让我思考了一下整个得分的问题。先前版本的应用程序是根据错过的射击次数进行评分的，因此如果没有任何射击失误，射手可以获得完美的分数。然而，这是不现实的，我真正想要的是射手射出最少的子弹。我改变了射手的记录方式，以跟踪所射击的平均数：
public class Shooter implements Comparable<Shooter> {
private static final int NUM_SHOTS = 40;
private List<Position> shots;
private int aveScore;
// Make a new set of random shots.
public Shooter newShots() {
shots = new ArrayList<Position>(NUM_SHOTS);
for (int i = 0; i < NUM_SHOTS; ++i) {
shots.add(newShot());
}
return this;
}
// Test this shooter against a ship
public int testShooter(Ship ship) {
int score = 1;
int hits = 0;
for (Position shot : shots) {
if (ship.madeHit(shot)) {
if (++hits >= ship.getSize())
return score;
}
score++;
}
return score-1;
}
// compare this shooter to other shooters, reverse order
@Override
public int compareTo(Shooter o) {
return o.aveScore - aveScore;
}
... the rest is the same, or getters and setters.
}
我也意识到，为了能够得到对战舰开火的平均射击次数，我必须对每个射手进行多次测试。因此，我对每个射手单独进行了多次测试。
// test all the shooters
private void testShooters() {
for (int i = 0, j = shooters.size(); i<j; ++i) {
Shooter current = shooters.get(i);
int totalScores = 0;
for (int play=0; play<NUM_PLAYS; ++play) {
ship.newOrientation();
ship.resetHits();
totalScores = totalScores + current.testShooter(ship);
}
current.setAveScore(totalScores/NUM_PLAYS);
}
}
现在，当我运行模拟时，我得到了平均输出的平均值。图表通常看起来像这样：
再次说明，射手们学得相当快，但需要一段时间才能通过随机变化将平均值降低。现在我的最佳射手有点更有意义：
Best=Shooter:6:[(1,0), (0,0), (0,-1), (2,0), (-2,0), (0,1), (-1,0), (0,-2), ...
第三部分答案：正如您所看到的，遗传算法通常不是难点。再次强调，它只是一段简单的代码，真正的目的是为了测试另一段代码——演员。在这里，演员由一个Shooter类实现。这些演员通常以图灵机的方式建模，也就是说，演员对于一组输入有一组定义好的输出。遗传算法帮助您确定状态表的最佳配置。在此问题的先前答案中，Shooter实现了一个概率矩阵，就像@SalvadorDali在他的答案中描述的那样。
经过充分测试之前的Shooter，我们发现它能做到的最好成绩大约是：
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)]
这表明平均需要5次射击，最少3次，最多9次才能击沉一艘3X3的战舰。9次射击的位置显示为X/Y坐标对。问题“是否可以做得更好？”取决于人类的机智。遗传算法不能为我们编写新的演员。我想知道一个决策树是否比概率矩阵更好，所以我实现了一个来尝试一下：
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();
}
}
Branch类是一个决策树中的节点（好吧，可能命名不太好）。在每次射击时，下一个选择的分支取决于该射击是否命中。
射手被修改以使用新的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();
}
}
Shooter需要实现哪些方法与之前的Shooters并没有区别。这意味着主要的GA模拟除了与突变相关的一行代码外，并没有发生变化，而且这可能还可以改进：Shooter child = shooters.get(l);
child.mutate( shooters.get(NUM_SHOOTERS - l - 1).getDecisionTree());
一个典型模拟运行的图像现在看起来像这样：
正如您所看到的，使用决策树进化出的最终最佳平均分数比使用概率矩阵进化出的最佳平均分数少了一次射击。同时请注意，这组射手训练到最佳状态需要约800代，大约是简单概率矩阵射手所需时间的两倍。最佳决策树射手的结果如下：
BEST Ave=4, Min=3, Max=6
Best=Shooter:4: [(0,-1)h:(0,1)h:(0,0) ... ]
在这里，平均数不仅少了一杆，而且最大杆数比概率矩阵射手低1/3。
此时需要一些非常聪明的人来确定这个演员是否已经达到了问题域的理论最优解，也就是说，这是您在尝试击沉3X3船时能做到的最好的吗？考虑到这个问题的答案在真正的战舰游戏中会变得更加复杂，因为它有几种不同大小的船只。您将如何构建一个演员，将已经被击沉的船只的知识纳入到随机选择和动态修改的行动中？这就是理解图灵机（也称为CPU）的重要性所在。
附注> 您还需要这个类：
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; }
}