人工智能如何为战舰进行基因编程建模

我有一个关于基因编程的问题。我将研究遗传算法游戏名为战舰.

我的问题是：我如何决定人工智能进化的“决策”模型？这是如何运作的？

我已经阅读了多篇论文和多个答案，这些论文和答案只是谈到使用不同的模型，但找不到具体的内容，不幸的是，我显然需要集中精力解决这个问题。

我希望它能够经过多次迭代而发展，并“学习”什么最有效，但不确定如何保存这些“决定”（我知道保存到文件中，但如何“编码”？） 以一种好的方式，所以它将学会对之前的行动采取立场，并根据当前董事会状态的信息。

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

如果有人可以给我指出正确的方向（链接？一些伪代码？类似的东西），那将非常感激，我尝试尽可能多地搜索谷歌，观看有关该主题的多个 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 轴的 +-3 和 Y 轴的 +-3 之间随机选择。是的，100 次射击有点过头了，但是，嘿，无论如何。通过一个Ship对此Shooter.testShooter它会给自己打分，100 分是最好的分数，0 是最差的分数。

This Shooter演员有reproduce and 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然后迭代若干代。对于每一代，设置一个newOrientation对于船，然后做testShooters，并对测试结果进行排序Collections.sort. printAverageScore的测试，然后构建nextGeneration。通过平均分数列表，您可以咳咳，进行“分析”。

A graph of the results looks like this:

正如您所看到的，它一开始的平均分数相当低，但学得很快。然而，船舶的方向不断变化，除了随机分量之外还会产生一些噪声。时不时地，突变会给群体带来一些混乱，但随着群体整体的进步，这种情况会越来越少。

挑战，以及许多论文肯定的原因，是让更多的事情变得可变，特别是以建设性的方式。例如，镜头的数量可以是可变的。或者，将镜头列表替换为一棵树，该树的分支取决于最后一个镜头是命中还是未命中might改善事情，但这很难说。这就是“决策”逻辑考虑的来源。拥有一个随机镜头列表或一棵根据先前镜头决定采用哪个分支的树是更好吗？更高级别的挑战包括预测哪些变化将使团队学习得更快并且不易受到不良突变的影响。

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

不管怎样，一如既往，从简单的地方开始，边学边学，直到你足够好，可以回去阅读论文。

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

更新日期：已添加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();
    }
}