Population.jack

/**
 * Ohh boy, we have a lot to go over in this one. The Population module is
 * where all the magic happens, and is what makes the genetic algorithm
 * genetic.
 */
class Population {
    static Array dots;
    static Array fitnessCache;
    static int bestDotFitness;
    static Array newBrainDirections;
    static int gen;
    static int populationCount;
    static int brainSize;
    static boolean onlyBest;
    static String allocatingString;
    static String escapeString;

    function void init() {
        // let dots = null;
        let allocatingString = "Allocating dot memory...";
        let escapeString = "Hold escape in the simulation to open the menu.";
    }

    function void config(int _brainSize, boolean _onlyBest,
                         int initialBestDotFitness) {
        var int i;
        var Dot dot;
        var Brain brain;
        var Array directions;
        var int diff;
        var int remainingExtendedHeap;
        var int remainingHeap;

        do Output.moveCursor(11, 22);
        do Output.printString(allocatingString);
        do Output.moveCursor(15, 9);
        do Output.printString(escapeString);
        // later TODO if i implement reallocation
        // if (~(dots = null)) {
        //     while (i < populationCount) {
        //         let dot = dots[i];
        //         do dot.dispose();
        //         let i = i + 1;
        //     }
        //     let i = 0;
        //     do dots.dispose();

        //     do fitnessCache.dispose();

        //     while (i < (populationCount - 1)) {
        //         let tmp = newBrainDirections[i];
        //         if (~(tmp > 16384)) {
        //             do tmp.dispose();
        //             let i = i + 1;
        //         } else {
        //             let i = populationCount;
        //         }
        //     }
        //     let i = 0;
        //     do newBrainDirections.dispose();
        //     do Memory.deFrag();
        // }

        let gen = 1;
        let brainSize = _brainSize;
        let onlyBest = _onlyBest;
        let bestDotFitness = initialBestDotFitness;

        let dot = Dot.new();
        let brain = dot.getBrain();
        let directions = brain.getDirections();

        // It's about to get real ugly. We're going to do some surgery on the
        // RAM, so if you're a bit squeamish please stand by.

        let diff = (directions[-1] - dot) + 2;
        let remainingHeap = 16384 - dot;
        let remainingExtendedHeap = 24576 - dot;
        /*
        // populationCount upper bound

        // dots
        populationCount + 2
        // dots memory
        + populationCount * diff
        // fitnessCache
        + populationCount + 2
        // newBrainDirections
        + (populationCount - 1) + 2
        // newBrainDirections memory
        + (populationCount - 1) * (brainSize + 3)
        // remaining space
        = remainingExtendedHeap

        populationCount + 2 + populationCount * diff + populationCount + 2 +
        (populationCount - 1) + 2 + (populationCount - 1) * (brainSize + 3) =
        remainingExtendedHeap

        p + 2 + pd + p + 2 + p - 1 + 2 + (p - 1) * (b + 3) = remainingExtendedHeap
        p + 2 + pd + p + 2 + p - 1 + 2 + pb + 3p - b - 3 = remainingExtendedHeap

        p + pd + p + p + pb + p + p + p = remainingExtendedHeap - 2 + b
        p(1 + d + 1 + 1 + b + 1 + 1 + 1) = remainingExtendedHeap - 2 + b
        p = (remainingExtendedHeap + b - 2) / (d + b + 6)

        // populationCount lower bound

        // dots
        populationCount + 2
        // dots memory
        + populationCount * diff
        // fitnessCache
        + populationCount + 2
        // newBrainDirections
        + (populationCount - 1) + 2
        // remaining space
        = remainingHeap

        populationCount + 2 + populationCount * diff + populationCount + 2 +
        (populationCount - 1) + 2 = remainingHeap

        p + 2 + pd + p + 2 + p - 1 + 2 = remainingHeap
        p + pd + p + p = remainingHeap - 5
        p(1 + d + 1 + 1) = remainingHeap - 5
        p = (remainingHeap - 5) / (d + 3)
        */
        let populationCount = Math.min(
            (remainingExtendedHeap + brainSize - 2) / (diff + brainSize + 6),
            (remainingHeap - 5) / (diff + 3)
        );

        let fitnessCache = Array.new(populationCount);
        let dots = Array.new(populationCount);
        let dots[0] = dot;
        let i = 1;
        while (i < populationCount) {
            let dots[i] = Dot.new();
            let i = i + 1;
        }
        let i = 0;

        // serves as temporary swap memory for later on
        // -1 because the best dot won't be changed
        let newBrainDirections = Array.new(populationCount - 1);
        if (~(newBrainDirections < 16387)) {
            do Sys.error(6);
        }
        do Screen.setColor(false);
        do Screen.drawRectangle(177, 122, 369, 133);
        do Screen.drawRectangle(73, 166, 449, 177);
        do Screen.setColor(true);
        while (i < (populationCount - 1)) {
            let newBrainDirections[i] = Array.new(brainSize + 1);
            let i = i + 1;
        }
        do Screen.clearScreen();
    }

    function void toggleOnlyBest() {
        let onlyBest = ~onlyBest;
    }

    function int getGen() {
        return gen;
    }

    function int getBestDotFitness() {
        return bestDotFitness;
    }

    function void update(boolean firstPairComponent) {
        var int i;
        var Dot dot;
        while (i < populationCount) {
            let dot = dots[i];
            do dot.update((~onlyBest) | (i = 0), firstPairComponent);
            let i = i + 1;
        }
    }

    function boolean allDotsDead() {
        var int i;
        var Dot dot;
        while (i < populationCount) {
            let dot = dots[i];
            if (~dot.getDead())
                return false;
            let i = i + 1;
        }
        return true;
    }

    function void naturalSelection() {
        // This is the abracadabra of the program. Let's dive in.
        var Dot dot;
        var Dot bestDot;
        var Brain brain;
        var Brain bestDotBrain;
        var int dotFitness;
        var int i;
        var int j;
        var int selectionSum;
        var int selectionSumCoef;
        var int randFitness;
        var int randFitnessCoef;
        var int fitnessSum;
        var int fitnessSumCoef;
        var int randTo32000;
        var int randToMinStep;
        var Array directions;
        var Array newDirections;
        var int scaleCache;
        var boolean mutated;
        var int dynamicMutationRateTimes32;
        var int minStep;
        var int dotMinStepCache;

        // Before we start, it's important to remember that any variable
        // ending with Coef is a counter for the number of times the variable
        // has overflown as a primitive way to represent larget numbers. You may
        // see strange artichmetic done on these types of variables, but all
        // it's really doing is preventing overflow.

        // STEP 1: Calculate fitness of every dot and find the best one. We're
        // also calculating the sum of all fitnesses to use for later.

        // safe to set as 1 because 1) calcualteFitness return >= 1 and 2)
        // bestDot can never be null after this loop
        let bestDotFitness = 1;
        while (i < populationCount) {
            let dot = dots[i];
            let dotFitness = dot.calculateFitness();
            let fitnessCache[i] = dotFitness;
            if (dotFitness > bestDotFitness) {
                let bestDotFitness = dotFitness;
                let bestDot = dot;
            // ensures brain and bestDotBrain is only defined when necessary
            } else if (dotFitness = bestDotFitness) {
                let brain = dot.getBrain();
                // doesnt run when bestDot is null
                let bestDotBrain = bestDot.getBrain();
                if (brain.getStep() < bestDotBrain.getStep()) {
                    let bestDot = dot;
                }
            }
            let fitnessSum = fitnessSum + dotFitness;
            if (fitnessSum < 0) {
                let fitnessSum = fitnessSum + ~32767;
                let fitnessSumCoef = fitnessSumCoef + 1;
            }
            let i = i + 1;
        }

        if (bestDot.getReachedGoal()) {
            let brain = bestDot.getBrain();
            let dotMinStepCache = brain.getStep();
            do Dot.setMinStep(dotMinStepCache);
        }

        // STEP 2: Select a weighted random dot to be the parent of the next
        // generation. For the number of dots, we select a random number between
        // 0 and the fitness sum from step one. We then keep adding up dot
        // fitnesses until it exceeds that number, and the dot that exceeds it
        // is the parent. In a way, this acts as a weighted random selection
        // where the higher the fitness, the more likely it is to be selected.

        let i = 0;
        while (i < (populationCount - 1)) {
            if (fitnessSumCoef = 0) {
                let randFitnessCoef = 0;
            } else {
                let scaleCache = 32767 / fitnessSumCoef;
                let randFitnessCoef = 32767;
                while (randFitnessCoef > fitnessSumCoef) {
                    // fitnessSumCoef = 296, randFitnessCoef = 32698
                    // this results in randFitnessCoef = 297 which is out of bounds
                    let randFitnessCoef = Math.abs(Util.random()) / scaleCache;
                }
            }
            let randFitness = Math.abs(Util.random());
            if (randFitnessCoef = fitnessSumCoef) {
                if (fitnessSum = 0) {
                    let randFitness = 0;
                } else {
                    let scaleCache = 32767 / fitnessSum;
                    while (randFitness > fitnessSum) {
                        // same with this it can also go out of bounds
                        let randFitness = Math.abs(Util.random()) / scaleCache;
                    }
                }
            }
            let selectionSum = 0;
            let selectionSumCoef = 0;
            let j = 0;
            while (j < populationCount) {
                let selectionSum = selectionSum + fitnessCache[j];
                if (selectionSum < 0) {
                    let selectionSum = selectionSum + ~32767;
                    let selectionSumCoef = selectionSumCoef + 1;
                }
                if ((selectionSumCoef > randFitnessCoef) |
                    ((selectionSumCoef = randFitnessCoef) &
                     (selectionSum > randFitness))) {
                    let dot = dots[j];
                    let j = populationCount; // break
                }
                let j = j + 1;
            }
            let brain = dot.getBrain();
            let directions = brain.getDirections();
            let newDirections = newBrainDirections[i];
            if (dotMinStepCache = 0) {
                let minStep = brain.getStep();
            } else {
                let minStep = dotMinStepCache;
            }

            // STEP 3: Mutate the parent's brain and store it in the swap memory
            // allocated earlier. Did I say swap memory? I also meant the screen
            // memory! Indeed, because we don't have enough RAM, we temporarily
            // use the screen as a memory buffer. This explains why you see
            // static on the screen during natural selection :)

            // where 1530 came from is a long story. If I decide to fully
            // explain it, here's a conversation I had with my friend for
            // reference for future me:
            // https://discord.com/channels/@me/890505752064716811/1173360871511183390

            // in short, the mutation rate is a function of the amount of steps
            // in the brain such that the mutation rate binomial distribution
            // is roughly constant
            let dynamicMutationRateTimes32 = Math.min(1000, 1530 / minStep) * 32;
            let mutated = false;
            let j = 0;
            while (j < minStep) {
                // scaleCache = 32767 / 1000 = 32
                let randTo32000 = Math.abs(Util.random());
                while (~(randTo32000 < 32000)) {
                    let randTo32000 = Math.abs(Util.random());
                }
                if (randTo32000 < dynamicMutationRateTimes32) {
                    let newDirections[j] = AccelerationVectorPair.random();
                    let mutated = true;
                } else {
                    let newDirections[j] = directions[j];
                }
                let j = j + 1;
            }
            let newDirections[brainSize] = minStep; // cache for later
            if (~mutated) {
                // if nothing mutated that's no fun! Force it to mutate anyways
                // through the use of radiation exposure
                let scaleCache = 32767 / minStep;
                let randToMinStep = minStep;
                // randToMinStep can be negative Math.abs does not guarantee
                // positive (-32768)
                while (~((randToMinStep > -1) & (randToMinStep < minStep))) {
                    let randToMinStep = Math.abs(Util.random()) / scaleCache;
                }
                let newDirections[randToMinStep] = AccelerationVectorPair.random();
            }
            let i = i + 1;
        }

        // STEP 4: Copy the swap memory back to the RAM and reinstantiate
        // everything.

        let i = 0;
        while (i < populationCount) {
            let dot = dots[i];
            let brain = dot.getBrain();
            let directions = brain.getDirections();
            do dot.instantiate();
            do brain.instantiate();
            let j = 0;
            if (~(i = 0)) {
                let newDirections = newBrainDirections[i - 1];
                let minStep = newDirections[brainSize];
            } else if (dot = bestDot) {
                let minStep = 0;
            } else {
                let brain = bestDot.getBrain();
                let newDirections = brain.getDirections();
                let minStep = brainSize;
            }
            while (j < minStep) {
                let directions[j] = newDirections[j];
                let j = j + 1;
            }
            let i = i + 1;
        }
        let gen = gen + 1;
    }

    function void instantiateDots() {
        var int i;
        var Dot dot;
        while (i < populationCount) {
            let dot = dots[i];
            do dot.instantiate();
            let i = i + 1;
        }
    }
}