java - AI 如何为战舰建模遗传编程

Question

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

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

我已经阅读了多篇论文和多个答案，它们只是谈论使用不同的模型，但找不到具体的内容，不幸的是，我显然需要全神贯注地解决这个问题。

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

我一直在考虑让 AI 做出决策的“树结构”，但实际上我不知道如何开始。

如果有人能给我指出正确的方向(链接？一些伪代码？类似的东西)，那将不胜感激，我尽可能多地使用谷歌搜索，观看多个关于主题，但我认为我只需要在正确的方向上稍微插入一下。

我也可能只是不知道到底要搜索什么，这就是为什么我对实现它的内容和方式一无所知。

Answer 1

第 I 部分的答案:遗传算法的基础是拥有一组参与者，其中一些参与者会进行繁殖。选择最适者进行繁殖，后代是 parent 稍有突变的副本。这是一个非常简单的概念，但要对其进行编程，您必须具有可以随机选择和动态修改的操作。对于战舰模拟，我创建了一个名为 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 分是最差分。

这个 Shooter actor 有 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 然后迭代若干代。对于每一代，为飞船设置一个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);
    }
}

更新:添加了 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();
    }
}