AI如何为战列舰的遗传编程建模

Question

我有一个关于遗传编程的问题。我将致力于game called Battleships的遗传算法。

我的问题是:我如何决定AI进化的“决策”模型？这是如何工作的呢？

我读了很多关于使用不同模型的论文和答案，但找不到具体的东西，不幸的是，我显然需要考虑这个问题。

我希望它在多次迭代中进化，并“学习”最有效的方法，但不确定如何保存这些“决定”(我知道如何保存到文件中，但如何“编码”？)以一种好的方式，因此它将学会对以前的操作采取立场，并基于当前董事会状态的信息。

我一直在考虑一种“树结构”，作为人工智能决策的基础，但我实际上不知道如何开始。

如果有人能给我指出正确的方向(链接？一些伪代码？就像这样)，我会非常感激，我试着尽可能多地搜索，看了很多关于这个话题的youtube视频，但我想我只需要在正确的方向上稍微推动一下。

我可能也不知道到底要搜索什么，这就是为什么我在实现什么和如何实现时没有得到任何结果。

Answer 1

答案第一部分：遗传算法的基础是有一组参与者，其中一些是复制的。选择最健康的进行繁殖，后代是父母的副本，略有变异。这是一个非常简单的概念，但要对其进行编程，您必须具有可以随机选择和动态修改的操作。对于战舰模拟，我创建了一个名为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轴上的+-3和Y轴上的+- 3之间随机选择。是的，100个镜头有点夸张，但嘿，随便了。向这个Shooter.testShooter传递一个Ship，它会给自己打分，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());
        }
    }
}

该代码从run方法中读取为伪代码:创建一个firstGeneration，然后迭代若干代。对于每一代，为ship设置一个newOrientation，然后执行testShooters，并使用Collections.sort对测试结果进行排序。测试的printAverageScore，然后构建nextGeneration。有了平均分的列表，你就可以，咳嗽，做一个‘分析’。

结果的图表如下所示：

​

正如你所看到的，它一开始的平均分数很低，但很快就学会了。然而，船的方向不断变化，除了随机分量外，还会产生一些噪声。每隔一段时间，一个突变就会让群体变得有点混乱，但随着群体的整体进步，这种情况会越来越少。

挑战，以及许多论文肯定的原因，是让更多的东西变得可变，特别是以一种建设性的方式。例如，快照的数量可以是可变的。或者，用一棵根据最后一次射击是命中还是未命中而分枝的树来替换射击列表可能会改善情况，但很难说。这就是“决策”逻辑考虑的地方。是有一个随机拍摄列表更好，还是有一棵树根据前一个拍摄决定采用哪个分支？更高层次的挑战包括预测哪些变化将使群体学习更快，更不容易受到不良突变的影响。

最后，考虑可能有多个组，例如，一个组是战舰猎人，一个组是潜艇猎人。尽管每个群体都有相同的代码，但它们可以“进化”出不同的内部“遗传学”，从而使它们能够专门完成自己的任务。

无论如何，像往常一样，从简单的东西开始，边学边学，直到你变得足够好，可以继续阅读论文。

PS>也需要这样：

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);
    }
}

UDATE:增加了Ship类，修复了几个bug：

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();
    }
}

Answer 2

我会向你推荐另一种方法。这种方法是基于船舶可能所在位置的可能性。我会在游戏的一个小版本上给你展示一个例子(所有其他版本的想法都是一样的)。在我的示例中，它是3x3区域，并且只有一艘1x2船。

现在，您需要一个空白区域，并将船放在所有可能的位置(存储船的一部分在矩阵元素中的次数)。如果您将对ship 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

它告诉你下一次拍摄的4个不同的可能位置。

例如，如果您错过了上一步的，您将获得以下矩阵：

2 2 2
2 M 2
2 2 2

这是基本的想法。您如何尝试重新定位船只的方式是基于规则，如何定位船只，以及您在每次移动后获得的信息。它可以是missed/got或missed/wounded/killed。

Answer 3

答案第二部分：遗传算法本身不是目的，它是实现目的的一种手段。在这个战列舰的例子中，最终目的是制造出最好的Shooter。我在程序的前一个版本中添加了a行，以输出最佳射手的射击模式，并注意到一些错误：

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);
    }
}

现在，当我运行模拟时，我得到了输出的平均值。图表通常如下所示：

同样，射手学得很快，但随机变化需要一段时间才能降低平均值。现在我最好的Shooter变得更有意义了：

Best=Shooter:6:[(1,0), (0,0), (0,-1), (2,0), (-2,0), (0,1), (-1,0), (0,-2), ...

因此，一个遗传算法正在帮助我设置我的Shooter的配置，但正如这里的另一个答案所指出的那样，只要考虑一下就可以得到好的结果。考虑一下，如果我有一个神经网络，其中有10种可能的设置，每个设置中有100个可能的值，那就是10^100个可能的设置，这些设置应该如何设置的理论可能比战舰射击理论更难一些。在这种情况下，遗传算法可以帮助确定最佳设置并测试当前理论。