// Classifier brain for a tank // // Control system based on templated rules. // // Author Matthew Caryl // Created 13.11.96 // // Although under copywrite to the author (Matthew Caryl) this code can be copied and modified for non-commercial // purposes as long as any derivatives contain this condition. package ThinkTank; import ADT.Random; import ADT.Queue; import ADT.QueueEmpty; import java.lang.Math; final class Classifier implements Brain { // Maths functions private static final float PI = (float) Math.PI; private static final float TO_RADIANS = PI / 180f; private static final float OCLOCK = (float) (Math.PI * 2f / 12f); private static final float ZERO = OCLOCK * 0f; private static final float ONE = OCLOCK * 1f; private static final float TWO = OCLOCK * 2f; private static final float THREE = OCLOCK * 3f; private static final float FOUR = OCLOCK * 4f; private static final float FIVE = OCLOCK * 5f; private static final float SIX = OCLOCK * 6f; private static final float SEVEN = OCLOCK * 7f; private static final float EIGHT = OCLOCK * 8f; private static final float NINE = OCLOCK * 9f; private static final float TEN = OCLOCK * 10f; private static final float ELEVEN = OCLOCK * 11f; // // Private classifier interface // static float TURRETSPEED = 4f; static float TANKSPEED = 1f; static int CHECKRULES = 8; // number of rules to check before giving up static int MUTATIONRATE = 2; private static final float SENSORCHANGE = 0.1f; // change for sensors if mutated private static final int TOPMUTATION = 25; // highest numbered mutation // status bit meanings - output private static final int forwardLeftTread = 1 << 0; private static final int reverseLeftTread = 1 << 1; private static final int forwardRightTread = 1 << 2; private static final int reverseRightTread = 1 << 3; private static final int turnTurretLeft = 1 << 4; private static final int turnTurretRight = 1 << 5; private static final int fireShell = 1 << 6; // status bit meanings - input private static final int tankLeftTurret = 1 << 16; private static final int tankRightTurret = 1 << 17; private static final int tankCenterTurret = 1 << 18; private static final int tankLeftTank = 1 << 19; private static final int tankRightTank = 1 << 20; private static final int collisionNETank = 1 << 24; private static final int collisionSETank = 1 << 25; private static final int collisionSWTank = 1 << 26; private static final int collisionNWTank = 1 << 27; private static final int obstacleNETank = 1 << 28; private static final int obstacleSETank = 1 << 29; private static final int obstacleSWTank = 1 << 30; private static final int obstacleNWTank = 1 << 31; // tank control private static int[] mutationSuccesses = new int[TOPMUTATION + 1]; // which mutations have been successful in the past private int currentMutation[] = new int[MUTATIONRATE]; // mutations of this brain private float radarWidth = PI; // radar field of view private float radarDepth = 4f; // radar depth of view // the brain private int[] inputTemplate = new int[0]; private int[] inputFilter = new int[0]; private int[] outputTemplate = new int[0]; private int[] outputFilter = new int[0]; private int position; private int status = 0; static { for (int i = TOPMUTATION; i >= 0; i--) mutationSuccesses[i] = 1; } // transfer from souce to destination private void transfer(int[] source, int sourceStart, int[] destination, int destinationStart, int length) { for (int i = sourceStart + length - 1, j = destinationStart + length - 1; i >= sourceStart; i--, j--) destination[j] = source[i]; } // insert value at position into source private int[] insert(int[] source, int pos, int value) { int[] destination = new int[source.length + 1]; transfer(source, 0, destination, 0, pos); destination[pos] = value; transfer(source, pos, destination, pos + 1, source.length - pos); return destination; } // delete at position in source private int[] delete(int[] source, int pos) { int[] destination = new int[source.length - 1]; transfer(source, 0, destination, 0, pos); transfer(source, pos + 1, destination, pos, source.length - pos - 1); return destination; } // swap first and second positions in source private void swap(int[] source, int first, int second) { int swapper = source[first]; source[first] = source[second]; source[second] = swapper; } // insert all 4 values into brain private void superInsert(int pos, int inputT, int inputF, int outputT, int outputF) { inputTemplate = insert(inputTemplate, pos, inputT); inputFilter = insert(inputFilter, pos, inputF); outputTemplate = insert(outputTemplate, pos, outputT); outputFilter = insert(outputFilter, pos, outputF); } // delete all 4 values from brain private void superDelete(int pos) { inputTemplate = delete(inputTemplate, pos); inputFilter = delete(inputFilter, pos); outputTemplate = delete(outputTemplate, pos); outputFilter = delete(outputFilter, pos); } // swap all 4 values in brain private void superSwap(int first, int second) { swap(inputTemplate, first, second); swap(inputFilter, first, second); swap(outputTemplate, first, second); swap(outputFilter, first, second); } // add new rule to brain private void remember(int inputT, int inputF, int outputT, int outputF) { superInsert(inputTemplate.length, inputT, inputF, outputT, outputF); } // mutate brain using those mutations which have proved successful in the past private void mutate(Random random) { int total = 0, current, which; for (which = TOPMUTATION; which >= 0; which--) total += mutationSuccesses[which]; for (which = TOPMUTATION, current = random.range(total); current >= mutationSuccesses[which]; which--) current -= mutationSuccesses[which]; switch (which) { case 0: // do nothing break; // change sensor parameters case 1: radarWidth = radarWidth * (random.range(2) == 0 ? 1f - SENSORCHANGE : 1f + SENSORCHANGE); break; case 2: radarDepth = radarDepth * (random.range(2) == 0 ? 1f - SENSORCHANGE : 1f + SENSORCHANGE); break; // modify brain case 3: // remove rule if (inputTemplate.length > 1) superDelete(random.range(inputTemplate.length)); break; case 4: // duplicate rule { int r = random.range(inputTemplate.length); superInsert(r, inputTemplate[r], inputFilter[r], outputTemplate[r], outputFilter[r]); } break; case 5: // shift rule { int r = random.range(inputTemplate.length); int p = (r == 0 ? inputTemplate.length: r) - 1; superSwap(r, p); } break; case 6: // or input template { int r = random.range(inputTemplate.length); int p = (r == 0 ? inputTemplate.length: r) - 1; inputTemplate[p] = inputTemplate[r] | inputTemplate[p]; } break; case 7: // and input template { int r = random.range(inputTemplate.length); int p = (r == 0 ? inputTemplate.length: r) - 1; inputTemplate[p] = inputTemplate[r] & inputTemplate[p]; } break; case 8: // xor input template { int r = random.range(inputTemplate.length); int p = (r == 0 ? inputTemplate.length: r) - 1; inputTemplate[p] = inputTemplate[r] ^ inputTemplate[p]; } break; case 9: // negate input template { int r = random.range(inputTemplate.length); inputTemplate[r] = ~inputTemplate[r]; } break; case 10: // or input filter { int r = random.range(inputFilter.length); int p = (r == 0 ? inputFilter.length: r) - 1; inputFilter[p] = inputFilter[r] | inputFilter[p]; } break; case 11: // and input filter { int r = random.range(inputFilter.length); int p = (r == 0 ? inputFilter.length: r) - 1; inputFilter[p] = inputFilter[r] & inputFilter[p]; } break; case 12: // xor input filter { int r = random.range(inputFilter.length); int p = (r == 0 ? inputFilter.length: r) - 1; inputFilter[p] = inputFilter[r] ^ inputFilter[p]; } break; case 13: // negate input filter { int r = random.range(inputFilter.length); inputFilter[r] = ~inputFilter[r]; } break; case 14: // or output template { int r = random.range(outputTemplate.length); int p = (r == 0 ? outputTemplate.length: r) - 1; outputTemplate[p] = outputTemplate[r] | outputTemplate[p]; } break; case 15: // and output template { int r = random.range(outputTemplate.length); int p = (r == 0 ? outputTemplate.length: r) - 1; outputTemplate[p] = outputTemplate[r] & outputTemplate[p]; } break; case 16: // xor output template { int r = random.range(outputTemplate.length); int p = (r == 0 ? outputTemplate.length: r) - 1; outputTemplate[p] = outputTemplate[r] ^ outputTemplate[p]; } break; case 17: // negate output template { int r = random.range(outputTemplate.length); outputTemplate[r] = ~outputTemplate[r]; } break; case 18: // or output filter { int r = random.range(outputFilter.length); int p = (r == 0 ? outputFilter.length: r) - 1; outputFilter[p] = outputFilter[r] | outputFilter[p]; } break; case 19: // and output filter { int r = random.range(outputFilter.length); int p = (r == 0 ? outputFilter.length: r) - 1; outputFilter[p] = outputFilter[r] & outputFilter[p]; } break; case 20: // xor output filter { int r = random.range(outputFilter.length); int p = (r == 0 ? outputFilter.length: r) - 1; outputFilter[p] = outputFilter[r] ^ outputFilter[p]; } break; case 21: // negate output filter { int r = random.range(outputFilter.length); outputFilter[r] = ~outputFilter[r]; } break; case 22: // input template mutation { int r = random.range(inputTemplate.length); inputTemplate[r] ^= 1 << random.range(32); } break; case 23: // input filter mutation { int r = random.range(inputFilter.length); inputFilter[r] ^= 1 << random.range(32); } break; case 24: // output template mutation { int r = random.range(outputTemplate.length); outputTemplate[r] ^= 1 << random.range(32); } break; case 25: // output filter mutation { int r = random.range(outputFilter.length); outputFilter[r] ^= 1 << random.range(32); } break; } position = random.range(inputTemplate.length); // record mutation at start of currentMutation for (int i = currentMutation.length - 1; i >= 1; i--) currentMutation[i] = currentMutation[i - 1]; currentMutation[0] = which; } // // Public classifier interface // // construct a brain with a basic rule set public Classifier(Random r) { // aim at tanks remember(tankLeftTurret, tankLeftTurret, turnTurretLeft, turnTurretLeft); remember(tankRightTurret, tankRightTurret, turnTurretRight, turnTurretRight); remember(0, tankCenterTurret, 0, turnTurretLeft | turnTurretRight); // move forward remember(0, reverseLeftTread | reverseRightTread, forwardLeftTread, forwardLeftTread); remember(0, reverseLeftTread | reverseRightTread, forwardRightTread, forwardRightTread); // reverse from tanks remember(tankLeftTank, tankLeftTank, 0, forwardRightTread); remember(tankRightTank, tankRightTank, 0, forwardLeftTread); remember(tankLeftTank, tankLeftTank, 0, forwardLeftTread); remember(tankRightTank, tankRightTank, 0, forwardRightTread); remember(tankLeftTank, tankLeftTank, reverseLeftTread, reverseLeftTread); remember(tankRightTank, tankRightTank, reverseRightTread, reverseRightTread); // avoid obstacles remember(obstacleNETank, obstacleNETank, reverseLeftTread, reverseLeftTread); remember(obstacleNETank, obstacleNETank, 0, forwardLeftTread); remember(obstacleNWTank, obstacleNWTank, reverseRightTread, reverseRightTread); remember(obstacleNWTank, obstacleNWTank, 0, forwardRightTread); remember(obstacleSETank, obstacleSETank, forwardRightTread, forwardRightTread); remember(obstacleSETank, obstacleSETank, 0, reverseRightTread); remember(obstacleSWTank, obstacleSWTank, forwardLeftTread, forwardLeftTread); remember(obstacleSWTank, obstacleSWTank, 0, reverseLeftTread); // shoot tanks remember(tankCenterTurret, tankCenterTurret, fireShell, fireShell); remember(fireShell, fireShell, 0, fireShell); // turn away from danger remember(collisionNETank, collisionNETank, reverseLeftTread, reverseLeftTread); remember(collisionNETank, collisionNETank, 0, forwardLeftTread); remember(collisionNWTank, collisionNWTank, reverseRightTread, reverseRightTread); remember(collisionNWTank, collisionNWTank, 0, forwardRightTread); remember(collisionSETank, collisionSETank, forwardRightTread, forwardRightTread); remember(collisionSETank, collisionSETank, 0, reverseRightTread); remember(collisionSWTank, collisionSWTank, forwardLeftTread, forwardLeftTread); remember(collisionSWTank, collisionSWTank, 0, reverseLeftTread); // randomise the rule order for (int i = inputTemplate.length - 1; i >= 0; i--) superSwap(i, r.range(inputTemplate.length)); position = r.range(inputTemplate.length); } // copy given brain public Classifier(Random r, Classifier c) { int size = c.inputTemplate.length; inputTemplate = new int[size]; inputFilter = new int[size]; outputTemplate = new int[size]; outputFilter = new int[size]; transfer(c.inputTemplate, 0, inputTemplate, 0, size); transfer(c.inputFilter, 0, inputFilter, 0, size); transfer(c.outputTemplate, 0, outputTemplate, 0, size); transfer(c.outputFilter, 0, outputFilter, 0, size); radarWidth = c.radarWidth; radarDepth = c.radarDepth; position = r.range(inputTemplate.length); } // // Public brain interface // // create a similar brain public Brain breed(Random r) { Classifier c = new Classifier(r, this); for (int i = currentMutation.length - 1; i >= 0; i--) mutationSuccesses[currentMutation[i]]++; for (int i = MUTATIONRATE; i > 0; i--) c.mutate(r); return c; } // create a similar brain with mate // -- not yet implemented -- public Brain breed(Brain mate, Random r) { Classifier c = new Classifier(r, this); for (int i = currentMutation.length - 1; i >= 0; i--) mutationSuccesses[currentMutation[i]]++; for (int i = MUTATIONRATE; i > 0; i--) c.mutate(r); return c; } // look at the environment public void sensor(TankSensor s) { // set all sensor bits to 0 status = status & ~(tankLeftTurret | tankRightTurret | tankCenterTurret | tankLeftTank | tankRightTank | collisionNETank | collisionSETank | collisionSWTank | collisionNWTank | obstacleNETank | obstacleSETank | obstacleSWTank | obstacleNWTank); // use sensors and set appropriate bits to 1 status = status | (s.turretRadar(radarWidth / -2f, radarWidth / -12f, radarDepth) ? tankLeftTurret : 0) | (s.turretRadar(radarWidth / +12f, radarWidth / +12f, radarDepth) ? tankRightTurret : 0) | (s.turretRadar(radarWidth / -12f, radarWidth / +12f, radarDepth) ? tankCenterTurret : 0) | (s.tankRadar(radarWidth / -2f, radarWidth / +12f, radarDepth) ? tankLeftTank : 0) | (s.tankRadar(radarWidth / -12f, radarWidth / +2f, radarDepth) ? tankRightTank : 0) | (s.collisionSensor(ZERO, THREE) ? collisionNETank : 0) | (s.collisionSensor(THREE, SIX) ? collisionSETank : 0) | (s.collisionSensor(SIX, NINE) ? collisionSWTank : 0) | (s.collisionSensor(-THREE, ZERO) ? collisionNWTank : 0) | (s.obstacleSensor(ZERO, THREE, 2f) ? obstacleNETank : 0) | (s.obstacleSensor(THREE, SIX, 2f) ? obstacleSETank : 0) | (s.obstacleSensor(SIX, NINE, 2f) ? obstacleSWTank : 0) | (s.obstacleSensor(-THREE, ZERO, 2f) ? obstacleNWTank : 0); } // a single move public void action(TankAction t) { int left, right; // find rule or not int j = (position == inputTemplate.length - 1) ? 0 : position + 1; for (; (inputTemplate[position] & inputFilter[position]) != (status & inputFilter[position]); position--) { if (position == j) return; else if (position == 0) position = inputTemplate.length; } // apply rule status = (status & ~outputFilter[position]) | (outputTemplate[position] & outputFilter[position]); // move tank left = ((status & forwardLeftTread) << 1) - ((status & reverseLeftTread) >> 1); right = ((status & forwardRightTread) >> 1) - ((status & reverseRightTread) >> 3); t.turn((float) (left - right) * TANKSPEED * TO_RADIANS); t.move((float) (left + right) * TANKSPEED / 2f); // turn turret left = (status & turnTurretLeft) >> 4; right = (status & turnTurretRight) >> 5; t.aim((float) (right - left) * TURRETSPEED * TO_RADIANS); // use shell if ((status & fireShell) == fireShell) t.fire(); // move onto next rule if (position == 0) position = inputTemplate.length - 1; else position--; } }