Java使用遗传算法，寻找十滴水问题的最优解
近期某手游出了个活动，经确认发现本质为十滴水游戏。
简单说一下规则，棋盘大小通常为6x6，在游戏开始时，棋盘随机有若干水珠，其大小范围为1-4。点击棋盘内的一格，会消耗玩家持有的1个小水滴，同时使得该单元格的水珠大小+1。如果水珠大小超过4，则水珠发生爆炸并消失，同时向四个方向各发射1个小水滴。小水滴匀速前进，前进时遇到第一个水珠则消失，同时该水珠大小+1，或者小水滴遇到棋盘边界而消失。当棋盘被清空时这一关通过，或者玩家持有的水滴耗尽而游戏结束。如果一次操作引发多个水珠爆炸，则每爆炸3个水珠，奖励1个水滴。如果只触发爆炸一次水珠通过这一关，则视为完美通关，额外奖励1个小水滴。对于该游戏，每次通关奖励2个小水滴。
查阅了相关资料后，得到了几条关键思路，即：
1、根据一个确定的盘面和一个坐标，通过计算，可以得到一个确定的执行结果，这样的操作称为一步。
2、一般不会在空白的单元格上设置小水滴，所以随机不停地在有水珠的单元格上添加小水滴，必然在有限的步骤后清空棋盘。
3、暴力遍历的话，由于状态空间太大，只要步数稍多（7步或更长），就不能在合理的时间内找到最优解。
所以，我们可以得到进一步的推论，我们可以使用一个有限且有序的点列表，解决一个盘面，并计算出该解法的小水滴的收益，期间最大投入小水滴的数量等结果。我们最终的目的是使得小水滴的收益最大化。
因此，我决定使用遗传算法，解决本问题。
首先定义游戏关键对象：
1 package bean; 2 3 import main.Game; 4 5 import java.util.HashMap; 6 import java.util.Map; 7 8 /** 9 * 位置点 10 */ 11 public class Point { 12 13 private static final Map<Integer, Map<Integer, Point>> POINT_MAP = new HashMap<>(); 14 15 /** 16 * X坐标 17 */ 18 private final int x; 19 20 /** 21 * Y坐标 22 */ 23 private final int y; 24 25 private Point(int x, int y) { 26 this.x = x; 27 this.y = y; 28 } 29 30 /** 31 * 获取一个点对象 32 * 33 * @param x X坐标 34 * @param y Y坐标 35 * @return 生成的点对象 36 */ 37 public static Point get(int x, int y) { 38 Map<Integer, Point> subPointMap = POINT_MAP.computeIfAbsent(x, i -> new HashMap<>()); 39 return subPointMap.computeIfAbsent(y, i -> new Point(x, y)); 40 } 41 42 public int getX() { 43 return x; 44 } 45 46 public int getY() { 47 return y; 48 } 49 50 public boolean isValidPosition() { 51 return x >= 0 && y >= 0 && x < Game.X && y < Game.Y; 52 } 53 54 @Override 55 public String toString() { 56 return String.format("(%s,%s)", x, y); 57 } 58 }
1 package bean; 2 3 /** 4 * 子弹对象，即爆裂发生时需要计算随时间变化的结果 5 */ 6 public class Bullet { 7 8 /** 9 * X坐标 10 */ 11 private int x; 12 13 /** 14 * Y坐标 15 */ 16 private int y; 17 18 /** 19 * X变化率 20 */ 21 private int dx; 22 23 /** 24 * Y变化率 25 */ 26 private int dy; 27 28 public Bullet() { 29 } 30 31 public Bullet(int x, int y, int dx, int dy) { 32 this.x = x; 33 this.y = y; 34 this.dx = dx; 35 this.dy = dy; 36 } 37 38 public Bullet(Point point, int dx, int dy) { 39 this(point.getX(), point.getY(), dx, dy); 40 } 41 42 public int getX() { 43 return x; 44 } 45 46 public void setX(int x) { 47 this.x = x; 48 } 49 50 public int getY() { 51 return y; 52 } 53 54 public void setY(int y) { 55 this.y = y; 56 } 57 58 public int getDx() { 59 return dx; 60 } 61 62 public void setDx(int dx) { 63 this.dx = dx; 64 } 65 66 public int getDy() { 67 return dy; 68 } 69 70 public void setDy(int dy) { 71 this.dy = dy; 72 } 73 74 /** 75 * 子弹移动一个回合 76 * 77 * @return 移动后的位置 78 */ 79 public Point move() { 80 x += dx; 81 y += dy; 82 return Point.get(x, y); 83 } 84 }
1 package bean; 2 3 /** 4 * 游戏的行动结果对象，会进行缓存 5 */ 6 public class MoveResult { 7 8 /** 9 * 行动后的盘面 10 */ 11 private int[][] arr; 12 13 /** 14 * 行动后获得的收益(可以由combo计算出) 15 */ 16 private int reward; 17 18 /** 19 * 行动连击数量，即本次行动导致多少爆炸 20 */ 21 private int combo; 22 23 public MoveResult() { 24 25 } 26 27 public MoveResult(int[][] arr, int reward, int combo) { 28 this.arr = arr; 29 this.reward = reward; 30 this.combo = combo; 31 } 32 33 public int[][] getArr() { 34 return arr; 35 } 36 37 public void setArr(int[][] arr) { 38 this.arr = arr; 39 } 40 41 public int getReward() { 42 return reward; 43 } 44 45 public void setReward(int reward) { 46 this.reward = reward; 47 } 48 49 public int getCombo() { 50 return combo; 51 } 52 53 public void setCombo(int combo) { 54 this.combo = combo; 55 } 56 }
1 package bean; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 6 /** 7 * 遗传算法使用的解答 8 */ 9 public class Answer { 10 11 /** 12 * 操作链，存储依次的执行操作 13 */ 14 private final List<Point> pointList = new ArrayList<>(); 15 16 /** 17 * 爆炸次数 18 */ 19 private int burstCount; 20 21 /** 22 * 累计的收益 23 */ 24 private int totalReward; 25 26 /** 27 * 区间最低收益 28 */ 29 private int minReward; 30 31 public Answer() { 32 } 33 34 public Answer(List<Point> pointList) { 35 this.pointList.addAll(pointList); 36 } 37 38 public List<Point> getPointList() { 39 return pointList; 40 } 41 42 public int getBurstCount() { 43 return burstCount; 44 } 45 46 public void setBurstCount(int burstCount) { 47 this.burstCount = burstCount; 48 } 49 50 public int getTotalReward() { 51 return totalReward; 52 } 53 54 public void setTotalReward(int totalReward) { 55 this.totalReward = totalReward; 56 } 57 58 public int getMinReward() { 59 return minReward; 60 } 61 62 public void setMinReward(int minReward) { 63 this.minReward = minReward; 64 } 65 66 /** 67 * 获取解的长度 68 * 69 * @return 解的长度 70 */ 71 public int length() { 72 return pointList.size(); 73 } 74 75 @Override 76 public String toString() { 77 return String.format("%s, %s, %s, %s, %s", totalReward, burstCount, length(), minReward, pointList); 78 } 79 }
以及工具类
1 package util; 2 3 import bean.Answer; 4 import bean.MoveResult; 5 import bean.Point; 6 import main.Game; 7 8 import java.util.ArrayList; 9 import java.util.List; 10 11 public class Utils { 12 13 /** 14 * 可视化一个Array（用于打印） 15 * 16 * @param game 游戏 17 * @param answer 解答 18 * @return 复制后的Array 19 */ 20 public static String answerString(Game game, Answer answer) { 21 StringBuilder builder = new StringBuilder(); 22 23 int[][] arr = game.getInitArr(); 24 int[][] moveArr = new int[Game.X][Game.Y]; 25 int moved = 0; 26 int totalReward = 0; 27 int minReward = 0; 28 int burstCount = 0; 29 StringBuilder moveBuilder = new StringBuilder(); 30 for (int i = 0; i < answer.length(); i++) { 31 Point point = answer.getPointList().get(i); 32 if (arr[point.getX()][point.getY()] <= 0) { 33 continue; 34 } 35 36 // 记录本次操作的结果，并更新棋盘状态 37 MoveResult move = Game.move(arr, point); 38 totalReward += move.getReward(); 39 if (minReward > totalReward) { 40 minReward = totalReward; 41 } 42 if (move.getCombo() > 0) { 43 burstCount++; 44 // 发生爆炸，则打印之前的行 45 if (moved > 0) { 46 answerStringArrLine(builder, moveBuilder, arr, moveArr); 47 builder.append("\r\n"); 48 moveArr = new int[Game.X][Game.Y]; 49 moved = 0; 50 } 51 } 52 arr = move.getArr(); 53 moveArr[point.getX()][point.getY()] += 1; 54 moved++; 55 56 builder.append(i).append(", Reward: ").append(move.getReward()).append(", TotalReward: ").append(totalReward).append(", Combo: ").append(move.getCombo()).append(", ").append(point); 57 builder.append("\r\n"); 58 if (move.getCombo() > 0) { 59 answerStringArrLine(builder, moveBuilder, arr, moveArr); 60 builder.append("\r\n"); 61 moveArr = new int[Game.X][Game.Y]; 62 moved = 0; 63 } 64 } 65 66 if (burstCount <= 1) { 67 builder.append("Full Combo!").append("\r\n"); 68 } else { 69 builder.append("BurstCount: ").append(burstCount).append("\r\n"); 70 } 71 72 builder.append(answer.getTotalReward()).append(", ").append(answer.getBurstCount()).append(", ").append(answer.length()).append(", ").append(answer.getMinReward()).append(": ").append(moveBuilder).append("\r\n"); 73 74 return builder.toString(); 75 } 76 77 private static void answerStringArrLine(StringBuilder builder, StringBuilder moveBuilder, int[][] arr, int[][] moveArr) { 78 List<String> moveList = new ArrayList<>(); 79 for (int x = 0; x < arr.length; x++) { 80 for (int y = 0; y < arr.length; y++) { 81 builder.append(arr[x][y]).append(", "); 82 } 83 builder.append(" "); 84 for (int y = 0; y < arr.length; y++) { 85 builder.append(moveArr[x][y]).append(", "); 86 if (moveArr[x][y] > 0) { 87 moveList.add(String.format("(%s, %s, %s)", x, y, moveArr[x][y])); 88 } 89 } 90 builder.append("\r\n"); 91 } 92 moveBuilder.append(moveList.toString()).append(" "); 93 } 94 95 /** 96 * 将一个数组转化为String（配合Map使用） 97 * 98 * @param arr 待处理数组 99 * @return 处理结果 100 */ 101 public static String arrKey(int[][] arr) { 102 StringBuilder builder = new StringBuilder(); 103 for (int i = 0; i < arr.length; i++) { 104 for (int j = 0; j < arr[i].length; j++) { 105 builder.append(arr[i][j]); 106 } 107 } 108 return builder.toString(); 109 } 110 111 /** 112 * 可视化一个Array（用于打印） 113 * 114 * @param arr 待复制数组 115 * @return 复制后的Array 116 */ 117 public static String arrString(int[][] arr) { 118 StringBuilder builder = new StringBuilder(); 119 for (int i = 0; i < arr.length; i++) { 120 for (int j = 0; j < arr[i].length; j++) { 121 builder.append(arr[i][j]); 122 builder.append(", "); 123 } 124 if (i < arr.length - 1) { 125 builder.append("\r\n"); 126 } 127 } 128 return builder.toString(); 129 } 130 131 /** 132 * 复制一个Array 133 * 134 * @param arr 待复制数组 135 * @return 复制后的Array 136 */ 137 public static int[][] arrCopy(int[][] arr) { 138 int[][] result = new int[arr.length][]; 139 for (int i = 0; i < arr.length; i++) { 140 result[i] = new int[arr[i].length]; 141 for (int j = 0; j < arr[i].length; j++) { 142 result[i][j] = arr[i][j]; 143 } 144 } 145 return result; 146 } 147 148 /** 149 * 返回一个在0到num之间的随机数，包含0，不包含num 150 * 151 * @param num 数字 152 * @return 返回随机数 153 */ 154 public static int randInt(int num) { 155 if (num >= 0) { 156 return randInt(0, num); 157 } else { 158 return randInt(num, 0); 159 } 160 } 161 162 /** 163 * 返回一个在min到max之间的随机数，包含min，不包含max 164 * 165 * @param min 随机数下限 166 * @param max 随机数上限 167 * @return 返回随机数 168 */ 169 public static int randInt(int min, int max) { 170 int diff = max - min; 171 int rand = (int) (Math.random() * diff); 172 return min + rand; 173 } 174 175 /** 176 * 求一组数字的最大值 177 * 178 * @param nums 输入数列 179 * @return 最大值 180 */ 181 public static int max(int... nums) { 182 int result = nums[0]; 183 for (int i = 1; i < nums.length; i++) { 184 if (nums[i] > result) { 185 result = nums[i]; 186 } 187 } 188 return result; 189 } 190 191 /** 192 * 求一组数字的最小值 193 * 194 * @param nums 输入数列 195 * @return 最小值 196 */ 197 public static int min(int... nums) { 198 int result = nums[0]; 199 for (int i = 1; i < nums.length; i++) { 200 if (nums[i] < result) { 201 result = nums[i]; 202 } 203 } 204 return result; 205 } 206 }
接下来需要模拟游戏过程了：
这部分的重点是，需要不停地扫描当前是否有水滴在活动，以及是否有水珠发生爆炸。两者要分开并依次进行，以防止多个水滴同时命中水珠后爆炸，导致结果误判。
计算完毕一个状态以后，可以把它缓存，之后无需重复计算。
1 package main; 2 3 import bean.Bullet; 4 import bean.MoveResult; 5 import bean.Point; 6 import util.Utils; 7 8 import java.util.ArrayList; 9 import java.util.HashMap; 10 import java.util.List; 11 import java.util.Map; 12 13 /** 14 * 游戏的基本参数与功能 15 * 如果需要分析别的盘面，在这里修改参数 16 */ 17 public class Game { 18 19 /** 20 * 棋盘X大小 21 */ 22 public static int X = 6; 23 24 /** 25 * 棋盘Y大小 26 */ 27 public static int Y = 6; 28 29 /** 30 * 爆裂门槛 31 */ 32 public static int BURST = 4; 33 34 /** 35 * 奖励倒数，COMBO除以这个数后得到奖励 36 */ 37 public static int REWARD_INV = 3; 38 39 /** 40 * 完美通关的额外奖励 41 */ 42 public static int REWARD_PFT = 1; 43 44 /** 45 * 缓存发生爆炸后的计算结果 46 */ 47 public static Map<String, MoveResult> MOVE_MAP = new HashMap<>(524288); 48 49 /** 50 * 待求解初始状态 51 */ 52 private int[][] initArr = { 53 {0, 2, 2, 1, 4, 4}, 54 {2, 1, 1, 1, 3, 0}, 55 {2, 3, 1, 2, 2, 4}, 56 {0, 3, 2, 0, 0, 4}, 57 {1, 0, 3, 2, 1, 0}, 58 {3, 3, 0, 2, 0, 0}, 59 60 }; 61 62 // public static void main(String[] args) { 63 // Game game = new Game(); 64 // MoveResult move = move(game.initArr, 5, 3); 65 // System.out.println(Utils.arrString(move.getArr())); 66 // System.out.println(move.getCombo()); 67 // } 68 69 /** 70 * @param arr 棋盘 71 * @param point 坐标点 72 * @return v1: 执行后的棋盘, v2: 本次操作的收益, v3: 是否发生了爆炸 73 */ 74 public static MoveResult move(int[][] arr, Point point) { 75 return move(arr, point.getX(), point.getY()); 76 } 77 78 /** 79 * 执行一次加水操作，返回执行后的棋盘，本次操作收益，是否发生爆炸 80 * 如果发生爆炸，需要缓存对应结果 81 * 82 * @param arr 棋盘 83 * @param x X坐标 84 * @param y Y坐标 85 * @return v1: 执行后的棋盘, v2: 本次操作的收益, v3: 是否发生了爆炸 86 */ 87 public static MoveResult move(int[][] arr, int x, int y) { 88 int[][] resArr = Utils.arrCopy(arr); 89 resArr[x][y]++; 90 if (resArr[x][y] <= BURST) { 91 // 本次操作不会导致爆炸，直接返回 92 return new MoveResult(resArr, -1, 0); 93 } 94 String arrKey = Utils.arrKey(arr) + x + y; 95 MoveResult result = MOVE_MAP.get(arrKey); 96 if (result != null) { 97 // 本次操作命中缓存，直接返回 98 return result; 99 } 100 101 // 循环计算爆炸结果 102 int combo = 0; 103 List<Bullet> bulletList = new ArrayList<>(); 104 do { 105 // 1. 所有水滴移动1回合 106 List<Bullet> newBulletList = new ArrayList<>(); 107 for (Bullet bullet : bulletList) { 108 Point point = bullet.move(); 109 if (!point.isValidPosition()) { 110 // 水滴出界，则移除掉它 111 continue; 112 } 113 if (resArr[point.getX()][point.getY()] > 0) { 114 // 水滴遇到了已存在的水球，则水球大小+1，移除水滴 115 resArr[point.getX()][point.getY()]++; 116 continue; 117 } 118 // 水滴通过校验，存活进入下一个回合 119 newBulletList.add(bullet); 120 } 121 122 // 2. 检查是否有水珠爆炸，是的话在该位置生成4个方向的新水滴，并将所在位置的格子置空 123 List<Point> burstPointList = availablePoints(resArr, 1); 124 for (Point point : burstPointList) { 125 newBulletList.add(new Bullet(point, 1, 0)); 126 newBulletList.add(new Bullet(point, 0, 1)); 127 newBulletList.add(new Bullet(point, -1, 0)); 128 newBulletList.add(new Bullet(point, 0, -1)); 129 resArr[point.getX()][point.getY()] = 0; 130 combo++; 131 } 132 133 bulletList = newBulletList; 134 } while (!bulletList.isEmpty()); 135 136 int reward = combo / REWARD_INV - 1; 137 result = new MoveResult(resArr, reward, combo); 138 MOVE_MAP.put(arrKey, result); 139 return result; 140 } 141 142 /** 143 * 获取可选的点 144 * 145 * @param arr 棋盘 146 * @param burst 点的状态，0为任意有水滴点，1为仅满，-1为仅不满 147 * @return 返回的可选点列表 148 */ 149 public static List<Point> availablePoints(int[][] arr, int burst) { 150 List<Point> pointList = new ArrayList<>(); 151 for (int i = 0; i < arr.length; i++) { 152 for (int j = 0; j < arr[i].length; j++) { 153 if (arr[i][j] > 0) { 154 int isBurst = arr[i][j] > BURST ? 1 : -1; 155 int result = burst * isBurst; 156 if (result >= 0) { 157 pointList.add(Point.get(i, j)); 158 } 159 } 160 } 161 } 162 return pointList; 163 } 164 165 public int[][] getInitArr() { 166 return initArr; 167 } 168 169 public void setInitArr(int[][] initArr) { 170 this.initArr = initArr; 171 } 172 }
接下来，就是使用遗传算法，计算出最优解了。
这里我想了想，找到了一个尽可能适合本问题的生成子代方法，大致是这样的：
1、分数最高的<精英个数>名后代，直接移入下一回合
2、分数最高的<精英个数>名后代，随机两两配对，独立地产生2个后代，可能变异
3、分数最高的<普通个数>名后代，随机两两配对，对立地产生2个后代，可能变异
4、分数最高的<随机个数>名后代，从随机位置截断，截断后的部分全部随机生成
配对时，以50%几率设置1个切断位点，25%几率设置2个切断位点，25%几率设置3个切断位点。重组位点在两个解长度较小值之内。
变异发生时，以50%几率修改一步，25%几率增加一步，25%几率删除一步。
生成子代后，计算它们的最终收益，爆炸次数、解的长度，以及期间最大投入成本，并排序。
如果计算出的解的最终收益、爆炸次数、解的长度发生更新，则回合数置零。当回合数超过<最大回合数>时，终止并输出结果。
经过参数调优，精英个数设置为128，普通个数为4096，随机个数为512，最大回合数为128，变异几率为0.125。
本算法和一般的遗传算法不同的地方：
1、不限制答案长度。（但理论最大是6x6x3步）
2、生成后代的方式比较丰富，但只允许适应度最高的一些解产生后代。但是，不在这范围内的解直接淘汰，而不是以几率被选择。
3、允许了最多3个重组位点，而不是固定1个。
4、允许突变发生增加和删除操作，而不是只有修改操作。
1 package main; 2 3 import bean.Answer; 4 import bean.MoveResult; 5 import bean.Point; 6 import util.Utils; 7 8 import java.util.ArrayList; 9 import java.util.Collections; 10 import java.util.Comparator; 11 import java.util.List; 12 13 /** 14 * 遗传算法，寻找一个尽可能收益最高的解 15 */ 16 public class Resolve { 17 18 /** 19 * 种群容量 20 * 初始生成数量、生成普通后代时的配对数量 21 */ 22 private int capacity = 4096; 23 24 /** 25 * 精英种群容量 26 * 精英种群直接移入下一回合，同时两两配对产生2个后代 27 */ 28 private int eliteCapacity = 128; 29 30 /** 31 * 随机种群容量 32 * 每回合对该数量的成员，在某位置截断，之后部分重新生成 33 * 它负责同时引入大量突变 34 */ 35 private int randomCutCapacity = 512; 36 37 /** 38 * 经过该回合数，最优解的适应度不发生变化，则终止并退出遗传算法，输出结果 39 */ 40 private int stableExitTurn = 128; 41 42 /** 43 * 重组时发生变异的几率 44 * 一旦发生，随机位置以25%几率新增1个操作，25%删除1个操作，50%修改1个操作（修改后可能与原操作相同） 45 */ 46 private double variationRate = 0.125D; 47 48 public int getCapacity() { 49 return capacity; 50 } 51 52 public void setCapacity(int capacity) { 53 this.capacity = capacity; 54 } 55 56 public int getEliteCapacity() { 57 return eliteCapacity; 58 } 59 60 public void setEliteCapacity(int eliteCapacity) { 61 this.eliteCapacity = eliteCapacity; 62 } 63 64 public int getRandomCutCapacity() { 65 return randomCutCapacity; 66 } 67 68 public void setRandomCutCapacity(int randomCutCapacity) { 69 this.randomCutCapacity = randomCutCapacity; 70 } 71 72 public int getStableExitTurn() { 73 return stableExitTurn; 74 } 75 76 public void setStableExitTurn(int stableExitTurn) { 77 this.stableExitTurn = stableExitTurn; 78 } 79 80 public double getVariationRate() { 81 return variationRate; 82 } 83 84 public void setVariationRate(double variationRate) { 85 this.variationRate = variationRate; 86 } 87 88 public static void main(String[] args) { 89 Resolve resolve = new Resolve(); 90 Game game = new Game(); 91 92 // for (int i = 0; i < game.getInitArr().length; i++) { 93 // for (int j = 0; j < game.getInitArr()[i].length; j++) { 94 // game.getInitArr()[i][j] = Utils.randInt(5); 95 // } 96 // } 97 // System.out.println(Utils.arrString(game.getInitArr())); 98 // System.out.println(); 99 100 Answer answer = resolve.select(game); 101 System.out.println(answer); 102 } 103 104 /** 105 * 遗传算法执行入口 106 * 107 * @param game 游戏 108 * @return 找到的最优解 109 */ 110 public Answer select(Game game) { 111 int turn = 0; 112 int stableTurn = 0; 113 int lastTotalReward = 0; 114 int lastBurstCount = 0; 115 int lastLength = 0; 116 List<Answer> answerList = new ArrayList<>(capacity); 117 118 // 初始化，产生最初的答案 119 for (int i = 0; i < capacity; i++) { 120 Answer answer = new Answer(); 121 calcTotalReward(game, answer); 122 answerList.add(answer); 123 } 124 sortAnswerList(answerList); 125 126 // 执行遗传算法 127 while (stableTurn < stableExitTurn) { 128 // 1. 生成下一代，同时计算总奖励 129 List<Answer> newAnswerList = new ArrayList<>(capacity + eliteCapacity * 2 + randomCutCapacity); 130 131 // A. 分数最高的<精英个数>名后代，直接移入下一回合 132 for (int i = 0; i < eliteCapacity; i++) { 133 newAnswerList.add(answerList.get(i)); 134 } 135 136 // B. 分数最高的<精英个数>名后代，随机两两配对，独立地产生2个后代，可能变异 137 List<Answer> eliteMateAnswerList = mate(game, answerList, eliteCapacity, 0); 138 newAnswerList.addAll(eliteMateAnswerList); 139 140 // C. 分数最高的<普通个数>名后代，随机两两配对，对立地产生2个后代，可能变异 141 List<Answer> mateAnswerList = mate(game, answerList, capacity, 2); 142 newAnswerList.addAll(mateAnswerList); 143 144 // D. 分数最高的<随机个数>名后代，从随机位置截断，截断后的部分全部随机生成 145 for (int i = 0; i < randomCutCapacity; i++) { 146 newAnswerList.add(randomCut(game, answerList.get(i))); 147 } 148 149 // 2. 更新循环状态 150 Collections.shuffle(newAnswerList); 151 sortAnswerList(newAnswerList); 152 Answer bestAnswer = newAnswerList.get(0); 153 turn++; 154 if (bestAnswer.getTotalReward() == lastTotalReward && bestAnswer.getBurstCount() == lastBurstCount && bestAnswer.length() == lastLength) { 155 stableTurn++; 156 } else { 157 stableTurn = 0; 158 } 159 lastTotalReward = bestAnswer.getTotalReward(); 160 lastBurstCount = bestAnswer.getBurstCount(); 161 lastLength = bestAnswer.length(); 162 answerList = newAnswerList; 163 System.out.println(turn + ", " + stableTurn + ": " + bestAnswer); 164 } 165 166 // 打印最终找到的最优解（16个） 167 System.out.println(); 168 System.out.println("最优Top16："); 169 for (int i = 0; i < 16; i++) { 170 Answer answer = answerList.get(i); 171 System.out.println(answer); 172 } 173 174 // 打印最优解 175 System.out.println(); 176 System.out.println("最优解关键盘面："); 177 Answer bestAnswer = answerList.get(0); 178 System.out.println(Utils.answerString(game, bestAnswer)); 179 return bestAnswer; 180 } 181 182 /** 183 * 两两配对，每一对产生2个后代 184 * 重组断点50%为1个，25%为2个，25%为3个。 185 * 186 * @param game 游戏 187 * @param answerList 排序后的解答列表 188 * @param limit 数量限制，只有最前面的解答有资格产生后代 189 * @param policy 0: 对立产生后代，生成2个子代，分别随机地独占亲代的基因，亲代基因不会丢失，1或以上：独立产生policy个后代，子代基因从亲代完全随机获得，互不影响 190 * @return 生成的子代列表 191 */ 192 public List<Answer> mate(Game game, List<Answer> answerList, int limit, int policy) { 193 int pairNum = limit >> 1; 194 ArrayList<Answer> parentAnswerList = new ArrayList<>(answerList.subList(0, limit)); 195 Collections.shuffle(parentAnswerList); 196 List<Answer> childAnswerList = new ArrayList<>(); 197 for (int pairNo = 0; pairNo < pairNum; pairNo++) { 198 Answer parentAnswer0 = parentAnswerList.get(2 * pairNo); 199 Answer parentAnswer1 = parentAnswerList.get(2 * pairNo + 1); 200 List<Point> parentPointList0 = parentAnswer0.getPointList(); 201 List<Point> parentPointList1 = parentAnswer1.getPointList(); 202 int minLength = Utils.min(parentAnswer0.length(), parentAnswer1.length()); 203 204 if (policy > 0) { 205 // 独立产生后代，子代基因从亲代完全随机获得，互不影响 206 for (int childNo = 0; childNo < policy; childNo++) { 207 int breakPointNum = Utils.max(Utils.randInt(4), 1); 208 List<Integer> matePositionList = new ArrayList<>(); 209 for (int i = 0; i < breakPointNum; i++) { 210 matePositionList.add(Utils.randInt(minLength)); 211 } 212 matePositionList.sort(Integer::compareTo); 213 214 List<Point> childPointList = new ArrayList<>(); 215 int starts = Utils.randInt(2); 216 int lastMatePosition = 0; 217 for (int i = 0; i < breakPointNum + 1; i++) { 218 List<Point> fragmentPointList; 219 List<Point> parentPointList = (i + starts) % 2 == 0 ? parentPointList0 : parentPointList1; 220 if (i < breakPointNum) { 221 int matePosition = matePositionList.get(i); 222 fragmentPointList = parentPointList.subList(lastMatePosition, matePosition); 223 lastMatePosition = matePosition; 224 } else { 225 fragmentPointList = parentPointList.subList(lastMatePosition, parentPointList.size()); 226 } 227 childPointList.addAll(fragmentPointList); 228 } 229 childAnswerList.add(new Answer(childPointList)); 230 } 231 } else { 232 // 对立产生后代，生成2个子代，分别随机地独占亲代的基因，亲代基因不会丢失 233 int breakPointNum = Utils.max(Utils.randInt(4), 1); 234 List<Integer> matePositionList = new ArrayList<>(); 235 for (int i = 0; i < breakPointNum; i++) { 236 matePositionList.add(Utils.randInt(minLength)); 237 } 238 matePositionList.sort(Integer::compareTo); 239 240 List<Point> childPointList0 = new ArrayList<>(); 241 List<Point> childPointList1 = new ArrayList<>(); 242 int lastMatePosition = 0; 243 for (int i = 0; i < breakPointNum + 1; i++) { 244 // 按照断点指定的位置，获得亲代基因的碎片 245 List<Point> fragmentPointList0; 246 List<Point> fragmentPointList1; 247 if (i < breakPointNum) { 248 int matePosition = matePositionList.get(i); 249 fragmentPointList0 = parentPointList0.subList(lastMatePosition, matePosition); 250 fragmentPointList1 = parentPointList1.subList(lastMatePosition, matePosition); 251 lastMatePosition = matePosition; 252 } else { 253 fragmentPointList0 = parentPointList0.subList(lastMatePosition, parentPointList0.size()); 254 fragmentPointList1 = parentPointList1.subList(lastMatePosition, parentPointList1.size()); 255 } 256 257 // 拼接亲代基因碎片，得到子代基因 258 if (i % 2 == 0) { 259 childPointList0.addAll(fragmentPointList0); 260 childPointList1.addAll(fragmentPointList1); 261 } else { 262 childPointList0.addAll(fragmentPointList1); 263 childPointList1.addAll(fragmentPointList0); 264 } 265 } 266 childAnswerList.add(new Answer(childPointList0)); 267 childAnswerList.add(new Answer(childPointList1)); 268 } 269 } 270 271 // 引入变异 272 for (Answer answer : childAnswerList) { 273 if (Math.random() < variationRate && answer.length() > 0) { 274 int variationType = Utils.max(Utils.randInt(4), 1); 275 int position = Utils.randInt(answer.length()); 276 switch (variationType) { 277 case 1: 278 // 修改一个步骤 279 answer.getPointList().remove(position); 280 // BREAK-THROUGH 281 case 2: 282 // 插入一个步骤，需要遍历到当前为止的棋盘状态，然后随机插入一个合法的位置 283 int[][] arr = game.getInitArr(); 284 for (int i = 0; i < position; i++) { 285 Point point = answer.getPointList().get(i); 286 if (arr[point.getX()][point.getY()] <= 0) { 287 continue; 288 } 289 // 记录本次操作的结果，并更新棋盘状态 290 MoveResult move = Game.move(arr, point); 291 arr = move.getArr(); 292 } 293 List<Point> remainPointList = Game.availablePoints(arr, 0); 294 if (!remainPointList.isEmpty()) { 295 Point point = remainPointList.get(Utils.randInt(remainPointList.size())); 296 answer.getPointList().add(position, point); 297 } 298 break; 299 case 3: 300 // 删除一个步骤 301 answer.getPointList().remove(position); 302 break; 303 } 304 } 305 calcTotalReward(game, answer); 306 } 307 return childAnswerList; 308 } 309 310 /** 311 * 从随机位置斩断一个解，之后部分随机生成 312 * 313 * @param game 游戏 314 * @param answer 解答 315 * @return 生成的新解答 316 */ 317 public Answer randomCut(Game game, Answer answer) { 318 int saveLength = Utils.randInt(answer.length()); 319 List<Point> savePointList = answer.getPointList().subList(0, saveLength); 320 Answer newAnswer = new Answer(savePointList); 321 calcTotalReward(game, newAnswer); 322 return newAnswer; 323 } 324 325 /** 326 * 验证解答，并计算总奖励 327 * 如果解答序列不完整，则随机生成之后序列，使其补充完整。 328 * 329 * @param game 游戏 330 * @param answer 答案 331 * @return 总奖励 332 */ 333 public static int calcTotalReward(Game game, Answer answer) { 334 int totalReward = 0; 335 int minReward = 0; 336 int burstCount = 0; 337 int[][] arr = game.getInitArr(); 338 339 // 遍历已有点的列表，验证并计算结果 340 List<Point> pointList = new ArrayList<>(answer.getPointList()); 341 for (Point point : answer.getPointList()) { 342 if (arr[point.getX()][point.getY()] <= 0) { 343 // 这个点已经被清空了，因此跳过它，将其从列表中删除 344 pointList.remove(point); 345 continue; 346 } 347 348 // 记录本次操作的结果，并更新棋盘状态 349 MoveResult move = Game.move(arr, point); 350 arr = move.getArr(); 351 totalReward += move.getReward(); 352 if (minReward > totalReward) { 353 minReward = totalReward; 354 } 355 if (move.getCombo() > 0) { 356 burstCount++; 357 } 358 } 359 360 // 检查是否棋盘未被清空，是的话则随机生成之后的解答 361 List<Point> remainPointList = Game.availablePoints(arr, 0); 362 while (!remainPointList.isEmpty()) { 363 Point point = remainPointList.get(Utils.randInt(remainPointList.size())); 364 pointList.add(point); 365 366 // 记录本次操作的结果，并更新棋盘状态 367 MoveResult move = Game.move(arr, point); 368 arr = move.getArr(); 369 totalReward += move.getReward(); 370 if (minReward > totalReward) { 371 minReward = totalReward; 372 } 373 if (move.getCombo() > 0) { 374 burstCount++; 375 } 376 377 remainPointList = Game.availablePoints(arr, 0); 378 } 379 380 // 追加完美通关奖励 381 if (burstCount <= 1) { 382 totalReward += Game.REWARD_PFT; 383 } 384 385 answer.getPointList().clear(); 386 answer.getPointList().addAll(pointList); 387 answer.setBurstCount(burstCount); 388 answer.setTotalReward(totalReward); 389 answer.setMinReward(minReward); 390 return totalReward; 391 } 392 393 public static void sortAnswerList(List<Answer> answerList) { 394 answerList.sort(Comparator.comparing(Answer::getTotalReward).reversed().thenComparing(Answer::getBurstCount).thenComparing(Answer::length)); 395 } 396 }
计算出的结果最终打印到控制台中。
实际用于解决该游戏后，发现了以下现象与问题：
1、最优解几乎总是先在棋盘上设置大量小水滴，之后一把将其全部引爆。
2、最优解如果直接打印，很多在同一个单元格的操作不放在一起，增加操作难度，比如一不小心点错单元格。
3、不是每次都能找到最优解，有的最优解出现概率很低，需要多次执行确认。
4、直接照着盘面改Array太麻烦了。
最终，我采取了以下措施：
1、输出解时。将一组不引爆水珠的一系列操作合并，增加一个次数参数。
2、将执行入口设置为了允许并发运行。一般同时执行3个实例，若找到的解的收益不同，则再执行几个看看。
3、我写了个程序，辅助将盘面录入为Array，以便粘贴。
1 package main; 2 3 import java.util.Scanner; 4 5 public class FormatArray { 6 public static void main(String[] args) { 7 System.out.println("粘贴纯数字格式，获得格式化的Array对象。注意最后需要多加一个空行。"); 8 Scanner scanner = new Scanner(System.in); 9 while (scanner.hasNext()) { 10 String line = scanner.next(); 11 char[] chars = line.toCharArray(); 12 StringBuilder builder = new StringBuilder(); 13 builder.append("{"); 14 for (int i = 0; i < chars.length; i++) { 15 builder.append(chars[i]); 16 if (i < chars.length - 1) { 17 builder.append(", "); 18 } 19 } 20 builder.append("},"); 21 System.out.println(builder.toString()); 22 } 23 } 24 }
如有兴趣，可以下载源文件：https://pan.baidu.com/s/1iWNIkNLUXDDadNLlaerIHg?pwd=bili
参考资料：
《也谈十滴水-启发式搜索》https://www.cnblogs.com/ComputingLife/archive/2010/09/19/1830873.html
热门相关：与校花同居：高手风流 上古传人在都市 绝代疯少 盛唐小园丁 龙组使命