Codingame smash the code contest

PerfTest.java

public class PerfTest {

	public static void main(String[] args) {
		
		int n = 1000002;
		
		String[] debugString = { 
				
				"New round ! -7-0-0-0-0",
				"Next blocks: -55-24-13-41-25-15-13-52",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    .4....",
				"......    .4....",
				".....2    .1....",
				"...3.4    .3....",
				"..5542    .55...",
				".12452    .54...",
		};
		
		Player.GameState gs = PlayerTest.getGameStateFromDebug(debugString);
		
		double starTime = System.currentTimeMillis();
		
		for(int i = 0; i < n; i++) {
			Player.GameLogic.applyMove(gs, new Player.Move(0, 3));
		}

		Player.debug("Duration: " + (System.currentTimeMillis() - starTime));
		Player.debug("Duration for 1000 moves: " + (System.currentTimeMillis() - starTime) / n * 1000);
		Player.printAGridForced(gs.myGrid);
		
	}

}

Player.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

class Player {

	// Debug stuff
	public static boolean isDebugOn = true;
	public static boolean isDebugGridOn = false;
	public static boolean isDebugModeOn = false;

	// Game constants
	public static int width = 6;
	public static int height = 12;
	public static int blockSize = 2;
	public static int nbBlocksToCome = 8;
	public static int nbMinAdjBlockToExplode = 4;
	public static int minColor = 1;
	public static int maxColor = 5;
	public static int maxMoves = 22;
	public static Move[] oneColorMoves;
	public static Move[] twoColorMoves;

	public static char[] colorTable = new char[] { '1', '2', '3', '4', '5' };
	public static int[] colorBonusTable = new int[] { 0, 2, 4, 8, 16 };
	public static int[] groupBonusTable = new int[] { 0, 1, 2, 3, 4, 5, 6, 8 };

	// Game variables
	public static int round = 0;
	public static boolean stopExec = false;
	public static int mctsMaxIterations = 10000;
	public static GameState expectedGS;
	public static boolean bim = false;
	public static int totalDuration;
	public static int totalIterations;
	public static int nbApplyMove;

	// Useful chars
	public static char empty = '.';
	public static char skull = '0';
	public static char test = '?';
	public static char explode = '*';

	// Time stuff
	public static int maxTurn = 200;
	public static int maxTime = 100; // 100 ms max to answer
	public static int margin = 20;
	public static long startTime;
	public static long maxTimeWithMargin = maxTime - margin;

	// AI stuff
	public static Random r = new Random();

	public static AI randomAI = new RandomAI();
	public static AI oneTurnAI = new OneTurnAI();
	public static AntiComboAI antiComboAI = new AntiComboAI(3);
	public static BlockAI blockAI = new BlockAI();
	public static MCTSAI mctsAI = new MCTSAI();
	public static NNColorAI nnColorAI = new NNColorAI();

	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);

		initializeMatch();

		// game loop
		while (true) {

			// Initialize the game state based on the inputs
			GameState realGS = initializeRound(in);

			// Compute the best move we've come up with
			Move move = compute(realGS);

			// Update some variables
			finalizeRound(realGS, move);

			// And output
			out(move, realGS);

		}
	}

	// Compute the best move using one of our AI
	public static Move compute(GameState realGS) {

		// Move result = randomAI.computeFull(realGS);
		// Move result = oneTurnAI.computeFull(realGS);
		// Move result = new NTurnBFAI(2).computeFull(realGS);
		Move result = new MCTSAI().computeFull(realGS);
		// Move result = new AntiComboAI(2).computeFull(realGS);
		// Move result = new ThreeBlockAI().computeFull(realGS);

		return result;
	}

	// Just initialize some basic stuff
	public static void initializeMatch() {

		// Initialize oneColorMoves: 6 vertical + 5 horizontal
		oneColorMoves = new Move[11];

		for (int i = 0; i < 11; i++) {
			if (i < width) {
				oneColorMoves[i] = new Move(i, 3);
			} else {
				oneColorMoves[i] = new Move(i - width, 0);
			}
		}

		// Initialize twoColorMoves: 12 vertical + 10 horizontal
		twoColorMoves = new Move[22];

		for (int i = 0; i < 22; i++) {
			if (i < width) {
				twoColorMoves[i] = new Move(i, 3);
			} else if (i < width * 2) {
				twoColorMoves[i] = new Move(i - width, 1);
			} else if (i < width * 3 - 1) {
				twoColorMoves[i] = new Move(i - width * 2, 0);
			} else {
				twoColorMoves[i] = new Move(i - width * 3 + 2, 2);
			}
		}

	}

	// Initialize the game state for a new round
	private static GameState initializeRound(Scanner in) {

		startTime = System.currentTimeMillis();
		round++;
		bim = false;
		nbApplyMove = 0;

		int myScore = 0;
		double opNuisance = 0;
		if (expectedGS != null) {
			// Previous round values
			myScore = expectedGS.myScore;
			opNuisance = expectedGS.opNuisance;
		}

		GameState result = new GameState(round, myScore, 0, 0, opNuisance); // TODO: estimate op score and my nuisance

		for (int i = 0; i < nbBlocksToCome; i++) {
			result.blocksToCome[i][0] = in.nextInt(); // color of the first block
			result.blocksToCome[i][1] = in.nextInt(); // color of the attached block
		}

		for (int i = 0; i < height; i++) {
			String row = in.next();
			result.myGrid[i] = row.toCharArray();
		}
		result.updateColH();

		for (int i = 0; i < height; i++) {
			String row = in.next(); // One line of the map ('.' = empty, '0' = skull block, '1' to '5' = colored block)
			// result.opGrid[i] = row.toCharArray(); // Not needed for the moment
		}

		printGameState(result);

		if (round > 1) {
			estimateOpScoreAndNuisance(result);
			testGameStateAgainstExpected(result);
		}

		return result;
	}

	private static void estimateOpScoreAndNuisance(GameState result) {
		// Try the possibilities and check if the result would be the same as actual or not

		// Move[] possibleMoves = getPossibleMoves(lastBlock);

	}

	// Just validates that we got what we expected (except skulls)
	public static boolean testGameStateAgainstExpected(GameState currentGS) {

		boolean result = true;
		int failCount = 0;

		for (int j = 0; j < height; j++) {

			for (int i = 0; i < width; i++) {
				if (expectedGS.myGrid[j][i] != currentGS.myGrid[j][i]) {
					failCount++;
				}
			}
		}

		if (failCount % width != 0) {
			result = false;
			for (int j = 0; j < height; j++) {
				for (int i = 0; i < width; i++) {
					if (expectedGS.myGrid[j][i] != currentGS.myGrid[j][i]) {
						debug("Failed at " + j + "," + i + " found " + currentGS.myGrid[j][i] + " but expected " + expectedGS.myGrid[j][i]);
					}
				}
			}

		}
		return result;
	}

	// Apply the move selected to get the correct score and nuisance
	private static void finalizeRound(GameState gs, Move move) {

		GameLogic.applyMove(gs, move);
		expectedGS = gs;
		totalDuration = (int) (System.currentTimeMillis() - startTime);
		debug("Round duration: " + totalDuration + " nbApply: " + nbApplyMove);
	}

	// Standar 2D array copy, can we do better perf ?
	private static char[][] copyGrid(char[][] aGrid) {
		char[][] result = new char[aGrid.length][aGrid[0].length];
		for (int j = 0; j < aGrid.length; j++) {
			System.arraycopy(aGrid[j], 0, result[j], 0, aGrid[j].length);
		}
		return result;
	}

	private static Move[] getPossibleMoves(int[] blocksToCome) {
		Move[] result;

		if (blocksToCome[0] == blocksToCome[1]) {
			result = oneColorMoves;
		} else {
			result = twoColorMoves;
		}

		return result;
	}

	private static void printGameState(GameState gs) {
		debugForInput("New round ! " + debugSep + round + debugSep + getDebugVariables(gs));
		debugNextBlocks(gs);
		printGrids(gs);
	}

	private static String getDebugVariables(GameState gs) {
		return gs.myScore + debugSep + String.format("%.2f", gs.myNuisance) + debugSep + gs.opScore + debugSep + String.format("%.2f", gs.opNuisance) + debugSep + totalDuration + debugSep
				+ totalIterations;
	}

	private static void debugNextBlocks(GameState gs) {
		String message = "Next blocks: ";
		for (int i = 0; i < nbBlocksToCome; i++) {
			message += debugSep + gs.blocksToCome[i][0] + gs.blocksToCome[i][1];
		}
		debugForInput(message);

	}

	public static void printGrids(GameState gs) {
		for (int j = 0; j < height; j++) {
			String row = "";
			for (int i = 0; i < width; i++) {
				row += gs.myGrid[j][i];
			}
			row += "    ";
			for (int i = 0; i < width; i++) {
				row += gs.opGrid[j][i];
			}
			debugForInput(row);
		}
	}

	public static void printAGrid(char[][] aGrid) {

		if (isDebugGridOn) {
			for (int j = 0; j < height; j++) {
				String row = "";
				for (int i = 0; i < width; i++) {
					row += aGrid[j][i];
				}
				debug(row);
			}
		}

	}

	public static void printAGridForced(char[][] aGrid) {

		for (int j = 0; j < height; j++) {
			String row = "";
			for (int i = 0; i < width; i++) {
				row += aGrid[j][i];
			}
			debug(row);
		}

	}

	// Output the column number
	public static void out(Move move, GameState gs) {
		if (!stopExec) {
			System.out.println(move.column + " " + move.rotation + " " + getMessage(gs));
		}
	}

	private static String getMessage(GameState gs) {
		String result = "";
		if (bim) {
			result += "Bim !";
		} else {
			result += getDebugVariables(gs);
		}
		return result;
	}

	// Debug !
	public static void debug(String message) {
		if (isDebugOn) {
			System.err.println(message);
		}
	}

	public static String debugStartLine = "\"";
	public static String debugEndLine = "\",";
	public static String debugSep = "-";

	// Debug for later input in tests
	public static void debugForInput(String message) {
		debug(debugStartLine + message + debugEndLine);
	}

	// The representation of a game state
	public static class GameState {

		public int round;

		public int myScore;
		public double myNuisance;

		public int opScore;
		public double opNuisance;

		protected char[][] myGrid;
		public int[] colH;
		public char[][] opGrid;

		public int[][] blocksToCome;

		public int nbSkullLinesGenerated;

		public int nbNew3BlocksGroups = 0;
		public int nbNew2BlocksGroups = 0;

		public GameState(int round, int myScore, double myNuisance, int opScore, double opNuisance) {
			this.round = round;

			this.myScore = myScore;
			this.myNuisance = myNuisance;

			this.opScore = opScore;
			this.opNuisance = opNuisance;

			myGrid = new char[height][width];
			opGrid = new char[height][width];
			blocksToCome = new int[nbBlocksToCome][blockSize];
			colH = new int[width];
		}

		public GameState copy() {
			GameState result = new GameState(this.round, this.myScore, this.myNuisance, this.opScore, this.opNuisance);
			result.myGrid = copyGrid(myGrid);
			// result.opGrid = copyGrid(opGrid);
			// result.colH = Arrays.copyOf(this.colH, this.colH.length);
			System.arraycopy(this.colH, 0, result.colH, 0, this.colH.length); // Really better ?
			result.blocksToCome = copyBlockToCome(blocksToCome);
			return result;
		}

		protected int[][] copyBlockToCome(int[][] blocksToCome) {
			int[][] result = new int[blocksToCome.length][blocksToCome[0].length];
			for (int j = 0; j < blocksToCome.length; j++) {
				result[j] = new int[] { blocksToCome[j][0], blocksToCome[j][1] };
			}
			return result;
		}

		public void updateColH() {

			for (int i = 0; i < width; i++) {
				colH[i] = getColumnHeight(myGrid, i);
			}
		}

		private static int getColumnHeight(char[][] aGrid, int column) {

			int result = -1;

			for (int j = height - 1; j >= 0; j--) {
				if (aGrid[j][column] == empty) {
					result = height - j - 1;
					break;
				}
			}

			if (result == -1) {
				result = height;
			}

			return result;
		}

		public String toString() {
			return "GS round " + round + " score " + myScore;
		}

	}

	public static class GameLogic {

		// Apply the move on the provided game state, updating the game state accordingly
		public static void applyMove(GameState gs, Move move) {
			applyMove(gs, move, 0);
		}

		// Apply the move on the provided game state, updating the game state accordingly
		public static void applyMove(GameState gs, Move move, int turn) {

			nbApplyMove++;

			boolean valid = true;
			ArrayList<Integer[]> pointsToCheck = new ArrayList<>();

			// 2. Put the blocks
			switch (move.rotation) {
			case 3:
				pointsToCheck.add(new Integer[] { height - gs.colH[move.column] - 1, move.column });
				valid &= applyBlock(gs, move.column, gs.blocksToCome[turn][1]);
				if (gs.blocksToCome[turn][0] != gs.blocksToCome[turn][1]) {
					pointsToCheck.add(new Integer[] { height - gs.colH[move.column] - 1, move.column }); // Only checks in case of different colors
				}
				valid &= applyBlock(gs, move.column, gs.blocksToCome[turn][0]);
				break;
			case 1:
				pointsToCheck.add(new Integer[] { height - gs.colH[move.column] - 1, move.column });
				valid &= applyBlock(gs, move.column, gs.blocksToCome[turn][0]);
				if (gs.blocksToCome[turn][0] != gs.blocksToCome[turn][1]) {
					pointsToCheck.add(new Integer[] { height - gs.colH[move.column] - 1, move.column }); // Only checks in case of different colors
				}
				valid &= applyBlock(gs, move.column, gs.blocksToCome[turn][1]);
				break;
			case 2:
				pointsToCheck.add(new Integer[] { height - gs.colH[move.column] - 1, move.column });
				pointsToCheck.add(new Integer[] { height - gs.colH[move.column - 1] - 1, move.column - 1 });
				valid &= applyBlock(gs, move.column, gs.blocksToCome[turn][0]);
				valid &= applyBlock(gs, move.column - 1, gs.blocksToCome[turn][1]);
				break;
			case 0:
				pointsToCheck.add(new Integer[] { height - gs.colH[move.column] - 1, move.column });
				pointsToCheck.add(new Integer[] { height - gs.colH[move.column + 1] - 1, move.column + 1 });
				valid &= applyBlock(gs, move.column, gs.blocksToCome[turn][0]);
				valid &= applyBlock(gs, move.column + 1, gs.blocksToCome[turn][1]);
				break;
			default:
				break;
			}

			if (valid) {

				// 3. Apply explosions and update the game state
				step = 0;
				scoreOfTheTurn = 0;
				applyExplosions(gs, pointsToCheck);

				// 4. Update the score, nuisance and skulls
				updateScoreNuisanceSkulls(gs);

			} else {
				// We can't play this move, record a negative score
				gs.myScore = -1;
			}

		}

		private static boolean applyBlock(GameState gs, int column, int block) {

			boolean result = height - gs.colH[column] >= 1;
			if (result) {
				gs.myGrid[height - gs.colH[column] - 1][column] = colorTable[block - 1];
				gs.colH[column]++;
			}

			return result;

		}

		private static int step;
		private static int scoreOfTheTurn;

		// Apply the explosions recursively
		public static void applyExplosions(GameState gs, List<Integer[]> pointsToCheck) {

			int explosions = 0;
			boolean[] colorExploded = new boolean[maxColor]; // Records if a given color exploded or not
			int colorBonus;
			int totalGroupBonus = 0;
			double chainPower;

			printAGrid(gs.myGrid);

			boolean[][] testedBlocks = new boolean[height][width];

			for (Integer[] point : pointsToCheck) {

				if (!testedBlocks[point[0]][point[1]] && isColor(gs.myGrid[point[0]][point[1]])) {
					boolean[][] countedSkulls = new boolean[height][width];
					int[] output = extendFromBlockAndCount(gs, gs.myGrid, point[0], point[1], testedBlocks, countedSkulls, colorExploded);
					explosions += output[0];
					totalGroupBonus += output[1];
				}
			}

			if (explosions > 0) {
				// Some blocks will explode, so remove them and check again from here
				step++;
				chainPower = getChainPower(step);
				colorBonus = getColorBonus(colorExploded);
				scoreOfTheTurn += getScore(explosions, chainPower, colorBonus, totalGroupBonus);

				// Remove the explosions and get at the same time the next points to check
				List<Integer[]> nextPointsToCheck = removeExplosions(gs);

				// Let's go for a new step
				applyExplosions(gs, nextPointsToCheck);
			}

		}

		private static ArrayList<Integer[]> removeExplosions(GameState gs) {

			ArrayList<Integer[]> result = new ArrayList<>();

			for (int i = 0; i < width; i++) {
				result.addAll(getBlocksDown(gs, i));
			}
			return result;
		}

		// Move the blocks down to replace the stuff which exploded !
		private static ArrayList<Integer[]> getBlocksDown(GameState gs, int i) {

			ArrayList<Integer[]> result = new ArrayList<>();

			boolean willExplode = false;
			int explodeFrom = -1;
			int firstExplodeFrom = -1;
			int explodeCount = 0;
			int totalExplode = 0;

			for (int j = height - 1; j >= 0; j--) {

				if (willExplode) {
					if (gs.myGrid[j][i] == explode) {
						// Just continue
						explodeCount++;
					} else {

						// Move everyting which is above... down !
						for (int b = explodeFrom; b >= 0; b--) {
							if (b - explodeCount >= 0) {
								gs.myGrid[b][i] = gs.myGrid[b - explodeCount][i];
							} else {
								gs.myGrid[b][i] = empty;
							}
						}

						// Restart from same row and reset variables
						j = explodeFrom;

						willExplode = false;
						totalExplode += explodeCount;
						explodeCount = 0;
					}
				} else {
					if (gs.myGrid[j][i] == explode) {
						// We enter a new explosion area
						explodeFrom = j;
						if (firstExplodeFrom == -1) {
							firstExplodeFrom = j;
						}
						willExplode = true;
						explodeCount++;
					}
				}
			}
			gs.colH[i] = gs.colH[i] - totalExplode;

			if (totalExplode > 0) {
				// At least something exploded in this column, so all points above need to be checked next
				for (int p = firstExplodeFrom; p >= (height - gs.colH[i]); p--) {
					result.add(new Integer[] { p, i });
				}
			}

			return result;
		}

		// Is the move valid in regards to the game state ?
		private static boolean isValid(Move move, GameState gs) {

			boolean result = false;

			if (move != null) {
				switch (move.rotation) {
				case 3:
					result = gs.colH[move.column] <= height - blockSize;
					break;
				case 1:
					result = gs.colH[move.column] <= height - blockSize;
					break;
				case 0:
					result = (gs.colH[move.column] <= height - 1) && (gs.colH[move.column + 1] <= height - 1);
					break;
				case 2:
					result = (gs.colH[move.column] <= height - 1) && (gs.colH[move.column - 1] <= height - 1);
					break;
				default:
					break;
				}
			}

			return result;
		}

		private static boolean isColor(char c) {
			int n = Character.getNumericValue(c);
			return n >= minColor && n <= maxColor;
		}

		// From the block at j,i, look left, right, up and down for blocks of the same color
		private static int[] extendFromBlockAndCount(GameState gs, char[][] myGrid, int j, int i, boolean[][] testedBlocks, boolean[][] countedSkulls, boolean[] colorExploded) {

			int groupBonus = 0;

			int d = 0; // The distance from the original point which is going to be incremented little by little
			boolean finished = false;

			char color = myGrid[j][i];
			myGrid[j][i] = test;
			testedBlocks[j][i] = true;
			int count = 1;

			while (!finished) {

				finished = true;

				for (int b = Math.max(0, j - d); b < Math.min(height, j + d + 1); b++) { // Vertical loop
					for (int a = Math.max(0, i - d); a < Math.min(width, i + d + 1); a++) { // Horizontal loop

						if (myGrid[b][a] == test) {
							// Try to expand it from there...

							// ... at the left
							if (a - 1 >= 0) {
								if (myGrid[b][a - 1] == color) {
									myGrid[b][a - 1] = test;
									testedBlocks[b][a - 1] = true;
									count++;
									finished = false;
								} else if (myGrid[b][a - 1] == skull && !countedSkulls[b][a - 1]) {
									countedSkulls[b][a - 1] = true;
								}
							}

							// ... at the right
							if (a + 1 < width) {
								if (myGrid[b][a + 1] == color) {
									myGrid[b][a + 1] = test;
									testedBlocks[b][a + 1] = true;
									count++;
									finished = false;
								} else if (myGrid[b][a + 1] == skull && !countedSkulls[b][a + 1]) {
									countedSkulls[b][a + 1] = true;
								}
							}
							// ... at the top
							if (b - 1 >= 0) {
								if (myGrid[b - 1][a] == color) {
									myGrid[b - 1][a] = test;
									testedBlocks[b - 1][a] = true;
									count++;
									finished = false;
								} else if (myGrid[b - 1][a] == skull && !countedSkulls[b - 1][a]) {
									countedSkulls[b - 1][a] = true;
								}
							}
							// ... at the bottom
							if (b + 1 < height) {
								if (myGrid[b + 1][a] == color) {
									myGrid[b + 1][a] = test;
									testedBlocks[b + 1][a] = true;
									count++;
									finished = false;
								} else if (myGrid[b + 1][a] == skull && !countedSkulls[b + 1][a]) {
									countedSkulls[b + 1][a] = true;
								}
							}
						}
					}
				}
				d++;
			}

			if (count == 3) {
				gs.nbNew3BlocksGroups++;
			} else if (count == 2) {
				gs.nbNew2BlocksGroups++;
			}

			if (count >= nbMinAdjBlockToExplode) {
				// The blocks will disappear !

				colorExploded[Character.forDigit(color, 10)] = true;

				for (int b = 0; b < height; b++) {
					for (int a = 0; a < width; a++) {

						if (myGrid[b][a] == test) {
							myGrid[b][a] = explode;
						} else if (myGrid[b][a] == skull && countedSkulls[b][a]) {
							myGrid[b][a] = explode;
						}
					}
				}

				groupBonus = getGroupBonus(count);

			} else {
				// Reset the color
				for (int b = 0; b < height; b++) {
					for (int a = 0; a < width; a++) {

						if (myGrid[b][a] == test) {
							myGrid[b][a] = color;
						}
					}
				}
				count = 0;
			}

			return new int[] { count, groupBonus };

		}

		private static void updateScoreNuisanceSkulls(GameState gs) {

			gs.myScore += scoreOfTheTurn;

			double nuisanceGenerated = scoreOfTheTurn / 70.0;
			double tempNuisance = gs.opNuisance + nuisanceGenerated;
			int nbSkullLinesGenerated = (int) tempNuisance / 6;
			gs.nbSkullLinesGenerated = nbSkullLinesGenerated;
			double newNuisance = tempNuisance % 6;

			gs.opNuisance = newNuisance;
		}

		// Rules say: score = (10 * B) * (CP + CB + GB)
		private static double getScore(int nbBlocksCleared, double chainPower, int colorBonus, int groupBonus) {
			return (10 * nbBlocksCleared) * (Math.min(999, Math.max(1, chainPower + colorBonus + groupBonus)));
		}

		private static double getChainPower(int step) {
			double result = 0;

			if (step > 1) {
				result = 8 * Math.pow(2, step - 2);
			}

			return result;
		}

		private static int getColorBonus(boolean[] colorExploded) {
			int count = 0;
			for (int i = 0; i < maxColor; i++) {
				if (colorExploded[i]) {
					count++;
				}
			}
			return colorBonusTable[count - 1];
		}

		private static int getGroupBonus(int nbBlocks) {
			nbBlocks = Math.min(nbBlocks, 11);
			return groupBonusTable[nbBlocks - 4];
		}

	}

	public static class Move {

		public int column;
		public int rotation;

		public Move(int column, int rotation) {
			this.column = column;
			this.rotation = rotation;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + column;
			result = prime * result + rotation;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Move other = (Move) obj;
			if (column != other.column)
				return false;
			if (rotation != other.rotation)
				return false;
			return true;
		}

		public String toString() {
			return "(" + column + "," + rotation + ")";
		}
	}

	public static abstract class AI {

		public Move computeFull(GameState gs) {

			Move result = compute(gs);

			if (result == null) {
				// For some reason the simulation failed, so play a block move
				debug("No good move, reverting to blocks");
				result = blockAI.compute(gs);
			}

			if (result == null) {
				// For some reason the simulation failed, so play a nncolor move
				debug("No good move, reverting to nncolor");
				result = nnColorAI.compute(gs);
			}

			if (result == null) {
				// For some reason the simulation failed, so play a random move
				debug("No good move, reverting to random :(");
				result = randomAI.compute(gs);
			}

			return result;

		}

		public abstract Move compute(GameState gs);
	}

	// Random valid move
	public static class RandomAI extends AI {

		@Override
		public Move compute(GameState gs) {

			Move result = null;

			Move[] possibleMoves = getPossibleMoves(gs.blocksToCome[0]);
			ArrayList<Move> possibleValidMoves = new ArrayList<>();

			for (Move move : possibleMoves) {
				if (GameLogic.isValid(move, gs)) {
					possibleValidMoves.add(move);
				}
			}

			while (result == null) {

				if (!possibleValidMoves.isEmpty()) {
					result = possibleValidMoves.get(r.nextInt(possibleValidMoves.size()));
					GameState gsCopy = gs.copy();
					GameLogic.applyMove(gsCopy, result);
					if (gsCopy.myScore > gs.myScore) {
						result = null;
					}

				} else {
					debug("This is the end, my friends.");
					result = new Move(0, 0);
				}
			}

			return result;
		}

	}

	// Best move ahead (should be the same as Brute force 1)
	public static class OneTurnAI extends AI {

		@Override
		public Move compute(GameState gs) {
			Move result = null;

			Move[] possibleMoves = getPossibleMoves(gs.blocksToCome[0]);
			int bestScore = Integer.MIN_VALUE;

			for (Move move : possibleMoves) {
				GameState gsCopy = gs.copy();
				GameLogic.applyMove(gsCopy, move);
				// debug("Checked move " + move + " found score: " + gsCopy.myScore);
				if (gsCopy.myScore > bestScore) {
					result = move;
					bestScore = gsCopy.myScore;
				}
			}

			if (bestScore == gs.myScore) {
				// We'll let random choose
				result = null;
			}

			return result;
		}

	}

	// MCTS
	public static class MCTSAI extends AI {

		public static int maxDepth = 0;
		public static int scoreObjective;
		public static int startMyScore;

		@Override
		public Move compute(GameState gs) {

			Move result = null;

			GameStateForMTCS gsMCTS = new GameStateForMTCS(gs);

			scoreObjective = 840 - (int) Math.floor(gs.opNuisance * 70);
			startMyScore = gs.myScore;

			if (startTime == 0) {
				startTime = System.currentTimeMillis();
			}

			long duration = System.currentTimeMillis() - startTime;
			int iterations = 0;

			debug("Starting mcts");

			// Let's simulate as much as possible within the time
			while ((duration < maxTimeWithMargin || isDebugModeOn) && iterations < mctsMaxIterations) {

				gsMCTS.selectAction();
				duration = System.currentTimeMillis() - startTime;
				iterations++;

			}

			debug("Selecting...");
			totalIterations = iterations;

			// And finally take the best move out of the simulation

			if (gsMCTS.children != null) {

				double bestChildrenScore = -1000;

				for (GameStateForMTCS children : gsMCTS.children) {
					debug("Child move " + children.moveToGetThere + " Eval: " + String.format("%.2f", children.scoreEval) + " Visits: " + children.nVisits);
					if (gs != null && (children.scoreEval / children.nVisits > bestChildrenScore)) {
						result = children.moveToGetThere;
						bestChildrenScore = children.scoreEval / children.nVisits;
					}
				}
				if (bestChildrenScore < 0.2) {
					result = null;
				}
			}

			debug("End mcts, duration for round " + gs.round + ": " + String.format("%03d", System.currentTimeMillis() - startTime) + " Number of iterations: " + String.format("%05d", iterations)
					+ " Max depth: " + maxDepth + " result: " + result);

			return result;
		}

		public static class GameStateForMTCS {

			GameState gs;

			int nVisits = 1; // Total number of visits of the position
			int depth = 0; // The depth of the position (original is 0)
			double scoreEval = 0;

			Move moveToGetThere; // The move list to get from origin to this state, length should be equal to depth
			GameStateForMTCS[] children; // Next children positions
			GameStateForMTCS parent;

			public static double epsilon = 1e-6;

			public GameStateForMTCS(GameState gs) {
				this.gs = gs.copy();
			}

			public GameStateForMTCS(GameState gs, int depth, Move moveToGetThere, GameStateForMTCS parent) {
				this.gs = gs.copy();
				this.depth = depth;
				this.moveToGetThere = moveToGetThere;
				this.parent = parent;
			}

			public String toString() {
				return "Move: " + moveToGetThere + " Depth: " + depth + " nVisits: " + nVisits + " scoreEval: " + String.format("%.2f", scoreEval) + " gs.Score: " + gs.myScore;
			}

			// Entry point to run a simulation
			public void selectAction() {
				List<GameStateForMTCS> visited = new LinkedList<GameStateForMTCS>();
				GameStateForMTCS cur = this;
				visited.add(this);
				while (cur != null && !cur.isLeaf()) {
					cur = cur.select();
					visited.add(cur);
				}
				if (cur != null) {
					double value;

					if (cur.depth > maxDepth) {
						maxDepth = cur.depth;
					}

					if (cur.depth < 7 && cur.gs.myScore != -1) {
						cur.expand();
						value = rollOut(cur);

					} else {
						value = -0.1;

					}
					for (GameStateForMTCS node : visited) {
						node.updateStats(value);
					}

				} else {
					// The game is finished
					nVisits++;
				}
			}

			// Creates the children of the position
			public void expand() {

				Move[] possibleMoves = getPossibleMoves(this.gs.blocksToCome[this.depth]);

				children = new GameStateForMTCS[possibleMoves.length];

				for (int i = 0; i < possibleMoves.length; i++) {
					Move move = possibleMoves[i];
					children[i] = createChildren(move);
				}

			}

			// Creates a new children position
			private GameStateForMTCS createChildren(Move move) {

				GameStateForMTCS result = new GameStateForMTCS(this.gs, this.depth + 1, move, this);

				GameLogic.applyMove(result.gs, move, result.depth - 1);

				return result;

			}

			// Select the most promising children among all children
			// Ref https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Exploration_and_exploitation
			private GameStateForMTCS select() {

				GameStateForMTCS selected = null;
				double bestValue = Double.MIN_VALUE;

				for (GameStateForMTCS c : children) {
					if (c != null) {
						double uctValue = (c.scoreEval / c.nVisits) + Math.sqrt(2) * Math.sqrt(Math.log(nVisits) / c.nVisits) + r.nextDouble() * epsilon;
						if (uctValue > bestValue) {
							selected = c;
							bestValue = uctValue;
						}
					}
				}
				return selected;
			}

			public boolean isLeaf() {
				return children == null || depth == 7;
			}

			// The tricky part, how to evaluate the value of a given position ?
			public double rollOut(GameStateForMTCS gs) {
				double result = -1;
				for (GameStateForMTCS c : gs.children) {
					if (c.gs.myScore > result) {
						result = c.gs.myScore;
					}
				}
				if (result != -1) {
					result = result - startMyScore;
					result = Math.min(result, scoreObjective);
					if (result < 200) {
						result = 0;
					}
					result = result / scoreObjective;
				} else {
					result = -0.1;
				}

				return result;
			}

			public void updateStats(double value) {
				nVisits++;
				scoreEval += value;

			}

		}

	}

	// Brute force depth n
	public static class NTurnBFAI extends AI {

		private int n;

		private GameState resultGameState;

		public NTurnBFAI(int n) {
			this.n = n;
		}

		@Override
		public Move compute(GameState gs) {

			Move result = null;

			ArrayList<ArrayList<Move>> moveList = getMoveList(gs);
			int bestScore = gs.myScore;

			for (ArrayList<Move> aMoveList : moveList) {
				GameState gsCopy = gs.copy();
				for (int i = 0; i < aMoveList.size(); i++) {
					GameLogic.applyMove(gsCopy, aMoveList.get(i), i);
					if (gsCopy.myScore == -1) {
						break;
					}
				}
				if (gsCopy.myScore >= bestScore) {
					result = aMoveList.get(0);
					bestScore = gsCopy.myScore;
					resultGameState = gsCopy;
				}
			}

			if (bestScore == gs.myScore) {
				// We'll let random choose
				result = null;
			}

			return result;
		}

		public GameState getResultGameState() {
			return resultGameState;
		}

		private ArrayList<ArrayList<Move>> getMoveList(GameState gs) {

			ArrayList<ArrayList<Move>> moveList = new ArrayList<>();

			for (int i = 0; i < n; i++) {

				Move[] possibleMoves = getPossibleMoves(gs.blocksToCome[i]);

				if (i == 0) {
					for (Move move : possibleMoves) {
						ArrayList<Move> aMoveList = new ArrayList<Move>();
						aMoveList.add(move);
						moveList.add(aMoveList);
					}
				} else {

					ArrayList<ArrayList<Move>> newMoveList = new ArrayList<>();

					for (ArrayList<Move> aMoveList : moveList) {
						for (int a = 0; a < possibleMoves.length; a++) {
							ArrayList<Move> temp = new ArrayList<Move>(aMoveList);
							temp.add(possibleMoves[a]);
							newMoveList.add(temp);
						}
					}
					moveList = newMoveList;
				}

			}
			return moveList;
		}

	}

	// Try to generate as fast a possible one line of skulls
	public static class AntiComboAI extends AI {

		private int n;

		public AntiComboAI(int n) {
			this.n = n;
		}

		@Override
		public Move compute(GameState gs) {

			Move result = null;
			boolean goodMoveFound = false;

			for (int i = 1; i <= n; i++) {
				NTurnBFAI ai = new NTurnBFAI(i);
				result = ai.compute(gs);
				GameState gsResult = ai.getResultGameState();

				if (gsResult != null && gsResult.nbSkullLinesGenerated >= 1) {
					// We've found a good move !
					bim = true;
					goodMoveFound = true;
					break;
				}

			}

			if (!goodMoveFound) {
				// We'll let random choose
				result = null;
			}

			return result;
		}

	}

	// Heuristic focused on building blocks of 3 or 2
	public static class BlockAI extends AI {

		@Override
		public Move compute(GameState gs) {

			Move result = null;
			Move result2 = null;

			Move[] possibleMoves = getPossibleMoves(gs.blocksToCome[0]);
			int bestScore3 = 0;
			int bestScore2 = 0;

			debug("Entering blocks, start 3B: " + gs.nbNew3BlocksGroups + " 2B: " + gs.nbNew2BlocksGroups);

			for (Move move : possibleMoves) {
				GameState gsCopy = gs.copy();
				GameLogic.applyMove(gsCopy, move);
				// debug("Checked move " + move + " found score: " + gsCopy.myScore);

				if (gsCopy.myScore == gs.myScore) {
					if (gsCopy.nbNew3BlocksGroups > bestScore3) {
						result = move;
						bestScore3 = gsCopy.nbNew3BlocksGroups;
					}

					if (gsCopy.nbNew2BlocksGroups > bestScore2) {
						result2 = move;
						bestScore2 = gsCopy.nbNew2BlocksGroups;
					}
				}

			}

			if (result == null) {
				if (result2 != null) {
					result = result2;
					debug("Getting " + bestScore2 + " new 2B with " + result);
				}

			} else {
				debug("Getting " + bestScore3 + " new 3B with " + result);
			}

			return result;
		}

	}

	// Heuristic focused on piling a color on top of the same "next next" color
	public static class NNColorAI extends AI {

		@Override
		public Move compute(GameState gs) {

			Move result = null;

			Move[] possibleMoves = getPossibleMoves(gs.blocksToCome[0]);
			int bestScore = 0;

			for (Move move : possibleMoves) {
				GameState gsCopy = gs.copy();
				GameLogic.applyMove(gsCopy, move);

				if (gsCopy.myScore == gs.myScore) {

					int tempScore = 0;

					switch (move.rotation) {
					case 1:
					case 3:
						if (checkIfNextNextColorIsTheSame(gs, move.column, gs.colH[move.column])) {
							tempScore++;
						}
						if (checkIfNextNextColorIsTheSame(gs, move.column, gs.colH[move.column] - 1)) {
							tempScore++;
						}

						break;
					case 2:
						if (checkIfNextNextColorIsTheSame(gs, move.column, gs.colH[move.column])) {
							tempScore++;
						}
						if (checkIfNextNextColorIsTheSame(gs, move.column - 1, gs.colH[move.column - 1])) {
							tempScore++;
						}
						break;
					case 0:
						if (checkIfNextNextColorIsTheSame(gs, move.column, gs.colH[move.column])) {
							tempScore++;
						}
						if (checkIfNextNextColorIsTheSame(gs, move.column + 1, gs.colH[move.column + 1])) {
							tempScore++;
						}
						break;
					default:
						break;
					}

					if (tempScore > bestScore) {
						debug("Move: " + move + " gave " + tempScore + " for NNColor");
						bestScore = tempScore;
						result = move;
					}

				}

			}

			return result;

		}

		private boolean checkIfNextNextColorIsTheSame(GameState gs, int column, int h) {

			boolean result = false;

			char colorToMatch = Character.forDigit(gs.blocksToCome[0][0], 10);
			char nextColor = 'a';
			char nextNextColor = 'a';

			int down = 1;

			while (nextColor == 'a' && (down + h < height)) {
				if (gs.myGrid[h + down][column] != colorToMatch) {
					nextColor = gs.myGrid[h + down][column];
				}
				down++;

			}

			if (nextColor != 'a') {
				while (nextNextColor == 'a' && (down + h < height)) {
					if (gs.myGrid[h + down][column] != nextColor) {
						nextNextColor = gs.myGrid[h + down][column];

					}
					down++;

				}
			}

			result = (nextNextColor == colorToMatch);

			return result;

		}

	}

}

PlayerTest.java

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotEquals;
import static org.junit.Assert.assertTrue;

import org.junit.Test;

public class PlayerTest {
	
	public static Player.GameState getGameStateFromDebug(String[] debugString) {
		
		Player.isDebugGridOn = false;
		Player.isDebugModeOn = true;
		Player.mctsMaxIterations = 10000;
		Player.initializeMatch();
		
		String[] firstLine = debugString[0].split(Player.debugSep);		
		Player.GameState result = new Player.GameState(Integer.valueOf(firstLine[1]), Integer.valueOf(firstLine[2]), Double.valueOf(firstLine[3]), Integer.valueOf(firstLine[4]), Double.valueOf(firstLine[5]));
		
		String[] secondLine = debugString[1].split(Player.debugSep);
		
		for (int i = 0; i <Player.nbBlocksToCome; i++) {
			result.blocksToCome[i][0] = Integer.valueOf(secondLine[i + 1].substring(0, 1));
			result.blocksToCome[i][1] = Integer.valueOf(secondLine[i + 1].substring(1));
		}
		
		for (int i = 0; i < Player.height; i++) {
			String myRow = debugString[i + 2].substring(0, 6);
			String opRow = debugString[i + 2].substring(10, 16);
			result.myGrid[i] = myRow.toCharArray();
			result.opGrid[i] = opRow.toCharArray();
		}
		result.updateColH();
		
		return result;
	}
	
	@Test
	public void testApplyMove() {
		
		String[] debugString = { 
				
				"New round ! -1-0-0-0-0",
				"Next blocks: -33-51-55-22-31-25-21-55",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
		};
		
		String[] debugStringExpected = { 
				
				"New round ! -1-0-0-0-0",
				"Next blocks: -33-51-55-22-31-25-21-55",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"....3.    ......",
				"....3.    ......",
		};
		
		Player.GameState gs = getGameStateFromDebug(debugString);
		Player.GameState gse = getGameStateFromDebug(debugStringExpected);
		
		Player.GameLogic.applyMove(gs, new Player.Move(4, 3));
		
		//Player.printAGrid(gs.getMyGrid());
		
		Player.expectedGS = gs;
		boolean result = Player.testGameStateAgainstExpected(gse);
		
		assertTrue(result);
		
	}
	
	@Test
	public void testApplyMove2() {
		
		String[] debugString = { 
				
				"New round ! -7-0-0-0-0",
				"Next blocks: -55-24-13-41-25-15-13-52",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    .4....",
				"......    .4....",
				".....2    .1....",
				"...3.4    .3....",
				"..5542    .55...",
				".12452    .54...",
		};
		
		String[] debugStringExpected = { 
				
				"New round ! -8-0-0-0-0",
				"Next blocks: -24-13-41-25-15-13-52-31",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				".....2    .4....",
				".....4    .4....",
				"...342    .1....",
				".12452    .34...",
		};
		
		Player.GameState gs = getGameStateFromDebug(debugString);
		Player.GameState gse = getGameStateFromDebug(debugStringExpected);
		
		Player.GameLogic.applyMove(gs, new Player.Move(1, 0));		
		
		Player.expectedGS = gs;
		boolean result = Player.testGameStateAgainstExpected(gse);
		
		assertTrue(result);
		assertEquals(gs.myScore, 40);
		
	}	
	
	@Test
	public void testApplyMove3() {
		
		String[] debugString = { 
				
				"New round ! -21-440-0.00-0-0.29-98-173",
				"Next blocks: -12-25-42-45-15-34-33-42",
				"......    ......",
				"......    ......",
				"......    ......",
				"1.2...    ......",
				"0.3...    ......",
				"024...    ......",
				"2211..    ......",
				"1105..    ......",
				"0301..    32....",
				"501000    5123..",
				"502000    4210..",
				"242312    451100",
		};
		
		String[] debugStringExpected = { 
				
				"New round ! -22-1080-0.00-0-3.43-99-168",
				"Next blocks: -25-42-45-15-34-33-42-22",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"..2...    ......",
				"..3...    ..0...",
				"..45..    001...",
				".301..    3220..",
				"501000    5123..",
				"502000    421000",
				"242312    451100",
		};
		
		Player.GameState gs = getGameStateFromDebug(debugString);
		Player.GameState gse = getGameStateFromDebug(debugStringExpected);
		
		Player.GameLogic.applyMove(gs, new Player.Move(1, 3));		
		
		Player.expectedGS = gs;
		boolean result = Player.testGameStateAgainstExpected(gse);
		
		assertTrue(result);
		assertEquals(gs.myScore, gse.myScore);
		
	}	
	
	@Test
	public void testApplyMoveMulti() {
		
		String[] debugString = { 
				
				"New round ! -4-0-0.00-0-0.00-99-455",
				"Next blocks: -43-52-41-21-55-53-12-42",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"1.....    ......",
				"1.....    ..1...",
				"53....    .21...",
				"22....    523...",
		};
		
		
		Player.GameState gs = getGameStateFromDebug(debugString);
		
		Player.GameLogic.applyMove(gs, new Player.Move(1, 0	));
		String[] debugStringExpected = { 
				
				"New round ! -5-0-0.00-0-0.00-119-512",
				"Next blocks: -52-41-21-55-53-12-42-12",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"1.....    ......",
				"14....    ..1...",
				"53....    .214..",
				"223...    5233..",
				};
		Player.expectedGS = gs;
		Player.GameState gse = getGameStateFromDebug(debugStringExpected);
		boolean result = Player.testGameStateAgainstExpected(gse);
		Player.isDebugGridOn = true;
		Player.printAGrid(gs.myGrid);
		assertTrue(result);
		
		Player.GameLogic.applyMove(gs, new Player.Move(2, 1), 1);
		debugStringExpected = new String[] { 
				
				"New round ! -6-0-0.00-0-0.00-113-483",
				"Next blocks: -41-21-55-53-12-42-12-45",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"1.....    ......",
				"142...    .21...",
				"535...    5214..",
				"223...    5233..",
				};
		Player.expectedGS = gs;
		gse = getGameStateFromDebug(debugStringExpected);
		result = Player.testGameStateAgainstExpected(gse);
		Player.isDebugGridOn = true;
		Player.printAGrid(gs.myGrid);
		assertTrue(result);
		
		Player.GameLogic.applyMove(gs, new Player.Move(0, 0), 2);
		debugStringExpected = new String[] { 
				
				"New round ! -7-0-0.00-0-0.00-116-745",
				"Next blocks: -21-55-53-12-42-12-45-41",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"4.....    ......",
				"11....    ..4...",
				"142...    .211..",
				"535...    5214..",
				"223...    5233..",
				};
		Player.expectedGS = gs;
		gse = getGameStateFromDebug(debugStringExpected);
		result = Player.testGameStateAgainstExpected(gse);
		Player.isDebugGridOn = true;
		Player.printAGrid(gs.myGrid);
		assertTrue(result);
		
		Player.GameLogic.applyMove(gs, new Player.Move(2, 1), 3);
		debugStringExpected = new String[] { 
				
				"New round ! -8-0-0.00-0-0.00-122-477",
				"Next blocks: -55-53-12-42-12-45-41-42",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"4.1...    ......",
				"112...    ......",
				"142...    ......",
				"535...    5.44..",
				"223...    5.33..",
				};
		Player.expectedGS = gs;
		gse = getGameStateFromDebug(debugStringExpected);
		result = Player.testGameStateAgainstExpected(gse);
		Player.isDebugGridOn = true;
		Player.printAGrid(gs.myGrid);
		assertTrue(result);
		
		Player.GameLogic.applyMove(gs, new Player.Move(3, 3), 4);
		debugStringExpected = new String[] { 
				
				"New round ! -9-0-0.00-0-0.00-101-471",
				"Next blocks: -53-12-42-12-45-41-42-13",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"4.1...    ......",
				"112...    ......",
				"142...    ......",
				"5355..    ..44..",
				"2235..    ..33..",
				};
		Player.expectedGS = gs;
		gse = getGameStateFromDebug(debugStringExpected);
		result = Player.testGameStateAgainstExpected(gse);
		Player.isDebugGridOn = true;
		Player.printAGrid(gs.myGrid);
		assertTrue(result);
		
		Player.GameLogic.applyMove(gs, new Player.Move(4, 1), 5);
debugStringExpected = new String[] { 
				
		"New round ! -10-360-0.00-0-5.14-99-409",
		"Next blocks: -12-42-12-45-41-42-13-41",
		"......    ......",
		"......    ......",
		"......    ......",
		"......    ......",
		"......    ......",
		"......    ......",
		"......    ......",
		"......    ......",
		"......    ......",
		"442...    ......",
		"532...    ..44..",
		"223.3.    5333..",
				};
		Player.expectedGS = gs;
		gse = getGameStateFromDebug(debugStringExpected);
		result = Player.testGameStateAgainstExpected(gse);
		Player.isDebugGridOn = true;
		Player.printAGrid(gs.myGrid);
		assertTrue(result);
		
		Player.GameLogic.applyMove(gs, new Player.Move(1, 0), 6);
		debugStringExpected = new String[] { 
				
				"New round ! -11-360-0.00-0-5.14-99-457",
				"Next blocks: -42-12-45-41-42-13-41-22",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				".12...    ......",
				"442...    ......",
				"532...    1244..",
				"223.3.    5333..",
						};
				Player.expectedGS = gs;
				gse = getGameStateFromDebug(debugStringExpected);
				result = Player.testGameStateAgainstExpected(gse);
				Player.isDebugGridOn = true;
				Player.printAGrid(gs.myGrid);
				assertTrue(result);
		
	}
	
	@Test
	public void testComputeInvalidColumn() {
		
		String[] debugString = { 
				
				"New round ! -14-0-0-0-0",
				"Next blocks: -44-33-22-33-22-33-44-44",
				"....2.    ......",
				"....2.    ......",
				"....1.    ......",
				"....1.    ......",
				"....2.    ......",
				"....2.    ......",
				".2..1.    ......",
				".2..1.    ......",
				".5..2.    ......",
				".5..2.    ......",
				"525315    .123..",
				"525315    .123..",
		};
		
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.Move move = Player.compute(gs);
		
		assertNotEquals(move, new Player.Move(4, 3));
		assertNotEquals(move, new Player.Move(4, 1));
		assertNotEquals(move, new Player.Move(3, 0));
		assertNotEquals(move, new Player.Move(4, 0));
		assertNotEquals(move, new Player.Move(4, 2));
		assertNotEquals(move, new Player.Move(5, 2));
	}
	
	@Test
	public void testComputeInvalidColumn2() {
		
		String[] debugString = { 
				
				"New round ! -17-80-0-0-0",
				"Next blocks: -41-11-53-52-44-11-53-32",
				"1.....    ......",
				"3.....    ......",
				"1.....    ......",
				"5.0...    ......",
				"0.4...    ......",
				"3.2...    ......",
				"5.2...    ..3...",
				"4.3...    ..1...",
				"1.2...    ..5...",
				"4.3.0.    ..2...",
				"502010    3111..",
				"424224    332442",
		};
		
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.Move move = Player.compute(gs);
		
		assertNotEquals(move, new Player.Move(0, 3));
		assertNotEquals(move, new Player.Move(0, 1));
		assertNotEquals(move, new Player.Move(0, 0));
		assertNotEquals(move, new Player.Move(1, 2));
	}
	
	@Test
	public void testApplyMoveScore() {
		
		String[] debugString = { 
				
				"New round ! -32-180-0-0-0",
				"Next blocks: -43-55-23-33-33-52-33-35",
				"0001..    ......",
				"4354..    ......",
				"2253..    ......",
				"2342..    ......",
				"5515..    ......",
				"1443..    ......",
				"4513..    ......",
				"2213..    ...3..",
				"41003.    15.2..",
				"55344.    11.5..",
				"315100    55134.",
				"312000    22521.",
		};
		
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.GameLogic.applyMove(gs, new Player.Move(4, 3));
		
		assertEquals(230, gs.myScore);
	}
	
	@Test
	public void testApplyMoveScoreAndNuisance() {
		
		String[] debugString = { 
				
				"New round ! -12-0-0.00-0-0.00",
				"Next blocks: -11-24-25-52-32-22-34-43",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    .5....",
				".4....    .1....",
				"53...1    .3....",
				"14...5    .1....",
				"24..11    .11...",
				"231.54    .5534.",
				"452342    .1534.",
		};
		
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.GameLogic.applyMove(gs, new Player.Move(3, 3));
		
		assertEquals(50, gs.myScore);
		assertEquals(0.71, gs.opNuisance, 0.01);
	}
	
	@Test
	public void testApplyMoveScoreAndNuisance2() {
		
		String[] debugString = { 
				
				"New round ! -38-280-0.00-0-4.00",
				"Next blocks: -31-42-23-11-32-42-32-41",
				"0210..    ......",
				"54353.    ......",
				"40035.    ......",
				"02221.    ......",
				"45151.    ......",
				"405013    ......",
				"242454    ......",
				"125500    ....4.",
				"412300    ....5.",
				"342400    ...35.",
				"130000    ...33.",
				"300011    2.3455",
		};
		
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.GameLogic.applyMove(gs, new Player.Move(5, 3));
		
		Player.printAGridForced(gs.myGrid);
		
		assertEquals(640, gs.myScore);
		assertEquals(3.14, gs.opNuisance, 0.01);
	}
	
	@Test
	public void testComputeNoNPE() {
		
		String[] debugString = { 
				
				"New round ! -22-720-0.00-0-4.29",
				"Next blocks: -11-14-45-24-14-23-21-51",
				".3.000    ......",
				".52300    ......",
				"500240    ......",
				"000144    ......",
				"000101    ......",
				"002004    ......",
				"000000    ......",
				"000000    ......",
				"000000    ......",
				"000050    ......",
				"010410    32....",
				"245254    55.4.0",
		};
		
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.Move move = Player.compute(gs);
		
		assertTrue(move != null);
	}
	
	@Test
	public void testComputeStartGame() {
		
		String[] debugString = { 
				
				"New round ! -1-0-0.00-0-0.00",
				"Next blocks: -44-44-14-52-32-12-44-52",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
		};
					
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.Move move = Player.compute(gs);
		
		assertTrue(move != null);
	}
	
	@Test
	public void testComputeStartGame2() {
		
		String[] debugString = { 
				
				"New round ! -1-0-0.00-0-0.00-0-0",
				"Next blocks: -12-43-12-52-21-14-15-31",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
		};
					
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.Move move = Player.compute(gs);
		
		assertTrue(move != null);
	}
	
	@Test
	public void testComputeDontExplode() {
		
		String[] debugString = { 
				
				"New round ! -4-40-0.00-0-0.57",
				"Next blocks: -43-53-52-15-53-54-52-21",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ...2..",
				"......    ..22..",
				"....33    ..332.",
		};
					
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.Move move = Player.compute(gs);
		Player.GameLogic.applyMove(gs, move);
		assertEquals(gs.myScore, 40);
	}
	
	@Test
	public void testComputeDontExplode2() {
		
		String[] debugString = { 
				
				"New round ! -4-0-0.00-0-0.00",
				"Next blocks: -53-34-52-15-42-52-14-45",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"433...    ...3..",
				"435...    44353.",
		};
					
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.Move move = Player.compute(gs);
		Player.GameLogic.applyMove(gs, move);
		
		assertNotEquals(gs.myScore, 40);
	}
	
	@Test
	public void testComputeUltimateMove() {
		
		String[] debugString = { 
				
				"New round ! -46-1750-0.00-0-1.00-51-10000",
				"Next blocks: -15-15-54-22-52-32-45-45",
				".00..1    ......",
				"040112    ......",
				"041420    ......",
				"005000    ......",
				"303000    ......",
				"234002    ......",
				"030005    ......",
				"000000    ...41.",
				"351100    ..125.",
				"413524    .4225.",
				"542045    .00100",
				"424245    011200",
		};
					
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.Move move = Player.compute(gs);
		
		assertEquals(new Player.Move(4, 2), move);
	}

	@Test
	public void testComputeDontExplode3() {
		
		String[] debugString = { 
				
				"New round ! -5-0-0.00-0-0.00-99-236",
				"Next blocks: -34-42-54-35-42-32-33-53",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"...1..    ......",
				"...2..    1.....",
				"...5..    53....",
				"..32..    23....",
				"..334.    432...",
		};
					
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.Move move = Player.compute(gs);
		Player.GameLogic.applyMove(gs, move);
		
		assertEquals(0, gs.myScore);
	}
	
	@Test
	public void testComputeDontExplode4() {
		
		String[] debugString = { 
				
				"New round ! -3-0-0.00-0-0.00-575-0",
				"Next blocks: -15-13-54-42-52-53-24-42",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"11....    14....",
				"14....    11....",
		};
					
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.Move move = Player.compute(gs);
		
		Player.GameLogic.applyMove(gs, move);
		
		assertNotEquals(gs.myScore, 40);
	}
	
	@Test
	public void testComputeBlocks() {
		
		String[] debugString = { 
				
				"New round ! -4-0-0.00-0-0.00-94-145",
				"Next blocks: -24-13-43-11-52-12-42-21",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"..2...    ......",
				"..1...    24....",
				".11...    11....",
				".43...    13....",
		};
					
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.Move move = Player.compute(gs);
		
		Player.GameLogic.applyMove(gs, move);
		
		assertEquals(1, gs.nbNew2BlocksGroups);
	}
	
	@Test
	public void testComputeBlocks2() {
		
		String[] debugString = { 
				
				"New round ! -5-0-0.00-0-0.00-97-758",
				"Next blocks: -33-33-33-14-53-35-22-31",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    .1....",
				"4415..    .25...",
				"4223..    32444.",
		};
					
		Player.GameState gs = getGameStateFromDebug(debugString);		
		Player.Move move = Player.blockAI.compute(gs);
		
		Player.GameLogic.applyMove(gs, move);
		Player.printAGridForced(gs.myGrid);
		
		assertEquals(1, gs.nbNew3BlocksGroups);
	}
	
	@Test
	public void testComputePerfectMove() {
		
		String[] debugString = { 
				
				"New round ! -15-680-0.00-0-3.71-82-273",
				"Next blocks: -52-21-55-23-22-23-35-21",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ..4...",
				"......    3.4...",
				".1....    2101..",
				"14....    0104..",
				"344...    0015..",
				"355...    30550.",
				"442...    144000",
				"4111..    554050",
		};
					
		Player.GameState gs = getGameStateFromDebug(debugString);	
		Player.mctsMaxIterations = 5000;
		Player.Move move = Player.compute(gs);
		
		assertEquals(new Player.Move(3, 3), move);
	}

	@Test
	public void testComputePerfectMove2() {
		
		String[] debugString = { 
				
				"New round ! -9-0-0.00-0-0.00-88-294",
				"Next blocks: -52-45-21-24-34-44-32-24",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				"......    ......",
				".4....    ......",
				"41....    ......",
				"1152..    3.....",
				"3211..    5.....",
				"22153.    35441.",
		};
					
		Player.GameState gs = getGameStateFromDebug(debugString);	
		Player.mctsMaxIterations = 5000;
		Player.Move move = Player.compute(gs);
		
		assertTrue(move.equals(new Player.Move(2, 0)) || move.equals(new Player.Move(3, 2)));
	}
	
}

Comments from Neumann - big thanks.

Salut,

J'ai parcouru ton code en vitesse (j'ai pas eu la patience de vraiment rentrer dedans, tu m'excuseras :P) et ce que je remarque en premier c'est la manière dont tu as géré la détection des explosions. Quel que soit le language choisi, il faut en premier lieu bien choisir les algos utilisés, et pour gérer ce genre de problématique, il y a le flood-fill.

Je suis pas sûr d'avoir capté à 100% ce que ta méthode extendFromBlockAndCount() faisait en détail, mais elle semble parcourir inutilement ta grille plusieurs fois.
Go check ça : https://fr.wikipedia.org/wiki/Algorithme_de_remplissage_par_diffusion
C'est facile à comprendre et ça te permet de détecter les groupes de billes sans passer plus d'une fois dans chaque cellule de la grille.

Après en terme d'optimisation, il faut pas oublier que ce qui coute le plus cher en Java c'est 1) de créer des objets, 2) l'utilisation de structures à taille non-fixe (collections genre liste, map, etc). Pour éviter ça y'a plusieurs options :

• Pré-instantier un pool d'objets durant le tour, et réutiliser ces objets durant les autres tours.
• Remplacer les listes et les queues par des tableaux à taille fixe, à utiliser coinjointement avec des objets pré-instantiés.

Quand j'étais en phase d'optimisation de la détection des explosions, j'ai principalement gagné du temps avec ces points :

• Le floodfill utilise une pile (queue), que j'ai implémenté à la main avec un tableau à taille fixe, et des indices glissants (méthode detonateFromPoint()). Cette méthode n'instantie aucun objet, j'ai beaucoup gagné en perf grâce à ça.
• Pour marquer les cellules parcourues lors d'un floodfill, naturellement tu instanties un tableau de boolean[W][H], mais encore une fois c'est couteux d'instantier un tel tableau à chaque appel de la fonction. A la place j'ai utilisé un tableau int[W][H] dans lequel je mettais un indice incrémenté à chaque itération. Au lieu de : if (!done[x][y]) {... done[x][y]=true;}, je peux faire : if (done[x][y] != currentIdx) {... done[x][y]=currentIdx;} Je peux ainsi réutiliser à chaque fois le même tableau sans jamais le réinstantier, ni jamais le réinitialiser.

Je suis loin d'être un expert en optimisation et/ou en Java, mais j'ai pas hésité à passer du temps (1 ou 2 jours) juste sur l'optimisation de la méthode qui simules les coups. Tu te fais un petit TU qui simule une explosion et vérifie que le board est bien modifié et que le score calculé est correct (pour t'assurer que t'introduis pas une régression en modifiant ton algo) et tu cherches à comprendre où ton algo passe le plus de temps (pour ça j'ai utilisé le profiler intégré dans le JDK, http://stackoverflow.com/questions/2267594/java-profiling-how-can-i-get-a-method-by-method-analysis-of-my-application). Faut pas non plus y passer trop de temps, le plus important c'est l'intelligence que tu introduis derrière, mais c'est pas à négliger.

Ce genre d'optim valent pour tous les languages je pense, mais c'est vrai qu'en Java c'est un poil plus compliqué d'avoir des perfs correctes.

J'ai vu le code du #1 Java, lui avait une approche différente, basée sur de très bonnes heuristiques. Mais quand tu vise le top3 d'un concours, il faut forcément utiliser des gros algos brute-force qui simulent beaucoup de choses en peu de temps (c'est pour ça que je vais passer au C++ pour pouvoir jouer dans la cour des grands :P). Après c'est largement possible de faire plein de choses en Java, mais c'est pas le language idéal pour ça.

J'espère que mon pavé aura répondu à quelques-unes de tes questions :slightly_smiling:

Bye,

Neumann.