AI如何为战列舰建立遗传规划模型
我有一个关于遗传编程的问题。 我将为一款名为Battleships的游戏开发一种遗传算法。
我的问题是：我如何决定人工智能的“决策”模型？ 这是如何工作的？
我已经阅读了多篇论文和多个答案，只是谈论使用不同的模型，但找不到具体的东西，不幸的是，我显然需要围绕这个问题。
我希望它能够在多次迭代中进化并“学习”最有效的方法，但不确定如何以一种好的方式保存这些“决定”（我知道一个文件，但“编码”如何？），所以它会学会采取先前行动的立场，并根据当前董事会状态的信息。
我一直在考虑为人工智能制定“树结构”，但我实际上并不知道如何开始。
如果有人可以指出我正确的方向（一个链接？一些伪代码？类似的东西），非常感谢，我尽可能地尝试谷歌，观看有关该主题的多个YouTubevideo，但我想我只需要朝着正确的方向微动一点。
我也可能只是不知道究竟要搜索什么，这就是为什么我对于实现此内容以及如何实现此结果的结果空白。
回答第一部分：遗传算法的基础是拥有一组演员，其中一些演员重现。 选择适者进行繁殖，后代是略有变异的父母的副本。 这是一个非常简单的概念，但要编程它，你必须有可以随机选择和动态修改的动作。 对于战舰模拟我创建了一个叫做Shooter的类，因为它在某个位置“射击”。 这里的假设是第一个位置被击中，射手现在正试图沉没战列舰。
public class Shooter implements Comparable { private static final int NUM_SHOTS = 100; private List shots; private int score; // Make a new set of random shots. public Shooter newShots() { shots = new ArrayList (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 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 pShots) { // copy parent's shots (okay for shallow) shots = new ArrayList (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演员有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 shooters = new ArrayList (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 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方法读取为伪代码：make 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类，修复了一些错误：
public class Ship { List 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 (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
它告诉你下一次拍摄的4个不同位置。
例如，如果您错过了上一步 ，您将获得以下矩阵：
2 2 2 2 M 2 2 2 2
这是基本的想法。 您尝试重新定位船舶的方式取决于船舶如何定位的规则以及每次移动后您获得的信息。 它可能被missed/got或missed/wounded/killed 。
回答第三部分：正如您所看到的， Genetic Algorithm通常不是困难的部分。 再一次，它是一段简单的代码，真正意味着要运用另一段代码，即演员。 这里，actor是在Shooter类中实现的。 这些演员通常以车床的方式建模，在某种意义上，演员有一组输入的定义输出。 GA可帮助您确定state table的最佳配置。 在此问题的先前答案中， 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坐标对。 问题是“这可以做得更好吗？” 取决于人类的聪明才智。 遗传算法不能为我们写新的演员。 我想知道decision tree是否可以比概率矩阵做得更好，所以我实现了一个尝试它：
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类是node中的一个node （好的，可能名字很差）。 每次射击时，选择的下一个分支取决于射击是否被击中。
射手有些修改以使用新的decisionTree 。
public class Shooter implements Comparable { 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());
现在，典型模拟运行的图表如下所示：
如您所见，使用Decision Tree演变的最终最佳平均分数比Probability Matrix的最佳平均分数低一个镜头。 还要注意，这组Shooters已经花了大约800代训练到他们的最佳状态，大约是简单概率矩阵Shooters两倍。 最佳决策树Shooter给出了这个结果：
BEST Ave=4, Min=3, Max=6 Best=Shooter:4: [(0,-1)h:(0,1)h:(0,0) ... ]
在这里，不仅平均值减少一次射击，而且最大射击次数比概率矩阵Shooter低1/3。
在这一点上，需要一些非常聪明的人来确定这个演员是否已经达到问题领域的理论最优，即，这是你试图沉没3X3船的最佳方法吗？ 考虑到这个问题的答案在真正的战舰游戏中会变得更加复杂，这种游戏有几种不同大小的船只。 你将如何建立一个演员，该演员将已经沉没的哪些船只的知识融入到randomly chosen and dynamically modified行动中？ 在这里，理解图灵机（也称为CPU）变得非常重要。
PS>您还需要这门课程：
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; } }
回答第二部分 ：遗传算法本身并不是目的，它是实现目标的手段。 在这个战舰的例子的情况下，最终是制作最好的Shooter 。 我在程序的先前版本中添加了一行，以输出最佳射手的镜头模式，并发现错误：
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 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 (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 { private static final int NUM_SHOTS = 40; private List shots; private int aveScore; // Make a new set of random shots. public Shooter newShots() { shots = new ArrayList (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
现在，当我运行模拟时，我得到平均值的平均值。 该图通常看起来像这样： 
同样，射击者学得很快，但随机变化需要一段时间才能降低平均值。 现在我最好的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个可能的设置以及如何设置这些设置的理论可能比战舰射手理论要困难一些。 在这种情况下，遗传算法可以帮助确定最佳设置和测试当前理论。